# Writeup for GreyCat Quals 2024/aes

## Introduction

The challenge provides source for both the remote server and their encryption scheme. A quick inspection of the source for the server tells us that to get the flag, we must decrypt a message that they send us that is encrypted with their encryption scheme, and we are allowed to send a single message that will get encrypted and sent back to us.

The source file for the encryption scheme is a little bit long and has a lot of components, and it would be difficult for someone to spot the vulnerability if they weren't already familiar with AES. However, the difference can quickly be found by referencing the original script (with completely normal AES) that it was adapted from, which is in these lines of code:

def mix_single_column(a):
    a[0], a[1], a[2], a[3] = a[1], a[2], a[3], a[0]

But before we get into the implications of this change, we must first understand how AES works.

## How AES Works

AES by design is a block cipher, which means that it splits the plaintext into blocks of a set size (16 bytes in this case) and encrypts the message block-by-block. For each block, AES repeatedly performs a sequence of sub-operations to mutate the "state" of the block, with the initial state being the plaintext and the final state being the ciphertext. There are 4 such sub-operations that each contribute differently to the security of AES. These steps are called AddRoundKey, SubBytes, ShiftRows, and MixColumns. The exact details of each step are not important to our analysis for this challenge, so instead we will go over a simplified overview of each step.

### The Key Schedule and AddRoundKey


AES "expands" the key into 11 "round keys" using something called a key schedule. In each of the 10 rounds, the corresponding round key is added to the block via a simple XOR of the roundkey bits and the state bits during the "AddRoundKey" step.


