DCTF 2022 MACdonalds 1 and 2 Solutions

Preface

In the writeup I assume that readers are familiar with basic cryptographic terms such as AES, modes of encryption, MAC, etc. Also, I assume that readers can read and understand the servers’ source code. So I will only concentrate on the high-level parts of the solution. If you don’t understand some parts of the writeup feel free to ask questions in the comments.

Also, I accept requests for future articles. If you can’t find “detailed enough” or “simple enough” resources on a particular topic, you can leave your requests in the comments and I will try to cover them in my future publications.

Similarities

As you might have guessed from tasks names both tasks are slightly different implementations of the same idea. Now, before we get to the solution it is appropriate to point out what both tasks are about. The description below is fair for both tasks.

For the challenge, we are given the server network address and its source code — a pretty basic kit for server-based tasks. The server allows us to perform two types of action:

1. tag — calculate MAC for the given message. We can perform this task only once.
2. verify — verify that the given message has the given tag. Here if verification is successful and the message we provided really has provided tag, then we will get the flag. The trick is that we cannot verify the same message we used to create a tag.

The attack should be something like this:

• Generate tag for some message
• Using generated tag forge tag for new message.

Now, in an ideal world, we could not have performed such an attack because we could only generate a valid tag for some message only knowing the secret key (which we don’t know). However, MAC generation implementations in both challenges have flaws that will allow us to forge the tag and get the flag.

MACdonalds 1 [200]

Server’s source code for the challenge:

The code above is pretty straightforward: for tag action, we must provide a message and the server will send back generated tag; for verify action, we must provide a message and a tag and the server checks if tag(message) == tag.

The only interesting function here is tag(). It performs some CBC-like encryption, although it doesn’t store intermediate encrypted blocks but just use them as IV for the next blocks. The function scheme looks like this:

Initial IV is all zeros, which makes life simpler for us, however, that is not really important.

So how do we break the scheme? The idea is pretty simple. We first generate a tag for some message a (for simplicity let’s use just one block). The server will give us some tag t. Now we know that the scheme above applied to a returns t.

Now we add new block b to message a. The scheme changes to the following:

The problem is that we cannot calculate t' because we don’t know the secret key. However, we can change b to whatever we like. I say, let’s change b to a ^ t. Then, b ^ t = a ^ t ^ t, and the scheme magically transforms to the following:

Here you have to remember that IV is set to zeros so a ^ IV = a. And as simple as that now we have two messages a and a + a ^ t having the same tag t. Let’s implement the attack.

To make my life simpler I will use a = 0, then a ^ t will just be equal to t. There was something wrong with the server, so automation didn’t work well even with the template code given by organizers so instead, I made the following code for the manual attack:

And the attack itself is on the screen

MACdonalds 2 [300]

The second challenge introduces some changes to the first one:

1. Now we can generate tag only for a one-block message.
2. The server uses random IV
3. The server uses a two-part tag which consists of iv and ct.
4. During verification, server checks not only that the new message is not equal to the old message but also that the new message does not contain the old message as its substring. This means that our old trick with a and a + a ^ t will not pass this check. This forces us to generate a completely different message.

The tag generation scheme didn’t really change, but now it is limited to one block:

Note that in the previous challenge we had two parts that we could change: message and tag. Now, we have three parts: message, iv, and ct. However, there is nothing we can do about ct it MUST stay the same (unless we find a way to break AES encryption). We also MUST change the message. This leaves us with the following task: change message and iv so that the scheme above still returns ct.

All right, let’s think. First of all, we have to change the message. Say we generated tag for message a. Now we decide to use some other message b. We will also change iv to some new value iv', although we didn’t decide what value we will use. Note, that to receive ct from AES encryption we need a ^ iv to be equal to b ^ iv':

a ^ iv == b ^ iv'

We have already picked value b, so we have a simple equation with one variable — iv'. We solve it to get:

iv' = a ^ iv ^ b

And as simple as that, we have broken the second challenge. Now, for implementation I again will use a = 0 , therefore iv' = iv ^ b. The auxiliary code for the attack:

And the attack itself: