Message Authentication & MACs
Encryption protects a message against passive attacks (eavesdropping), while message authentication protects against active attacks — an attacker who modifies traffic, replays it, changes its order/timing, or forges its origin. Message authentication is concerned with three things:
What Message Security Must Defend Against
Traffic analysis and disclosure attacks (a passive attacker simply reading or profiling traffic) are countered by message encryption.
Masquerade, content modification, sequence modification, timing modification, and repudiation (of origin or destination) are countered by message authentication / integrity and digital signatures.
Three Approaches to Message Authentication
Conventional (Symmetric) Encryption
Authentication using symmetric encryption — if the ciphertext decrypts to something sensible with the shared key, it's assumed to be authentic.
Public Key Encryption
Authentication using asymmetric (public-key) encryption.
Message Authentication Without Encryption
The message itself is not always encrypted — instead an authentication tag (a MAC) is generated and appended to it. Authentication and confidentiality can also be combined into one algorithm by encrypting the message plus its authentication tag.
Message Authentication Code (MAC)
A MAC is a small, fixed-size block of data generated from the message plus a secret key: MAC = C(K, M). It is appended to the message when sent. Unlike encryption, a MAC algorithm need not be reversible — the receiver simply re-computes the MAC over the received message using the same key and checks that it matches.
If the recomputed MAC matches, the message is authenticated, which guarantees:
- The message has not been altered
- The message is coming from the alleged sender (they hold the shared key)
- If the message carries a sequence number (as with TCP), ordering is guaranteed
NIST recommends using DES to produce an encrypted version of the message, then taking the last 16 or 32 bits of that ciphertext as the code. The authentication algorithm does not need to be reversible — only "hard to forge."
A MAC can add secrecy too — but keep the keys separate
A MAC provides authentication; encryption can be layered on for secrecy. Generally use separate keys for each. The MAC can be computed before or after encryption — computing it before encryption is generally regarded as the better order.
Why Use a MAC?
- Sometimes only authentication is needed — no secrecy required
- Sometimes authentication needs to persist longer than the encryption (e.g. archival use — the data may be decrypted eventually, but you still want to verify it wasn't tampered with)
A MAC is NOT a digital signature
A MAC uses a shared secret key known to both parties, so either party could have generated it — it cannot prove authorship to a third party the way a digital signature (built on asymmetric keys) can.
Requirements for MACs
Taking the possible attacks into account, a MAC algorithm must satisfy:
1. Given a message and its MAC, it is infeasible to find another message with the same MAC.
2. MAC values should be uniformly distributed (no bias, no shortcuts).
3. The MAC should depend equally on all bits of the message (no bit should matter more than another).
Mnemonic — "F.U.D." for MAC Requirements
"Forge-proof, Uniform, Dependent-on-everything" → can't Forge a second message with the same MAC, output is Uniformly distributed, and the MAC is Dependent equally on every bit of the input. Three requirements, three F.U.D. words.
HMAC — Keyed-Hash Message Authentication
HMAC builds a MAC out of a hash function instead of a block cipher. It's specified as Internet standard RFC 2104.
HMAC Design Objectives
The HMAC Formula
Where:
- K⁺ is the secret key, padded out to the hash function's block size
- ipad and opad are two fixed, specified padding constants (inner pad / outer pad)
- The message is first hashed together with the inner-padded key, then that result is hashed again together with the outer-padded key
Cheap overhead, any hash function works
The overhead of HMAC is just 3 extra hash computations beyond what hashing the message alone would need. Any hash function can be plugged in — e.g. MD5, SHA-1, RIPEMD-160, Whirlpool.
HMAC Security
The proven security of HMAC is tied directly to the security of its underlying hash algorithm. Attacking HMAC requires either:
Simply try to guess/search the secret key K used in the construction.
Because HMAC is keyed, this would require observing a very large number of messages generated under the same key — far harder than an unkeyed birthday attack on a bare hash function.
The choice of underlying hash function is a trade-off between speed and security constraints.
Mnemonic — "Hash the Hash, In then Out"
"Inner first, Outer last" — HMAC hashes the message with the inner pad first (produces an inner digest), then hashes that result with the outer pad. Remember the order alphabetically: ipad before opad, inside before outside — matching the nesting of the formula itself.
Hash Functions — Definition & Properties
A one-way hash function is an alternative to a MAC: it accepts a variable-size message M as input and produces a fixed-size message digest H(M). Unlike a MAC, a hash function does not take a secret key as input — to authenticate a message with a hash function, the digest is simply sent alongside the message (often itself protected some other way, e.g. signed or encrypted).
The output size n is a property of the specific function. Common values are 128, 160, and 256 bits. Well-known hash functions include MD5, SHA, and SHA-1.
Hash Functions Are Versatile
Message & file integrity checks
Secure login (password storage)
Fingerprints of keys
Authentication
Digital signatures
A hash function computes a fixed-length value from a variable-length source — similar in spirit to checksums in communication protocols, or an index in a database. It is far more convenient to handle a small hash of a document than the document itself. This chapter deals specifically with cryptographically secure hash functions.
The Two Core Security Properties
Given a hash output x, it is unfeasible to compute a value v such that H(v) = x. You can't reverse a digest back into a message.
It is unfeasible to find x1 and x2 such that H(x1) = H(x2) with x1 ≠ x2 — two different inputs that hash to the same output.
The Four Desirable Properties of a Hash Function
Efficient to Compute
It should be possible to efficiently compute the hash value z = H(m) for any message m.
One-Way (Preimage Resistance)
Given a hash value z = H(m), it should be computationally infeasible to find m. A function with this property is called a one-way function.
Weak Collision Resistance
Given a message m, it should be infeasible to find another message m′ such that H(m) = H(m′). This is a second-preimage attack.
Strong Collision Resistance
It should be infeasible to find any two messages m and m′ (attacker's choice of both) such that H(m) = H(m′).
Naming note
Property 3 (fixed message, find a second one with the same hash) is weak collision resistance. Property 4 (find any two colliding messages at all) is strong collision resistance. Strong collision resistance is the harder property to guarantee — that's exactly what the birthday attack exploits (see Section 04).
Mnemonic — "E-O-W-S": Efficient, One-way, Weak, Strong
"Every Old Wizard Solves" → Efficient to compute → One-way (can't invert) → Weak collision resistance (can't find a second match for a GIVEN message) → Strong collision resistance (can't find ANY matching pair). Notice the properties get progressively harder to guarantee as you go down the list.
Attacks on Hash Functions & the Birthday Paradox
Hash functions face two broad categories of attack: brute-force attacks (which exploit the general structure — applicable to any hash function of a given digest size) and cryptanalytic attacks (which exploit a weakness in the specific algorithm's internal design, so they succeed faster than exhaustive search).
Preimage Attack
Given a hash value, find any y such that H(y) equals that given hash value. Breaks one-wayness.
Second Preimage Attack
Given a specific message x, find a different message y with H(x) = H(y). Breaks weak collision resistance.
Collision Attack
Find any two messages x and y (attacker picks both) such that H(x) = H(y). Breaks strong collision resistance.
Mnemonic — Fixed vs Free
"Pre = you're given one, Collision = you pick both" — in a (second) preimage attack, one message is fixed/given and you hunt for its match. In a collision attack, both messages are free — you get to choose both, which is why collisions are found dramatically faster (birthday paradox, below).
The Birthday Paradox — Why Collisions Are "Easy"
Classic worked example from the slides: suppose a hash function H produces n-bit values.
Compose a document, "nice treaty," and generate about 2^(n/2)+1 semantically-equivalent versions of it (reworded, but meaning the same thing). Similarly compose an "evil treaty" and generate about 2^(n/2)+1 semantically-equivalent versions of that. With probability ½ or more, there will exist a version of the nice treaty and a version of the evil treaty that share the same hash value — a collision an attacker can exploit (e.g. getting someone to sign the "nice" version, then swapping in the identically-hashed "evil" one).
Why this matters: √ (square-root) cost, not full brute force
Because of the birthday effect, finding a collision only costs on the order of 2^(n/2) attempts rather than 2^n — this is why digest sizes need to be roughly double the security level you actually want against collisions.
| Real-World Collision Costs (from slides) | Effort |
|---|---|
| Collisions in SHA-1 (160-bit) | Found by ~2⁶³ attempts |
| Collisions in MD5 (128-bit) | Found in ~8 hours on a notebook PC |
Mnemonic — "Half the Bits, Not All the Bits"
"Birthday = square-root shortcut" — just like it only takes ~23 people in a room for a 50% chance two share a birthday (not 183, half of 365), it only takes ~2^(n/2) hash attempts to find a collision (not 2^n). That's why MD5's 128-bit digest gives only ~2^64 collision security, not 2^128 — and why it's now considered broken.
UNIX Password Hashing & Salting
Classic UNIX systems used a modified form of DES as if it were a hash function to store passwords: encrypt a NULL string using the password itself as the DES key (rather than encrypting the password). This scheme historically truncated passwords to 8 characters, and applied an artificial slowdown by running DES 25 times in a row. Modern UNIX systems can instead be configured to use the MD5 hash function.
The core problem: passwords aren't random
With 52 upper/lowercase letters, 10 digits, and 32 punctuation symbols, there are 94⁸ ≈ 6 quadrillion possible 8-character passwords — but humans overwhelmingly reuse dictionary words, names, and pet names, shrinking the practical space to roughly 1 million common passwords.
crypt(3) — How the Classic Scheme Works
Choose a Salt
A random salt is chosen when the password is first set.
Salt Disrupts the DES E-box
The salt introduces disorder into DES in one of 16,777,216 (2²⁴) or 4,096 (2¹²) possible ways — i.e. using 24 or 12 bits of salt: if bit i of the salt is set, bits i and i+24 are swapped in the DES E-box output.
Encrypt a Constant, Repeatedly
The DES key (derived from the password) is used to encrypt a 64-bit constant, iterated count times. crypt(pwd, salt) is basically DES on a NULL plaintext.
Output the Encoded String
Returns a null-terminated string, 20 or 13 bytes (plus null) in length: the salt "setting" followed by the encoded 64-bit encryption.
The classic UNIX password field format is a 13-character Base64-encoded (6 bits/char) string = 78 bits total, made up of 12 bits of salt and a 64-bit hashed value — shown as sX5/Fhl9yCMNK (2-char salt + 11-char hash).
What salting actually buys you
Users with the same password end up with different entries in the password file (since each gets a different random salt), which defeats a single precomputed lookup table covering all users at once. But a dictionary attack targeted at one salt is still fully possible.
Handling Longer Passwords
Later modifications to crypt(3) allowed longer passwords by splitting them into groups of 8 characters: the first key is generated from the first 8-character group, then keys for subsequent groups are XOR'd into the DES encryption of the current key, using itself as the key.
Dictionary Attacks
The /etc/passwd file is world-readable (it also holds user/group IDs needed by
many system programs), which is exactly what makes offline dictionary attacks feasible: an attacker computes
H(word) for every word in a dictionary and checks whether the result appears in the password file.
| Scenario | Numbers from the Slides |
|---|---|
| Typical password dictionary size | ~1,000,000 common entries (names, pet names, words) |
| Online guessing rate | ~10 guesses/second (reasonable for a live website) |
| Full dictionary attack time | At most ~100,000 sec (28 hrs); ~50,000 sec (14 hrs) average |
| Offline attack | Much faster than online — this estimate is conservative |
| If passwords were truly random (6 chars, 94-symbol alphabet) | ~689,869,781,056 combinations → ~1,093 years to exhaust on average |
Mnemonic — "Salt Stops Reuse, Not Guessing"
"Salt = spice, not a lock" — salting stops an attacker from reusing one precomputed table (like a rainbow table) across every account, because each hash is seasoned differently. It does nothing to slow a targeted dictionary attack against one specific user's salt — that's why humans choosing weak, guessable passwords remains the real vulnerability.
Combining Hashing with Encryption
To simultaneously protect confidentiality and authenticity, four combination approaches exist (often required together, but usually implemented as separate mechanisms):
Hash-then-encrypt: E(K, (M || H(M)))
MAC-then-encrypt: E(K2, (M || MAC(K1, M)))
Encrypt-then-MAC: C = E(K2, M), T = MAC(K1, C)
Encrypt-and-MAC: C = E(K2, M), T = MAC(K1, M)
Hash Algorithms — MD5, SHA-1 & the SHA-2 Family
The three named algorithm families from the slides:
MD5 Message Digest Algorithm
Developed by Ron Rivest at MIT. Takes a message of arbitrary length and compresses it into a 128-bit hash, processed using 32-bit words and 512-bit blocks. It's the "son of MD2 and MD4" — direct successor in the MD line.
Append Padding Bits
Pad so the bit length ≡ 448 mod 512 (i.e. 64 bits short of a multiple of 512). Padding is always added, even if the message is already the right length. Padding bits are a single 1 followed by as many 0s as needed.
Append Length
A 64-bit field is appended containing the length of the original message modulo 2⁶⁴, bringing the total to an exact multiple of 512 bits. The expanded message can be viewed as N 32-bit words, N = L × 16 for L 512-bit blocks.
Process Block by Block
The hashing runs block-by-block; at the end of four rounds per block, the round output is added to the running values of the buffer A, B, C, D.
MD5 is broken — don't use it for security
Full details are in RFC 1321. Hans Dobbertin showed MD5 is not collision resistant, so it's not advisable to rely on it. It remains in legacy use in protocols like IPSec, but for new work it should be avoided.
MD4 — MD5's Precursor
MD4's design goals — carried over into MD5 — were: security, speed, simplicity/compactness, and favoring a little-endian architecture. MD5 improved on MD4 in six specific ways:
- A fourth round was added
- Each step got a unique additive constant
- The round-2 function g changed from (bc ∨ bd ∨ cd) to (bd ∨ c d′) — made less symmetric
- Each step now adds in the result of the previous step, for a faster avalanche effect
- The input-word access order in rounds 2 and 3 was changed to look less like one another
- Shift amounts per round were re-optimized and made distinct per round, for a faster avalanche effect
Secure Hash Algorithm (SHA / SHA-1)
Originally designed by NIST & NSA in 1993, revised in 1995 as SHA-1. It's the US standard for use with the DSA signature scheme (standard FIPS 180-1 1995 / Internet RFC 3174 — note: the algorithm is "SHA," the standard is "SHS"). Based on the design of MD4, with key differences; produces 160-bit hash values. 2005 cryptanalysis results raised real concerns about SHA-1's future use.
SHA-1 Logic — Steps
Overall structure mirrors MD5:
Append Padding Bits
Same idea as MD5's padding step.
Append Length
Same idea as MD5's length step.
Initialize the MD Buffer
A 160-bit buffer of five 32-bit registers A, B, C, D, E holds intermediate and final results. A/B/C/D initialize the same as in MD5; E = C3D2E1F0. Stored big-endian (most significant byte at the low address).
Process 512-bit Blocks — the Compression Function
The heart of the algorithm: 4 rounds of 20 steps each (80 steps total). Each round uses a different primitive logical function (f1–f4), and each round consumes the current 512-bit block plus the 160-bit ABCDE buffer, updating it. Only 4 distinct additive constants (Kt) are used across all 80 steps, each based on the integer part of 2³⁰ × a square root:
| Step Range | Constant Kt | Derived From |
|---|---|---|
| 0 ≤ t ≤ 19 | 5A827999 | [2³⁰ × √2] |
| 20 ≤ t ≤ 39 | 6ED9EBA1 | [2³⁰ × √3] |
| 40 ≤ t ≤ 59 | 8F1BBCDC | [2³⁰ × √5] |
| 60 ≤ t ≤ 79 | CA62C1D6 | [2³⁰ × √10] |
The output of the 4th round (80th step) is added to the previous chaining value CVq to produce CVq+1 — carried into the next 512-bit block.
Revised Secure Hash Standard (SHA-2 Family)
NIST issued the revision FIPS 180-2 in 2002, adding three additional versions — SHA-256, SHA-384, SHA-512 — designed for compatibility with the increased security level offered by AES. Structure and detail closely resemble SHA-1, so analysis techniques should transfer, but security levels are considerably higher.
| Property | SHA-1 | SHA-224 | SHA-256 | SHA-384 | SHA-512 |
|---|---|---|---|---|---|
| Message digest size | 160 | 224 | 256 | 384 | 512 |
| Max message size | < 2⁶⁴ | < 2⁶⁴ | < 2⁶⁴ | < 2¹²⁸ | < 2¹²⁸ |
| Block size | 512 | 512 | 512 | 1024 | 1024 |
| Word size | 32 | 32 | 32 | 64 | 64 |
| Number of steps | 80 | 64 | 64 | 80 | 80 |
SHA-512 Compression Function
The heart of SHA-512: it processes the message in 1024-bit blocks across 80 rounds, each round updating a 512-bit buffer using a 64-bit value Wt derived from the current message block, plus a round constant based on the cube root of the first 80 prime numbers.
Mnemonic — "128, 160, then Double Every Time"
"MD-5-and-a-2-8, SHA-1-6-oh, then 2-2-4-2-5-6-3-8-4-5-1-2" — simpler: MD5 = 128 bits, SHA-1 = 160 bits, and the SHA-2 family digest sizes are literally baked into their names: SHA-224, SHA-256, SHA-384, SHA-512. If you remember the algorithm's number, you already know its digest size.
Mnemonic — "512 Block, Except the Big Two"
"384 and 512 go big on blocks" — every hash in this family uses a 512-bit block / 32-bit word setup, except SHA-384 and SHA-512, which switch to a 1024-bit block / 64-bit word setup. The two "big number" algorithms use the two "big number" internals.
Hash vs. encryption — the core distinction
Encryption is reversible (given the key) and typically uses a key; a cryptographic hash is deterministic, has no key, produces a fixed-size digest regardless of input size, and is designed to be practically irreversible. Encryption protects confidentiality; a hash function protects integrity/fingerprinting (unless wrapped into a MAC/HMAC, which adds authentication).
Exam Tips & Tricks
MAC needs a key, hash function doesn't
MAC = C(K, M) — always requires a shared secret key. A plain hash function H(M) never takes a key; that's the single biggest distinguishing fact examiners test.
Weak = fixed message, Strong = both free
Weak collision resistance (2nd preimage): attacker is given one message and must find a match. Strong collision resistance: attacker can pick both colliding messages — much easier via the birthday attack.
MD5 and SHA-1 are both considered broken for collisions
MD5 collisions: ~8 hours on a notebook. SHA-1 collisions: found by ~2⁶³ attempts. Neither should be used where collision resistance matters (e.g. certificates, digital signatures) — prefer SHA-2 or SHA-3.
Digest size ≈ 2× your intended collision-security bits
Because of the birthday attack, collision resistance is only ~n/2 bits of security for an n-bit digest. A 128-bit digest (MD5) gives only ~64-bit collision security — that's why it's weak today.
Salt defeats precomputation, not guessing
A salt makes identical passwords hash differently across users, defeating one shared rainbow table/lookup. It does NOT slow down a dictionary attack aimed at one specific salted hash.
HMAC security ties to the underlying hash
HMAC is only as strong as its embedded hash function. Attacking it needs either brute-forcing the key or a birthday attack that (because it's keyed) needs a huge number of messages under the same key.
Quick Reference — Everything at a Glance
| Topic | Key Point |
|---|---|
| Encryption vs. authentication | Encryption defends against passive attacks; message authentication defends against active attacks |
| Message authentication covers | Integrity, origin validation, non-repudiation |
| 3 approaches to authentication | Symmetric encryption, public-key encryption, MAC (no encryption needed) |
| MAC definition | Small fixed-size block: MAC = C(K, M); needs a shared secret key |
| NIST MAC method (classic) | Encrypt with DES, take last 16 or 32 bits of ciphertext as the code |
| MAC requirements | Can't forge a 2nd message w/ same MAC; uniformly distributed; depends on all bits equally |
| MAC vs digital signature | MAC uses a shared key (either party could forge it) — not proof of authorship like a signature |
| MAC-then-encrypt order | Generally regarded as better to compute the MAC BEFORE encrypting |
| HMAC formula | HMAC_K(M) = Hash[(K⁺ XOR opad) || Hash[(K⁺ XOR ipad) || M]] |
| HMAC standard | RFC 2104; overhead = 3 extra hash computations; works with any hash (MD5, SHA-1, RIPEMD-160, Whirlpool) |
| HMAC attacks | Brute-force the key, or a (much harder, keyed) birthday attack |
| Hash function definition | H: {0,1}* → {0,1}ⁿ — arbitrary length in, fixed n-bit digest out, no key |
| Common digest sizes | 128, 160, 256 bits |
| Hash function uses | Integrity, secure login, key fingerprints, authentication, digital signatures |
| One-way property | Given H(v)=x, infeasible to find v (preimage resistance) |
| Collision-free property | Infeasible to find x1 ≠ x2 with H(x1) = H(x2) |
| Weak collision resistance | Given message m, infeasible to find different m′ with same hash (2nd preimage) |
| Strong collision resistance | Infeasible to find ANY two messages m, m′ with the same hash |
| Preimage attack | Find y such that H(y) equals a given hash value |
| Collision attack cost | ~2^(n/2) via birthday paradox, far less than brute-force 2^n |
| SHA-1 collision cost | ~2⁶³ attempts (2005 results raised concerns) |
| MD5 collision cost | ~8 hours on a notebook PC — considered broken |
| UNIX password scheme (classic) | Encrypts NULL string using password as DES key; truncated to 8 chars; DES run 25× for slowdown |
| Modern UNIX alternative | Can be configured to use MD5 hash instead |
| Salt purpose | Same password → different stored hash per user; defeats shared precomputed tables, not targeted dictionary attacks |
| Salt size / crypt(3) output | 12 bits of salt + 64-bit hashed value = 13-character (78-bit) Base64 string |
| Dictionary attack numbers | ~1M word dictionary, 10 guesses/sec → ~14 hrs avg online; offline much faster |
| Random password strength | 6-char, 94-symbol alphabet → ~690 billion combos → ~1,093 yrs to brute-force on average |
| Combining hash + encryption | Hash-then-encrypt, MAC-then-encrypt, Encrypt-then-MAC, Encrypt-and-MAC |
| MD5 | Ron Rivest; 128-bit digest; 512-bit blocks; 32-bit words; RFC 1321; broken (not collision resistant) |
| MD5 padding | Pad to length ≡ 448 mod 512, then append 64-bit original length field |
| MD4 → MD5 changes | +1 round, unique constants per step, less-symmetric g function, faster avalanche, reordered word access, distinct shift amounts |
| SHA-1 | NIST/NSA, 1993, revised 1995; 160-bit digest; 512-bit blocks; 4 rounds × 20 steps = 80 steps |
| SHA-1 buffer | 160-bit buffer: registers A,B,C,D,E; E = C3D2E1F0; stored big-endian |
| SHA-1 constants | Only 4 distinct Kt values across 80 steps, based on 2³⁰×√(2,3,5,10) |
| SHA-2 family | FIPS 180-2 (2002): SHA-256, SHA-384, SHA-512 added; designed to pair with AES |
| SHA-2 digest sizes | 224 / 256 / 384 / 512 bits — the number IS the digest size |
| SHA-2 block/word sizes | SHA-1/224/256: 512-bit blocks, 32-bit words. SHA-384/512: 1024-bit blocks, 64-bit words |
| SHA-2 step counts | SHA-1/384/512: 80 steps. SHA-224/256: 64 steps |
| SHA-512 compression | 1024-bit blocks, 80 rounds, 512-bit buffer, Wt per round, constants from cube roots of first 80 primes |
| Hash vs encryption | Hash = no key, one-way, fixed digest, integrity/fingerprint. Encryption = uses a key, reversible, confidentiality |