Writeup by sin-infosec for Macaque

TLDR

Forge an authentication tag by breaking the logic of a homemade tag generation.

Recon

Here is the macaque.py file that we are provided with and that is running on the remote service:

The script is pretty straightforward, we have access to an oracle that provides a valid deterministic homemade tag for a given message, with a limit of 3 requests to the oracle, and we then need to forge a valid tag for a message that wasn’t sent to the oracle yet. Let’s dig into the tag creation code:

class Macaque():
    def __init__(self, k1, k2):
        self.k1 = k1
        self.k2 = k2
        self.bs = AES.block_size
        self.zero = b"\x00" * self.bs

if __name__ == "__main__":

    S = set()
    singe = Macaque(os.urandom(16), os.urandom(16))

When we connect to the service, the class Macaque is initialized with two random keys. Theses keys will remain the same for the whole session. Now how are these keys used during the signature process?

    def tag(self, m):
        m = pad(m, self.bs)
        c1 = AES.new(self.k1, AES.MODE_CBC, iv = self.zero).encrypt(m)
        c2 = AES.new(self.k2, AES.MODE_CBC, iv = self.zero).encrypt(m)
        return c1[-self.bs:] + c2[-self.bs:]

Here is a sketch of the signature process, where $P_1,P_2,…,P_k$ are the $k$ 16-bytes plaintext blocks that are given in input, $Tag$ is the authentication tag, and $AES_{K_i}$ represents the AES encryption with key $K_i$:

So we get the concatenation of the last blocks of two AES encryptions of the plaintext in CBC mode with distinct keys and null IV. The last remark that is worth noting is that the input is padded before creating the tag using Crypto.Util.Padding pad function, that uses PKCS#7 padding to either fill the last block of plaintext with (block_size - len(last_block)) * bytes([(block_size - len(last_block))]), or add a block of 16 b"\x10" if the input is already a multiple of the block size. A visual example always helps:

>>> pad(b"a",16).hex()
'610f0f0f0f0f0f0f0f0f0f0f0f0f0f0f'
>>> pad(b"abcd",16).hex()
'616263640c0c0c0c0c0c0c0c0c0c0c0c'
>>> pad(b"a"*16,16).hex()
'6161616161616161616161616161616110101010101010101010101010101010'

The Attack

Allright, time for the attack, here is how I exploited this:

• send 'a' as a message for the first request to the oracle. The padded plaintext input $P_1$ will be 'a' + '\x0f' * 15 and the tag will be $Tag = AES_{K_1}(P_1) || AES_{K_2}(P_1)$

• Choose a random block $M$, let’s say 'b' * 16, then send 'a' + '\x0f' * 15 + xor(Tag[:16],'b' * 16) as a message for the second request to the oracle. The padded plaintext input $P=(P_1’||P_2’||P_3’$) will be ''a' + '\x0f' * 15 + xor(Tag[:16],'b' * 16) + '\x10' * 16 and the tag will be:

$$ \begin{aligned} Tag &= AES_{K_1}(P_3’ \oplus C_2’)|| AES_{K_2}(P_3’ \oplus C_2’)) \\ Tag &= AES_{K_1}(P_3’ \oplus AES_{K_1}(P_2’ \oplus C_1’))|| AES_{K_2}(P_3’ \oplus AES_{K_2}(P_2’ \oplus C_1’)) \\ Tag &= AES_{K_1}(P_3’ \oplus AES_{K_1}(P_2’ \oplus AES_{K_1}(P_1’))|| AES_{K_2}(P_3’ \oplus AES_{K_2}(P_2’ \oplus AES_{K_2}(P_1’))) \end{aligned} $$

And we chose $P_1’ = P_1$, $P_2’ = M \oplus AES_{K_1}(P_1)$ and $P_3’$ is naturally the padding block, so we get:

$$ AES_{K_1}(P_3’ \oplus AES_{K_1}(M)|| AES_{K_2}(P_3’ \oplus AES_{K_2}(P_2’ \oplus AES_{K_2}(P_1’)))$$

Notice that the first part of this tag is the valid part regarding $K_1$ of message $M$. Now, with our last request we can repeat the process with $K_2$, to get the second part of our forged token!

• Finally, just send the message $M$ and its forged token to the verifier to grab the flag!

You will find below my solving script:

from pwn import *

def choice(letter):
	o.recvuntil(b"Quit\n")
	o.sendline(letter.encode())

def get_tag(message):
	choice("t")
	o.recvuntil(b">>> ")
	o.sendline(message.hex())
	o.recvuntil(b"Tag (hex): ")
	return bytes.fromhex(o.recvline().strip().decode())

context.log_level = "debug"

o = remote("challenges1.france-cybersecurity-challenge.fr", 6000)

tag_a = get_tag(b"a")

tag_a1 = tag_a[:16]
tag_a2 = tag_a[16:]

message = b"b" * 16

tag_forged_1 = get_tag(b"a" + b"\x0f" * 15 + xor(message,tag_a1))[:16]
tag_forged_2 = get_tag(b"a" + b"\x0f" * 15 + xor(message,tag_a2))[16:]
tag_forged = tag_forged_1 + tag_forged_2

choice("v")
o.recvuntil(b"Message (hex):")
o.recvuntil(b">>> ")
o.sendline(message.hex())
o.recvuntil(b">>> ")
o.sendline(tag_forged.hex())
print(o.recvline())

o.close()

$in