The HalfFeed service allows us to encrypt almost any message.
The only restriction is that it cannot contain the string “cat flag”:
1
2
3
4
5
6
7
8
9
10
11
12
13
defencrypt(halffeed):
global nonce
P = recv_data('plaintext')
ifb'cat flag'in P:
print('[EXCEPTION] Invalid Command "cat flag"')
exit()
C, T = halffeed.encrypt(nonce.to_bytes(16, byteorder='big'), P)
send_data('ciphertext', C)
send_data('tag', T)
nonce += 1
We can also provide a ciphertext, that is split on “;”.
If any of the segments is “cat flag” we win:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
defexecute(halffeed):
N = recv_data('nonce')
C = recv_data('ciphertext')
T = recv_data('tag')
P = halffeed.decrypt(N, C, T)
if P isnot None:
cmds = P.split(b';')
for cmd in cmds:
if cmd.strip() == b'cat flag':
withopen('./flag') as f:
print(f.read())
else:
print('[EXCEPTION] Unknown Command')
else:
print('[EXCEPTION] Authentication Failed')
exit()
We have our job cut out for us.
Encryption is done using some Frankenstein mode with a AES-CTR-like encryption with a AES-CBC-MAC-like authentication.
The relevant parts of the code is provided below,
though it is easier to read the description that follows:
The tag is then encrypted, before processing the next block:
\[
\text{tag} \leftarrow \text{AES}_{k_i}(\text{tag})
\]
\[
k_{i+1} \leftarrow \text{AES}_{k_i}(k_i)
\]
Visually the tag generation operates as follows:
The IV affects not only \( T_0 \), but also \( k_0 \) and hence the “key-schedule”
for the encryption (indicated above with different colored boxes).
However when we reconnect the IV is reset, hence we can trick the server into reusing the same IV.
When we encrypt two different plaintexts with the same IV,
the key-schedule and initial tag will be the same. Illustrated below:
We can then “glue” the two ciphertexts with the same IV together,
by having a prefix from the first message, a specially crafted block,
then the postfix from the second message.
The resulting tag will be that of the second message, \( T_3' \):
By picking \( A = \Delta \oplus P_2 \), where \( \Delta = (C_2 \oplus C_2')\text{[:8]} + (P_2 \oplus P_2')\text{[8:]} \).
Note that we can manipulate the plaintext \( A \) by xoring the same difference into the ciphertext \( C_2 \),
since it is completely linear:
We make use of this by requesting a number of encryptions of 3 block messages under the same IV, where \( P_1 = r \ |\!| \ \text{";cat fla"} \) for random \( r \):
Then we glue every pair of ciphertexts together and hope that \( A \) starts with “g;”.
In which case the plaintext will contain “;cat flag;” as desired:
By the birthday paradox we need \( \approx \sqrt{ 2^{16} } = 256 \) plaintext/ciphertexts pairs
for the attack to succeed.
After “glueing” together such a ciphertext and tag, we simply (manually, not in doit.py) send this to the server and obtain the flag: