02 — Cryptography Fundamentals

Concepts, vocabulary, adversary models, principles, and security definitions. Prerequisite for understanding all the other files in the compendium.

---

1. Basic vocabulary

---

2. Kerckhoffs's principles (1883)

Auguste Kerckhoffs, La Cryptographie Militaire (Journal des Sciences Militaires, vol. IX, 1883):

1. The system must be practically, if not mathematically, indecipherable.
2. It must not require secrecy; it may fall into enemy hands without inconvenience. ⭐ — the canonical principle.
3. Its key must be communicable and memorizable without notes, and changeable at will.
4. It must be applicable to telegraphic correspondence.
5. It must be portable, and its use must not require more than one person.
6. The system must be easy to use, with no mental strain or knowledge of a long list of rules.

Bruce Schneier's modern restatement: "Security through obscurity is no security". Shannon's restatement: "The enemy knows the system".

---

3. Shannon's principles (1949)

Claude Shannon, Communication Theory of Secrecy Systems (Bell System Technical Journal 28, 1949):

Perfect secrecy

A cipher has perfect secrecy if for all P, P', and C:

The ciphertext gives no information about the plaintext. Shannon's theorem: perfect secrecy requires \(|K| \geq |M|\) — a key at least as long as the message. The One-Time Pad is the only practical realization, with a truly random key, of the same size, used once.

Confusion and diffusion

• Confusion: the relationship between key and ciphertext must be complex and non-linear. Each ciphertext bit depends on many key bits.
• Diffusion: the relationship between plaintext and ciphertext must be spread out. One plaintext bit affects many ciphertext bits (avalanche).

Modern block ciphers alternate layers of substitution (S-boxes — confusion) and permutation/mixing (P-boxes or matrix multiplication — diffusion). SPN structure (Substitution-Permutation Network — AES) or Feistel (DES).

---

4. Adversary models

In increasing order of power:

Hierarchy: COA ⊂ KPA ⊂ CPA ⊂ CCA1 ⊂ CCA2.

Security definitions IND-* / SUF-* / EUF-*

IND-CPA game (intuition):

1. The adversary chooses two messages \(m_0\), \(m_1\) of the same size.
2. The challenger draws a random \(b \in \{0,1\}\) and sends \(C = E_k(m_b)\).
3. The adversary tries to guess \(b\).
4. The cipher is IND-CPA secure if \(\Pr[\text{adv guesses}] - 1/2\) is negligible in \(\lambda\).

---

5. One-way and trapdoor functions

---

6. Theoretical models

Random Oracle Model (ROM)

