BITSCTF 2026 - Aliens Eat Snacks - Cryptography Writeup

Category: Cryptography
Flag: BITSCTF{7h3_qu1ck_br0wn_f0x_jump5_0v3r_7h3_l4zy_d0g}

Challenge Description#

Custom AES-like implementation with only 4 rounds (standard AES-128 has 10). Given files: aes.py, output.txt, README.md.

Key information from output.txt:

key_hint: 26ab77cadcca0ed41b03c8f2e5 (13 of 16 bytes leaked)
encrypted_flag: 8e70387dc377a09cbc721debe27c468157b027e3e63fe02560506f70b3c72ca19130ae59c6eef47b734bb0147424ec936fc91dc658d15dee0b69a2dc24a78c44
num_samples: 1000 known plaintext/ciphertext pairs

Analysis#

The challenge leaks 13 out of 16 key bytes, leaving only 3 unknown bytes to brute-force:

$2^{24} = 16,777,216$

This is fully brute-forceable with optimized C + OpenMP.

Solution#

Parse key_hint as first 13 bytes of the AES key. Brute-force all possible values for last 3 bytes. For each candidate key, encrypt sample plaintext #1 and compare with ciphertext #1, then encrypt sample plaintext #2 and compare. If both match, key is recovered.

File used: bruteforce_aes.c

#include <stdint.h>
#include <stdio.h>
#include <string.h>

#ifdef _OPENMP
#include <omp.h>
#endif

static uint8_t SBOX[256];
static uint8_t MUL2[256], MUL3[256];

static inline uint8_t gf_mult(uint8_t a, uint8_t b) {
    uint8_t result = 0;
    for (int i = 0; i < 8; i++) {
        if (b & 1) result ^= a;
        uint8_t hi = a & 0x80;
        a <<= 1;
        if (hi) a ^= 0x1B;
        b >>= 1;
    }
    return result;
}

static uint8_t gf_pow(uint8_t base, uint16_t exp) {
    uint8_t result = 1;
    while (exp) {
        if (exp & 1) result = gf_mult(result, base);
        base = gf_mult(base, base);
        exp >>= 1;
    }
    return result;
}

static void init_tables(void) {
    for (int i = 0; i < 256; i++) SBOX[i] = gf_pow((uint8_t)i, 23) ^ 0x63;
    for (int i = 0; i < 256; i++) {
        MUL2[i] = gf_mult(0x02, (uint8_t)i);
        MUL3[i] = gf_mult(0x03, (uint8_t)i);
    }
}

static const uint8_t RCON[10] = {0x01,0x02,0x04,0x08,0x10,0x20,0x40,0x80,0x1B,0x36};

static void key_expansion_4round(const uint8_t key[16], uint8_t round_keys[80]) {
    uint8_t words[20][4];
    for (int i = 0; i < 4; i++) {
        words[i][0] = key[4*i+0];
        words[i][1] = key[4*i+1];
        words[i][2] = key[4*i+2];
        words[i][3] = key[4*i+3];
    }
    for (int i = 4; i < 20; i++) {
        uint8_t temp[4] = {words[i-1][0], words[i-1][1], words[i-1][2], words[i-1][3]};
        if (i % 4 == 0) {
            uint8_t t = temp[0];
            temp[0] = temp[1]; temp[1] = temp[2]; temp[2] = temp[3]; temp[3] = t;
            temp[0] = SBOX[temp[0]]; temp[1] = SBOX[temp[1]]; temp[2] = SBOX[temp[2]]; temp[3] = SBOX[temp[3]];
            temp[0] ^= RCON[(i/4)-1];
        }
        words[i][0] = words[i-4][0] ^ temp[0];
        words[i][1] = words[i-4][1] ^ temp[1];
        words[i][2] = words[i-4][2] ^ temp[2];
        words[i][3] = words[i-4][3] ^ temp[3];
    }
    for (int r = 0; r <= 4; r++) {
        for (int i = 0; i < 4; i++) {
            round_keys[r*16 + i*4 + 0] = words[r*4+i][0];
            round_keys[r*16 + i*4 + 1] = words[r*4+i][1];
            round_keys[r*16 + i*4 + 2] = words[r*4+i][2];
            round_keys[r*16 + i*4 + 3] = words[r*4+i][3];
        }
    }
}

static inline void add_round_key(uint8_t s[16], const uint8_t rk[16]) { for (int i=0;i<16;i++) s[i]^=rk[i]; }
static inline void sub_bytes(uint8_t s[16]) { for (int i=0;i<16;i++) s[i]=SBOX[s[i]]; }

static inline void shift_rows(uint8_t s[16]) {
    uint8_t t[16];
    for (int r=0;r<4;r++) for (int c=0;c<4;c++) t[r+4*c] = s[r+4*((c+r)&3)];
    memcpy(s,t,16);
}