The AddRoundKey step is obviously necessary for the secret key to matter at all in the encryption. But why do we need separate keys for each round? In short, having repeating keys in a cipher with multiple rounds introduces a vulnerability to an attack called a [slide attack](https://en.wikipedia.org/wiki/Slide_attack). The key schedule of AES removes this vulnerability, and thus helps to obscure the relationship between the key and the ciphertext.

### SubBytes

During this step, each individual byte in the state is substituted based on a reference table called the [S-box](https://en.wikipedia.org/wiki/Rijndael_S-box), similar to how letters are substituted in a monoalphabetic substitution.


It may be confusing why the same S-box is used for every SubBytes operation. However, it is still a very important step as the S-box was specially designed to be as non-linear as possible, protecting against linear cryptanalysis.

### ShiftRows

ShiftRows simply transposes the block by shifting its "rows" as its name suggests. This rather simple step allows for ciphertext bytes to rely on multiple key bytes, increasing security through cryptographic confusion.


### MixColumns

Despite it's seemingly simple name, MixColumns is one of the more convoluted steps. For now we can think of it as a black-box function of an entire column of the state, whose output is another column.


Since it is a function of the entire column, MixColumns is the only step where the following state of a given byte is dependent on state bytes that are not itself. In combination with the ShiftRows step, any given byte's encryption will eventually depend on every other byte. Therefore, this step is very important as it gives AES very strong cryptographic diffusion.

Now we have seen how every step plays their separate role in making AES at a block granularity secure. What happens if one of them is missing?

## The Vulnerability

Lets go back to the lines of code that have changed with this AES implementation.

def mix_single_column(a):
    a[0], a[1], a[2], a[3] = a[1], a[2], a[3], a[0]

Now we know that this is a change to specifically the MixColumns step of AES, where instead of this black-box that mixes around the bytes and outputs a new set of bytes, there is only a simple and predictable transposition of the bytes and nothing else. Based on what we discussed previously about the purpose of MixColumns, this is pretty bad, because now a ciphertext byte is now only a function of the key and a singular plaintext byte, rather than every plaintext byte.

To help visualize this, lets analyze the "lifetime" of a byte through one round of encryption.


During a round, a given byte of the state first gets substituted (predictably), and then it "slides" into a new position (predictably), and then gets added with the corresponding round key byte (less predictably, since the key is secret). We notice that none of these operations rely on any of the other bytes in the state, only at most the value of the byte from its previous state. AES is just this sequence repeated multiple times (with a few minor tweaks), and so if we follow this byte through the entire lifetime of the cipher, we realize that this byte's final value is simply dependent on its initial value, its initial position and the key (which importantly, is the same between the given ciphertext and the encryption oracle), and that it will be in a new position in the ciphertext.

At this point we already should be thinking about a possible solve path. In the meantime, we can try to find which output bytes correspond to which input bytes by making a dummy matrix where the value of each byte is its position, and run it through only ShiftRows and MixColumns in the order that they happen in AES.

def encrypt_block(self, plaintext):
    assert len(plaintext) == 16

    plain_state = bytes2matrix(plaintext)

    for i in range(1, self.n_rounds):
        shift_rows(plain_state)
        mix_columns(plain_state)

    shift_rows(plain_state)

    return matrix2bytes(plain_state)

password = bytes.fromhex("00112233445566778899aabbccddeeff")
key = bytes.fromhex("00000000000000000000000000000000")
AES = AES(key)
states = AES.encrypt(password).hex()

orders = []

for i in range(16):
    orders.append(int(states[2*i],16))
print(orders)
# orders = [5, 14, 7, 12, 9, 2, 11, 0, 13, 6, 15, 4, 1, 10, 3, 8]

The resulting list tells us that the zeroth byte of the ciphertext came from the fifth byte of the plaintext, the first byte came from the fourteenth, etc.

## The Exploit

My initial instinct for solving this challenge was to use the encryption oracle with a known plaintext to reverse engineer the key. After all, without MixColumns, the relationship between a ciphertext byte and a plaintext byte is a lot simpler, since now we do not have to worry about what the other bytes are.

However, I quickly realized that this is still infeasible, even if the relationships are a lot simpler. This is the fault of the key schedule and the S-box. For example, suppose we only have two rounds of this cipher's encryption, and we care about byte $i$ in the plaintext. This byte moves to position $j$ after the first round of ShiftRows + MixColumns and position $k$ after the second round. Then, the relationship between byte $k$ in the final state $F$ and byte $i$ in the initial state $I$ is

$F_k = S(S(I_i \bigoplus K_{0,i}) \bigoplus K_{1,j}) \bigoplus K_{2,k}$

With just two rounds, it is already a pretty ugly equation, and it is also difficult to simplify due to the non-linearity of the S-box. We would also need to match an original key to several round keys, so this approach would be pretty much no better than guessing the key.

Instead lets try something different. Before, we stated that a ciphertext byte is dependent on a single plaintext byte, the position of said plaintext byte, and the key. Lets call this function $C_j = F(b_i, i, k)$ where $b_i$ is the byte value, $k$ is the key, and $i,j$ are indices such that ```orders[j] = i```. But since the key is invariant between both encryptions, we do not have to worry about it, and the function now becomes $C_j = G(b_i, i)$.

The ciphertext is just a collection of function outputs $C$, and we can use the oracle to test which inputs produce these outputs. But how much mileage can we really get out of the oracle if we're only allowed one input?

As it turns out, this cipher has another vulnerability which I have not mentioned yet: its mode of operation.

### A Quick Aside on Block Cipher Modes of Operation

With block ciphers, how an individual block is encrypted is determined solely by the encryption scheme, whether it be AES, 3DES, Blowfish, or another block cipher. How the blocks interact with each other, on the other hand, is determined by a scheme independent of the cipher itself called a "mode of operation". Commonly in CTFs you will come across a mode of operation called cipher blockchaining (CBC) which is relatively secure when used along with AES, where the encrypted version of a previous block is a factor in determining the encrypted version of the next block.

Electronic codebook is the simplest mode of operation, where the blocks do not have any interaction with each other at all; each block is encrypted independently and all the blocks are simply concatenated together to produce the final ciphertext. A quick read of the source code confirms that this is the mode of operation that the server is using. This comes with a lot of security implications, and the one in particular that we care about is that we can concatenate a bunch of inputs together to produce a singular input and the resulting output will be the corresponding outputs of every input. So in reality, we have as many inputs as we want to.

Normally this wouldn't be nearly as big of an issue if the server were using normal AES, since the 16 byte plaintext message space is still too large to brute force search through. But because of the changed MixColumns, we can focus on even smaller units and greatly reduce the domain that we will be searching through. With our function $G(b_i, i)$, there are only 16 possible indices that $i$ can be since blocks only hold 16 bytes, and there are 256 possible values for $b_i$, which means we will only need 4096 inputs to completely reveal the function $G$. After that, we can look at the value of any ciphertext byte at index j and find a $b_i$ and $i$ that satisfy both $C_j = G(b_i, i)$ and ```orders[j] = i```.

We can now get to coding!

### Putting Together the Solve

We can generate the payload of all the inputs we need by stringing together blocks of all the same character for each character in increasing order.

for i in range(256):
    payload += hex(i)[2:].zfill(2) * 16

r = remote("challs.nusgreyhats.org", 35100)
r.sendline(payload.encode())

After fetching the encrypted password and the output from the oracle, we can search the oracle output for a block that matches a certain byte of the password. The index of that block relative to all other blocks will determine the plaintext byte, since each block contains the same character. After finding the correct byte value, we will need to place it in the correct position in the plaintext password, so we reference the ```order``` list that we generated previously.

output = "a really really long hex string, just trust me that its supposed to be here"
chunks, chunk_size = len(output), len(output)//257
stuff = [ output[i:i+chunk_size] for i in range(0, chunks, chunk_size) ]

password = "df03fb8e44181643eeeb6dc367b16e0bf71163e8d599f65ccb90ad3f4f03d78f"
answer = ["" for _ in range(16)]
# we only need to care about the first block of the password
# since the second one is just padding
for j in range(16):
    substr = password[2*j:2*(j+1)]
    for i in range(256):
        if substr == stuff[i][2*j:2*(j+1)]:
            answer[orders[j]] = hex(i)[2:].zfill(2)
            break
answer = "".join(answer)
print(answer)

We can send our answer to the server and get the flag.