Encryption Without Key

Task description

Someone built their own encryption algorithm that doesn’t use a key. Can you show them why this isn’t secure, and why it should be called encoding, not encryption?

The original was in Croatian; this is my translation. The task’s own framing is the whole point: an invertible transformation that needs no secret to reverse is encoding, whatever its author calls it.

What the binary does

The encode binary (statically linked, stripped x86-64) takes an input file and an output path, and does three things:

1. Computes a 16-byte “fingerprint” of the input, built from how often each byte value appears and how often each adjacent byte pair appears, sorted and folded through SHA-256’s internal round constants.
2. Uses that fingerprint as the seed for a splitmix64 PRNG (recognisable in the disassembly by its signature constants, 0x9e3779b97f4a7c15, 0xbf58476d1ce4e5b9, 0x94d049bb133111eb) to Fisher-Yates shuffle the identity permutation [0..255] into a 256-byte substitution table.
3. Replaces every input byte b with table[b].

Why the fingerprint gives it away

The fingerprint is built entirely from statistics about which values appear how often, byte frequencies and pair frequencies, sorted before hashing. A one-to-one substitution of byte values permutes which value carries which frequency, but it can’t change the multiset of frequencies themselves, and since the fingerprint sorts them before hashing, it comes out identical whether it’s computed on the plaintext or on the already-substituted ciphertext.

That means the substitution table isn’t a secret derived from something only the encoder knows; it’s derived entirely from a property that’s preserved by the very transformation it produces. Anyone holding only the scrambled output can recompute the same fingerprint, generate the same table, and reverse the substitution, exactly why this is encoding rather than encryption: there’s no key an attacker lacks.

Recovering the plaintext

Running the encode binary again, on the already-encoded encoded.bin, produces a second encoding using the same table (since the fingerprint, and therefore the table, is unchanged by the first pass). Comparing the once-encoded and twice-encoded bytes position by position reveals, for each byte value, which other value it maps to, tracing out the substitution table’s permutation cycles directly. From there, building the inverse table and applying it to encoded.bin recovers the original file.

(An alternative, since byte substitution is a permutation and every permutation has a finite order, is to keep applying encode to its own output repeatedly; eventually the cycle returns to the original plaintext, since the permutation’s order always divides 256 factorial.)

The exploit

./encode encoded.bin encoded_twice.bin   # re-encode with the (unchanged) same table

once = open('encoded.bin', 'rb').read()
twice = open('encoded_twice.bin', 'rb').read()

table = {}                        # table[b] = encode(b), read straight off the two encodings
for a, b in zip(once, twice):
    table[a] = b

inverse = [0] * 256
for a, b in table.items():
    inverse[b] = a

plaintext = bytes(inverse[b] for b in once)
open('decoded.bin', 'wb').write(plaintext)

The result

The decoded output is a block of Lorem Ipsum filler text, with the flag embedded inside it:

CTF2026[714771130153]