R11. Cryptography: More Primitives

What this lecture covers

This final recitation extends the two cryptography lectures with several more primitives: digital signatures as a standalone tool (not just a hash application), message authentication codes (MACs) for symmetric-key integrity, hash trees (Merkle trees) for verifying files stored on an untrusted server, and a worked review of the knapsack cryptosystem and why it was broken. Throughout, the instructor builds each primitive by proposing a naive construction, having the class find an attack against it, and then fixing it - showing concretely how cryptographic definitions get their teeth.

After watching, you should be able to define correctness and unforgeability for signatures and MACs, explain why naively using raw RSA as a signature scheme is broken, describe how a hash tree lets you verify one file against a single stored root hash, and explain why knapsack-based cryptosystems have a density trade-off that makes them vulnerable.

Key ideas

• Digital signature: a pair of functions, sign(secret key, message) -> signature and verify(public key, message, signature) -> true/false; required properties are correctness (a genuine signature always verifies) and unforgeability (no one without the secret key can produce a valid signature on a message they haven't already seen signed).
• Naive RSA-as-signature is broken: using RSA decryption as "sign" and encryption as "verify" is forgeable two ways - multiplying two seen signatures forges a signature for the product message (using RSA's multiplicative/malleable property), and picking an arbitrary signature and raising it to the public exponent instantly produces a valid (message, signature) pair.
• Fixing it with hashing: signing hash(M)^d instead of M^d defeats both attacks, provided the hash is one-way and collision resistant, though this "hash-then-RSA" approach remains ad hoc - it resists known attacks but isn't proven secure.
• Message authentication code (MAC): the symmetric-key analog of a signature, using one shared key; verification recomputes the MAC and compares, and correctness/unforgeability are defined the same way as for signatures.
• Replay attacks: even a valid signed or MAC'd message can be resent later by an attacker; the fix is to include a strictly incrementing counter (or similar freshness marker) inside the signed message.
• Hash tree (Merkle tree): hashes files pairwise up to a single root hash stored locally, giving O(1) local storage and O(log n) time to verify or update any one file, versus O(n) for storing all hashes or hashing all files together.
• Knapsack cryptosystem density: transforms an easy super-increasing knapsack into an apparently hard one; the scheme only works if the modulus is large enough relative to the weights, but that pushes the "density" (roughly n / log(max weight)) below a threshold where low-density attacks succeed.

Walkthrough

Digital signatures and correctness/unforgeability (0:21)

The recitation reintroduces digital signatures as a standalone primitive: sign uses a secret key, verify uses the matching public key. Through class discussion, two properties emerge as required: correctness (a signature produced by sign must always pass verify) and unforgeability (an adversary who has seen some message-signature pairs must not be able to produce a valid pair for any new message).

Breaking and fixing "RSA as signature" (8:04)

The naive idea is to reuse RSA's encryption/decryption as verify/sign. This is broken by two attacks: multiplying two previously seen (message, signature) pairs produces a valid forgery for the product message, thanks to RSA's malleability; and simply choosing a signature value and raising it to the public exponent yields a valid pair for a nonsensical but technically legitimate message. The fix is to sign the hash of the message rather than the message itself, which defeats both attacks as long as the hash function is one-way and collision resistant - though the recitation notes this "hash-then-sign" pattern is only known to resist known attacks, not proven secure from first principles.

Weaknesses: replay attacks and freshness (28:04)

A subtler problem is raised: even a correctly signed message can be captured and resent later by someone else, since the signature itself doesn't say when it was created. The fix demonstrated is to prepend an incrementing counter to every signed message, so a repeated counter value reveals a replay rather than a genuine new message.

Message authentication codes (29:24)

MACs fill the symmetric-key gap in the primitive landscape (private-key encryption, public-key encryption, and signatures are joined by MACs for symmetric-key integrity). A MAC uses one shared key for both generating and verifying the tag; hashing the key concatenated with the message is highlighted as a simple construction that works securely with SHA-3 (though not safely with SHA-1 for related reasons the recitation doesn't detail).

Verifying files with a hash tree (36:34)

The recitation poses a real problem: verifying that a file downloaded from a cloud server is both correct and the latest version. Storing one hash per file works but costs O(n) local space; hashing all files together costs O(1) space but O(n) time to verify or update anything. The hash tree (Merkle tree) solves both: hash each file, then hash pairs of hashes up to a single root, stored locally. Verifying or updating one file only touches the O(log n) hashes on its path to the root. The recitation also sketches why this is secure: if collision resistance holds, changing a leaf must change every hash on its path to the root, or else you've found a hash collision.

Reviewing the knapsack cryptosystem and density attacks (42:34)

The recitation reviews how a knapsack cryptosystem transforms an easy super-increasing sequence into a disguised "hard" one via multiplication and modular reduction, with encryption computing a subset sum and decryption inverting the transform back into the easy domain. This only decrypts correctly if the modulus exceeds the sum of all weights. That constraint forces a low "density" (roughly the number of items over the log of the largest weight), and knapsack instances below a density threshold (historically estimated around 0.45, later refined) are breakable by low-density attacks. The recitation closes by tying this back to the deeper lesson from the lecture: NP-complete problems are hard only in the worst case, and cryptography needs average-case hardness, which is why building crypto systems directly on knapsack or graph coloring failed.

Before you watch

• Watch both cryptography lectures in this course first, since this recitation assumes familiarity with hash function properties (one-wayness, collision resistance) and the RSA algorithm.
• Review the knapsack cryptosystem material from the lecture, since this recitation's final section is an explicit review of it.

Check your understanding

1. Why does raising an arbitrarily chosen signature to the public RSA exponent produce a valid forgery against the naive RSA-as-signature scheme?
2. What specific properties of the hash function are needed to fix that naive signature scheme, and why does each matter?
3. How does a hash tree let you verify a single file in O(log n) time while using only O(1) local storage?
4. Why does the knapsack cryptosystem's need for a large modulus create a trade-off with density, and how does that trade-off lead to attacks?