static inline void mix_columns(uint8_t s[16]) {
    uint8_t t[16];
    for (int c=0;c<4;c++) {
        uint8_t s0=s[0+4*c], s1=s[1+4*c], s2=s[2+4*c], s3=s[3+4*c];
        t[0+4*c] = MUL2[s0]^MUL3[s1]^s2^s3;
        t[1+4*c] = s0^MUL2[s1]^MUL3[s2]^s3;
        t[2+4*c] = s0^s1^MUL2[s2]^MUL3[s3];
        t[3+4*c] = MUL3[s0]^s1^s2^MUL2[s3];
    }
    memcpy(s,t,16);
}

static void encrypt_block(const uint8_t rk[80], const uint8_t pt[16], uint8_t out[16]) {
    uint8_t s[16]; memcpy(s,pt,16);
    add_round_key(s, rk + 0);
    for (int r=1;r<4;r++) {
        sub_bytes(s); shift_rows(s); mix_columns(s); add_round_key(s, rk + 16*r);
    }
    sub_bytes(s); shift_rows(s); add_round_key(s, rk + 64);
    memcpy(out,s,16);
}

static int hex_to_bytes(const char *hex, uint8_t *out, size_t out_len) {
    if (strlen(hex) != out_len*2) return 0;
    for (size_t i=0;i<out_len;i++) {
        unsigned v; if (sscanf(hex+2*i, "%2x", &v) != 1) return 0;
        out[i] = (uint8_t)v;
    }
    return 1;
}

int main(void) {
    init_tables();
    const char *key_hint_hex = "26ab77cadcca0ed41b03c8f2e5";
    const char *pt1_hex = "376f73334dc9db2a4d20734c0783ac69";
    const char *ct1_hex = "9070f81f4de789663820e8924924732b";
    const char *pt2_hex = "a4da3590273d7b33b2a4e73210c38a05";
    const char *ct2_hex = "f501ed98c671cf1a23e5c028504d2603";

    uint8_t key_prefix[13], pt1[16], ct1[16], pt2[16], ct2[16];
    if (!hex_to_bytes(key_hint_hex, key_prefix, 13) ||
        !hex_to_bytes(pt1_hex, pt1, 16) ||
        !hex_to_bytes(ct1_hex, ct1, 16) ||
        !hex_to_bytes(pt2_hex, pt2, 16) ||
        !hex_to_bytes(ct2_hex, ct2, 16)) {
        return 1;
    }

    volatile int found = 0;
    uint8_t found_key[16] = {0};

    #pragma omp parallel
    {
        uint8_t key[16], rk[80], out[16];
        memcpy(key, key_prefix, 13);

        #pragma omp for schedule(dynamic, 4096)
        for (uint32_t s = 0; s <= 0xFFFFFF; s++) {
            if (found) continue;
            key[13] = (uint8_t)(s >> 16);
            key[14] = (uint8_t)(s >> 8);
            key[15] = (uint8_t)(s);

            key_expansion_4round(key, rk);
            encrypt_block(rk, pt1, out);
            if (memcmp(out, ct1, 16) != 0) continue;
            encrypt_block(rk, pt2, out);
            if (memcmp(out, ct2, 16) != 0) continue;

            #pragma omp critical
            {
                if (!found) {
                    found = 1;
                    memcpy(found_key, key, 16);
                }
            }
        }
    }

    if (!found) return 2;
    printf("KEY=");
    for (int i = 0; i < 16; i++) printf("%02x", found_key[i]);
    printf("\n");
    return 0;
}

Compile and run:

gcc -O3 -march=native -fopenmp bruteforce_aes.c -o bruteforce_aes
./bruteforce_aes

Output:

KEY=26ab77cadcca0ed41b03c8f2e5cdec0c

Use recovered key to decrypt encrypted_flag block-by-block:

#!/usr/bin/env python3
from aes import AES

key = bytes.fromhex("26ab77cadcca0ed41b03c8f2e5cdec0c")
encrypted_flag = bytes.fromhex(
    "8e70387dc377a09cbc721debe27c468157b027e3e63fe02560506f70b3c72ca1"
    "9130ae59c6eef47b734bb0147424ec936fc91dc658d15dee0b69a2dc24a78c44"
)

cipher = AES(key)
plaintext = b"".join(cipher.decrypt(encrypted_flag[i:i+16]) for i in range(0, len(encrypted_flag), 16))

# PKCS#7 unpad
pad = plaintext[-1]
plaintext = plaintext[:-pad]

print(plaintext.decode())

Output:

BITSCTF{7h3_qu1ck_br0wn_f0x_jump5_0v3r_7h3_l4zy_d0g}