Human RNG

Full solution below. Spoilers ahead.

Task description

You’ve heard about LCGs, LFSRs, MTs, Xorshifts, RDRANDs, Lavarands… But, can you crack a Human RNG? (watch human_rng_at_work)

What is handed out

File	Contents
encrypt.py	Encodes the flag as a QR code and XORs its modules with a keystream
bitstream.txt	1999 public bits typed by a human, followed by <1681-bits-redacted>
ciphertext.png	The 41x41 encrypted QR code, scaled by 10
human_rng_at_work.mp4	A 3 minute phone video of someone typing on a keyboard

There is no remote service. encrypt.py builds a version 6, ECC level H, mask 0 QR code of the flag (41x41 = 1681 modules, no border), takes the last 1681 bits of bitstream.txt as the key (the redacted ones), XORs the modules in row-major order and saves ciphertext.png. It also states the shape of the flag body:

# The flag body is lowercase English words separated with underscores.
assert len(body) == 44
assert re.fullmatch(r"[a-z]+(?:_[a-z]+)+", body)

So this is a one-time pad whose pad was typed by a human. The goal is the 44 character body without the redacted key bits.

The human is a biased RNG

A one-time pad is unbreakable only when the key bits are uniform and independent. These were typed by a person, so they are neither. Measuring the 1999 public bits:

Statistic	Public bits	Ideal RNG
P(next bit differs from the previous one)	0.702	0.5
Lag-1 autocorrelation (bits as +1/-1)	-0.41	0
Run lengths 1/2/3/4/5/6	998/254/117/29/4/1	geometric with ratio 1/2
Held-out cross-entropy of a bigram model	about 0.86 bits per bit	1.00

People avoid repeats and alternate too much. A bigram model (the probability of each bit given the one before it) captures almost all of the structure. Trained on the first half of the public bits and scored on the second, order 1 reached 0.86 bits per bit, and orders 2 and 3 did slightly worse (0.87 and 0.88), so there is nothing beyond the immediate neighbour to model. Autocorrelation is near 0 past lag 3 and LZMA barely compresses the bits. Each key bit therefore carries about 0.14 bits of non-randomness, which adds up to well over a hundred bits of evidence across the 1160 modules that depend on the flag.

The bigram model, and how a candidate is scored

The model is a 2x2 table of log-probabilities L2[prev][cur], Laplace-smoothed, from adjacent public bits. A candidate key’s score is sum over i of L2[k_{i-1}][k_i]. A key that alternates about 70% of the time, like the human’s, scores high under this table; a uniform random key scores low. That gap is the entire signal the attack rides on.

Which modules are already known

Many modules do not depend on the flag body: the finder, timing and alignment patterns, the format information for (H, mask 0), the dark module, and the encoded constants (mode indicator, length, FortID{, }, terminator, the EC 11 padding). Reading the ciphertext and XORing against the all-a QR shows exactly 521 such positions out of 1681, with the remaining 1160 depending on the body. At those 521 positions key = ciphertext XOR qr is known exactly, and it already looks human (for example 101010101).

The QR is affine in the flag, and the blocks are independent

Reed-Solomon parity bytes are a GF(2)-linear function of the data bytes: multiplication by a constant in GF(256) is linear over GF(2) and addition is XOR. The fixed mask and function patterns cancel under XOR. So the whole QR matrix is an affine function of the flag bytes. I precomputed 44 x 27 delta matrices D[j][v] = QR(body with char j = v) XOR QR(base) and confirmed on random bodies that XORing single-character deltas reproduces a multi-character change exactly. For a candidate body:

key = ct XOR M0 XOR (XOR over j of D[j][body_j])

Then I score how human that key looks. Version 6-H splits the data into 4 Reed-Solomon blocks of 15 data and 28 error-correction codewords. Each block’s modules depend only on its own 7 to 15 characters. The 4-bit mode-indicator offset makes body characters 6, 21 and 36 each straddle two blocks:

Block	Body characters scored
A	0 to 5, plus the high nibble of 6
B	7 to 20, plus the low nibble of 6 and the high nibble of 21
C	22 to 35, plus the low nibble of 21 and the high nibble of 36
D	37 to 43, plus the low nibble of 36

Each block is scored on its own, summing L2[k_{i-1}][k_i] over adjacent key bits whose values this block (plus the fixed modules) determines. Neighbours in other blocks are unknown, which adds the same constant to every candidate, so it drops out of the ranking.

