Writeup by Lcram33 for SCator

Table of contents

This challenges uses a simplified AES implementation. It works on 16 byte blocks, and has 11 rounds. The key is 16 bytes long, and randomly generated. Although the random library is used, which is not cryptographically secure, we cannot recover the key by guessing the seed.

We are given :

The encrypted flag (encrypted with the standard AES library, not the simplified one)
10 “plaintext” messages (10 random blocks)
Their “leakage”, which is the Hamming weight of the state after the initial incomplete round (addRoundKey and subBytes)

Hamming weight is the number of bits that are 1 in a binary representation of a number. For example, the Hamming weight of 5 (binary 101) is 2.

What can we do with all of this ?

The first step is realizing that in the initial round, the key derived from the key scheduling algorithm is the original key, e.g. keys[0] = key.
We can therefore “go backwards” for each operation and recover the key byte by byte.

Note however that the Hamming weight is not reversible. But since we are working on one byte, this can easly brute-forced.

We can list all the bytes having only $l_i$ bits, where $l_i$ is the Hamming weight of $S(m_{i,j} \oplus k_i)$ ($i$ being the byte index, and $j$ being the message index).
Then, apply the reverse SBOX $S^{-1}$ to all the candidates, and XOR the result with the corresponding byte of the message $m_{i,j}$, to get a list of the possible bytes for $k_i$.

Doing this for all the messages $j$, we should find the same key byte in all the lists, which is the correct key byte. So we can do some intersection of the lists to find the key byte at each step:

key_bytes_list = list()
for i in range(16):
    candidates = SBOX.copy() # all the possible bytes are in this list so let's reuse it :)
    for j in range(len(messages)):
        l = leakages[j][i]
        m = messages[j][i]
        new_candidates = [SBOX_INV[x] ^ m for x in SBOX if HW(x) == l]
        candidates = list(x for x in candidates if x in new_candidates)

        if len(candidates) == 1:
            break

    if len(candidates) != 1:
        print("Too many candidates for byte", i)
        print(candidates)
        exit(1)

All we have to do next is decrypt the flag with the recovered key.

Flag

FCSC{56e92f08e3516ad9375a260b851eb98a836ef549288de79323e9e0d6772a0bb3}

Solution code

import json
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad

from scator import SBOX # avoid redefining SBOX


def HW(x):
    res = 0
    while x > 0:
        x &= x-1
        res += 1
    return res


SBOX_INV = [SBOX.index(x) for x in range(256)]


# === Main program ===

with open("scator.json", "r") as f:
    data = json.load(f)

c = bytes.fromhex(data["encrypted_flag"])
messages = [bytes.fromhex(m) for m in data["messages"]]
leakages = [bytes.fromhex(l) for l in data["leakages"]]

key_bytes_list = list()
for i in range(16):
    candidates = SBOX.copy() # all the possible bytes are in this list so let's reuse it :)
    for j in range(len(messages)):
        l = leakages[j][i]
        m = messages[j][i]
        new_candidates = [SBOX_INV[x] ^ m for x in SBOX if HW(x) == l]
        candidates = list(x for x in candidates if x in new_candidates)

        if len(candidates) == 1:
            break

    if len(candidates) != 1:
        print("Too many candidates for byte", i)
        print(candidates)
        exit(1)
    
    key_bytes_list.append(candidates[0])
    # print(f"Key byte {i} = {candidates[0]}") # debug


key = bytes(key_bytes_list)
iv = b"\x00" * 16
d = AES.new(key, AES.MODE_CBC, iv).decrypt(c)

flag = unpad(d, 16).decode()

print(flag)