NEWJEANS IS FIVE

crypto 192 solves by william_etotheipi

Challenge

NewJeans is not NewJeans without any one of its members. What is AES without one of its components?

Understanding the cipher

chall.py is a from-scratch AES-128 implementation. Key expansion, AddRoundKey, SubBytes, ShiftRows, MixColumns are all present in name. Except two of them aren't doing anything:

def SubWord(word):
    return word          # should run every byte through the AES S-box

def SubBytes(state):
    return state          # should run every byte through the AES S-box

Both the block cipher's SubBytes step and the key schedule's SubWord step are stubbed out to identity functions. It's meant to be AES, but SubBytes is blank, so it doesn't do anything. AES has five named components: SubBytes, ShiftRows, MixColumns, AddRoundKey, and KeyExpansion. Here the one nonlinear component, the S-box substitution, is missing from both places it's used. Everything left is XOR, a fixed byte permutation, and MixColumns (a fixed matrix multiply over GF(2⁸)), and every one of those is linear over GF(2).

That means the entire 10-round cipher, for a fixed but unknown set of round keys, collapses to:

AES_128(x) = L(x) ⊕ C

where L is a fixed 128×128 linear map over GF(2) and C is a constant. The whole thing is just a big affine cipher over 128-bit blocks, structurally identical to the substitution and Hill ciphers elsewhere in this CTF.

Recovering L without knowing the key

output.txt gives us AES(pt1) and AES(flag) under the real, unknown round keys:

94ae785acdb0d7c919f4893697659c8c   # AES128(pt1), pt1 = "incomprehensible"
58f86ce660590bb05495c0dcd2d4d438   # AES128(flag)

We don't need the real round keys to find L. AddRoundKey is just XOR, so running the same round function with all-zero round keys makes every AddRoundKey a no-op and isolates exactly the linear part, L. Running each of the 128 standard basis vectors (1<<0, 1<<1, and so on) through that zero-keyed cipher gives L one column at a time.

With L known, solve for the constant using the known plaintext: C = AES(pt1) ⊕ L(pt1). Then decrypt the flag: flag = L⁻¹(AES(flag) ⊕ C), where L⁻¹ comes from Gaussian elimination over GF(2).

Solution

ZERO_KEYS = ["0"*32] * 11

def apply_L(x_int):
    x_hex = format(x_int, "032x")
    y_hex = AES_128_noSubBytes(x_hex, ZERO_KEYS)   # same round function, zeroed keys
    return int(y_hex, 16)

def build_matrix():
    return [apply_L(1 << bit) for bit in range(128)]     # L's columns

# invert_gf2(cols) does standard GF(2) Gaussian elimination to get L^-1

pt1 = int("696e636f6d70726568656e7369626c65", 16)
ct1 = int("94ae785acdb0d7c919f4893697659c8c"[:32], 16)
ct2 = int("58f86ce660590bb05495c0dcd2d4d438", 16)

cols = build_matrix()
inv_cols = invert_gf2(cols)

C = ct1 ^ apply_matrix(cols, pt1)
flag_int = apply_matrix(inv_cols, ct2 ^ C)
print(flag_int.to_bytes(16, "big").decode())

Round-trip verified: re-encrypting the recovered flag byte for byte reproduces ct2.