1.
1 Overview of Cryptology
● Cryptology = umbrella term. It splits into:
○ Cryptography (designing methods to keep messages secret).
○ Cryptanalysis (studying and breaking cryptosystems). Modern cryptography
relies on cryptanalysis to test and validate security; without people trying to break
systems, we can’t trust them.
● Main branches of cryptography:
○ Symmetric algorithms: same secret key for encrypt/decrypt; historically all
cryptography until 1976; still used widely for encryption & integrity.
○ Asymmetric (public-key) algorithms: introduced in 1976
(Diffie–Hellman–Merkle); each user has a public key and a private key; enables
digital signatures, key establishment, and encryption.
○ Cryptographic protocols: combine building blocks (e.g., TLS in your browser).
● Hybrid designs: real systems mix symmetric + asymmetric (+ hash functions) to
leverage each one’s strengths.
1.2 Symmetric Cryptography
● Setting: Alice ↔ Bob over an insecure channel while an attacker (Oscar) can
eavesdrop. Encrypt plaintext x with a key k to get ciphertext y; Bob decrypts with the
same key. Key ideas/terms: plaintext x, ciphertext y, key k, key space (all possible keys).
● Key distribution: the algorithms are public; only the key must remain secret (and must
be securely shared/stored).
● Security goals beyond secrecy (later in the course): integrity and authentication (e.g.,
“message integrity”, “sender authentication”).
● Toy example—substitution cipher:
○ Replace each letter with another (random permutation). It’s great for illustrating
attacks, but it’s insecure.
○ Brute-force (exhaustive key search): try every key until decrypted text matches
known plaintext; formalized as checking d (y) ?= x over all keys.
○ Analytical attack—letter frequency analysis: exploits that a fixed substitution
preserves statistics (e.g., ‘E’ is common in English), so ciphers fall quickly despite
huge key spaces. (This is emphasized across the section and summarized in the
index entry).
1.3 Cryptanalysis
● Ways to break systems (high-level map):
○ Classical cryptanalysis: brute-force and structure-exploiting analytical attacks.
○ Implementation (side-channel) attacks: recover keys by observing power, EM
radiation, timing, etc. (especially with physical access devices like smart cards).
○ Social engineering: trick/bribe/coerce humans into revealing secrets (e.g., fake
“IT” phone calls). Security fails at the weakest link.
● Kerckhoffs’ Principle (must know!): the system must remain secure even if the attacker
knows everything about it except the key (security by obscurity is unsafe).
● How many key bits are enough? (when brute-force is the best known attack):
○ 56–64 bits: short-term (hours/days).
○ 112–128 bits: long-term (decades) absent quantum computers.
○ 256 bits: long-term even considering known quantum algorithms. Also, ~80-bit
symmetric ≈ ~1024-bit RSA in “security level”.
Quick study notes (exam-oriented)
Key terms
● Cryptology = cryptography + cryptanalysis; hybrid schemes mix symmetric &
asymmetric.
● Symmetric crypto: same secret key; public algorithms, private keys; challenge: key
distribution.
● Cryptanalysis buckets: classical (brute-force/analytical), side-channel, social
engineering; defend weakest link.
Must-remember principles
● Kerckhoffs’ Principle: assume attacker knows your algorithm; only the key is secret.
● Big lesson from substitution cipher: huge key space ≠ secure; structure leaks (letter
frequencies) enable fast breaks.
● Key lengths: 128-bit symmetric is the practical “sweet spot” today; 256-bit gives extra
margin; symmetric vs. asymmetric bit lengths are not directly comparable.
Common pitfalls to avoid
● Relying on “secret algorithms” or proprietary designs (security by obscurity).
● Assuming only math attacks matter—humans and implementations often break first.
Fast self-check (you should be able to answer):
1. Define cryptography vs. cryptanalysis and give one example of each.
2. Why is a substitution cipher broken by frequency analysis even with ~2⁸⁸ keys?
(Because mapping is fixed; stats leak.)
3. State Kerckhoffs’ Principle in one sentence.
4. What security horizon do 56–64, 112–128, and 256-bit symmetric keys roughly provide?
1.4 Modular Arithmetic and More Historical
Ciphers
Why this section matters
● The authors use classical ciphers (Caesar, affine) to introduce modular
arithmetic—the math you’ll need everywhere later, especially in public-key crypto.
Mini-module on modular arithmetic (the essentials)
● Definition (congruence / “mod”): For integers a, r, and modulus m>0,
a ≡ r (mod m) iff m | (a−r). Think: “divide by m and look at the remainder,” but formally.
● Equivalence classes: Numbers that differ by multiples of m are in the same class (e.g.,
for m=9, …, −6, 3, 12, 21, …). This is why the clock analogy works so well.
● Rings Zm: With + and × “mod m,” results stay in Zm (closure). You’ll use ring facts
constantly when you invert elements, define keys, etc.
Classical ciphers, written “mod m”
● Shift/Caesar cipher: Map letters to numbers (A→0,…,Z→25) and encrypt with
y ≡ x + k (mod 26); decrypt with x ≡ y − k (mod 26).
● Affine cipher (generalizes shift):
y ≡ a·x + b (mod 26); decrypt x ≡ a⁻¹·(y−b) (mod 26). The key is k=(a,b) with
gcd(a,26)=1 (so a has an inverse mod 26).
Security takeaways from the classics
● Shift & affine are insecure: tiny key spaces → brute-force; and, like substitution, fixed
letter mapping leaks frequency structure. Great for learning; not for real security.
1.5 Discussion and Further Reading (what
the authors suggest)
● The book targets practical crypto for class/self-study and ends each chapter with
pointers for deeper dives.
● For historical ciphers and their impact: Bauer, Kahn, and Singh are
recommended—excellent context and “bedtime reading.” The section also points to
standard intros to number theory.
1.6 Lessons Learned (author’s checklist)
● Don’t roll your own crypto; even pros rely on cryptanalyst review.
● Don’t use unproven algorithms/protocols. Stick to vetted standards.
● Attackers hit the weakest link: a big key space doesn’t save you from analytical or
non-brute-force attacks.
● Key-length intuition: the section contrasts 128/256-bit-style margins and notes the
quantum angle at a high level. (You’ll see formal tables later in the book.)
● Modular arithmetic is your compact language for describing/analysing even “toy”
schemes like the affine cipher—skills you’ll reuse for RSA/ECC.
Quick midterm notes (skim this)
Core math
● a ≡ r (mod m) ⇔ m | (a−r); numbers form equivalence classes modulo m; computations
happen in rings Zm (closure under +, ×).
Cipher formulas to know
● Caesar: y ≡ x + k (mod 26); x ≡ y − k (mod 26).
● Affine: y ≡ a·x + b (mod 26); x ≡ a⁻¹·(y−b) (mod 26); require gcd(a,26)=1.
Security morals
● Big key space ≠ secure if structure leaks (frequency attacks beat substitution/affine).
● Use standardized, analyzed primitives; don’t invent your own.
Further reading (names to drop)
● Bauer, Kahn, Singh for history; standard number-theory intros referenced by the authors.
1-minute self-check
1. Define a ≡ r (mod m) and give a quick example of an equivalence class.
2. Write Caesar and affine encryption and the affine invertibility condition.
3. Give two reasons shift/affine are insecure.
Mini-lecture: Chapter 2 — Stream Ciphers
What a stream cipher is (and how it differs from a block
cipher)
● A stream cipher encrypts one symbol at a time (often 1 bit/byte) by XORing the
plaintext with a keystream produced from a secret key (and usually a nonce/IV).
Security rides entirely on the keystream being unpredictable. In contrast, block ciphers
act on fixed-size blocks and need modes (CBC/CTR/GCM) to handle longer data.
(SpringerLink)
● XOR (mod-2 addition) is perfect here: it’s fast, invertible with the same operation, and if
the keystream is random, each ciphertext bit is equally likely to be 0 or 1.
([Link])
Two flavors: synchronous vs. self-synchronizing
● Synchronous: keystream depends only on key (+ nonce/IV). Sender and receiver must
stay in lockstep; bit flips don’t propagate.
● Self-synchronizing (asynchronous): keystream also depends on previous ciphertext;
can resync after losses, but bit errors can propagate for a while. ([Link])
Randomness pipeline (RNG → PRNG/DRBG →
keystream)
● True RNG (TRNG) harvests physical noise (jitter, radioactivity, etc.). Great for
keys/nonces, but slow/irregular.
● PRNG stretches a short seed into many bits; a CSPRNG/DRBG adds unpredictability
(next-bit infeasibility). In practice, stream ciphers rely on a DRBG-like construction
internally. ([Link])
The One-Time Pad (OTP): perfect but impractical
● Encrypt bitwise: (c_i = p_i \oplus k_i); decrypt with the same XOR.
● Perfect secrecy if the key is truly random, at least as long as the message, and never
reused. It’s typically impractical because distributing/storing one key per message is
painful. (Reusing the pad is catastrophic—“two-time pad”.) ([Link])
LFSRs (Linear Feedback Shift Registers): fast but
predictable alone
● Hardware-friendly shift registers with XOR feedback; period up to (2^m-1) for degree (m)
with a primitive feedback polynomial.
● Alone they’re predictable (linear); observing about (2m) output bits lets an attacker
recover the LFSR. Hence real designs combine multiple LFSRs and add nonlinearity.
([Link])
● Trivium: a compact, modern stream cipher built from (non-linear) shift registers;
designed to be small in hardware. ([Link])
Performance & examples
● Stream ciphers are often extremely fast in software/hardware; classic example: RC4
(historically very fast, now deprecated due to biases/attacks). Slides compare throughput
vs DES/AES to highlight speed. ([Link])
What the chapter covers at a glance (for
orientation)
● “Stream Ciphers” is explicitly Chapter 2 in the book’s TOC; content = intro to stream
ciphers, RNGs, OTP, LFSRs, and a modern design (Trivium). (SpringerLink)
Midterm-ready notes (skim these)
Core formulas & definitions
● Encryption: (C = P \oplus S) (S = keystream); Decryption: (P = C \oplus S). If S is
indistinguishable from random and never reused with the same key/nonce, confidentiality
holds. ([Link])
● Synchronous vs. self-synchronizing stream ciphers—know the
resynchronization/error-propagation trade-off. ([Link])
● RNG vs PRNG vs CSPRNG: TRNG = entropy source; PRNG = deterministic expander;
CSPRNG = PRNG with unpredictability (next-bit test). ([Link])
● OTP: perfect secrecy only if key is truly random, as long as message, single use.
([Link])
● LFSR: period ≤ (2^m−1); linear ⇒ predictable from ~(2m) bits; combine multiple and add
nonlinearity (e.g., Trivium). ([Link])
Do’s & Don’ts (high-yield)
● Do use a nonce/IV once per key; don’t ever reuse keystream (two-time pad leak).
(Equal ciphertexts or (C_1 \oplus C_2 = P_1 \oplus P_2) reveals plaintext relations.)
([Link])
● Do seed your CSPRNG from a real OS RNG; don’t invent your own RNG.
([Link])
● Do assume an active attacker; don’t rely on “looks random”—you want unpredictable
keystreams and, in practice, authenticated encryption (AEAD) when possible. (AEAD
is covered later, but mention it as best practice.)
Quick self-check (exam style)
1. Why is XOR the natural combiner for stream ciphers? (invertible, linear, and hides bits if
keystream is random.) ([Link])
2. State the three OTP conditions for perfect secrecy and one reason it’s impractical.
([Link])
3. Define TRNG vs PRNG vs CSPRNG; which do you seed from the OS and which do you
run for bulk keystream? ([Link])
4. What’s the period upper bound of a degree-(m) LFSR and why isn’t a single LFSR
secure? ([Link])
4.1 Introduction (why AES and how it’s
structured)
● AES (Rijndael) is the modern symmetric block cipher standard.
● Block size: 128 bits (fixed). Key sizes: 128, 192, 256 bits.
● Rounds (depend on key length):
○ AES-128: 10 rounds, AES-192: 12, AES-256: 14.
● State representation: a 4×4 matrix of bytes (“state”), filled column-wise from the
16-byte block.
● High-level round structure:
○ Initial: AddRoundKey
○ Rounds 1…Nr−1: SubBytes → ShiftRows → MixColumns → AddRoundKey
○ Final round: SubBytes → ShiftRows → AddRoundKey (no MixColumns)
● Design goal: fast on a wide range of platforms, strong against known attacks (esp.
differential & linear cryptanalysis), and easy to implement in constant time.
4.2 Overview of the AES Algorithm (the
four steps + key schedule)
The four round transformations
1. SubBytes (nonlinear S-box)
○ Byte-wise substitution with a fixed 8→8-bit S-box.
○ Constructed as: multiplicative inverse in GF(2^8) (0 maps to 0), then a fixed
affine transform over GF(2).
○ Purpose: provide nonlinearity and good resistance to differential/linear attacks.
2. ShiftRows (intra-row permutation)
○ Row 0: shift by 0; Row 1: left by 1; Row 2: left by 2; Row 3: left by 3 (bytes wrap
around).
○ Purpose: spread bytes across columns to help diffusion.
3. MixColumns (linear diffusion over GF(2^8))
○ Treat each column as a 4-byte vector and multiply by a fixed MDS matrix in
GF(2^8):
[
\begin{bmatrix}
02 & 03 & 01 & 01\
01 & 02 & 03 & 01\
01 & 01 & 02 & 03\
03 & 01 & 01 & 02
\end{bmatrix}
]
○ Multiplications by 02 and 03 are done in GF(2^8) (see “xtime” note below).
4. AddRoundKey (key mixing)
○ XOR the state with the round key (derived from the master key).
○ Only operation that directly involves the key material.
Key schedule (round keys)
● Input: master key of 128/192/256 bits (Nk = 4/6/8 32-bit words).
● Output: (Nr+1) round keys, each 16 bytes.
● Core operations:
○ RotWord: rotate a 4-byte word by 1 byte.
○ SubWord: apply the S-box to each byte.
○ Rcon: round constants injected once per round (in the first word of each round’s
expansion) to break symmetries.
● AES-256 also uses an extra SubWord on every 4th word of each 8-word block in the
schedule.
Implementation notes (you’ll see these in labs/exams):
● xtime(a): multiply byte a by 2 in GF(2^8): left-shift by 1; if the msb was 1, XOR with
0x1B (because reduction is mod the AES irreducible polynomial 0x11B).
● Multiply by 3: 3·a = (2·a) ⊕ a = xtime(a) ⊕ a.
4.3 Some Mathematics: A Brief
Introduction to Galois Fields (what you
need for AES)
Fields you’ll meet
● GF(p): integers modulo a prime p (addition/multiplication mod p).
● GF(2^n): polynomials with coefficients in GF(2), modulo an irreducible polynomial of
degree n.
Bytes as polynomials (GF(2^8))
● A byte b7…b0 represents the polynomial ( b_7x^7 + \cdots + b_1x + b_0 ) with
coefficients in {0,1}.
● Addition: XOR of coefficients (bitwise XOR).
● Multiplication: polynomial multiply, then reduce modulo an irreducible degree-8
polynomial.
● AES chooses: (m(x)=x^8+x^4+x^3+x+1) (hex 0x11B). That’s why xtime reduces with
0x1B when the carry falls off the high bit.
Why GF(2^8) matters in AES
● SubBytes: uses the multiplicative inverse in GF(2^8), then an affine map.
● MixColumns: is matrix multiplication where each entry is in GF(2^8).
● AddRoundKey: still ordinary XOR (same as addition in GF(2^8)).
● Takeaway: once you’re comfy with “bytes = polynomials” and “reduce mod 0x11B,” AES
operations feel mechanical.
Midterm-ready notes (skim these)
AES parameters
● Block = 128 bits; Keys = 128/192/256; Rounds = 10/12/14.
Round flow
● Initial AddRoundKey → (Nr−1)×[SubBytes, ShiftRows, MixColumns, AddRoundKey] →
Final [SubBytes, ShiftRows, AddRoundKey].
S-box recipe
● (S(b) = \text{Affine}(\text{Inv}_{GF(2^8)}(b))), with 0 → 0; gives nonlinearity and good
differential/linear profiles.
MixColumns matrix
● Multiply each column by the fixed 4×4 matrix with entries {02,03,01,01} over GF(2^8).
● Fast rules: 2·a = xtime(a), 3·a = xtime(a) ⊕ a.
Key schedule cues
● RotWord, SubWord, Rcon; AES-256 does an extra SubWord on every 4th word.
GF(2^8) essentials
● Bytes ↔ polynomials over GF(2).
● Reduce by 0x11B.
● Addition = XOR; inverse exists for all nonzero elements (needed for S-box).
Quick self-check (answer in a sentence)
1. Why does AES need GF(2^8) at all?
Because SubBytes (inversion) and MixColumns (matrix multiply) are defined over
GF(2^8), which lets us do algebra on bytes with good diffusion/nonlinearity.
2. What’s xtime and why 0x1B?
xtime(a) = multiply by 2 in GF(2^8); if the left shift overflows, reduce by AES’s
polynomial (x^8+x^4+x^3+x+1) → XOR with 0x1B.
3. Which step is omitted in the final round and why?
MixColumns is omitted; the structure still ensures diffusion while keeping decryption
(and structure) tidy.
4. How is the S-box built and what property does that give?
GF(2^8) inversion + affine map → strong nonlinearity and resistance to linear/differential
cryptanalysis.
4.4 Internal Structure of AES (what’s really
inside a round)
State as a 4×4 byte matrix. AES works on 16 bytes arranged column-wise. Every round
transforms this matrix to diffuse and confuse information.
Round = 4 steps (except the last):
1. SubBytes — nonlinearity
○ Each byte goes through the S-box: compute multiplicative inverse in GF(2^8)
(0→0) then apply a fixed affine transform.
○ Purpose: defeat linear/differential attacks (gives strong “confusion”).
2. ShiftRows — inter-column shuffling
○ Row shifts by 0,1,2,3 bytes to spread S-box effects across columns.
3. MixColumns — column diffusion
○ Treat each column as a 4-byte vector and multiply by a fixed 4×4 matrix over
GF(2^8).
○ Fast rules: 2·a = xtime(a); 3·a = xtime(a) ⊕ a.
4. AddRoundKey — key mixing
○ XOR the state with the round key from the key schedule.
Key schedule (why round keys look “random”)
● From a 128/192/256-bit master key, AES derives Nr+1 round keys.
● Operations: RotWord (byte rotate), SubWord (S-box per byte), and Rcon (round
constants) injected to break symmetry.
● AES-256 has an extra SubWord on every 4th word (slows key XOR patterns).
Design vibe: byte-oriented, simple operations (lookup, XOR, shifts, finite-field multiplies) that
map well to software and hardware.
4.5 Decryption (the inverse pipeline)
Decryption uses inverse steps in reverse order:
● Start from the last round key and go: AddRoundKey → InvShiftRows → InvSubBytes
→ InvMixColumns (for all but the final round), finishing with AddRoundKey after
InvShiftRows → InvSubBytes in the last round (no InvMixColumns there).
Inverse components:
● InvShiftRows: rotate rows right by 0,1,2,3.
● InvSubBytes: inverse S-box (inverse affine, then multiplicative inverse).
● InvMixColumns: multiply by the inverse matrix (coeffs 0x0E, 0x0B, 0x0D, 0x09 in
GF(2^8)).
Practical trick: many implementations precompute decryption round keys already multiplied by
InvMixColumns to keep the same operation order per round and speed up code.
4.6 Implementation in Software and
Hardware (how people actually ship AES)
Software paths
● T-tables (classic): precompute the combined effect of
SubBytes+ShiftRows+MixColumns into 4 tables of 256 32-bit words; each round
becomes a handful of table loads and XORs.
○ Pro: fast on old CPUs. Con: table lookups leak through cache-timing side
channels; avoid in new code unless you’re mitigating.
● Bitslicing: express AES as boolean ops on many blocks in parallel; constant-time by
construction, great for side-channel resistance and SIMD throughput.
● AES-NI / ARMv8 AES: dedicated CPU instructions for SubBytes/MixColumns rounds
and keygen—fast and constant-time; the modern default.
● Constant-time discipline: no secret-dependent branches or memory accesses;
compare tags in constant time; zeroize keys.
Hardware paths
● Iterative core (area-saving): 1 round per cycle (or a few cycles), reusing the same
round hardware → small area, moderate throughput.
● Fully unrolled / pipelined: all rounds instantiated with pipeline registers → very high
throughput (Gb/s+), larger area.
● S-box choices: LUT vs composite-field arithmetic (GF((2^4)^2)) to save gates.
● Side-channels: add masking, hiding, or dual-rail logic for power/EM resistance.
4.7 Discussion and Further Reading
(where to look next)
● Primary specs: NIST FIPS-197 (AES standard) and the original Rijndael paper/book
(Daemen & Rijmen) explain design rationale, S-box construction, and proofs of basic
properties.
● Security landscape: learn about linear/differential cryptanalysis resistance, related-key
observations on the AES-256 schedule (the cipher remains secure in practice), and
abundant side-channel literature (cache, timing, power).
● Implementation guidance: NIST SP 800-38 series (modes), NIST SP 800-38D (GCM),
plus practical guides on constant-time coding and microarchitecture pitfalls.
4.8 Lessons Learned (what exam
questions love)
● Structure matters: combining a strong S-box (nonlinearity) with linear diffusion
(ShiftRows+MixColumns) gives fast avalanche and frustrates classic attacks.
● Key mixing every round is essential—AddRoundKey ties diffusion/confusion to secret
material each step.
● Math under the hood: viewing bytes as GF(2^8) elements explains S-box and
MixColumns mechanics; once you “think in the field,” AES becomes predictable to
compute by hand.
● Security ≠ just the permutation: modes (GCM/CTR/CBC) and nonce discipline
determine real-world confidentiality; prefer AEAD.
● Implementation is security: constant-time code, AES-NI/ARM AES, and side-channel
countermeasures beat clever but leaky table tricks.
● Choose the right trade-offs: software vs hardware, iterative vs unrolled, lookup vs
composite-field—all are about area/latency/throughput and leakage.
Midterm-ready notes (skim)
Parameters & rounds
● Block: 128b. Keys: 128/192/256 → Rounds: 10/12/14.
Round flow
● Init AddRoundKey → (Nr−1)×[SubBytes, ShiftRows, MixColumns, AddRoundKey] →
Final [SubBytes, ShiftRows, AddRoundKey].
S-box recipe
● (S(b)=\text{Affine}(\text{Inv}_{GF(2^8)}(b))), (S(0)=0).
MixColumns shortcuts
● 2·a = xtime(a); 3·a = xtime(a) ⊕ a. Decrypt uses 0x0E/0x0B/0x0D/0x09.
Key schedule cues
● RotWord, SubWord, Rcon; extra SubWord every 4th word in AES-256.
Decryption order
● Start from last round key: AddRoundKey → InvShiftRows → InvSubBytes →
(InvMixColumns except final) … end with AddRoundKey.
Software
● Prefer AES-NI/ARM AES or bitslicing (constant-time). Avoid cache-leaky T-tables unless
mitigated.
Hardware
● Iterative (small) vs pipelined (fast). Consider composite-field S-boxes and side-channel
countermeasures.
Don’t forget modes
● Use AEAD (AES-GCM). Nonces must be unique per key.
Quick self-check (one-liners)
1. Why omit MixColumns in the final round?
To keep decryption symmetric/simple while preserving sufficient diffusion from earlier
rounds.
2. What makes the S-box nonlinear?
GF(2^8) inversion (nonlinear) followed by an affine map.
3. One practical reason T-tables fell out of favor?
Cache-timing side channels—table index depends on secret-derived bytes.
4. How does decryption change the coefficients in the column mix?
Use the inverse matrix with coefficients {0x0E, 0x0B, 0x0D, 0x09} over GF(2^8).
UC §5.1 Encryption with Block Ciphers: Modes of Operation—plus compact study notes
you can skim before your exam.
Class explanation
Why “modes”?
A block cipher (e.g., AES) transforms one fixed-size block. Real messages are longer or oddly
sized, so we “wrap” the cipher in a mode of operation to handle multi-block data securely. UC
introduces five core modes—ECB, CBC, CFB, OFB, CTR—and previews authenticated
encryption with GCM (encrypt + integrity). Some modes need padding when the message
length isn’t a multiple of the block size (UC notes this explicitly and even gives a simple 1||0…0
padding example).
1) ECB — Electronic Codebook
Idea. Encrypt each block independently: (y_i = e_k(x_i)). Decrypt with (x_i = e_k^{-1}(y_i)).
Pros. Simple, parallelizable; bit errors don’t propagate.
Fatal con. Deterministic: equal plaintext blocks (\rightarrow) equal ciphertext blocks (leaks
patterns; enables traffic analysis and cut-and-paste rearrangements). UC even shows the
famous “ECB penguin” effect/pattern leakage and stresses that we generally want probabilistic
encryption (randomized with an IV).
Exam mantra: “ECB = patterns leak → don’t use for data beyond a single random
block.”
2) CBC — Cipher Block Chaining
Idea. Chain blocks with XOR; randomize with an IV.
Encrypt:
● First block: (y_1 = e_k(x_1 \oplus IV))
● Next blocks: (y_i = e_k(x_i \oplus y_{i-1}))
Decrypt (reverse the two steps):
● First: (x_1 = e_k^{-1}(y_1) \oplus IV)
● Next: (x_i = e_k^{-1}(y_i) \oplus y_{i-1}).
Notes.
● Fresh, unpredictable IV as a nonce → probabilistic encryption (same plaintext, different
ciphertexts).
● You can transmit the IV in the clear; decryption needs to know it.
● If you (incorrectly) reuse a constant IV, first ciphertext blocks repeat and leak sameness
across messages.
● Padding often required for the last partial block (e.g., PKCS#7/RFC 5652).
Parallelism. Encryption is sequential; decryption can be parallelized per block given previous
ciphertexts.
Integrity. CBC encryption alone doesn’t authenticate; malicious flips cause randomized but
meaningful changes to plaintext on decrypt, motivating MAC/AEAD (e.g., GCM).
3) OFB — Output Feedback (stream-cipher style)
Idea. Turn the block cipher into a synchronous stream cipher: start from an IV, encrypt it to
get a keystream block (s_1), XOR with plaintext (x_1) to get (y_1); then repeatedly encrypt the
previous keystream value to get (s_2, s_3, …) (cipher output feeds back).
Formulas.
● First: (s_1 = e_k(IV),; y_1 = s_1 \oplus x_1)
● General: (s_i = e_k(s_{i-1}),; y_i = s_i \oplus x_i) (same for decrypt).
Notes.
● Same encrypt/decrypt (XOR with keystream); precompute keystream; requires
nonce-style IV.
● Bit flips in ciphertext flip corresponding plaintext bits (no error spread). Still no integrity.
4) CFB — Cipher (Ciphertext) Feedback (stream-cipher
style)
Idea. Like OFB but feed back the ciphertext (asynchronous stream cipher). First keystream
from (e_k(IV)), then (e_k(y_{i-1})) for later blocks.
Formulas.
● First: (y_1 = e_k(IV)\oplus x_1)
● General: (y_i = e_k(y_{i-1})\oplus x_i) (and same XOR for decrypt).
Notes.
● Supports narrow-width feedback (e.g., 8-bit for keystrokes), shifting ciphertext into a
register.
● Needs a nonce-style IV; still no integrity.
5) CTR — Counter Mode (stream-cipher style)
Idea. Keystream = encrypt counter blocks; XOR with plaintext. Input is (IV ,|, CTR_i) (must
never repeat under a key).
Formulas. (y_i = e_k(IV ,|, CTR_i) \oplus x_i) and same for decryption.
Engineering.
● Typical AES-CTR uses a 96-bit IV + 32-bit counter → up to (2^{32}) blocks ≈ 32 GiB per
IV before you must pick a new IV.
● Highly parallelizable (no feedback), great for high-throughput systems.
● Still no integrity; combine with a MAC or use an AEAD.
GCM — Galois/Counter Mode (AEAD)
Idea. Encrypt with CTR, then compute a fast MAC (GHASH) over ciphertext and optional AAD
to give an authentication tag (T) (encrypt-then-MAC).
UC’s definition shows: derive counter from IV; compute (y_i = e_k(CTR_i)\oplus x_i). For
authentication, set (H=e_k(0)) and iterate (g_i = (g_{i-1}\oplus y_i)\times H) in (GF(2^{128}));
final tag (T = (g_n\times H)\oplus e_k(CTR_0)). Receiver recomputes and checks (T).
Takeaways. Confidentiality and integrity; widely standardized (NIST SP 800-38D).
Quick study notes (exam-ready)
● ECB: (y_i=e_k(x_i)). Leaks patterns; avoid for multi-block data.
● CBC: (y_1=e_k(x_1\oplus IV),; y_i=e_k(x_i\oplus y_{i-1})). Needs fresh nonce IV; same
plaintext + same IV → leaks sameness. Padding (e.g., PKCS#7) required. Decrypt in
parallel. No integrity—use MAC/AEAD.
● OFB: Synchronous stream cipher from (s_1=e_k(IV)), then (s_i=e_k(s_{i-1}));
(y_i=s_i\oplus x_i). Precompute keystream; IV = nonce.
● CFB: Asynchronous stream cipher; keystream from (e_k(IV)), then (e_k(y_{i-1}));
(y_i!=!keystream\oplus x_i). Byte-sized feedback variant for keyboards, etc..
● CTR: (y_i=e_k(IV ,|, CTR_i)\oplus x_i). Never reuse (IV, counter) with same key;
parallel & fast; limit data per IV (e.g., 32 GiB with 32-bit counter).
● GCM (AEAD): CTR + GHASH over ciphertext and AAD; tag (T) checked on decrypt.
Protects confidentiality and authenticity.
Common pitfalls
● Reusing IVs/nonces in CBC/CTR/GCM breaks security (pattern leaks or catastrophic
keystream reuse).
● Confusing encryption with authentication: ECB/CBC/CFB/OFB/CTR alone don’t
authenticate; use AEAD (e.g., GCM) or MAC (CMAC/HMAC).
● Padding errors in CBC (be clear on the rule you use; PKCS#7 is standard).
When to pick what (cheat-sheet)
● Don’t pick ECB for multi-block data.
● CBC if you must interop with legacy, with random IV + MAC.
● CTR for speed/parallelism, with nonce discipline + MAC.
● GCM by default today (AEAD): fast, widely supported, includes integrity.
11.1 Motivation: Signing Long Messages
Mini-lecture (what I’d say in class)
Public-key signature algorithms (RSA/DSA/ECDSA) can only sign data up to a certain size (e.g.,
RSA’s input is bounded by the modulus—hundreds of bytes), but real messages (emails, files)
are much longer. The naïve idea—split the message into blocks and sign each block—fails: it’s
computationally heavy, doubles transmission size, and is insecure (blocks can be removed,
reordered, or spliced).
The fix is “hash-then-sign”: compute a short fingerprint (z=h(x)) and sign that single hash. The
receiver recomputes (h(x)) and verifies the signature on (z).
Midterm notes
● Problem with “sign-each-block”: too slow, bloats size, vulnerable to cut–paste/reordering.
● Hash-then-sign pipeline: sender sends ((x, s=\mathrm{sig}{k{\text{pr}}}(h(x)))); receiver
checks (\mathrm{ver}{k{\text{pub}}}(s, h(x))).
● Therefore, security of signatures heavily depends on hash function properties.
11.2 Security Requirements of Hash
Functions
Mini-lecture
A cryptographic hash (h) must compress arbitrary-length input to fixed length while meeting
three core properties:
1. Preimage resistance (one-wayness): given (z), it’s infeasible to find any (x) with
(h(x)=z).
2. Second-preimage resistance (weak collision): given (x_1), infeasible to find a
different (x_2) with the same hash.
3. Collision resistance (strong collision): infeasible to find any pair (x_1\neq x_2) with
(h(x_1)=h(x_2)).
Why they matter: with weak collisions, a signed message (x_1) can be swapped for a different
(x_2) that hashes the same (signature verifies!).
The birthday attack intuition
For n-bit hashes, collisions appear after about (2^{n/2}) trials (not (2^n))—the birthday bound.
That’s why 128-bit collision security needs ~256-bit hash outputs for safety goals.
Midterm notes
● Know precise definitions: preimage / second-preimage / (strong) collision.
● Birthday bound: ~(2^{n/2}) work for a collision; motivates modern output sizes.
● In signature schemes, hash collisions ⇒ signature substitution attacks.
11.3 Overview of Hash Algorithms
Mini-lecture
Two big families:
A) Dedicated hash functions (custom designs). Classic lineage: MD4 → MD5 → SHA-0 →
SHA-1 → SHA-2 (and others like RIPEMD). They process messages in blocks using an
iterated compression function—the Merkle–Damgård (M–D) paradigm. MD4 introduced fast,
software-friendly Boolean operations; MD5 (128-bit) and SHA-1 (160-bit) followed, with
increasing strength (and later-found weaknesses).
B) Block-cipher-based hash functions. You can build a compression function from a block
cipher. Well-known constructions:
● Matyas–Meyer–Oseas: (H_i = E_{g(H_{i-1})}(x_i)\oplus x_i).
● Davies–Meyer: (H_i = H_{i-1}\oplus E_{x_i}(H_{i-1})).
● Miyaguchi–Preneel: (H_i = H_{i-1}\oplus x_i \oplus E_{g(H_{i-1})}(x_i)).
All of these are iterated (M–D style): split message into blocks, feed each with the current
chaining value into a compression function; the last chaining value is the hash.
Security sizing note. If your hash output equals the block size (b) (e.g., 128 bits), collision
security is only ~(2^{b/2}) by birthday—too low today. Options include larger block ciphers (e.g.,
Rijndael with 192/256-bit blocks) or wide-pipe constructions like Hirose that produce a (2b)-bit
hash (e.g., 256 bits from AES-128/256).
Midterm notes
● Merkle–Damgård = “compression → iterate over blocks → final chaining value is hash”.
● Dedicated family highlights: MD4/MD5/SHA-1/SHA-2 (know basic history, outputs).
● Block-cipher-based: MMO, Davies–Meyer, Miyaguchi–Preneel—memorize the formulas.
● Output length drives collision security (birthday bound); wide-pipe designs or larger
block widths fix that.
Quick self-check (answer in one line)
1. Why not sign blocks individually?
Because it’s slow, doubles size, and enables reordering/splicing attacks.
2. State the three hash properties.
Preimage, second-preimage, collision resistance.
3. Why do many hashes output ≥256 bits?
To get ~128-bit collision security via the birthday bound.
4. What is Merkle–Damgård?
Iterated compression over message blocks; last chaining value is the hash.
5. One block-cipher-based compression you should recognize?
Davies–Meyer: (H_i=H_{i-1}\oplus E_{x_i}(H_{i-1})).