Dragon CTF 2021, Baby MAC Writeup

For challenge we are provided with the server network address and its source code. Consider the source code:

Here is the essentials of the source:

• There are two operations it can perform: sign and verify
• sign operation takes some hex string data as an input, calculates its signature and returns the signature with the data back. data cannot contain gimme flag in it.
• verify takes the hex string data as an input, takes first 16 bytes of the data as a signature, calculates the signature with sign for other bytes and checks if provided signature equals to the calculated one
• If we provide provide valid signature for string that contains gimme flag we receive flag

Let’s consider how the signature is calculated

sign function takes data and key parameters as input. The key value is randomly generated on every new connection to server so we don’t know it. data is padded with pad function until its length is multiple by 16. Next, data is being split into blocks of length 16. Each block then runs through the loop:

• XOR with current mac
• encrypt mac with AES

In the end mac is encrypted once again and returned as a signature. Schematically this looks as follows

Now, how do we calculate the signature for gimme flag not knowing the key. We can use server to sign any arbitrary string we want, but not those that contain gimme flag.

There are few observations to make. First, what if we try to sign empty message? Then sign function will pad so the signed message would look like this 10101010101010101010101010101010 (that’s how pad function works). And after that, this one block will be XORed with initial mac, which is 00000000000000000000000000000000 and twice encrypted with AES

Second, using signature for empty string we can create make server generate signature for gimme flag with it thinking it signs other value. How is that? Well, consider the signature for gimme flag. This data will be padded with 0x06 byte to get value gimme flag\x06\x06\x06\x06\x06\x06. mac initially contains 16 zeroes. So schematically

So basically, it is just twice encrypted gimme flag\x06\x06…\x06 , because of XORing with 00…00. Now consider the general scheme again

What if Mn XORed with mac equals to gimme flag? Well, then we get the valid signature of gimme flag isn’t it? Because still that just twice encrypted gimme flag. So to get valid signature of gimme flag our data doesn’t have to contain gimme flag at all. It is just sufficient that last block of data XORed with precalculated by that moment mac equals to some string containing gimme flag. We can construct such a data but we will have to predict mac value.

But the mac is generated by AES encryption, so it is pretty random, how can we predict what value will it have at any point? This is where we can use the empty string signature. Empty string signature is just twice encrypted 10...10 string. If we set first block of data to 10...10 and the second block of data to 00...00, then at third iteration mac value will be the exact value of empty string signature:

Now if we set M3 to emptyStringSignature ^ gimme flag , then after XOR at third iteration we get gimme flag and than it is twice encrypted. So this signature will be exactly the same as the signature for gimme flag string, but our data does not contain any gimme flag, so we can make server sign it.

The following code is the exploit: