Try   HackMD

Google CTF 2020: Oracle

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.

Challenge Summary

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.

Solution

Part I: A brief summary for the state in AEGIS-128L

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

Si is updated to
Si+1
given 32-byte payload
M
. Let's define
Si=(si,0,si,1,...,si,7)
and
M=(m0,m1)
. We have:

  • si+1,0AESEnc(si,7,si,0)m0
    ,
  • si+1,4AESEnc(si,3,si,4)m1
    , and
  • si+1,jAESEnc(si,j1,si,j)
    for
    j=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

(ki,0,ki,1) for the
i
-th round is given by:

ki,0=(si,2si,3)si,1si,6,ki,1=(si,6si,7)si,5si,2.

Part II: Recovering part of the state

Now we are given that key and IV are unchanged. This implies that the initial state, i.e.,

s00,s01,...,s09 are constants too.

Suppose that we have two 96-byte messages

M(1) and
M(2)
with only the first two blocks are different (Formally, if
M(k):=(m00(k),m01(k),...,m21(k)
), then
mij(1)=mij(2)
if and only if
i0
).

The following table summarizes which of the

sij's that would be different (marked by an !), when encrypting
M(1)
and
M(2)
respectively.

i
\
j
0 1 2 3 4 5 6 7
0
1 ! !
2 ! ! ! !

What does this imply? Knowing that

s2,j(1)=s2,j(2) for
j=2,3,6,7
. Let's look closely on the last 32 bytes of the keystream:

k20(1)k20(2)=m20(1)c20(1)m20(2)c20(2)=[(s22(1)s23(1))s21(1)s26(1)][(s22(2)s23(2))s21(2)s26(2)]=s21(1)s21(2).

And similarly

k21(1)k21(2)=s25(1)s25(2).

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

k20(1)k20(2):

k20(1)k20(2)=s21(1)s21(2)=AESEnc(s10(1),s11(1))AESEnc(s10(2),s11(2))=p(s10(1))s11(1)p(s10(2))s11(2)=p(s10(1))p(s10(2))=p(AESEnc(s07(1),s00(1))m00(1))p(AESEnc(s07(2),s00(2))m00(2))=p(xm00(1))p(xm00(2)).

(We define

x:=AESEnc(s07,s00)=s10m00(1) 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
k20(1)k20(2)
. 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.

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

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

M(3) 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
s10
(respectively
s14
).

Part III: Finishing the first part of the challenge

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

s20 and
s24
. We are able to leak
s30
and
s34
with the same idea.

Two more questions remain: How is it made possible in seven queries? And more importantly, how can we recover

sij for all
j
, for some
i
(preferably
i=0 or 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):

  1. 0000000000
  2. 0000110000
  3. 0000220000 - Derive
    s10
    and
    s14
    uniquely with (1) and (2)
  4. 0000001100
  5. 0000002200 - Derive
    s20
    and
    s24
    uniquely with (1) and (4)
  6. 0000000011
  7. 0000000022 - Derive
    s30
    and
    s34
    uniquely with (1) and (6)

Challenge 2. Recover

s1,j for all
j
.

From above, we are able to derive

si,0 and
si,4
for
i=1,2,3
with
mij=0
. Hence, the state transition would be
si+1,jp(si,j1)sij
for all
i,j
. Equivalently
si,j1=p1(si+1,jsij)
.

We are able to compute inverses of

p1 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
s1,j
's can be derived.







%0



s₁₀

s₁₀



s₁₇

s₁₇



s₁₀->s₁₇





s₁₄

s₁₄



s₁₃

s₁₃



s₁₄->s₁₃





s₂₀

s₂₀



s₂₇

s₂₇



s₂₀->s₂₇





s₂₀->s₁₇





s₂₄

s₂₄



s₂₃

s₂₃



s₂₄->s₂₃





s₂₄->s₁₃





s₃₀

s₃₀



s₃₀->s₂₇





s₃₄

s₃₄



s₃₄->s₂₃





s₁₆

s₁₆



s₂₇->s₁₆





s₁₂

s₁₂



s₂₃->s₁₂





s₁₃->s₁₂





s₁₁

s₁₁



s₁₃->s₁₁





s₁₂->s₁₁





s₁₅

s₁₅



s₁₂->s₁₅





s₁₇->s₁₆





s₁₇->s₁₅





s₁₆->s₁₁





s₁₆->s₁₅





After all, the first part of the challenge is done.

Part IV: AEGIS-128 vs AEGIS-128L

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

m). This is how the state transited:

  • si+1,0p(si,4)si,0m
    , and
  • si+1,jp(si,j1)si,j
    for
    1j4
    .

Moreover, the keystream

ki for the
i
-th round is also altered:
ki=(si,2si,3)si,1si,4
.

Part V: Exploring the challenge

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

M(1):=(m0(1),m1(1),m2(1)) and
M(2):=(m0(2),m1(2),m2(2))
with only the first block being different. Then the last 16 bytes in the keystream will be:

k2(1)k2(2)=[(s22(1)s23(1))s21(1)s24(1)][(s22(2)s23(2))s21(2)s24(2)]=s21(1)s21(2)=p(s10(1))s11(1)p(s10(2))s11(2)=p(s10(1))p(s10(2))=p(AESEnc(s04(1),s00(1))m1(1))p(AESEnc(s04(2),s00(2))m1(2))=p(xm0(1))p(xm0(2)).

Hereby denote

x:=AESEnc(s04,s00)=s10m0(1). Simply put, if we have the ciphertexts for
M(1)
and
M(2)
(denote it as
C(k)=(c0(k),c1(k),c2(k))
), 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:

  1. Sends
    C?
    . We will obtain something like this:
    ​​​​UnicodeDecodeError: 'ascii' codec can't decode byte 0xe8 in position 34...
    
  2. Flips the 35th byte by \xe8 in
    C?
    . Sends the patched
    C?
    :
    ​​​​UnicodeDecodeError: 'ascii' codec can't decode byte 0xcb in position 35...
    
  3. Flips the 36th byte by \xcb in
    C?
    . Repeat the process until we receive OK, meaning that the plaintext is now ASCII-encoded.
  4. 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.
  5. 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

s10 with 65536 entries (or more). We can spend another 17 queries to find the actual
s10
, however.

REMAINING ORACLE CALLS: 135 - 17×2 = 101.

With the same idea, we can recover

s20,s30,s40 with 17×6 queries. This would allow us to recover
s10,s11,...,s14
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 =

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
.

With the exploit script written, I am able to reach the very end locally. Congratulations to me!

Part IV: Wait Aren't we done?

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:

  1. Wait until the challenge has a 10-minute timeout, or
  2. 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.

6.1. Reducing online complexity

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])

6.2. Reducing offline complexity

For example, this is the method I implemented to solve for

x from
p(xa)p(xb)=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 solns

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

x once every 0.2 second.

At last - we are able to get the flag in 30 seconds locally and around 55 seconds online!

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →


Credits

  • Thanks @harrier who noticed that my lever did not hurt. Playing Minecraft too much, I misspelt liver.
  • Thanks @hellman pointing that we are able to bruteforce byte bybyte instead of bruteforcing columns, since that we can apply MixColumns inverse (the corresponding tweet).
tags: CTF