Crypto challenge from ECW 2023

Cryptoflow

I won’t go into much details in the reverse stuff, you can always ask on the ECW discord or me directly for more details.

The problem

We are given the server source, which is a binary, a little reverse for fun.

The main first load the key, the flag and sends the flag encrypted with aes. We then have a while loop :

• empty the round keys and message buffer
• read the user message
• send backthe message encrypted

At this point everything is correct, so we’ll investigate the function that reads the user message, which is the only input.

int GetMessage(void)

{
  long lVar1;
  char *__ptr;
  int iVar2;
  undefined8 *puVar3;
  byte bVar4;
  
  bVar4 = 0;
  puts("Enter the cleartext (at most 224 character), I will give you the ciphertext back.");
  iVar2 = 0;
  __ptr = last_message;
  while( true ) {
    fread(__ptr,1,1,stdin);
    if (*__ptr == '\n') break;
    iVar2 = iVar2 + 1;
    __ptr = __ptr + 1;
  }
  iVar2 = iVar2 + 1;
  if (mycanary != -6144092017055948237) {
    // not happy and empty the message buffer
  return iVar2

We can see that the loop reading the user input stops only when we send a newline, so we can write more than the buffer created (it says we have to stay under 224 characters but we are hackers).

The solution

We can use that to overwrite data after our buffer but what do we got. Scrolling on ghidra or ida, we can find a buffer which seems to be the AES sbox (confirmed by checking the bytes with the AES specification).

The address of the message buffer is 104020 and the address of the sbox is 104120, suspiciously very close. Good we know we can overwrite the sbox, but what can we do with that ?

The first idea is to make it linear, meaning that we can find a linear relation between the inputs and outputs. A good example is sbox = list(range(256)) where every input gives itself. That modification makes AES linear, tha means that the output bits are a linear combination (addition mod 2 or xor) of the input bits and the key bits, so setting up equations with symbolic variables in sagemath allows to recover the key bits (very good explanation in this post). I’m willingly going fast on this because this is not the way I did it, because the newline stops the input and apparently this was to annoying for me to change the sbox in two times.

For anyone who is interested in the symbolic variables in sagemath, I use them in my solution for Straightline.

So what did I do ? As every ctf player I asked myself what would happen if the sbox was filled with 0’s, turns out this is a big problem because of how aes works:

- Initial round key addition:
    1. AddRoundKey
- 9, 11 or 13 rounds:
    1. SubBytes
    2. ShiftRows
    3. MixColumns
    4. AddRoundKey
- Final round (making 10, 12 or 14 rounds in total):
    1. SubBytes
    2. ShiftRows
    3. AddRoundKey

If we look closely at the last round, we can see that the last operation is a xor with the last round key. The 2 operations before are a ShiftRows with just shift the rows around and a SubBytes which is the use of the sbox.

Thanks to our modification, every bytes after the SubBytes operation are just 0’s, so our final result is the last round key, in clear.

Can we recover the master key with the final round key ? Yes, the round keys are only xor of previous round keys and some sbox thingy. Because it’s a ctf we’ll stole the code from this github repository.

Solve script :

from pwn import remote

r = remote("instances.challenge-ecw.fr",int(35746))

r.recvlines(2)

enc = bytes.fromhex(r.recvline().decode())

r.recvlines(2)

r.sendline(b"\x00"*16+b"c"*(224-16)+bytes.fromhex("33221100DDCCBBAA")+b"a"*24+b"\x00"*256)

print(r.recvlines(1))

cri = bytes.fromhex(r.recvline().decode())

from typing import List
from functools import reduce

sbox = # normal sbox

inv_sbox = # normal inv_sbox

rcon = [int(x).to_bytes(4, 'little') for x in [ 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1B, 0x36, ]]

def xor_bytes(*arg: bytes) -> bytes:
    assert len({len(x) for x in arg}) == 1 # all args must have the same length
    xor_fun = lambda x, y : x ^ y
    return bytes(reduce(xor_fun, byt3s) for byt3s in zip(*arg))

def rot_word(word: bytes) -> bytes:
    '''
    apply the RotWord transformation to a bytes object of length 4
    '''
    assert len(word) == 4
    return bytes((word[(i + 1) % 4] for i in range(4)))

def inv_rot_word(word: bytes) -> bytes:
    '''
    apply the inverse of the RotWord transformation to a bytes object of length 4
    '''
    assert len(word) == 4
    return bytes((word[(i - 1) % 4] for i in range(4)))

def sub_word(word: bytes) -> bytes:
    '''
    apply the AES S-Box to each of the bytes of the 4-byte word
    '''
    assert len(word) == 4
    return bytes((sbox[w] for w in word))

def inv_sub_word(word: bytes) -> bytes:
    '''
    apply the inverse of the AES S-Box to each of the bytes of the 4-byte word
    '''
    assert len(word) == 4
    return bytes((inv_sbox[w] for w in word))


def reverse_key_schedule(round_key: bytes, aes_round: int):
    '''
    reverse the AES-128 key schedule, using a single round_key.
    '''
    assert len(round_key) * 8 == 128
    for i in range(aes_round - 1, -1, -1):
        a2 = round_key[0:4]
        b2 = round_key[4:8]
        c2 = round_key[8:12]
        d2 = round_key[12:16]

        d1 = xor_bytes(d2, c2)
        c1 = xor_bytes(c2, b2)
        b1 = xor_bytes(b2, a2)
        a1 = xor_bytes(a2, rot_word(sub_word(d1)), rcon[i])

        round_key = a1 + b1 + c1 + d1

    return round_key

key = reverse_key_schedule(cri,10)

from Crypto.Cipher import AES

print(AES.new(key,AES.MODE_ECB).decrypt(enc))

Flag : ECW{Whyd0yOuMod1fyMySb0xDude??!}

Shadowwws