bread_vs_keys

A cryptographic challenge involving a custom key exchange protocol based on "bread words" (vectors of signed integers). The challenge requires recovering a shared secret by exploiting the structure of the conjugation operation to decrypt a ChaCha20-Poly1305 ciphertext.

Challenge Overview

Protocol Implementation

1. Parameters: (a=80, b=20, c=20, d=40, e=43, f=50).
2. Public keys: 20 “bread” words per party, each a vector of signed ints (~40 long).
3. Private key: a long word k built from the public words.
4. Conjugations: Each party computes conjugated public words using their private key.
5. Shared secret: inv(k) || (Bob_conj[i] or inv(Bob_conj[i])) for the factors of k, then reduced.
6. Key derivation: HKDF(SHA256, salt=None, info=None) on the serialized shared secret (int32, big‑endian) → 32‑byte key.
7. Encryption: ChaCha20‑Poly1305 (no AAD).

Vulnerability

Alice’s first conjugation word is structured as inv(k) || Bob_pub[0] || k. Because Bob_pub[0] is known and the prefix is the inverse of the suffix, you can split the conjugation and recover k directly. The private key k is itself a concatenation of Alice’s public words (or their inverses), so it can be factored deterministically.

Exploitation

Recovery steps

1. Parse the transcript Extract Alice/Bob public key slices, Alice/Bob conjugation slices, and the nonces/ciphertexts from the final run in output.txt.

2. Recover k

   • Let c0 = Alice_conj[0].
   • Let m = len(Bob_pub[0]).
   • prefix_len = (len(c0) - m) // 2.
   • k = c0[prefix_len + m :] (the suffix); sanity check: c0[:prefix_len] == invert(k) and c0[prefix_len:prefix_len+m] == Bob_pub[0].

3. Factor k Walk through k, matching against each Alice public word or its inverse to get a sequence of (index, sign) pairs.

4. Rebuild shared secret

   • Start with secret = invert(k).
   • For each (idx, sign) in the factorization, append Bob_conj[idx] if sign=+1, else invert(Bob_conj[idx]).
   • Reduce adjacent inverse cancellations.

5. Derive key Serialize each int in secret as big‑endian signed 32‑bit, concatenate, and feed to HKDF(SHA256, salt=None, info=None, length=32).

6. Decrypt Use the derived key with ChaCha20‑Poly1305 and the provided nonces/ciphertexts (no AAD).

One‑shot reproduction script

Save as python3 - <<'PY' ... from the repo root (requires cryptography).

import re
from cryptography.hazmat.primitives.kdf.hkdf import HKDF
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.ciphers.aead import ChaCha20Poly1305

def parse_slice(start_label, end_label):
    arrs, collecting = [], False
    with open("output.txt") as f:
        for line in f:
            if line.startswith(start_label):
                collecting = True
                continue
            if collecting:
                if line.startswith(end_label):
                    break
                m = re.match(r"^\[\+\]\s*\[([^\]]+)\]", line)
                if m:
                    arrs.append(list(map(int, m.group(1).split(","))))
    return arrs

def invert(word): return [-x for x in reversed(word)]
def reduce_word(word):
    stack = []
    for x in word:
        if stack and stack[-1] + x == 0:
            stack.pop()
        else:
            stack.append(x)
    return stack

def factor(k, pub):
    inv = [invert(w) for w in pub]
    seq, i = [], 0
    while i < len(k):
        for idx, w in enumerate(pub):
            wl = len(w)
            if k[i:i+wl] == w:
                seq.append((idx, 1)); i += wl; break
            if k[i:i+wl] == inv[idx]:
                seq.append((idx, -1)); i += wl; break
        else:
            raise SystemExit(f"no match at {i}")
    return seq

alice_pub = parse_slice("[+] Alice's public key slice:", "[+] Bob's public key slice:")
bob_pub   = parse_slice("[+] Bob's public key slice:", "[+] Private keys generated")
alice_conj= parse_slice("[+] Alice's conjugation slice:", "[+] Bob's conjugation slice:")
bob_conj  = parse_slice("[+] Bob's conjugation slice:", "[+] Computing shared secret")

c0 = alice_conj[0]
m = len(bob_pub[0])
prefix_len = (len(c0) - m) // 2
k = c0[prefix_len + m:]               # recovered private word
assert c0[:prefix_len] == invert(k)   # sanity
assert c0[prefix_len:prefix_len+m] == bob_pub[0]

seq = factor(k, alice_pub)
secret = invert(k)
for idx, sgn in seq:
    w = bob_conj[idx]
    secret += w if sgn == 1 else invert(w)
secret = reduce_word(secret)

secret_bytes = b"".join(int(x).to_bytes(4, "big", signed=True) for x in secret)
key = HKDF(algorithm=hashes.SHA256(), length=32, salt=None, info=None).derive(secret_bytes)
print("key:", key.hex())

nonces = [
    "b89f5e980e3ca215b36aebd3",
    "8775915484dbc8989e666c0e",
    "0d7407b272b343306b640a55",
    "fd480ad268b9c74d4b960ac3",
]
cts = [
    "c1c5e0fa89f695cffac00eebca4e5aadd10c4ea0945902fe919b6326dd81f1bd1b",
    "07138d4a2e0c379bed99d93042673407103ca934f8a78d2896fbf37a941b3f244775c064fb2dffa3429d405851b0e8529d73e8fe01f5f25daee440f3",
    "771fdbf92caa7e9905bab2c516b3f74020b9a94390f174c3e9262cdfa22411b67bb51cbd248710f6542a2b9b3f0156ea15ece330c00e",
    "10c1abeb84b7007de7237aa287e2da5022cb6d6b82d7dc5936cb8f524735f152096b3335a4d36f2eb3326f4927ff61e0595748c0853234f97654a1a45044bd7a9eeba95a5191433a9bb6dd7fa2f356eaf5affcefa82728022e7e668c72a7a3feb043c7f32bc3157f34e58183f67921b9fb53f0",
]

aead = ChaCha20Poly1305(key)
for n, c in zip(nonces, cts):
    pt = aead.decrypt(bytes.fromhex(n), bytes.fromhex(c), None)
    print(pt.decode(errors="ignore"))

Expected Output

key: 3a61e3fc552881595e177e5d9978a41d909fc2ccf308882cb258ff1f1134c584
Give me the Flag!
Why did the prisoner choose Bread over Keys?
Because Bread tastes better than Keys.
Correct! Here's your flag: flag{b3c4u5e_bR34d_t4st35_b3tt3R_Th4n_k3Y5_d2h5IGRpZCB5b3UgZG8gdGhpcw==}