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 is updated to given 32-byte payload . Let's define and . We have:
But what is AESEnc
? Let's see the implementation.
Well… we will go through this later. Let's introduce how keystreams are generated from the state. It is (relatively) simple. The keystream for the -th round is given by:
Now we are given that key and IV are unchanged. This implies that the initial state, i.e., are constants too.
Suppose that we have two 96-byte messages and with only the first two blocks are different (Formally, if ), then if and only if ).
The following table summarizes which of the 's that would be different (marked by an !
), when encrypting and respectively.
\ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|---|
0 | ||||||||
1 | ! | ! | ||||||
2 | ! | ! | ! | ! |
What does this imply? Knowing that for . Let's look closely on the last 32 bytes of the keystream:
And similarly .
Why is it useful? Let's define a new function, p
:
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 :
(We define for ease of reading.)
And now the only unknown is . Can we solve it easily? Yes indeed: we can compute bytes 0, 5, 10, 15 of from the first four bytes of . Along with three more equalities from p
, we are able to recover completely. I used an meet-in-the-middle approach to solve for 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 and compute another solution set of . After all, it is very likely that is the only element in the intersection of the two sets. With , we are able to compute (respectively ).
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 and . We are able to leak and with the same idea.
Two more questions remain: How is it made possible in seven queries? And more importantly, how can we recover for all , for some (preferably )?
Challenge 1. Recover the above states in 7 queries.
In short, we are encrypting these seven plaintexts (each 0
represents 16 \x00
's, etc):
0000000000
0000110000
0000220000
- Derive and uniquely with (1) and (2)0000001100
0000002200
- Derive and uniquely with (1) and (4)0000000011
0000000022
- Derive and uniquely with (1) and (6)Challenge 2. Recover for all .
From above, we are able to derive and for with . Hence, the state transition would be for all . Equivalently .
We are able to compute inverses of easily. Solving system of linear equations would be all good, but I'm doing it with meet-in-the-middle. Code reuse for the win! For now, let's visualize how '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 ). This is how the state transited:
Moreover, the keystream for the -th round is also altered: .
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 ) to the oracle, we will obtain:
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 by \x80
and send it to the oracle, we will be receiving another error:
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 and with only the first block being different. Then the last 16 bytes in the keystream will be:
Hereby denote . Simply put, if we have the ciphertexts for and (denote it as ), 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 ).
However, since 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:
\xe8
in . Sends the patched :
\xcb
in . Repeat the process until we receive OK, meaning that the plaintext is now ASCII-encoded.\x80
(for example, bytes 33 and 34) to throw errors from the oracle.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 with 65536 entries (or more). We can spend another 17 queries to find the actual , however.
REMAINING ORACLE CALLS: 135 - 17×2 = 101.
With the same idea, we can recover with 17×6 queries. This would allow us to recover 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 . That's pretty good, we are able to solve the challenge every time.
REMAINING ORACLE CALLS: -1 + 1 =
Learn More →
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:
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.
For example, this is the method I implemented to solve for from - it takes one second each time:
However, 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 once every 0.2 second.
At last - we are able to get the flag in 30 seconds locally and around 55 seconds online!
MixColumns
inverse (the corresponding tweet).CTF