ECB Lasagna — b01lers CTF 2026

Description

I think I dropped something into the lasagna, can you untangle it for me?

We are given chall.py and output.txt (base64 of a 360-byte blob).

import base64
from Crypto.Cipher import AES
from Crypto.Util.strxor import strxor

flag = open("../flag.txt").read().strip()

s = ""
for c in flag:
    s += c * 2
flag = s

cipher = AES.new(b"lasagna!" * 2, AES.MODE_ECB)
result = b"\0" * len(flag)

for i in range(len(result)):
    ciphertext = cipher.encrypt(flag[i].encode() * 16)
    layer = b"\0" * i + ciphertext
    if len(layer) < len(result):
        layer += b"\0" * (len(result) - len(layer))
    if len(layer) > len(result):
        layer = layer[len(result):] + layer[len(layer)-len(result):len(result)]
    result = strxor(result, layer)

print(base64.b64encode(result).decode())

Goal: recover the 180-character plaintext flag from the 360-byte ciphertext.

Reconnaissance

A few facts drop out immediately:

• The AES key b"lasagna!" * 2 is constant and known, so AES-ECB acts as a fixed 1-byte → 16-byte lookup table: D[c] = AES_ECB(bytes([c]) * 16) for c ∈ [0, 256).
• The flag is first character-doubled: if the original flag is m[0..179], the encrypted buffer uses f[2p] = f[2p+1] = m[p], so L = len(f) = 360.
• For each position i, the code drops D[f[i]] starting at offset i in a buffer of length L. The tail-reordering branch (layer[len(result):] + ...) is precisely a cyclic wrap-around mod L.
• All 360 "layers" are XOR-accumulated into the output.

Putting it together, the output byte at position j is:

result[j] = XOR_{k=0..15} D[f[(j - k) mod L]][k]

Each layer i contributes D[f[i]][k] to position (i+k) mod L, which by a change of variable is the formula above.

Math — collapsing by doubling

This is where the plaintext doubling becomes a fatal structural weakness.

Take any odd j = 2p + 15 with 15 ≤ j < L. The 16 indices j, j-1, ..., j-15 split into 8 consecutive pairs:

• k = 2i → f[j - 2i] = f[2(p+7-i) + 1] = m[p+7-i] (odd index → duplicate)
• k = 2i+1 → f[j - 2i-1] = f[2(p+7-i)] = m[p+7-i] (even index → original)

Both elements of each pair reference the same original character m[p+7-i]. So if we define

E_i[c] = D[c][2i] XOR D[c][2i+1]       for i in 0..7, c in 0..255

the equation collapses from 16 terms to 8:

result[2p + 15] = E_0[m[p+7]] XOR E_1[m[p+6]] XOR ... XOR E_7[m[p]]

This is a linear convolutional filter over the plaintext alphabet with an 8-tap window. Given 7 consecutive known characters m[p..p+6] we solve for m[p+7] in one step:

E_0[m[p+7]] = result[2p+15] XOR E_1[m[p+6]] XOR E_2[m[p+5]] XOR ... XOR E_7[m[p]]

and then look up which printable byte c satisfies E_0[c] = <that byte>.

Tiny 2-char sanity example

Imagine m = "AB" so f = "AABB" and L = 4. Layer i places D[f[i]] cyclically starting at position i. For odd j = 2p+15 we'd need L ≥ 16 so this toy case is only illustrative, but the pair-aliasing logic holds: any window of 16 consecutive positions of f starting at an odd offset covers each m[q] exactly twice, at byte lanes (2i, 2i+1) of D[m[q]]. XORing those two lanes is exactly what E_i is.

Even-j equations give a free validator

For even j = 2p + 14 the window is shifted by one, so both endpoints are unpaired and the middle 14 positions still pair cleanly:

result[2p + 14] = D[m[p+7]][0] XOR D[m[p-1]][15] XOR XOR_{i=1..7} (D[m[p+7-i]][2i-1] XOR D[m[p+7-i]][2i])

Since we already know m[p-1..p+6] at the time we decide m[p+7], this is a linear equation in D[m[p+7]][0] — a perfect filter that throws out almost all spurious candidates.

Solution

1. Precompute D[c] and E_i[c] for all 256 byte values.
2. Guess the flag prefix bctf{ (5 chars). We need 7 chars to bootstrap the recurrence, so brute-force the next 2 characters over printable ASCII (95^2 = 9025 starts).
3. For each start, unroll the odd-j recurrence for p = 0, 1, ..., 172 to recover m[7], m[8], ..., m[179]. Keep only printable E_0 pre-images.
4. Use the even-j equation to further filter the candidate list at each step (usually reduces to one candidate).
5. Backtrack if a position has no printable candidate. Only the correct 2-char bootstrap produces a fully printable 180-char flag.

Key excerpts from solve.py

Precomputation:

KEY = b"lasagna!" * 2
CIPHER = AES.new(KEY, AES.MODE_ECB)

# D[c] = AES_ECB_encrypt(c * 16)
D = [CIPHER.encrypt(bytes([c]) * 16) for c in range(256)]

# Pair-XOR filters (8 lanes, one per i in 0..7)
E = [[D[c][2*i] ^ D[c][2*i+1] for c in range(256)] for i in range(8)]

One-step inversion of the odd-j equation:

def candidates_for_next(m, output):
    """Given m[0..len(m)-1] known with len(m) >= 7, find candidates for m[len(m)]."""
    n = len(m)
    p = n - 7
    j = 2 * p + 15
    if j >= L:
        return []
    # result[j] = E_0[m[p+7]] XOR E_1[m[p+6]] XOR ... XOR E_7[m[p]]
    val = output[j]
    for i in range(1, 8):
        val ^= E[i][m[p + 7 - i]]
    return [c for c in PRINTABLE if E[0][c] == val]

Even-j validator used to prune candidates:

def verify_even(m, p, output):
    j = 2 * p + 14
    if j >= L or j < 15 or p < 1:
        return True
    val = D[m[p+7]][0] ^ D[m[p-1]][15]
    for i in range(1, 8):
        val ^= D[m[p+7-i]][2*i - 1]
        val ^= D[m[p+7-i]][2*i]
    return val == output[j]

Main loop (simplified): start from prefix = b"bctf{" + c1 + c2, extend with candidates_for_next filtered by the even-j constraint, backtrack on dead ends. With the correct c1='y', c2='0' the recurrence marches through all 180 characters with essentially no branching.

Verification

Re-running chall.py with the recovered flag reproduces output.txt exactly.

Takeaways

• ECB with a known key is not encryption, it's a lookup table. If you see AES-ECB with a hard-coded key encrypting single-byte-repeated plaintexts, treat AES_ECB(c*16) as a 256-entry table and reason linearly from there.
• Duplication symmetries collapse XOR sums. Any construction that doubles, triples or otherwise repeats plaintext elements creates index aliasing. Summing the ciphertext contributions of aliased positions reduces the number of independent unknowns per equation — often turning "impossible" convolutions into small alphabet recurrences.
• Shift-and-XOR = convolution. A ciphertext that is XOR_i D[f[i]] << i (with possible cyclic wrap) is a convolution over GF(2)^8. If the "filter" D[·] is invertible or injective on the expected alphabet, the plaintext can be recovered with a linear decoder plus a short bootstrap.
• A known prefix is usually enough. Here we only needed 5 known chars (bctf{) and a tiny 95^2 brute-force; any constraint that fixes the first 7 chars fully determines the rest.