Bellare + Rogaway (CCS '93). We treat a hash as an ideal random function: each new query returns a uniformly random value. ROM proofs give a heuristic guarantee — a scheme secure in the ROM may be secure with a real hash, but it is not guaranteed (Canetti-Goldreich-Halevi 1998 showed artificial counterexamples).

Standard Model

No idealized oracles. Proofs are harder but more convincing. Schemes like RSA-OAEP, Cramer-Shoup, Boneh-Boyen have standard-model versions.

Generic Group Model

The adversary can only use group operations (multiplication, exponentiation) without exploiting the representation. Used to prove lower bounds (Shoup 1997, Maurer 2005).

Universal Composability (UC)

Canetti 2001. A framework for proving compositional security: if F is UC-secure, it is secure within any larger protocol. Ideal for multi-party protocols.

---

7. Cryptography hierarchy

Symmetric vs asymmetric

By purpose

• Confidentiality: encryption (AES, ChaCha20, RSA-OAEP, ECIES).
• Integrity: hash, MAC (HMAC, KMAC, Poly1305, CMAC).
• Authenticity: MAC, digital signature.
• Non-repudiation: digital signature (not MAC — anyone with the MAC key can forge).
• Freshness: nonces, timestamps, sequence numbers.
• Anonymity: ring signatures, group signatures, mix-nets.
• Computational privacy: FHE, MPC, ZKP.

---

8. Security levels

Conventionally measured in bits — meaning: the best known attack takes \(2^n\) operations.

Equivalence rule (classical, NIST SP 800-57):

---

9. Randomness generation

Entropy sources

• Hardware: ring oscillators, thermal noise, shot noise, Intel RDRAND, ARM TRNG.
• OS pooling: Linux getrandom(2), /dev/urandom, /dev/random; macOS SecRandomCopyBytes; Windows BCryptGenRandom.
• User input: keyboard and mouse timing — relevant at initial boot and in VMs.

CSPRNGs

• AES-CTR DRBG (NIST SP 800-90A) — AES output in CTR mode.
• HMAC-DRBG (NIST SP 800-90A) — popular.
• Hash-DRBG (NIST SP 800-90A).
• Fortuna (Schneier, 2003) — used in FreeBSD.
• ChaCha20-based — Linux since 4.8 (2016).
• DualECDRBG ❌ — the original NIST SP 800-90A included it. NSA backdoor suspected and later confirmed (Snowden); removed in 2014.

Rules

• Never use Math.random(), rand(), random(), srand(time()).
• Always use the OS cryptographic API (getrandom, BCryptGenRandom).
• Seed carefully after boot — cloned VMs, embedded, and IoT are vulnerable (Mining Your Ps and Qs, Heninger et al. 2012; ROCA).

---

10. Modern design principles

"Don't roll your own crypto"

Implementing primitives is easy; implementing them securely (no side-channels, no subtle bugs) is extremely hard. Use audited libraries:

• libsodium (high-level, secure by default).
• NaCl (predecessor of libsodium, DJB).
• BoringSSL (Google's fork of OpenSSL).
• OpenSSL 3.x (with the FIPS provider when required).
• Tink (Google, high-level).
• Ring (Rust, fork of BoringSSL).
• age (file encryption, Filippo Valsorda).

Constant-time

All code that touches a secret must execute in time independent of the secret: no branches on a secret, no table lookups indexed by a secret, no variable-time multiplications on old CPUs. Bernstein is the evangelist. AES-NI helps (dedicated instructions).

Misuse-resistance

APIs should make incorrect use hard:

• NaCl/libsodium — only crypto_secretbox (authenticated), no raw ECB.
• AES-GCM-SIV (Gueron-Lindell) — degrades gracefully under nonce reuse.
• Tink — versioned keysets, built-in rotation.

Defense in depth

Redundant layers. E.g.: TLS + HSTS + HPKP (legacy) / CT (Certificate Transparency); LUKS + dm-verity; signed binaries + boot guard.

Hybrid (classical + PQC)

Combine an established classical algorithm + a new PQC one. An attack must break both. Standard during the transition (X25519MLKEM768 = X25519 ⊕ ML-KEM-768).

---

11. Proof methods

---

12. Who trusts what (chain of trust)

Each link is a possible point of compromise. Confidential Computing tries to shorten the chain by isolating the workload from the host.

---

13. Cultural differences: "American" vs "European" cryptography

---

14. Relevant standards

---

15. Essential bibliography

• Katz + Lindell, Introduction to Modern Cryptography, CRC Press, 3rd ed. 2020 — the standard undergraduate/graduate text.
• Boneh + Shoup, A Graduate Course in Applied Cryptography — free at toc.cryptobook.us.
• Menezes, van Oorschot, Vanstone, Handbook of Applied Cryptography (CRC) — a technical classic, free at cacr.uwaterloo.ca/hac/.
• Schneier, Applied Cryptography, 1996 (dated but a cultural reference).
• Aumasson, Serious Cryptography, No Starch Press 2017 — a modern practical reference.
• Ferguson + Schneier + Kohno, Cryptography Engineering, Wiley 2010.
• Bernstein, Lange, et al., Post-Quantum Cryptography, Springer 2009 (handbook).
• Goldreich, Foundations of Cryptography, 2 volumes Cambridge — theoretical, dense.

Online

• IACR ePrint Archive: eprint.iacr.org
• Real World Crypto Symposium proceedings
• CFRG (Crypto Forum Research Group) IETF
• Cryptography Stack Exchange (community Q&A)
• David Wong, Real-World Cryptography (Manning 2021)
• Filippo Valsorda blog filippo.io
• Trail of Bits blog, NCC Group Cryptography Services