# Macaron

Macaron was a 200 points cryptanalysis challenge at FCSC 2020.

We were given a script, macaron.py, as well as an ip/port where the script is running as a service.

The script implements a custom MAC algorithm. It allows us to get the MAC of a message or to get the flag by giving a correct MAC corresponding to the message of our choice.

# MAC computation

The custom MAC uses HMAC internally, with two secret keys, `k1`

and `k2`

.
It starts by padding the input to be a multiple of 60.
It then cuts the input in blocks of 30 bytes, and prepend 2 bytes of "block nonce" to each blocks. I will call those 32 bytes block \(B_i\), where \(i\) is the index of the block as well as the value the bloc nonce represent.

It initlize \(ht\) to 0, and loops over the following computations:

- \(d = HMAC(k_1, B_{i-1} || B_i)\)
- \(ht = ht \oplus d\)

The final MAC is \(HMAC(k_2, ht)\). It returns a concatenation of all the block nonces, and the final MAC.

The final MAC looks like \(HMAC(k_2, HMAC(k_1, B_0 || B_1) \oplus ... \oplus HMAC(k_1, B_{n-1} || B_n))\)

# Forging

One can notice that the internal structure of the MAC links the blocks together using a XOR operator, which have some cool properties. One of them is the fact that its self-cancelling, ie \(A \oplus B \oplus B = A\). Another is that its commutative, ie \(A \oplus B = B \oplus A\).

Our goal wil be to get two times the same group of 2 blocks in the middle, so it will cancels out and have the same MAC as the same message without the two blocs.

The only "protection" against this is the "block nonces", but the function that checks if a MAC is valid take the concatenation of all the block nonces as a parameter, so thats not really a problem and i will ignore the block nonces for simplicity in the next lines.

Another thing to consider is that the padding is always added, even if the input length is already a mutiple of 60. That means that the last block of our two messages must be the same.

I have chosen to get the MAC of `AB`

, which becomes `ABPP`

after getting padded.
The forged message will be `ABABAB`

, which is `ABABABPP`

after getting padded.
Lets check out why they have the same MAC:

- MAC
`ABPP`

:$$HMAC(k_2, HMAC(k_1, A||B) \oplus HMAC(k_1, B||P) \oplus HMAC(k_1, P||P))$$ - MAC
`ABABABPP`

:$$HMAC(k_2, HMAC(k_1, A||B) \oplus HMAC(k_1, B||A) \oplus HMAC(k_1, A||B) \oplus HMAC(k_1, B||A) \oplus HMAC(k_1, A||B) \oplus HMAC(k_1, B||P) \oplus HMAC(k_1, P||P))$$As Xor is commutative and self-cancelling, \(HMAC(k_1, A||B) \oplus HMAC(k_1, B||A) \oplus HMAC(k_1, A||B) \oplus HMAC(k_1, B||A)\) is equal to \(0\). So we are left with the same MAC as`ABPP`

.

For the block nonces, we simply have to put the same ones for each \(A\) block and the same of for each \(B\) block. For the two padding blocks, we add the "02" and "03" block nonces, because its the ones they were associated with when creating the first MAC.

Here is the final script:

```
from macaron import *
m = Macaron()
A = b"A"*30
B = b"B"*30
print("First message MAC computation")
tag_hash, tag_nonce = m.tag(A + B)
forged_tag_nonce = (b'\x00\x00' + b'\x00\x01') * 3 + b'\x00\x02' + b'\x00\x03'
forged_tag_hash = tag_hash
forged_message = (A + B) * 3
print("Forged message MAC verification")
print(m.verify(forged_message, (forged_tag_hash, forged_tag_nonce)))
```

and its execution:

```
First message MAC computation
B0 = b'\x00\x00AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\x00\x01BBBBBBBBBBBBBBBBBBBBBBBBBBBBBB'
B1 = b'\x00\x01BBBBBBBBBBBBBBBBBBBBBBBBBBBBBB\x00\x02<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<'
B2 = b'\x00\x02<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\x00\x03<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<'
tag_hash final b'K\x9e\xed\x07\x1b \x1e\xd4\x03\x93\xed\x10_@\xdf\x8d\xf2F\xde6\x04\x96C\xb4\x8d\xe5_\x16\xe9\x8fJ\xef'
Forged message MAC verification
B0 = b'\x00\x00AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\x00\x01BBBBBBBBBBBBBBBBBBBBBBBBBBBBBB'
B1 = b'\x00\x01BBBBBBBBBBBBBBBBBBBBBBBBBBBBBB\x00\x00AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA'
B2 = b'\x00\x00AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\x00\x01BBBBBBBBBBBBBBBBBBBBBBBBBBBBBB'
B3 = b'\x00\x01BBBBBBBBBBBBBBBBBBBBBBBBBBBBBB\x00\x00AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA'
B4 = b'\x00\x00AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA\x00\x01BBBBBBBBBBBBBBBBBBBBBBBBBBBBBB'
B5 = b'\x00\x01BBBBBBBBBBBBBBBBBBBBBBBBBBBBBB\x00\x02<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<'
B6 = b'\x00\x02<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\x00\x03<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<'
True
```

Giving that to the service, and we get our flag :-).