Crypto Foundations and Threat Models

The first four exercises teach different questions: how a deterministic state changes, how to remove a sampling bias, how collisions accumulate, and what reusing a pad reveals. A correct implementation of any one does not establish a secure protocol. Start by stating what the attacker observes and what must remain hidden or unforgeable.

Turn a security claim into an attacker experiment

Imagine a service sends an encrypted command and accepts any decrypted bytes. A passive observer tries to learn the command: that is a confidentiality goal. An active observer flips bits so the receiver performs a different command: that tests integrity and authenticity. Encryption that satisfies the first goal need not satisfy the second. Replaying an old authentic command is another failure unless the protocol binds freshness.

A threat model records attacker access, desired failure, and constraints. Known-plaintext access exposes some plaintext/ciphertext pairs. Chosen-plaintext access lets an attacker request encryptions. Chosen-ciphertext access additionally gives a decryption interface subject to the security experiment's restrictions. These are different evidence budgets, not interchangeable labels for a strong attacker.

The following constructions are exercises for tracing and diagnosis. The toy generator and unauthenticated pad operations are not a secure application protocol.

Trace state separately from output

XorShift64Star.Next applies three unsigned 64-bit XOR/shift updates, saves that intermediate state, then returns it multiplied by 2685821657736338717 modulo 2^64. For seed 1:

start                     0000000000000001
x ^= x >> 12              0000000000000001
x ^= x << 25              0000000002000001
x ^= x >> 27              0000000002000001  ← saved State
multiply modulo 2^64      47e4ce4b896cdd1d  ← returned output

Saving the multiplied output as State changes the next step and fails the specified sequence. Unsigned overflow is intentional here; it is not a general excuse to ignore integer bounds elsewhere. A zero state would remain zero under all three XOR/shift updates, so the constructor replaces seed zero with its specified nonzero constant.

A deterministic generator expands a state into a sequence; it does not create new secret uncertainty. If an attacker knows the state, the next output is computable. Passing a frequency test does not prove prediction resistance. The generator author's discussion explicitly distinguishes these non-cryptographic generators from secure randomness, and RFC 4086 explains why a small seed space remains a small search space even when outputs are long.

Count residues to derive rejection sampling

Use a three-bit uniform source, values 0 through 7, and reduce modulo 3:

residue 0: 0,3,6  → 3 representatives
residue 1: 1,4,7  → 3 representatives
residue 2: 2,5    → 2 representatives

The reduction is biased. Accept only 0 through 5 and retry 6 or 7. Each residue then has two representatives, so conditioned on acceptance the output is uniform.

The exact UniformMod contract uses M=maxUint64 and limit=M-(M%n), accepting r<limit. The interval [0,limit) contains a whole number of n-sized groups. This formulation avoids trying to represent 2^64 in uint64, though it sometimes rejects more values than a maximal acceptance interval. For n=1 it rejects M and returns zero for other draws; for a three-bit version with n=4 it accepts 0 through 3, although accepting all eight values would also be unbiased. Follow the specified cutoff so a deterministic fake RNG consumes the expected number of draws.

A fake stream [7,6,5] with three-bit n=3 rejects twice and returns 5%3=2. A loop that accepts r==limit adds one extra representative of residue zero. Test this exact boundary, not just an output histogram.

The input requires n>=1 and fresh uniform draws. An adversarial stream can make retries continue forever. Rejection sampling fixes the distribution mapping; it cannot make a predictable source cryptographically unpredictable.

Derive the birthday estimate and its numeric boundary

For q independent uniform samples among N=2^b possible hash outputs, there are q(q-1)/2 pairs. The exercise uses this approximation:

p(q) ≈ 1 - exp(-q(q-1)/(2N))
t = -2N ln(1-target)
q ≈ ceil((1 + sqrt(1+4t))/2)

With b=8 and target=0.5, t is approximately 354.891. The real root is approximately 19.345, so the estimated threshold is 20 samples. Verify minimality: q=19 gives approximately 0.4873; q=20 gives approximately 0.5239. This is a threshold under the stated approximation, not the exact occupancy probability.

Use math.Log1p(-target) so very small targets do not disappear when subtracting from one. Any positive target requires at least two samples; floating-point rounding near q=1 must not return one. For b=256, the threshold may be far larger than the largest machine int. The exercise therefore saturates at maxInt before conversion. Saturation means “unrepresentable in this return type,” not that maxInt samples attain the target. Float64 cannot distinguish every large integer either; the interface intentionally returns a rounded approximation, not an arbitrary-precision proof of minimality.

The generic collision scale is about 2^(b/2), while finding a preimage for a fixed target has generic scale about 2^b. Changing b from 64 to 80 multiplies the collision scale by 2^8, not 2^16. Neither count alone specifies real-world attack cost or security of an entire construction.

Recover only what pad reuse actually reveals

For equal-length byte strings, c1=p1 XOR k and c2=p2 XOR k. XORing cancels k and reveals p1 XOR p2. It does not automatically reveal both plaintexts. If p1 is known, then p2=c1 XOR c2 XOR p1.

With c1=0x12, c2=0x34, and p1=0x56, first obtain 0x12 XOR 0x34=0x26, then 0x26 XOR 0x56=0x70. RecoverMessage repeats this independently at each byte and returns nil for unequal lengths. A fresh returned slice preserves the three inputs.

An ideal one-time pad needs a uniform secret pad independent of the message, as long as that message, used once. It provides secrecy but does not detect an attacker flipping ciphertext bits. A nonce in a modern mode is not necessarily secret or random: requirements are mode-specific. CTR needs unique counter blocks under a key, while CBC needs an unpredictable IV. Predictable counters are not automatically insecure nonces; reuse of the same keystream is the relevant failure here. The mode specification separates these conditions.

Reconstruct a changed case

Use a four-bit source (0..15), n=5, and this exercise's cutoff formula with M=15. Which draws are accepted? How often does each residue occur? Separately, recover p2 from p1=0xa0, c1=0x0f, c2=0x3c.

Reveal the reasoning

The limit is 15, so accept 0..14 and reject 15. Each residue has three representatives. Recovery gives 0x0f XOR 0x3c XOR 0xa0=0x93. Without the known p1, only the XOR relation 0x33 would be established.

Implement and test one boundary per exercise: state-versus-output after two generator steps; a rejected cutoff before an accepted draw; birthday saturation and tiny positive targets; and unequal pad lengths. Then explain why composing this toy generator with unbiased reduction still does not produce a secure key generator.