Step 231. Completing Cryptopals Set 1 — The Textbook of XOR Attacks, in My Code
Level 3 — Real-World CTF & Advanced Offensive Skills | Difficulty ★★★☆☆ | Estimated time: 6 hours
Prerequisites: Step 90 (XOR and encoding), the Python numeric instincts of Steps 229–230. An AES library appears for the first time.
⚠️ All exercises in this chapter are for your own lab and legal platforms only. Applying them to unauthorized systems is a crime.
- What you need: Python 3 (measured: 3.12.14),
pip install pycryptodome(for AES), internet access (to check the original problems). - Caution: Cryptopals (cryptopals.com) is a public, legal study problem set — a site its creators built specifically to encourage attack practice. However, problems requiring original problem-file downloads (challenges 4, 6, 7, 8) involve external data, so this chapter’s code is measured against self-generated data using the same algorithms. All output is measured.
Cryptopals is widely called the finest curriculum for "learning cryptographic attacks through code." Set 1’s eight problems are the textbook of XOR attacks — break single-byte XOR with frequency analysis, and for repeating-key XOR, estimate the key length via Hamming distance, then decompose the problem into per-column single-key problems. Today’s goal is not "knowing the answers" but owning "a machine that auto-grades 256 candidates with one scoring function." That machine gets reused in Set 2 and every Crypto problem beyond.
1. Learning Objectives
By the end of this chapter, you will be able to:
- Convert freely among hex ↔ bytes ↔ base64 and explain each format’s role
- Implement Hamming distance and know its meaning as "the count of differing bits"
- Auto-decrypt a single-byte XOR ciphertext with an English-frequency scoring function
- Estimate a repeating-key XOR key length via normalized Hamming distance and recover the key via column splitting
- Perform AES-ECB decryption with a library and identify ECB ciphertexts via repeated-block detection
2. Background Knowledge — Today’s Tools and Concepts
Today’s Tools at a Glance
| Category | Details |
|---|---|
| Language/environment | Python 3 (measured: 3.12.14) + pycryptodome (for AES-ECB decryption) |
| Today’s commands | bytes.fromhex(), base64.b64encode(), bin(x).count("1"), AES.new(key, AES.MODE_ECB) |
| Concepts needed | XOR (Step 90), Hamming distance, frequency analysis, column decomposition of repeating-key XOR, block ciphers and ECB |
| Today’s deliverable | xorlib.py — scoring function + single-key breaker + key-length estimator (reused in later chapters) |
2-1. Three Representations — hex, bytes, base64
Three faces of the same data. bytes is the substance (the actual 0s and 1s), hex is hexadecimal notation for human reading (2 characters per byte), and base64 is a 64-character encoding for channels that only pass text (email, JSON) — 4 characters per 3 bytes. Crypto problems hand you data as hex or base64, but computation always happens after converting to bytes.
2-2. Hamming Distance — How Many Bits Differ Between Two Byte Strings
The Hamming distance is the number of differing bits between two byte strings. XOR each byte pair and only the differing bits become 1, so the sum of bin(x ^ y).count("1") is the distance. The famous test vector: the distance between "this is a test" and "wokka wokka!!!" is 37 — you’ll use it again today as a gauge for whether your implementation is correct.
2-3. Frequency Analysis — Language Engraves Statistics
English sentences have biased letter frequencies — e, t, a, and spaces dominate. Single-byte XOR merely shifts the plaintext’s statistics; it can’t erase them. So "try all 256 keys and pick the result that looks most like English" decrypts without knowing the key. The scoring function decides success or failure — the ratio of spaces and letters alone goes a long way, and penalizing non-printable characters makes it far more stable.
2-4. Decomposing Repeating-Key XOR — Find the Length and the Game Is Over
When you XOR with a repeating key K, plaintext characters at the same position get encrypted with the same key byte. Slice the ciphertext into columns of stride L (the key length) and each column is a single-byte XOR problem. The catch is you don’t know L — this is where Hamming distance comes in. Adjacent blocks cut at the correct L are "English XOR English," so few bits differ (normalized distance ~2–3), while a wrong L looks near-random (~4). Compare normalized distances for L candidates 2–40 to pin it down.
3. Follow Along
All output in this chapter was measured 2026-09-09 on Python 3.12.14. Problem data was self-generated with the same algorithms — get the original problems from cryptopals.com and feed them to the same code.
3-1. hex ↔ base64 (Challenge 1)
import base64
raw = bytes.fromhex("43727970746f20747261636b21")
print("hex -> bytes:", raw)
print("bytes -> base64:", base64.b64encode(raw).decode())
print("base64 -> hex round trip:", base64.b64decode(base64.b64encode(raw)).hex())
hex -> bytes: b'Crypto track!'
bytes -> base64: Q3J5cHRvIHRyYWNrIQ==
base64 -> hex round trip: 43727970746f20747261636b21
How to read the output: three representations round-tripping one piece of data. The trailing == is base64 padding — it appears when the source byte count isn’t a multiple of 3. The original challenge 1 gives a much longer hex string, but these three lines are the entire conversion code.
3-2. Hamming Distance (Warm-up for Challenge 6)
def hamming(a, b):
return sum(bin(x ^ y).count("1") for x, y in zip(a, b))
print("hamming distance:", hamming(b"this is a test", b"wokka wokka!!!"))
hamming distance: 37
How to read the output: matches the public test vector 37 — the implementation is correct. This one function supports all of the key-length estimation ahead.
3-3. Single-Byte XOR Breaking (Challenge 3)
Build the scoring function and the "brute-force all 256" breaker.
FREQ = "etaoin shrdlu" # letters common in English (including the space)
def score(bs):
s = 0
for x in bs.lower():
c = chr(x)
if c in FREQ: s += 2
elif c.isalpha() or c in " .,'!?": s += 1
elif x < 32 or x > 126: s -= 5 # penalty for non-printable characters
return s
def break_single_xor(ct):
best = (-10**9, None, None)
for k in range(256):
pt = bytes(x ^ k for x in ct)
sc = score(pt)
if sc > best[0]:
best = (sc, k, pt)
return best
plain = b"The quick brown fox jumps over the lazy dog, again and again."
ct = bytes(x ^ 0x42 for x in plain)
sc, k, pt = break_single_xor(ct)
print("recovered key: 0x%02x, score: %d" % (k, sc))
print("recovered plaintext:", pt.decode())
recovered key: 0x42, score: 104
recovered plaintext: The quick brown fox jumps over the lazy dog, again and again.
How to read the output: without knowing the key, it graded 256 candidates and found 0x42. The secret isn’t brute force — it’s grading. Wrong keys spew control characters and get caught by the penalty (-5); only the right key revives English statistics.
3-4. Finding the Ciphertext Among Many Lines (Challenge 4)
Of 60 random lines, only one is English encrypted with single-key XOR. Reuse the scoring function to find "the most English-looking line."
import secrets
lines = [secrets.token_bytes(30) for _ in range(60)]
lines[37] = bytes(x ^ 0x35 for x in b"Now that the party is jumping and the bass kicked in")
best = max((score(break_single_xor(l)[2]), i, break_single_xor(l)[2])
for i, l in enumerate(lines))
print("most English-looking line: #%d, score %d" % (best[1], best[0]))
print("contents:", best[2].decode())
most English-looking line: #37, score 93
contents: Now that the party is jumping and the bass kicked in
How to read the output: Python finishes 60 lines × 256 keys = 15,360 gradings in a flash. The original challenge 4 (a 325-line file) runs on this exact code — just open the file into lines.
3-5. Full Repeating-Key XOR Break (Challenge 6)
Three stages: key-length estimation → column splitting → per-column single-key breaking.
def rep_xor(data, key):
return bytes(b ^ key[i % len(key)] for i, b in enumerate(data))
def guess_keysize(ct, lo=2, hi=15):
out = []
for ks in range(lo, hi + 1):
blocks = [ct[i:i+ks] for i in range(0, ks * 6, ks)]
pairs = [(blocks[i], blocks[j]) for i in range(6) for j in range(i + 1, 6)]
d = sum(hamming(a, b) / ks for a, b in pairs) / len(pairs)
out.append((d, ks))
return sorted(out)[:3]
text = (b"Back in the lab again, cooking up the same old plaintext. "
b"The rhythm of English repeats itself like a drum machine. "
b"Letter frequencies leak through every single column we split. "
b"Split the ciphertext into columns and each one is a single key puzzle. "
b"Drums keep pounding rhythm to the brain, la de da de dee. ")
rct = rep_xor(text, b"ICE")
print("key-length candidates:", [(ks, round(d, 2)) for d, ks in guess_keysize(rct)])
ks = guess_keysize(rct)[0][1]
key_bytes = bytearray()
for col in range(ks):
_, k, _ = break_single_xor(rct[col::ks]) # extract just column col and single-key-break it
key_bytes.append(k)
print("recovered key:", bytes(key_bytes))
print("recovered plaintext, first 60 chars:", rep_xor(rct, bytes(key_bytes))[:60].decode())
key-length candidates (normalized Hamming distance, ascending): [(3, 2.27), (7, 2.4), (12, 2.4)]
recovered key: b'ICE'
recovered plaintext, first 60 chars: Back in the lab again, cooking up the same old plaintext. Th
How to read the output: skip the normalization (dividing by the key length) and longer key lengths are automatically disadvantaged, producing misjudgments — the / ks is mandatory. Key length 3 came out lowest at 2.27, and the column-splitting attack recovered the key ICE exactly. The one slice rct[col::ks] is all there is to "column extraction."
3-6. AES-ECB Decryption and Repeated-Block Detection (Challenges 7–8)
from Crypto.Cipher import AES
aes_key = b"YELLOW SUBMARINE"
msg = b"yellow submarine" * 4 + b"all my friends are" # 4 repeats of a 16B block
cipher = AES.new(aes_key, AES.MODE_ECB)
pad = bytes([16 - len(msg) % 16]) * (16 - len(msg) % 16)
ct = cipher.encrypt(msg + pad)
print("ECB decryption, first 46 bytes:", cipher.decrypt(ct)[:46])
blocks = [ct[i:i+16] for i in range(0, len(ct), 16)]
print("of %d blocks, %d unique" % (len(blocks), len(set(blocks))))
print("-> repeats present means ECB suspected:", len(set(blocks)) < len(blocks))
ECB decryption, first 46 bytes: b'yellow submarineyellow submarineyellow submari'
of 6 blocks, 3 unique
-> repeats present means ECB suspected: True
How to read the output: in ECB, the same plaintext block always becomes the same ciphertext block — the four yellow submarines repeat identically in the ciphertext (3 unique = 4 repeats + remainder + padding). This property is both the solution to Set 1’s final problem (finding the ECB line in a ciphertext file) and the main attack material of the next chapter.
4. Missions & Exercises
Mission — Completing xorlib.py and Self-Verifying Set 1
- Organize today’s functions into
xorlib.py—hamming,score,break_single_xor(returns(score, key, plaintext)),rep_xor,guess_keysize,detect_ecb_blocks(ct, bs=16)(returns the number of repeated blocks) - Write a self-verification script: ① pass the Hamming test vector (37) ② recover self-made single-key and repeating-key ciphertexts without seeing the keys ③ succeed at ECB repeated-block detection
- Download the actual Set 1 problems (challenges 1–8) from cryptopals.com and solve them with the same functions — for challenge 4 and 6 files,
open(...).read().splitlines()is all you need to add - (Optional) Improve the scoring function — adding a letter-frequency table (weighted
etaointiers) raises accuracy on short sentences
Exercises
Exercise 1. hex and base64 are both "text representations." Compute how many characters 12 bytes become in each, and explain why base64 has the edge in transfer efficiency.
Exercise 2. In single-byte XOR breaking, what error arises without the "non-printable penalty (-5)"? Describe a scenario where a wrong key gets a high score.
Exercise 3. In repeating-key XOR key-length estimation, which direction do you misjudge without normalization (hamming / ks)? Explain using the 3-5 numbers as evidence.
Exercise 4. Explain why ECB’s "same block = same ciphertext" property occurs, starting from the definition of a block cipher (block-wise substitution under a fixed key). And name one thing an attacker can learn from this property alone, without the plaintext.
5. Model Answers & Completion Criteria
Mission Model Answer
The key is unifying function return values — if break_single_xor always returns a (score, key, plaintext) tuple, challenges 3, 4, and 6 all run on the same function.
def detect_ecb_blocks(ct, bs=16):
blocks = [ct[i:i+bs] for i in range(0, len(ct), bs)]
return len(blocks) - len(set(blocks)) # number of repeated blocks
Grading criteria: ① all three self-verifications pass (recovery happens without seeing the keys) ② the same functions work on the original challenge data ③ reusable via xorlib.py import alone. The completion condition is not "code written fresh per problem" but "a toolbox used across every problem."
How to verify: separate the ciphertext-generation code from the decryption code, and check the decryption side never sees the key used in generation. A recovered key coincidentally matching the generation key (hardcoding) is the most common self-deception.
Exercise Answers
Answer 1. 12 bytes become 24 characters in hex (2 per byte) and 16 characters in base64 (4 per 3 bytes). Base64 uses 4/3 characters per byte — 33% shorter than hex’s 2 — so it consumes less bandwidth on text channels. In return, neither can be computed on directly; both are just preprocessing back to bytes before computation.
Answer 2. XOR with a wrong key often turns bytes like the plaintext’s spaces (0x20) into control characters (0x00–0x1F). Without the penalty those score 0, so a wrong key that happens to surface a few common letters can beat the right answer. Remove the penalty term from the measured scoring function and the error rate on short sentences visibly climbs — the essence of a scoring function isn’t "rewarding English" but "penalizing non-English."
Answer 3. Without normalization, Hamming distance grows roughly in proportion to block length, so longer key lengths have larger raw distances. In other words, you misjudge in the direction that favors short key lengths (2, 3) regardless of the true answer. In 3-5, ks=3’s normalized distance was 2.27 — inside the English-statistics range (2–3) — and that value was the minimum among the candidates.
Answer 4. A block cipher is a deterministic function substituting a 16-byte block for a 16-byte block under a fixed key. ECB feeds each block to this function independently, so identical input blocks necessarily produce identical output blocks. Without knowing the plaintext, the attacker can learn "where the plaintext repeats" — structure and patterns. This is the root of image-outline leakage (next chapter’s penguin experiment) and the byte-at-a-time attack.
Completion Criteria Checklist
- [ ] I can write the three hex/bytes/base64 conversion lines from memory
- [ ] My Hamming distance implementation passes the test vector 37
- [ ] I decrypted single-byte XOR without the key using the scoring function
- [ ] I auto-detected the ciphertext line among many lines
- [ ] I estimated the key length with normalized Hamming distance and recovered the repeating key via column splitting
- [ ] I performed AES-ECB decryption with pycryptodome
- [ ] I identified an ECB ciphertext by its repeated-block count
- [ ] Mission: xorlib.py complete + applied successfully to the original Set 1 data
6. Common Pitfalls & Fixes
Wall 1. ValueError: non-hexadecimal number found in fromhex() arg at position 0
Symptom: ValueError: non-hexadecimal number found in fromhex() arg at position 0 (measured 2026-09-09).
Cause: the hex string contains characters outside 0–9a–f (spaces, newlines, a 0x prefix). Newlines are the classic case when reading problem files.
Fix: strip newlines with .strip(), and when reading a whole file, remove all whitespace at once with "".join(f.read().split()).
Wall 2. binascii.Error: Only base64 data is allowed
Symptom: binascii.Error: Only base64 data is allowed (measured 2026-09-09, with validate=True).
Cause: the base64 string has newlines mixed in, or you mistakenly fed a hex string to the base64 decoder. Challenge 7, whose file is multiple lines of base64, is the classic case.
Fix: join the lines and then decode: base64.b64decode("".join(lines)). Re-checking whether the problem says hex or base64 is also quick.
Wall 3. The scoring function picks a wrong key
Symptom: the recovered plaintext is garbled yet scores high.
Cause: the sentence is short so statistics are unstable, or there’s no penalty term so control characters pass score-free (see Exercise 2).
Fix: keep 3-3’s three tiers (common letters +2 / letters +1 / non-printable -5), and for short inputs, eyeball the top 3 candidates. "Candidate narrowing + human reading" beats full automation in the field.
Wall 4. Key-length estimation picks a multiple of the answer
Symptom: the real key is 3, but 6 or 9 ranks first.
Cause: that’s normal — slicing at a multiple of key length L still repeats the same key pattern, so the distance comes out low.
Fix: run the column-splitting attack on the top 2–3 candidates, and if a recovered key is a repetition of a shorter cycle (e.g., ICEICE), take just the front part. The fix is the habit of looking at the whole candidate list, as in 3-5.
Wall 5. You installed pycryptodome but import crypto works/doesn’t
Symptom: installed, yet ModuleNotFoundError: No module named 'Crypto'.
Cause: the package name is pycryptodome; the import name is Crypto (capital C). Conflicts with the old pycrypto can tangle imports.
Fix: after python -m pip install --quiet pycryptodome, verify with from Crypto.Cipher import AES. If the legacy pycrypto is present, remove it and reinstall.
7. Summary
Today’s Concepts
| Concept | One-line explanation |
|---|---|
| hex / base64 | Two text representations of bytes — always back to bytes before computing |
| Hamming distance | The count of differing bits — the ruler for key-length estimation |
| Frequency analysis | Auto-grading 256 candidates with English statistics (etaoin) |
| Repeating-key XOR decomposition | Key-length estimation (normalized Hamming) → column splitting → per-column single-key |
| ECB repeat detection | Same plaintext block = same ciphertext block — compare unique-block counts |
Today’s Commands & Code
| Command | What it does |
|---|---|
bytes.fromhex(s) / b.hex() |
hex ↔ bytes |
base64.b64encode(b) / b64decode(s) |
base64 ↔ bytes |
bin(x ^ y).count("1") |
Bit difference — the atom of Hamming distance |
ct[col::ks] |
Extract column col of repeating-key XOR |
AES.new(key, AES.MODE_ECB) |
ECB-mode AES (for study) |
len(set(blocks)) < len(blocks) |
ECB repeated-block detection |
An Instinct More Important Than Commands
Set 1’s true graduation prize isn’t code — it’s the scoring function. "The ability to express in numbers what a correct answer looks like" is the engine of every classical cipher attack. And what the last two problems left behind — ECB’s flaw that "same block, same ciphertext" — is where the next chapter begins. Don’t throw away today’s xorlib.py; it continues straight into Set 2.
Once every box is checked, Step 231 is complete. Click the checkbox in the sidebar to save your progress.