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: