THE GARDEN

the-67th-line

Updated 19 Sep 2026

• •

  Attribution

  • •

    Solved by rn. AI-assisted solve; the original assistance links are preserved below.

• •

  What it asked

  • •

    Follow a 105-symbol social-media clue to the attached archive, recover a $12\times20$-bit cipher key from chosen integral sets and known plaintext, then authenticate and decrypt sealed.json.

• •

  Clue

  • •

    Map the 105 O/B symbols from oldest to newest into five-bit groups. The readable modern-Bacon interpretation is RISTEK?LINK?ASTERGATE; the out-of-alphabet values act as separators, leading to ristek.link/astergate.

  • •

    The archive contains chall.py, records.json, records.bin, and sealed.json. The clue locates the data; it is not part of the key-recovery proof.

• •

  Math and approach

  • •

    Each byte has a 20-bit key split into a 12-bit matrix selector $u$ and an 8-bit final XOR value $l$. The three round keys depend only on the 12-bit upper parts; the lower byte appears only in the final transform.

  • •

    A complete affine input set has dimension $9$ and therefore $2^9=512$ elements. Before the final quadratic layer, every coordinate has algebraic degree at most $8$, so its XOR over the entire 9-dimensional set is zero.

  • •

    For a guessed $(u,l)$, partially invert the final byte: $s=q^{-1}(M_u^{-1}(c\oplus l))$. XOR these values over every complete set. Wrong upper keys are rejected by the zero-sum tests.

  • •

    The integral test leaves 16 lower-byte variants for a correct upper key because of the Feistel structure. Recover the exact lower byte from a known plaintext block at its recorded offset.

  • •

    Rebuild the full key and open sealed.json. The HMAC check is the final key validation. The decrypted value is 32 raw bytes and is formatted as COMPFEST18{hex}, not interpreted as an ASCII flag.

  • •

    The PDF’s final call uses an undefined sealed_ol_keys variable. The corrected call is open_sealed(sealed_obj, final_keys).

• •

  Solution

  • •

    from collections import Counter
    from pathlib import Path
    import json
    
    # Copy these exact cipher primitives from chall.py / the reviewed solve:
    # matrix, invert_matrix, apply_rows, invert_q, round_key, g, q,
    # permute, open_sealed, xor_all.
    N = 12
    
    def odd_values(column):
        return [v for v, count in Counter(column).items() if count & 1]
    
    def recover_upper(active_sets, byte_index):
        columns = []
        for blocks in active_sets:
            values = odd_values([block[byte_index] for block in blocks])
            if values:
                columns.append(values)
            if len(columns) == 5:
                break
        candidates = []
        for upper in range(1 << 12):
            inv = invert_matrix(matrix(upper))
            table = [invert_q(apply_rows(inv, x)) for x in range(256)]
            if any(all(xor_all(table[v ^ low] for v in col) == 0
                       for col in columns) for low in range(256)):
                candidates.append(upper)
        return candidates
    
    info = json.loads(Path('records.json').read_text())
    raw = Path('records.bin').read_bytes()
    sets = []
    for meta in info['sets']:
        if meta.get('d', 0) < 9 or meta['count'] != 512:
            continue
        start = meta['offset'] * N
        blob = raw[start:start + meta['count'] * N]
        sets.append([blob[i:i+N] for i in range(0, len(blob), N)])
    
    uppers = []
    for i in range(N):
        candidates = recover_upper(sets, i)
        assert len(candidates) == 1, (i, candidates)
        uppers.append(candidates[0])
    
    known = bytes.fromhex(info['sets'][0]['base'])
    offset = info['sets'][0]['offset']
    ct = raw[offset*N:(offset+1)*N]
    dummy = [u << 8 for u in uppers]
    state = known
    for rnd in range(3):
        state = bytes(g(a ^ b) for a, b in zip(state, round_key(dummy, rnd)))
        state = permute(state)
    state = bytes(a ^ b for a, b in zip(state, round_key(dummy, 3)))
    
    keys = []
    for i, upper in enumerate(uppers):
        before_low = apply_rows(matrix(upper), q(state[i]))
        keys.append((upper << 8) | (ct[i] ^ before_low))
    
    plain = open_sealed(json.loads(Path('sealed.json').read_text()), keys)
    print('COMPFEST18{' + plain.hex() + '}')
    

• •

  Verification

  • •

    The $q$-layer inverse was exhaustively checked for all 256 byte values. The integral degree argument was checked independently. The challenge archive itself was not attached here, so the recorded flag remains sourced from the team PDF rather than a new replay.

• •

  Concepts

  • •

    Integral cryptanalysis; higher-order derivatives over $\mathrm{GF}(2)$; quadratic Feistel permutations; known-plaintext key completion; authenticated decryption.

• •

  Source

  • •

    Source: team PDF, “Write Up COMPFEST18 Qualifier by PLN - Dokter Amnesia Pecinta PDF”. Page numbers below refer to the PDF’s printed page numbers. Printed pp. 34–49.

  • •

    AI assistance: https://chatgpt.com/share/6a929df8-9dec-83ec-b98a-b971a0311101

  • •

    AI assistance: https://share.gemini.google/5IOLYF07pDsw

◌ Explore connections in Graph view