rgoussu.dev
rgoussu@goussu: ~/library/security/exercises
❯ ~/library/security/exercises cat cryptopals-crypto-challenges-subject.md

Cryptopals — crypto challenges (sets 1–3) — subject

# The staged work statement for Cryptopals sets 1–3 — build XOR, AES-ECB/CBC/CTR from primitives, then break them with the padding oracle — runnable offline against published test vectors.

Subjectsaved 2026-08-08source #cryptography#security#encryption#exercise#aes#subject

Brief

You are handed a pile of ciphertext and a promise that "it's encrypted, so it's safe." Your job is to disprove that promise with your own code. Over three staged sets you will first build the primitives byte by byte — encodings, XOR ciphers, block modes — and then turn them against themselves: recover keys you were never given, decrypt secrets with no key at all, and end holding plaintext that "encryption without integrity" swore you could never read. Work in any language; the only rule is that you understand every byte that moves.

Instructions

Implement each stage yourself and verify it before moving on. The sets build on each other — set 2 reuses your set-1 XOR helpers, set 3 reuses your set-2 block code.

Set 1 — Building blocks

  1. Hex ↔ base64. Write conversions between raw bytes, hex, and base64. Everything downstream speaks bytes; these are the plumbing. Do not use a language feature that hides the base64 alphabet from you — lay out the 6-bit groups yourself.
  2. Fixed XOR. XOR two equal-length buffers. One line, but it is the atom of everything that follows.
  3. Single-byte XOR cipher. A buffer was XORed against one repeated byte. Try all 256 keys, score each candidate plaintext by English letter-frequency (ETAOIN-style, or chi-squared against expected frequencies), and pick the winner. Recover the key byte and the message.
  4. Detect single-char XOR. One line in a file of hex strings was produced by the above. Score every line's best decrypt and surface the one real message.
  5. Repeating-key (Vigenère) XOR. Encrypt with a multi-byte key cycled across the plaintext, then break it: (a) guess the keysize by minimizing the normalized Hamming distance between blocks, (b) transpose the ciphertext into keysize columns, (c) solve each column as an independent single-byte XOR. Reassemble the key.
  6. AES-128-ECB decrypt. Here you may call a library's raw AES block operation — that is the one primitive you are allowed to borrow. Decrypt an ECB-mode ciphertext given the key, and write an oracle that detects ECB by spotting repeated 16-byte blocks in a ciphertext (identical plaintext blocks → identical ciphertext blocks is ECB's fatal tell).

Set 2 — Block crypto

  1. PKCS#7 padding. Pad an arbitrary buffer to a block boundary by appending N bytes of value N. Write both pad and validate-and-strip.
  2. CBC from scratch. Implement CBC mode by hand on top of your library's ECB block function only: XOR each plaintext block with the previous ciphertext block (the IV for block 0) before encrypting; reverse for decrypt. You must not call a library's CBC.
  3. ECB/CBC detection oracle. Build an encryption oracle that pads the input with random bytes and flips a coin between ECB and CBC per call; then, from the outside, detect which mode was used by feeding it a long run of identical bytes and watching for repeated blocks.
  4. Byte-at-a-time ECB decryption. An oracle encrypts your-input || unknown-secret under ECB with a fixed key. Recover the secret one byte at a time by aligning it against a controlled prefix and matching block outputs against a dictionary you build. Do the simple version first, then the harder variant where the oracle prepends a fixed random-length prefix you must detect and account for.

Set 3 — The payoff

  1. CBC padding oracle. Given only an oracle that tells you whether a ciphertext's PKCS#7 padding is valid, recover the full plaintext of a CBC ciphertext with no key. Attack block by block: manipulate the previous ciphertext block to force valid padding, derive the intermediate state one byte at a time from the last byte inward, XOR back to plaintext. This is the milestone that permanently changes how you read "encryption without authentication".
  2. CTR mode. Implement CTR: encrypt a counter block stream and XOR it into the plaintext (encryption and decryption are the same operation). Then break fixed-nonce CTR — several messages encrypted under the same nonce reuse the same keystream, so the problem collapses into repeating-key XOR across the aligned ciphertexts. Recover the keystream statistically.
  3. Write up the lessons. For each break, record the single design rule that would have stopped it: authenticate with an AEAD construction, never reuse a nonce/IV, and make padding checks constant-time so no oracle leaks.

Constraints

  • Implement the primitives yourself. XOR, PKCS#7 padding, CBC, and CTR are all yours to build. The only borrowed piece is a library's raw AES-128 single-block encrypt/decrypt — the ECB block operation everything else is composed from.
  • No high-level mode helpers. Do not call a library's CBC, CTR, or GCM; that would skip the lesson.
  • Random keys/IVs must be cryptographically random; keep them fixed only where a challenge says the oracle uses a fixed key.
  • Keep the attacks black-box: an attack may only use what its oracle actually returns (a plaintext scoring, a mode guess, a padding-valid boolean), never the hidden key.

Acceptance

  • Milestone 1 (Set 1 basics): each step passes its published fixture — hex/base64 round-trips, the fixed-XOR output matches, the single-byte and repeating-key breaks recover the exact known plaintexts and keys, ECB detection flags the planted line, and the AES-ECB decrypt yields readable text. Verify against the challenge test vectors.
  • Milestone 2 (Set 2 block crypto): PKCS#7 pad/validate round-trips; your hand-rolled CBC decrypts what it encrypts and matches a reference CBC on the same key/IV; the detection oracle names the right mode across many random trials; byte-at-a-time recovers the full hidden secret in both the simple and random-prefix variants.
  • Milestone 3 (Set 3 payoff): the padding oracle recovers the complete plaintext of a CBC ciphertext with no key; CTR encrypts/decrypts correctly; the fixed-nonce CTR break reconstructs the messages. Each matches the known plaintext.
  • Milestone 4 (lessons): a short written note per attack names the one preventive rule (AEAD authentication, unique nonces, constant-time padding checks).

Related