Crypto Foundations & Threat Models

Why this module exists

Most engineers can call crypto/* or a library wrapper. Very few can explain what security guarantees they actually get, what the attacker can do, or how a seemingly small mistake breaks the system. This module builds the mental model that turns a "library user" into someone who can reason about designs, review protocols, and avoid subtle failures.

This pack is deliberately hands-on. You will implement toy primitives from scratch to see exactly where the security comes from and where it collapses. In production, do not roll your own crypto. But for learning, building the machinery is the fastest way to stop making category errors.

1) Security goals: what are you trying to protect?

Cryptography is not "make it secret." It is a set of goals that you choose explicitly. Confusing them causes real failures.

• Confidentiality: an attacker cannot learn the message contents.
• Integrity: an attacker cannot modify data without detection.
• Authenticity: an attacker cannot forge data that appears to come from a trusted identity.
• Availability: the system remains usable under attack (not purely cryptographic, but critical in design).
• Non-repudiation: a sender cannot later deny a valid signature.

Important: encryption alone does not provide integrity. A ciphertext can be malleable even if its plaintext is hidden. This is why modern systems use authenticated encryption (AEAD) instead of "encrypt then hope."

2) Threat models: define the attacker before the defense

Security claims are only meaningful relative to an attacker model. A useful threat model has three parts:

1. Capabilities: passive eavesdropping vs active modification; online vs offline; chosen-input access to encryption or decryption oracles.
2. Goals: recover plaintext, forge messages, impersonate, or just distinguish real data from random.
3. Constraints: time, compute, storage, and acceptable probability of success.

Common attacker classes:

• CPA (chosen-plaintext attack): attacker can encrypt chosen messages.
• CCA (chosen-ciphertext attack): attacker can decrypt chosen ciphertexts (except the challenge).
• KPA (known-plaintext attack): attacker sees some plaintext/ciphertext pairs.
• Passive vs active: observation only vs modification and injection.

If you do not define the attacker, you cannot evaluate a design. This is the first question you should ask in any crypto review.

3) Security levels and work factors

Cryptography uses computational security: breaking the scheme is not mathematically impossible, just infeasible given current resources.

Key idea: we quantify security by work factor (roughly, the number of operations to break a scheme) and compare it to real-world budgets.

• Preimage resistance of a b-bit hash: ~2^b work to invert.
• Collision resistance of a b-bit hash: ~2^(b/2) work (birthday bound).
• Symmetric keys: k-bit security is ~2^k work.
• Asymmetric keys: security depends on algorithm (e.g., RSA, ECC), not just key length.

Rule of thumb: 128-bit security is a strong modern baseline for symmetric primitives; 256-bit for long-term or post-quantum margins.

4) Randomness and entropy (where most systems fail)

Good crypto is not just "random-looking"; it is unpredictable to the attacker. Statistical randomness is not enough if the attacker can predict future outputs.

Key concepts:

• Uniformity: every value is equally likely.
• Unpredictability: even after observing outputs, the next output is still hard to predict.
• Entropy: a measure of uncertainty. Min-entropy focuses on the most likely outcome and is the relevant notion for security.

A classic mistake is modulo bias: mapping uniform 64-bit values to [0,n) by x % n is biased unless 2^64 is divisible by n. The fix is rejection sampling: throw away values in the "bias tail" and retry.

5) One-time pad and key reuse

The one-time pad is information-theoretically secure (perfect secrecy), but only if:

• the key is truly random,
• the key is as long as the message, and
• the key is used exactly once.

If the same key is reused, the system collapses:

c1 = p1 XOR k c2 = p2 XOR k c1 XOR c2 = p1 XOR p2

If an attacker knows or guesses one plaintext, the other is immediately recovered. This idea reappears in many modern failures (nonce reuse in stream ciphers, reused IVs in CTR, etc.).

6) Determinism vs probabilistic encryption

Deterministic encryption leaks equality patterns (same plaintext -> same ciphertext). Secure modern encryption is probabilistic: randomness or a nonce is mixed into the encryption so repeated messages look different.

If the randomness is reused or predictable, security drops back to the deterministic case. This is why correct nonce management is a security requirement, not an implementation detail.

7) Implementation pitfalls (even if the math is perfect)

Correct math is not enough. Implementations leak.

• Timing leakage: early exits or branches can reveal secrets.
• Error oracles: different error messages become decryption oracles.
• Padding and parsing: malformed inputs can reveal internal structure.
• State reuse: nonces or keys reused across messages.

Security is an end-to-end property. A sound algorithm inside a leaky protocol is still broken.

What you will build

1. Toy PRNG: XorShift64* - implement a deterministic generator and see why "looks random" is not the same as "unpredictable."
2. Unbiased modulo reduction - use rejection sampling to remove bias.
3. Birthday collision threshold - compute how many samples break collision resistance for a hash size.
4. Two-time pad recovery - recover a plaintext when a one-time pad key is reused.

Key takeaways

• Start with explicit goals and threat models.
• Security levels are about work factor, not key size alone.
• Randomness is about unpredictability, not just distribution.
• Reuse of secrets (keys, nonces, IVs) is catastrophic.
• Real-world security depends on implementations and protocol details.

In the next modules, we will build concrete primitives and protocols on top of these foundations.