Why a character-level hill-climb finds nothing

A simulated annealing over all 27^44 bodies found only noise (best around -1598, against around -1430 for the real key). Changing one character flips about 28 times 8 parity modules pseudo-randomly, so the score has no gradient to climb. The right answer is a needle, and the search has to enumerate structured candidates, English word sequences, block by block.

Dead end: the video

The video has roughly 1600 to 1700 audible keystrokes (about 10 per second over 175 s), close to the 1681 redacted bits, so I tried classifying each press as 0 or 1 by sound. I tried onset detection with a press/release split, k-means and GMMs on log-band spectra, narrow resonance bands near 6 and 11 kHz, stereo time and level differences, pairwise waveform cross-correlation and a learned projection that maximises lag-1 anti-correlation. I also ran a supervised offset scan against key row 6, which is fully known (41 bits). The best result was about 55% label alternation, and nothing held up on held-out data. The hand covers the keys on camera, so the video’s only real hint is that a human made the key.

Block A: the first seven characters

I enumerated underscore-joined word sequences from the top 20,000 English words (wordfreq), trimmed to 7-character prefixes, and scored every one against block A. Re-running that search offline:

$ python solve.py search-prefix
humans_  -256.4
jc_q_sf  -268.3
jc_q_si  -268.3
...
26199562 candidates, mean -307.8 std 8.1

humans_ is the single best of 26,199,562 prefixes, beating the runner-up by about 12 bits and sitting 6.4 standard deviations above the mean. This is the one step that needed the long search; everything after it was cheap.

Blocks C and D: a guessed phrase confirms them

Given humans_ and the task’s theme, I guessed humans_are_terrible_random_number_generators and scored all four blocks against 20,000 random bodies (the “random” and “max” columns):

block A:  -256.4  random -309.2±8.3  max -275.1  z=6.4
block B:  -372.4  random -369.9±8.7  max -330.9  z=-0.3   <- wrong
block C:  -319.0  random -382.7±9.5  max -339.3  z=6.7
block D:  -267.2  random -309.5±8.4  max -273.2  z=5.1

Blocks A, C and D were strongly significant and block B scored like noise. That confirmed ..andom_number_generators across the last 23 characters and left 12 unknown characters in the middle (body[7..18]), between the first word and the start of the last words.

Block B: the middle twelve characters

A systematic search over one to three word combinations was running. In the meantime I scored guesses by hand against block B:

Middle (12 characters)	Block B z
are_terrible	-0.3
arent_secure	-0.3
are_horrible	-0.6
are_insecure	1.3
are_not_good	5.6

are_not_good was my own guess, and its block B score (-321.1, above the random max of -330.9, z = 5.6) singled it out. I stopped the systematic search before it would have reached that phrase on its own. Checking the full body gives four significant blocks:

$ python solve.py check <44-character body>
block A:  -256.4  random -309.2±8.3  max -275.1  z=6.4
block B:  -321.1  random -369.9±8.7  max -330.9  z=5.6
block C:  -319.0  random -382.7±9.5  max -339.3  z=6.7
block D:  -267.2  random -309.5±8.4  max -273.2  z=5.1

Checking the whole key

Computing key = QR(flag) XOR ciphertext for the recovered body:

	Public bits	Recovered key
Alternation rate	0.702	0.724
Fraction of ones	0.475	0.485
Bigram log-likelihood	about -0.86 bits per bit	-0.851 bits per bit

The total bigram score is -1430.9. Filling the flag-dependent modules with random bits instead gives about -1788 with a standard deviation near 24, so the real key sits roughly 15 standard deviations out, and all 521 fixed modules agree with the key read directly off the ciphertext. The recovered key is statistically the same human who typed the public bits.

The solver’s two entry points are python solve.py search-prefix and python solve.py check <44 character body>. It needs qrcode, pillow, numpy and wordfreq. There is no endpoint to submit to, so the recovered body (shown only in the flag field) is the result.

Takeaways

Even a person trying to be random alternates about 70% of the time, and a human keystream is not a one-time pad: use a CSPRNG. Small per-bit bias adds up, especially against a plaintext as structured as a QR code, whose function patterns and fixed prefix expose key bits directly and whose Reed-Solomon parity is a deterministic linear function of the data rather than more randomness. The independent blocks turned a 27^44 search into four small ones, and checking each hypothesis against the known key bits early is what kept the acoustic dead end from eating more time.