Baby Crypto

Task description

Yet another totally secure secret vault implementation. Take a look, and let us know what you think…

A vault with one key for everything

The handout is a single file, chall.py. On connect, the service prints a “Secure Vault” banner, creates a vault, stores the flag as its first secret, then offers a three-item menu: store a new secret (it gets encrypted and appended), export every stored secret as hex-encoded JSON, or exit. A signal.alarm(15) closes the session after fifteen seconds, so whatever I do has to fit in one connection.

The startup code pins down what I am attacking:

assert FLAG.startswith("FortID{") and FLAG.endswith("}")
vault = Vault()
vault.insert(FLAG)          # the flag becomes Secret #0

Vault.insert encrypts a value and files it under Secret #N, and Vault.export dumps the lot:

def insert(self, secret_value):
    ciphertext = self.cipher.encrypt(secret_value.encode("utf-8"))
    self.entries[f"Secret #{len(self.entries)}"] = ciphertext.hex()

So the flag’s ciphertext is always Secret #0, and I can read it with the export option any time. The whole question is how to decrypt it without the key, and the answer is in the cipher.

Where the bug lives

Every secret, including the flag, runs through this:

class Cipher:
    def __init__(self):
        self.key = get_random_bytes(16)

    def encrypt(self, plaintext):
        cipher = AES.new(self.key, AES.MODE_CTR, nonce=plaintext[:8])
        return cipher.encrypt(plaintext)

Two choices here are each enough to sink it. The key is generated once per Cipher, so one key covers the flag and every secret I submit in the same session. And the nonce is not random: it is plaintext[:8], the first eight bytes of whatever is being encrypted.

Why a plaintext-derived nonce breaks everything

AES-CTR (counter mode, which turns the AES block cipher into a stream cipher) encrypts by generating a keystream from the key and nonce and XORing that keystream onto the plaintext. The security rests on one rule: never encrypt two different messages with the same key and nonce. Break that and both messages share the same keystream, which is the two-time-pad problem. If you know one of the two plaintexts you can peel the keystream off it and decrypt the other, with no attack on AES itself.

Here the nonce comes from the message, so two plaintexts that begin with the same eight bytes are encrypted under the same nonce, and therefore the same keystream. The flag’s first eight bytes are FortID{ plus one more character:

F  o  r  t  I  D  {  ?
0  1  2  3  4  5  6  7    <- byte index

Bytes 0 to 6 are the fixed prefix. Byte 7, the first character of the flag body, is the only unknown in the nonce. If I store a secret that opens with the flag’s exact first eight bytes, the vault encrypts it under the identical keystream used for the flag.

Deriving the keystream from my own ciphertext

For a probe plaintext P I control, with ciphertext C the vault returns:

KS = C XOR P

recovers the keystream, because C = P XOR KS. The flag’s ciphertext C_flag used that same keystream, so:

FLAG = C_flag XOR KS

Only byte 7 of the nonce is unknown, so I do not have to guess the flag, only that one nonce byte. I send one probe per printable candidate, each shaped FortID{ + candidate + padding, in a single session before the alarm fires. The correct candidate is the one whose probe reproduces the flag’s nonce, and its derived keystream decrypts Secret #0 into a well-formed FortID{...} string. Every byte but that one comes from the service’s own arithmetic.

string.printable.strip() is 94 characters (the printable set minus the six whitespace characters), so there are 94 probes. Each probe is the 7-byte prefix, one candidate byte, and 256 bytes of A padding, 264 bytes in total. The padding is there so the probe (and the keystream recovered from it) is never shorter than the flag ciphertext, which would leave the flag’s tail undecrypted.

PREFIX = b"FortID{"
PAD = b"A" * 256
CANDIDATES = [c.encode() for c in string.printable.strip()]   # 94 of them

def solve(output):
    vault = json.loads(re.search(rb"\{\"Secret #0\".*\}", output).group())
    flag_ct = bytes.fromhex(vault["Secret #0"])
    for i, c in enumerate(CANDIDATES, start=1):
        probe_pt = PREFIX + c + PAD
        keystream = xor(bytes.fromhex(vault[f"Secret #{i}"]), probe_pt)
        pt = xor(flag_ct, keystream)
        if pt[7:8] == c and pt.startswith(PREFIX) and pt.endswith(b"}") and pt.isascii():
            return pt.decode()

The surviving candidate is the one whose guessed character equals the decrypted byte at position 7 and whose decryption is printable ASCII ending in }. That is a structural self-consistency check on a value the keystream produced, not a brute force of the flag text.

Proving the mechanism offline

I did not have the live service when writing this up, and I did not want the flag doing any work the maths should do. So I reimplemented the vault’s Cipher and Vault exactly as chall.py has them, seeded it with a stand-in flag, FortID{pr00f_0f_c0ncept_n0t_th3_r3al_fl4g}, and ran the same 94 probes and the same solver against it:

number of probes: 94
  probe for b'p': b'FortID{pAAAAAAAA'... total len 264
  probe for b'A': b'FortID{AAAAAAAAA'... total len 264
  probe for b'0': b'FortID{0AAAAAAAA'... total len 264
matched nonce byte 7: b'p'
recovered == standin : True
recovered           : b'FortID{pr00f_0f_c0ncept_n0t_th3_r3al_fl4g}'
len: 42 sha256: 9336867efd19

The stand-in’s body starts with p, exactly one probe (the p probe) reproduced its nonce, and XORing that probe’s recovered keystream against the stand-in ciphertext returned the full stand-in verbatim. The real run against the live vault is identical arithmetic with Secret #0 holding the real flag’s ciphertext; the surviving candidate there decrypts to b'FortID{St0p_B31ng_Cr3at1v3...', the flag shown below.

Why only byte 7 is unknown, and why the padding is needed

The keystream for a CTR message depends only on the key and the nonce, which here is plaintext[:8]. For the flag, seven of those eight bytes are the constant FortID{, so the keystream is fully determined except for the contribution of byte 7, the first character of the flag body. A probe FortID{<c>... reproduces the flag’s nonce exactly when c is that byte, and for the right c the probe’s keystream matches the flag’s byte for byte, so XORing it against the flag ciphertext yields the whole plaintext.

The 256 bytes of padding make each probe 264 bytes long, which guarantees the recovered keystream is at least as long as the flag ciphertext. CTR generates keystream block by block as needed, so a probe shorter than the flag would leave the flag’s trailing bytes with no keystream to cancel them.

What the vault should have done

A nonce has to be unique per key and must never be a function of the plaintext. The fix is a random nonce, generated independently and prepended to the ciphertext so the recipient can use it, or a strict monotonic counter that never repeats under one key. The flag’s own text spells out the lesson the challenge was built around: stop being creative with nonces. Nonce generation is the one place in a cipher to be completely boring.