I was teamed-up with Black Bauhinia on Google CTF this time. I have solved 7 challenges alone and 3 challenges with my teammates.
In particular, Oracle is a crypto challenge with 13 solves. It has got me spending 12 hours. All in all, it was a great experience in terms of learning, but my liver hurts. This piece of writeup may be very computation intensive, just because I would like to make everything clear.
There are two parts of the challenges. In the first part, we are required to recover an internal state for AEGIS-128L given the encryption oracle. For the second part, we are required to forge a ciphertext given an error oracle from decryption.
AEGIS-128L has an internal state that is initially computed solely by the key and the IV. It is of 128 bytes, broken into eight 16-byte blocks. Let's S_i is updated to S_(i+1) given 32-byte payload M. Let's define S_i = (s_(i,0), s_(i,1), ..., s_(i,7)) and M = (m_0, m_1). We have:
s_(i+1,0) -> AESEnc(s_(i,7), s_(i,0)) ^ m_0,s_(i+1,4) -> AESEnc(s_(i,3), s_(i,4)) ^ m_1, ands_(i+1,j) -> AESEnc(s_(i,j-1), s_(i,j))forj = 1, 2, 3, 5, 6, 7.
But what is AESEnc? Let's see the implementation.
def aes_enc(s: block, t: block) -> block:
"""Performs the AESENC operation with tables."""
t0 = (te0[s[0]] ^ te1[s[5]] ^ te2[s[10]] ^ te3[s[15]])
t1 = (te0[s[4]] ^ te1[s[9]] ^ te2[s[14]] ^ te3[s[3]])
t2 = (te0[s[8]] ^ te1[s[13]] ^ te2[s[2]] ^ te3[s[7]])
t3 = (te0[s[12]] ^ te1[s[1]] ^ te2[s[6]] ^ te3[s[11]])
s = _block_from_ints([t0, t1, t2, t3])
return _xor(s, t)Well... we will go through this later. Let's introduce how keystreams are generated from the state. It is (relatively) simple. The keystream (k_(i,0), k_(i,1)) for the i-th round is given by:
k_(i,0) = (s_(i,2) & s_(i,3)) ^ s_(i,1) ^ s_(i,6) and k_(i,1) = (s_(i,6) & s_(i,7)) ^ s_(i,5) ^ s_(i,2).
Now we are given that key and IV are unchanged. This implies that the initial state, i.e., s_00, s_01, ..., s_09 are constants too.
Suppose that we have two 96-byte messages M1 and M2 with only the first two blocks are different (Formally, if Mk := (mk_00, mk_01, ..., mk_21), then m1_ij = m2_ij$ if and only if i != 0).
The following table summarizes which of the s_ij's that would be different (marked by an !), when encrypting M1 and M2 respectively.
| i \ j | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 0 | ||||||||
| 1 | ! | ! | ||||||
| 2 | ! | ! | ! | ! |
What does this imply? Knowing that s1_(2,j) = s2_(2,j) for j = 2, 3, 6, 7. Let's look closely on the last 32 bytes of the keystream:
We can derive that k1_20 ^ k2_20 == s1_21 ^ s2_21, and similarly k1_21 ^ k2_21 == s1_25 ^ s2_25.
Why is it useful? Let's define a new function, p:
def p(s: block) -> block:
t0 = (te0[s[0]] ^ te1[s[5]] ^ te2[s[10]] ^ te3[s[15]])
t1 = (te0[s[4]] ^ te1[s[9]] ^ te2[s[14]] ^ te3[s[3]])
t2 = (te0[s[8]] ^ te1[s[13]] ^ te2[s[2]] ^ te3[s[7]])
t3 = (te0[s[12]] ^ te1[s[1]] ^ te2[s[6]] ^ te3[s[11]])
return _block_from_ints([t0, t1, t2, t3])Déjà vu? It is more or less the same with AESEnc. We can state that AESEnc(s, t) == p(s) ^ t too. Looking even more closely, one could observe that the first four bytes from p solely depends on bytes 0, 5, 10 and 15 from s.
Knowing this, we can further expand k1_20 ^ k2_20 = p(x ^ m1_00) ^ p(x ^ m2_00), Where x = AESEnc(s_07, s_00) = s_10 ^ m1_00 for ease of reading.)
And now the only unknown is x. Can we solve it easily? Yes indeed: we can compute bytes 0, 5, 10, 15 of x from the first four bytes of k1_20 ^ k2_20. Along with three more equalities from p, we are able to recover x completely. I used an meet-in-the-middle approach to solve for x in five seconds.
But wait. There is a problem: I am able to find 65536 candidates (or even more) instead of 1, but I am unable to eliminate the rest. The possible number of states will be growing exponentally! What can I do? The solution is actually simple: Just send M3 and compute another solution set of x. After all, it is very likely that x is the only element in the intersection of the two sets. With x, we are able to compute s_10 (respectively s_14).
We can extend the above idea to leak more. By sending two 128-byte messages with blocks 3 and 4 being different, we are able to recover s_20 and s_24. We are able to leak s_30 and s_34 with the same idea.
Two more questions remain: How is it made possible in seven queries? And more importantly, how can we recover s_ij for all j, for some i (preferably i = 0 or i = 1)?
Challenge 1. Recover the above states in 7 queries.
In short, we are encrypting these seven plaintexts (each 0 represents 16 \x00's, etc):
000000000000001100000000220000- Derives_10ands_14uniquely with (1) and (2)00000011000000002200- Derives_20ands_24uniquely with (1) and (4)00000000110000000022- Derives_30ands_34uniquely with (1) and (6)
Challenge 2. Recover s_(1,j) for all j.
From above, we are able to derive s_(i,0) and s_(i,4) for i = 1, 2, 3 with m_ij = 0. Hence, the state transition would be s_(i+1,j) -> p(s_(i,j-1)) ^ s_(ij) for all i and j. Equivalently s_(i,j-1) = p_inverse(s_(i+1,j) ^ s_ij).
We are able to compute inverses of s_(1,j)'s can be derived.
After all, the first part of the challenge is done.
For the second part, AEGIS-128 is used. The state is now 80 bytes (five 16-byte blocks). The payload size has been reduced to one block (let's denote it by
s_(i+1,0) -> p(s_(i,4)) ^ s_(i,0) ^ m, ands_(i+1,j) -> p(s_(i,j-1) ^ s_(i,j))for1 <= j <= 4.
Moreover, the keystream k_i for the i-th round is also altered: k_i = (s_i2 & s_i3) ^ s_i1 ^ s_i4$.
I have no idea what's going on, so I decided to recover the printable secret_plaintext first.
It is pretty easy, and is made possible because we are able to receive the error from the oracle. In particular, from pt.decode("ascii").
We are able to recover the plaintext with bit-flipping. To begin with, we can flip the whole ciphertext by \x80. The first 32 bytes for the plaintext would be flipped by \x80 as well. If we send the flipped ciphertext (denote by c_?) to the oracle, we will obtain:
UnicodeDecodeError: 'ascii' codec can't decode byte 0xe7 in position 0: ordinal not in range(128)
This means that the first byte of the flipped plaintext would be \xe7. Hence, the first byte of the plaintext is \x67 (g). We then flip the first byte of c_? by \x80 and send it to the oracle, we will be receiving another error:
UnicodeDecodeError: 'ascii' codec can't decode byte 0xc6 in position 1: ordinal not in range(128)
This recovers the second byte - x46 (F). Since the secret plaintext is 96-byte long, we can recover it with 96 oracle calls.
REMAINING ORACLE CALLS: 231 - 96 = 135.
With a plaintext recovered, it is time for us to try to recover the internal state. Can we devise a similar strategy that is similar to the first part of the challenge? Formally, what will happen if we have two 48-byte messages M1 = (m1_0, m1_1, m1_2) and M2 = (m2_0, m2_1, m2_2) with only the first block being different. Then the last 16 bytes in the keystream will be k1_2 ^ k2_2 = p(x ^ m1_0) ^ p(x ^ m2_0).
Hereby denote x = AESEnc(s_04, s_00) = s_10 ^ m1_0. Simply put, if we have the ciphertexts for M1 and M2 (denote it as Ck = (ck_0, ck_1, ck_2)), we are able to recover one-fifths of the state if this happens.
How are we able to do it? Well actually, we have recovered the secret plaintext above. We can flip the first block of the ciphertext arbitrarily (to C_?).
However, since k2_2 is altered, the third block of the message would be updated. Luckily we are able to recover the message in 17 oracle calls. Here's how:
- Sends
C_?. We will obtain something like this:UnicodeDecodeError: 'ascii' codec can't decode byte 0xe8 in position 34... - Flips the 35th byte by
\xe8inC_?. Sends the patchedC_?:UnicodeDecodeError: 'ascii' codec can't decode byte 0xcb in position 35... - Flips the 36th byte by
\xcbinC_?. Repeat the process until we receive OK, meaning that the plaintext is now ASCII-encoded. - For now, we have recovered a subset of message bytes. We then flip the unknown bytes by
\x80(for example, bytes 33 and 34) to throw errors from the oracle. - Repeat step 1 until all unknown bytes are recovered.
In short, we spent 16 oracle calls to recover the message, and one oracle call to indicate us to flip all the bytes those were originally printable. We are then able to recover a possible set of s_10, however.
REMAINING ORACLE CALLS: 135 - 17×2 = 101.
With the same idea, we can recover s_20, s_30, s_40 with 17×6 queries. This would allow us to recover s_10, s_11, ..., s_14 and hence forging arbitrary messages (along with a slightly longer AD).
REMAINING ORACLE CALLS: 101 - 17×6 = -1.
Shoot - we are one query short. Since we are able to recover one byte of the plaintext in each of the queries, so it doesn't hurt to sacrifice one oracle calls by guessing one byte. So... in theory, we are able to finish the challenge with once every 256 times.
Luckily, if we are given a incorrect plaintext (actually keystream), we are unable to recover a single s_*. That's pretty good, we are able to solve the challenge every time.
REMAINING ORACLE CALLS: -1 + 1 = 🎉.
With the exploit script written, I am able to reach the very end locally. Congratulations to me!
No... When I am interacting to the server, I am always disconnected while sending one of the 231 oracle calls. Asking the organizers in IRC, knowing that there was an 1-minute timeout - it was later increased to 10 minutes. Unfortunately, my solution runs for around 5 minutes. I have two choices:
- Wait until the challenge has a 10-minute timeout, or
- Optimize the script and have it completed in one minute.
Seeing that there are already few teams solving the challenge, I think (2) would be fun.
For inputs that does not require immediate feedbacks, we can send them at the same time. This is an example when I am recovering secret_plaintext in the second part.
# Before optimization
test_ciphertext = bytes([c^0x80 for c in ciphertext])
m0 = b''
for i in range(96):
r.sendline(base64.b64encode(test_ciphertext))
test_ciphertext = cxor(test_ciphertext, i, 0x80)
p, mc = try_decrypt_read(r)
assert p == i
m0 += bytes([mc^0x80])
# After optimization
test_ciphertext = bytes([c^0x80 for c in ciphertext])
m0 = b''
for i in range(96):
r.sendline(base64.b64encode(test_ciphertext))
test_ciphertext = cxor(test_ciphertext, i, 0x80)
for i in range(96):
p, mc = try_decrypt_read(r)
assert p == i
m0 += bytes([mc^0x80])For example, this is the method I implemented to solve for x from p(x ^ a) ^ p(x ^ b) = c - it takes one second each time:
def px_subsolve(a_sub, b_sub, c_sub):
# Given a_sub, b_sub, c_sub (4 bytes), find x_sub such that
# te0[(x_sub ^ a_sub)[0]] ^ te1[(x_sub ^ a_sub)[1]] ^ te2[(x_sub ^ a_sub)[2]] ^ te3[(x_sub ^ a_sub)[3]]
# ^ te0[(x_sub ^ a_sub)[0]] ^ te1[(x_sub ^ a_sub)[1]] ^ te2[(x_sub ^ a_sub)[2]] ^ te3[(x_sub ^ a_sub)[3]]
# = c_sub
# Reformulating:
# te0[(x_sub ^ a_sub)[0]] ^ te1[(x_sub ^ a_sub)[1]] ^ te0[(x_sub ^ a_sub)[0]] ^ te1[(x_sub ^ a_sub)[1]] ^ c_sub
# = te2[(x_sub ^ a_sub)[2]] ^ te3[(x_sub ^ a_sub)[3]] ^ te2[(x_sub ^ a_sub)[2]] ^ te3[(x_sub ^ a_sub)[3]]
lhss = {}
for x0, x1 in itertools.product(range(256), repeat=2):
# LHS
xs = [be0[x0^a_sub[0]], be0[x0^b_sub[0]], be1[x1^a_sub[1]], be1[x1^b_sub[1]], c_sub]
y = reduce(_xor, xs)
lhss[y] = lhss.get(y, []) + [(x0, x1)]
solns = []
for x2, x3 in itertools.product(range(256), repeat=2):
# RHS
xs = [be2[x2^a_sub[2]], be2[x2^b_sub[2]], be3[x3^a_sub[3]], be3[x3^b_sub[3]]]
y = reduce(_xor, xs)
for x0, x1 in lhss.get(y, []):
solns.append(bytes([x0, x1, x2, x3]))
return solnsHowever, if we force a_sub == b'\0'*4 and b_sub == b'\1'*4 or b_sub == b'\2'*4, the right hand side can be precomputed. We are able to solve for
At last - we are able to get the flag in 30 seconds locally and around 55 seconds online! 🎉