Oh great shaman!
Somehow the village idiot got his hands on this fancy control machine controlling things. Obviously, we also want to control things (who wouldn’t?), so we reverse-engineered the code. Unfortunately, the machine is cryptographically protected against misuse.
Could you please maybe spend a few seconds of your inestimably valuable time to break that utterly simple cryptosystem and enlighten us foolish mortals with your infinite wisdom?
nc 104.155.168.28 31031
NOTE: Since I am really bad at math, the share received from the server won’t be accepted when sent back. Don’t get confused by this — the challenge is solvable nevertheless.
Summary: hash length extension, manipulation of secret shares.
The challenge server consists of a mix of secret sharing, authentication and command execution. Briefly, it works as follows:
- The server generates a command of the form
cmd = checksum + "echo Hello!#" + [32 random bytes],
and interprets it as an integer modulo 256-bit prime $p$. - The server splits the command into 3 shares with threshold equal to 2, meaning that knowing any 2 of the 3 shares is enough to recover the secret. Shamir’s secret sharing is used (using polynomials over $\mathbb{F}_p$).
- One of the shares is signed by prepending a MAC:
signed_share = SHA256(key + share) + share. - The signed share is sent to the client.
- Now the server listens to queries from the client, the number is limited by 0x123.
- In each query, the client cant send a signed share.
- The server combines it with another share.
- The server checks the checksum and if it is good, executes the command.
Modifying the share
First observation: if the MAC is good enough, we can’t generate any other signed share and therefore we can’t execute any command other than “echo Hello”. Therefore we have to attack the MAC. Luckily, it is vulnerable to the well known Hash Length Extension attack. There is a very convenient tool called hash_extender for performing the attack.
The attack allows us, given a hash of the form SHA256(key + share), to append some uncontrolled padding and, additionally, arbitrary amount of data to the hash input. This appending is done in such a way that we can compute the new hash value without knowing the key. That is, we can generate more signed shares of the form share + [padding] + [any data].
What does it give to us? The share has the following format: (32-byte $x$, 32-byte $y$) and the values are packed in the Little Endian order (least significant bytes first). When the values are unpacked, everything after $y$ will be considered as a part of $y$. Even if it’s more than 32 bytes, it will be taken modulo $p$. That is, we can modify the share’s $y$ by adding $(2^{256} \times padding + 2^{256+e} \times value)$ to it, where $e$ is determined by padding. Since it is reduced modulo $p$ afterwards, we can actually obtain arbitrary $y_{wanted}$. Indeed, setting $$value \equiv (y_{wanted} – y_{orig} – 2^{256} \times padding) / 2^{256+e} \pmod {p}$$ will do the job.
Here’s python code for modifying the signed share’s $y$ component to arbitrary value:
# hash_extender is a wrapper around the command line hash_extender # trick: first we append nothing to obtain the base value testdata, _sig = hash_extender( data=share, hash=sig, append="", hashname="sha256", length=keylen ) # y = 2^e * c + sometrash (mod p) # c = (y - sometrash) / 2^e (mod p) e = len(testdata) * 8 inv2e = invmod(2**e, p) trash = from_bytes(testdata) % p def gen_share_with_y(y): c = (y - trash) * inv2e % p newdata, newsig = hash_extender(data=share, hash=sig, append=to_bytes(c), hashname="sha256", length=keylen) return newsig + newdata.encode("hex") |
Digging into the secret sharing
Our final goal is to execute some evil command on the server. The command is obtained from combining the two shares: our share and one of the server’s shares. We can partially modify our share, but the server’s share stays untouched! Is it still possible to modify the command in a meaningful way? Hoping for lucky random commands (like “sh\n”) is a bad idea, since the command is prepended by a SHA256 checksum…
Let’s look closer at the sharing scheme. When splitting the shares, the server creates a random polynomial of degree 1 (it has (threshold) coefficients) with the constant coefficient equal to the secret being shared. Then it is evaluated on three random points, and the three $(x_i, y_i)$ pairs are the shares. For a polynomial of degree 1, any two different points are enough to recover the full polynomial, that’s how it works! The interpolation algorithm is implemented on the server and we actually don’t care about the implementation, we care only about semantics of it.
We can think about the combining step as follows: the server has two shares $(x_1, y_1)$ and $(x_2, y_2)$ and it wants to find two coefficients $a, b$ in the finite field $\mathbb{F}_p$ for which the equation $a*x + b = y$ holds for both shares. That is, it solves the following linear system with two unknowns $a, b$:
$$\begin{cases}
a x_1 + b = y_1,\\
a x_2 + b = y_2,\\
\end{cases}$$
Then $b$ is the constant coefficient in the polynomial and so is the initial secret.
Let’s say our share is number 2, so we control $y_2$. Let’s solve the system for $b$:
$$\begin{split}
a & = & \frac{y_1 – y_2}{x_1 – x_2}, \\
b & = & y_2 – a x_2 = y_2 – x_2\frac{y_1 – y_2}{x_1 – x_2} = y_2 – u + y_2 / v = w y_2 – u.
\end{split}$$
Note that we have done some variable replacements, since we don’t really care about all values $(x_1, y_1, x_2)$, but only about the minimum number of expressions involving them. We obtained that the algorithm the server uses to combine the shares is basically a linear function of $y_2$, which we control! So we have only two unknowns, the coefficients $w$ and $u$! How can we learn them? Obviously we need to get some information from the server, since we know nothing about the share #1.
Recovering the linear coefficients
For simplicity, let’s rename variables and assume that the server computes $secret \equiv a y_2 + b \pmod{p}$ ($a$ and $b$ are the new unknowns, unrelated to previous ones).
Since we have no information about $a, b$ we can’t set $secret$ in a meaningful way first. Therefore the checksum check will fail… and the server will leak a part of the $secret$ that he combined!
def unpack(msg, key = b''): tag = msg[:SHA.digest_size] if tag == SHA.new(key + msg[len(tag):]).digest(): return msg[len(tag):] print('bad {}: {}'.format(('checksum', 'tag')[bool(key)], tohex(tag))) |
Unluckily, the server leaks only 256 least significant bits of the secret (from 512). To sum up, we have the following oracle:
(Share with $y_2$) $\mapsto$ (256 LSBs of the resulting secret).
First, we can query $y_2 = 0$ and obtain the LSBs of $secret = (0y_2 + b) \mod{p} = b$. Then we can query $y_2 = 1$ and obtain LSBs of $(a + b) \mod{p}$, which quite often will be equal to just LSBs of $a + b$, therefore we can learn also LSBs of $a$. So, we can learn 256 LSBs of $a$ and $b$ in 2 queries.
Now, let’s try to shift $a$ down so that we learn the MSBs of it. To do this we set $y_2$ to $2^{-256} \pmod{p}$. However this is not exactly the shift due to modulo $p$. What we obtain is:
$$(y_2 a + b) \mod{p} = (2^{-256} a + b) \mod {p} = ((a + kp) / 2^{256} + b) \mod {p},$$
where $k$ is such that $a + kp \equiv 0 \pmod{2^{256}}$ and the last division is done in integers. Luckily, we know LSBs of $a$, that is, we know $a \mod{2^{256}}$, we can predict LSBs of $k$:
$$k \equiv -a/p \pmod{2^{256}}.$$
Now comes an interesting point. The smallest such $k = k_0$ is less than $2^{256}$. All other $k$ satisfying this condition can be described as $k = k_0 + t2^{256}$ for some integer $t$. Note that:
$$\begin{split}
((a + kp) / 2^{256} + b) \mod{p} & = & ((a + k_0p + 2^{256}tp) / 2^{256} + b) \mod{p}\\
& = & ((a + k_0p) / 2^{256} + b + tp) \mod{p},
\end{split}$$
…and $tp$ goes away due to modulo! This means that we need to know only $k \equiv -a/p \mod{2^{256}}$, which we can compute as mentioned before.
Moreover, we can guess whether the last addition of $b$ overflowed the modulo or not. Let’s assume that it did not, it is quite probable. Then for the query $y_2 = (2^{-256} \mod{p})$ we get (note the modulo change):
$$r = (2^{-256}a + b) \mod{p} \equiv (a + kp) / 2^{256} + b \pmod{2^{256}}.$$
Then using known LSBs of $b$ we get:
$$2^{256} (r – b) \equiv a + kp \pmod {2^{512}}.$$
$$a \equiv 2^{256} (r – b) – kp \pmod {2^{512}}.$$
We learned the full $a$! Recall that we assumed that addition of $b$ does not overflow the modulo. We can guess this and try to add $p$, or choose first $y_0=2^{128}$ instead of $y_0=2^{256}$ and learn full $a$ in two steps. This trick allows us to notice the additional subtraction of $p$ since in the first query half of the obtained bits should match the known bits of $a$.
Ok, how to learn full $b$ now? Sadly, we can’t shift it and the effect of it’s high bits is quite limited. We now can exploit the effect of $b$ on overflowing the modulo: for specially crafted queries we will check how many times we overflow the modulo and deduce some information about $b$. Recall that we can query
$$(ay_0 + b) \mod {p} = ay_0 + b -kp$$
for some $k$. Note that since $b < p$, its value may change $k$ only by $1$. Let's perform a binary search of the real value of $b$. Assume that we know that $b_l \le b \le b_r$ for some known $b_l, b_r$. Let $mid = (b_l + b_r) / 2$. Then we can craft such $y_0$ that for fall $b_l \le b < mid$ we will get known $k = k_0$ and for $mid \le b \le b_r$ we will get $k = k_0 - 1$. Such $y_0$ can be obtained as $y_0 \equiv -mid / a \pmod{p}$, since then $$(y_0 a + b) \mod{p} = (b - mid) \mod{p}$$ and then we will get either $b - mid$ or $b - mid + p$. Since we know LSBs of $b$ and $mid$, we can easily distinguish between two cases and divide the search space for $b$ by 2. Note that we need to learn only 256 MSBs of $b$, so we are good with around 256 queries for this binary search.
To sum up, we need 2 queries to learn LSBs of $a$ and $b$, 2 queries to learn full $a$ and at most 256 queries to learn full $b$.
Here’s python code for recovering $a, b$:
def oracle(y): assert 'what have you got' in f.read_line() f.send_line(gen_share_with_y(y)) res = f.read_line() assert "bad checksum" in res, "oracle failed: %r" % res return from_bytes(res.split()[-1].decode("hex")) MOD = 2**256 blow = oracle(0) % MOD alow = (oracle(1) - blow) % MOD i2 = invmod(2, p) a = alow for e in (128, 256): mod2 = 2**e k = invmod(p, mod2) * (-a) % mod2 assert (a + k * p) % mod2 == 0 res = (oracle(i2**e) - blow) % MOD shifted = ((res << e) - k * p) % (MOD << e) # did we get additional -p because of b? if shifted % MOD != a % MOD: res = (oracle(i2**e) - blow + p) % MOD shifted = ((res << e) - k * p) % (MOD << e) assert shifted % MOD == a % MOD a |= shifted print "Learned full a:", tohex(a) if a >= p: assert 0, "Failed, seems in the second query there was an overflow." ia = invmod(a, p) bl = 0 br = p - a - 1 while bl < br: mid = (bl + br) // 2 x = ia * (-mid) % p assert (x*a + mid) % p == 0 res = oracle(x) % MOD if res == (blow - mid) % MOD: bl = mid elif res == (blow - mid + p) % MOD: br = mid - 1 else: assert 0, "Failed, seems in the second query there was an overflow." if bl >> 256 == br >> 256: break b = br - br % MOD + blow print "Learned full b:", tohex(b) if b >= p: assert 0, "Failed, seems in the second query there was an overflow." |
Forging the Evil Command
Finally, when we have learned $a$ and $b$, we can forge and execute arbitrary commands:
def pack(msg, key=''): return SHA.new(key + msg).digest() + msg packed = from_bytes(pack(r"echo PWNED; bash")) assert packed < p y = (packed - b) * ia % p assert (a * y + b) % p == packed print "Command executing:" assert 'what have you got' in f.read_line() f.send_line(gen_share_with_y(y)) f.interact() |
In half of the runs we will get a shell!
1 ping
[…] http://mslc.ctf.su/wp/tum-ctf-2016-shaman-crypto-500/ […]