1

CS 161, Summer 2026 @ UC Berkeley

Slides credit: Nick Weaver, Nicholas Ngai, Peyrin Kao, Henry Corrigan-Gibbs, Jonah Bedouch

Cryptographic Hashes

Lecture 9 (Authentication 2)

SU26 Announcement:

Please fill out midterm logistics form ASAP if you need adjustments.

What is Cryptography?

Lecture 9, CS 161, Summer 2026

Intro to Cryptography

• What is Cryptography?
• Definitions

Cryptographic Hashes

• Collision-Resistant Hash Functions (CRHFs)
• Building CRHFs
• Other Cryptographic Hash Properties
• Do Cryptographic Hashes Prove Authenticity?

Hash Applications

• Merkle Trees
• Password Hashing

Goodbye, Passwords

Last time, we saw that passwords and session tokens had a major flaw:

• If someone sees your password or session token (i.e. across the network), they can successfully impersonate you!

To do better, we need to learn about cryptography.

Cryptography Definition

Cryptography: Secure communication and computation against adversarial behavior.

​

Why study cryptography?

• It is built on beautiful theory.
• It works in practice.
• It solves an important everyday problem.

​

Cryptography draws on algorithms, complexity, architecture, number theory…

• Warning: There will be math. We will try to review prerequisites as they appear.

​

Cryptography is a "success story" within computer security.

• Computer systems rarely fail because the cryptography failed.
• What are the common causes of security failure?

What You Will (and Won't) Learn in this class

What are the common causes of security failure?

• Human error: A good theoretical tool exists, but we don't know how to properly use it, or we are too lazy to use it.
• Implementation: The math theory is sound, but the code has a bug.

​

This class will make you a more informed user of crypto tools.

• Which tool is best for the problem I have?
• How do I properly use this tool?

​

This class will not teach you how to design or write your own crypto tools.

• Proper cryptographic analysis is much deeper than what we'll cover.
• Even one small edge case could ruin the security of your whole tool.

Don't Roll Your Own Crypto

Crypto algorithms are secure because they have been analyzed by experts for years.

• Do: Use existing, well-vetted algorithms.
• Don't: Design your own homemade algorithms.

​

Implementations of these algorithms are exceptionally subtle and hard-to-test.

• Do: Import standard crypto libraries.
• Don't: Write your own crypto code.

​

If you remember nothing else from this course: Don't roll your own crypto.

• Former TAs tried writing their own crypto code for online exams during COVID.
• The code was broken… and students might have seen the exam ahead of time.
• Don't write your own crypto, or else you might be the next cautionary tale.

Definitions

Lecture 9, CS 161, Summer 2026

Intro to Cryptography

• What is Cryptography?
• Definitions

Cryptographic Hashes

• Collision-Resistant Hash Functions (CRHFs)
• Building CRHFs
• Other Cryptographic Hash Properties
• Do Cryptographic Hashes Prove Authenticity?

Hash Applications

• Merkle Trees
• Password Hashing

Cryptography Definitions

Warning: Math approaching.

• In order to learn about cryptography, we first have to explore some of the "grammar" that cryptographers use.
• We'll start each lecture with a short definitions section.

Cryptography: A Common Problem

Cryptography: Secure communication and computation against adversarial behavior.

​

Where might you use cryptography?

• Texting:
• Online shopping:
• Banking:
• Software updates:

To summarize all these scenarios, we often use a common cast of characters.

You

Your friend

You

Amazon

ATM

Bank

Your phone

App Store

Meet Alice, Bob, Eve, and Mallory

The heroes: Alice and Bob are two users who want to communicate securely over a channel.

The villain: Mallory is an active attacker ("man-in-the-middle") who can read and modify data on the channel.

Alice

Bob

Mallory

Authenticity

Goal: Alice and Bob need to know that they're talking to each other.

• Authenticity: Prevent Mallory from tampering with messages, by detecting when the original message has been changed.

​

Alice

Bob

Mallory

Efficient (PPT) Attackers

Mallory models real-world attackers, so we give her real-world limitations.

• Some attacks exist in theory, but they would take a long time to run in practice.
• So we don't worry about them.

​

We will only consider efficient attackers.

Many ways to define efficient. One is Probabilistic Polynomial Time (PPT):

• Probabilistic: The attacker is allowed to use randomness (e.g. flip coins).
• Polynomial time: The attacker is limited to polynomial-time runtime, e.g.:
• O(N²) and O(N³) and O(log N) is okay.
• O(2^N) and O(N!) is not allowed.

The sun would burn out before they finished.

What N is depends on the specific scheme being discussed.

Quantifying Efficiency: Brute-Force Attacks

Another way to define "efficient" is by counting operations:

• 2³⁰ = Ops/second on a laptop.
• 2⁵⁸ = Ops/second on Fugaku supercomputer.
• 2⁶⁸ = Crypto ops/second on Bitcoin network.
• 2⁹² = Crypto ops/year on Bitcoin network.
• 2¹¹⁴ = Crypto ops required to use enough energy to boil ocean.
• 2¹²⁸ = We design cryptosystems to defend against attacks using this much energy.
• 2¹⁴⁰ = Crypto ops required to use one year of sun’s energy.

​

Punchline: If an attack requires >2¹²⁸ operations, it is impossible.

​

Negligible Probabilities

Mallory models real-world attackers, so we give her real-world limitations.

• Some attacks exist in theory, but they succeed with extremely small probability.
• So we don't worry about them.

​

To model this, we introduce negligible and non-negligible probabilities:

• Negligible values: 1/2¹²⁸, 1/2²⁵⁶
• Non-negligible values: 1/3, 51/100, 1
• The precise definition is out of scope.

In many of our definitions:

• A scheme is secure if an attacker's advantage is ≤ negligible�(even if it's not exactly 0).
• A scheme is only insecure if an attacker's advantage is non-negligible.

Smaller than the probability of winning the Powerball lottery jackpot every single day of your life.

Cryptography Roadmap

How do we teach cryptography?

• In this unit, we’ll talk about authenticity:�"How do we prove we are who we claim to be?"
• Then, in the next unit, we’ll talk about confidentiality:�"How do we talk to each other without others listening?"

Along the way, we’ll develop some insights into how cryptographic systems work.

Collision-Resistant Hash Functions (CRHFs)

Lecture 9, CS 161, Summer 2026

Intro to Cryptography

• What is Cryptography?
• Definitions

Cryptographic Hashes

• Collision-Resistant Hash Functions (CRHFs)
• Building CRHFs
• Other Cryptographic Hash Properties
• Do Cryptographic Hashes Prove Authenticity?

Hash Applications

• Merkle Trees
• Password Hashing

Hashes

A hash function is a function that deterministically compresses a long input to a fixed-length output.

• Not all hash functions are useful in cryptography (think hash tables from CS 61B).
• Not all hash functions are useful at all (e.g. H(x) = 1).

Read this as: Function mapping (→) an arbitrary number (*) of zeroes and ones, to n zeroes and ones.

Same input gives same output every time.

n is a fixed number, commonly 256.

Collisions

Collision: Two distinct values x and x' such that H(x) = H(x').

• In English: two different inputs with the same output.
• If H(x) = x², then a collision is x = 5 and x' = –5. (Many others exist.)
• If H(x) = x mod 3, then a collision is x = 1 and x' = 4. (Many others exist.)

​

Can a hash function have no collisions at all?

• Size of input space {0,1}^* is infinitely large.
• Size of output space {0,1}²⁵⁶ is 2²⁵⁶ values.

​

There are way more inputs than outputs.�By the pigeonhole principle, there must be�collisions. (In fact, there are infinitely many.)

Reminder: {0,1}^* means arbitrary-length bitstring, {0,1}²⁵⁶ means 256-bit string.

{0,1}^*

{0,1}²⁵⁶

When mapping from large input space to small output space, collisions occur.

Collision Resistance

Preventing collisions is impossible. But we can make them hard to find.

Intuition: I give you a hash function. Can you find two inputs with the same output?

• If yes: Hash is not collision resistant.
• If no: Hash is collision resistant.

​

If the output space is small like {0,1}², finding collisions would be easy.�How big should the output space be?

A hash function H is collision resistant if

no efficient adversary can find distinct x and x' such that H(x) = H(x').

"no efficient adversary" = finding collisions is theoretically possible, but not actually feasible.

Two inputs with the same output = a collision.

Collision resistance = it's hard to find collisions.

Breaking Collision-Resistance: Birthday Paradox

The birthday paradox: If you pick 2^n/2 elements independently at random from a set of size 2ⁿ, with probability > ⅓ you will pick at least one element twice.

​

We can think of computing H(random input) as picking a random n-bit hash output.

​

By birthday paradox, after hashing 2^n/2 random inputs, we're likely to find a collision.

​

Therefore: If a hash function has n-bit output, an attacker picking inputs at random (brute-force attack) finds a collision in roughly 2^n/2 tries.

• If n = 256, the attacker needs roughly 2¹²⁸ tries.�This is infeasible!

Building CRHFs

Lecture 9, CS 161, Summer 2026

Intro to Cryptography

• What is Cryptography?
• Definitions

Cryptographic Hashes

• Collision-Resistant Hash Functions (CRHFs)
• Building CRHFs
• Other Cryptographic Hash Properties
• Do Cryptographic Hashes Prove Authenticity?

Hash Applications

• Merkle Trees
• Password Hashing

Examples of Non-Collision-Resistant Hash Functions

Some hash functions that are not collision-resistant:

​

H(M) := Output the first n bits of M.

Collision: x = 0ⁿ, x' = 0ⁿ || 0ⁿ

Because the first n bits of both x and x' are all zeroes.

​

H(M) := Chop M into n-bit blocks. Output the XOR of all blocks.

Collision: x = 0ⁿ || 0ⁿ, x' = 1ⁿ || 1ⁿ

Because XORing together two all-zero blocks yields all zeroes,�and XORing together two all-one blocks also yields all zeroes.

:= means "is defined as."

0ⁿ means "0 repeated n times."

​

|| is concatenation, so this is 0 repeated 2n times.

Examples of Non-Collision-Resistant Hash Functions

Some hash functions that are not collision-resistant:

​

Let H be a collision-resistant hash function.

H'(M) := H(M)[:64]

​

Since H' has 64-bit output, it takes roughly 2^64/2 = 2³² tries for a brute-force attacker to find a collision. This is a feasible number!

Brackets are for slicing, so [:64] means the first 64 bits of the H(M) value.

Building Collision-Resistant Hash Functions

We don't know how to prove that a function is actually collision-resistant.

• Instead, we assume that certain standard hash functions are collision-resistant.
• These assumptions are based on years of cryptanalysis.�("Experts have tried to find collisions for years and failed…so it's probably safe, right?")

​

Examples of standard hashes:

• MD5 and SHA-1: Once thought secure, now completely broken.
• SHA-2: Current standard, used everywhere.
• Variants: SHA-256, SHA-384, SHA-512 (the number is the output size).
• SHA-3: An alternative to SHA-2. Current standard but less common in practice.

​

Modern CPUs have hardware specially designed to do SHA-2 computations quickly.

• Another reason to avoid rolling your own crypto: The standard is faster.

Building Collision-Resistant Hash Functions

Common method of creating CRHFs:

• Build a CRHF h for small inputs.
• Extend h to handle long inputs.

​

The Merkle-Damgard construction lets you build a big CRHF from a small CRHF.

• Input: h : {0,1}²ⁿ → {0,1}ⁿ. Notice the input size is a fixed small size like 2n.
• Output: H : {0,1}^* → {0,1}ⁿ. Works on arbitrary-length inputs.

​

You can prove that if h is a CRHF, then H is a CRHF.

• Proof sketch: Assume H is not CRHF, i.e. you can find long collisions.�Then you can also find a short collision on h, so h is not a CRHF.�Contradiction! So H was a CRHF all along.

Can't prove h is a CRHF. Rely on cryptanalysis.

Merkle-Damgard Construction

Merkle-Damgard uses h : {0,1}²ⁿ → {0,1}ⁿ to construct H : {0,1}^* → {0,1}ⁿ like this:

Input M (arbitrary length)

M0

M1

M2

MN

…

Pad

Split M into n-bit chunks. Add padding bytes if the last chunk is < n bits.

Initial fixed value

h

h

h

h

At every step, input the previous output and the next chunk into h.

Notice: This is 2n bits of input.

Output H(M)

…

Other Cryptographic Hash Properties

Lecture 9, CS 161, Summer 2026

Intro to Cryptography

• What is Cryptography?
• Definitions

Cryptographic Hashes

• Collision-Resistant Hash Functions (CRHFs)
• Building CRHFs
• Other Cryptographic Hash Properties
• Do Cryptographic Hashes Prove Authenticity?

Hash Applications

• Merkle Trees
• Password Hashing

Collision Resistance Implies Nothing Else

Collision resistance doesn’t say anything about other properties.

• Very important not to assume hash functions do things they don't!
• Can lead to insecure systems.

​

We will (briefly) look at a few other properties of some cryptographic hashes.

Length Extension Attacks

Many hash functions are vulnerable to length-extension attacks.

• Given H(x) (but not x), an attacker can pick their own y,�and "keep running" the hash to find H(x||y).
• If the hash function pads x, the attacker's y might have to include the pad as part of the extended message (shown below).

H(X)

h

y'

pad_y'

H(x||pad_x||y')

H(x||y) where y=pad_x||y'.

The output of H(x) is the internal �state of the hash function.

One-Wayness

​

​

�Intuitively, think of one-wayness as a challenge:

• I give you a hash function.
• I pick a random x, compute H(x) = y, and give you y. I do not give you x.

Can you find some x' such that H(x') = y?

• If yes: Hash is not one-way.
• If no: Hash is one-way.

​

Informally: "It is hard to invert H on random inputs."

• Though, note that the x' you give could be the same or different as the x I used.

A hash function H is one-way if given H(x) but not x,

no efficient adversary can find an x' such that H(x) = H(x').

One-Wayness vs. Collision Resistance

The subtle difference between one-wayness and collision resistance:

I give you the green target y.

You must find a red input that hashes to y.

I don't give you a green target.

You must find any two red inputs with the same output.

Do Cryptographic Hashes Prove Authenticity?

Lecture 9, CS 161, Summer 2026

Intro to Cryptography

• What is Cryptography?
• Definitions

Cryptographic Hashes

• Collision-Resistant Hash Functions (CRHFs)
• Building CRHFs
• Other Cryptographic Hash Properties
• Do Cryptographic Hashes Prove Authenticity?

Hash Applications

• Merkle Trees
• Password Hashing

Cryptographic Hashes Can Sometimes Prove Authenticity

​

A scenario with no security:

Today: You store a file in the cloud.

Tomorrow: You download the file.

File f

File f

Malicious file f'

Compromised cloud!

Cryptographic Hashes Can Sometimes Prove Authenticity

You can use hashes to check that the file is unmodified!

Today: You store a file in the cloud, �and you store a hash of the file locally.

Tomorrow: You download the file.

Re-compute the hash and compare with h.

File f

File f

Malicious file f'

Compromised cloud!

I remember h = H(f).

h ≠ H(f'). Reject!

Real-World Cryptographic Hashes

WhatsApp and Signal safety numbers:

• The hash of some important data is displayed on your phone �and your friend's phone.
• If the hashes don't match, one of your phones has been hacked �and has the wrong data!

Downloading large files from mirrors:

• A large package (e.g. Linux is 1.5 GB) can be downloaded from �many (untrusted) third-party mirror sites.
• The original website publishes a hash.
• If the hash of your download doesn't�match the hash on the website,�you have a malicious download!

​

Hashes Don't Always Prove Authenticity

What about the original setting?

• Alice sends messages to Bob, with Mallory tampering messages.

Main problem: If the attacker can modify the hash value, checking the hash does not provide authenticity.

Main issue we must solve: Hashes are not authenticated. Anybody can compute them.

Alice

Bob

Mallory

M and H(M)

M' and H(M')

I hashed M' and it matches the hash I received. Looks good.

Application: Merkle Trees

Lecture 9, CS 161, Summer 2026

Intro to Cryptography

• What is Cryptography?
• Definitions

Cryptographic Hashes

• Collision-Resistant Hash Functions (CRHFs)
• Building CRHFs
• Other Cryptographic Hash Properties
• Do Cryptographic Hashes Prove Authenticity?

Hash Applications

• Merkle Trees
• Password Hashing

Scenario: Sharing Large Files

Scenario: I want to share a 40 GB movie with many people.

• I don't want to host it for download myself since bandwidth is expensive.
• I want people to be able to download it quickly.

​

Solution: I split the movie up into 1 KB chunks, and give the chunks to many people.

• Now, people can download from multiple people at once, and then share it themselves too!

​

Issue: If even one person sends the wrong chunk, people aren't going to be able to recover the movie.

Hash List

Bad idea 1: I publish a hash of the entire file.

• No way to check if a specific chunk is wrong.�Users can only check the entire file at once.

​

Bad idea 2: I publish a hash of each chunk.

• This is 40,000,000 hashes, or 1.28GB of hashes (3.2% of the file size).
• If I let other people share the hashes, they could be tampered with, so people have to ask me for hashes. (Bandwidth issue again!)

Merkle Trees (1/2)

Better idea: Build a Merkle Tree of hashes.

• Start with the per-chunk hashes.
• Take the hashes, hash them together pairwise, and repeat!

C0

C1

C2

C3

h0=H(C0)

h1=H(C1)

h2=H(C2)

h3=H(C3)

h01=H(h0||h1)

h23=H(h2||h3)

h0123=H(h01||h23)

C4

C5

C6

C7

h4=H(C4)

h5=H(C5)

h6=H(C6)

h7=H(C7)

h45=H(h4||h5)

h67=H(h6||h7)

h4567=H(h45||h67)

h0…7=H(h0123||h4567)

Merkle Trees (2/2)

Once I've constructed this tree, I can publish the root, and ask other people sharing the file to also send the hashes of every sibling in the hash tree.

• Example: When sharing C3, also share h2, and h01.
• This gives the user enough information to compute h3, h23, and h0123.
• Because of collision resistance, an attacker can't find a set of values that produce the same h0123 for a different C3. If h0123 matches my root, the value is legit.

C0

C1

C2

C3

h0=H(C0)

h1=H(C1)

h2=H(C2)

h3=H(C3)

h01=H(h0||h1)

h23=H(h2||h3)

h0123=H(h01||h23)

O(logN) siblings shared alongside C3.

O(logN) hashes computed by the user downloading C3.

Most of the tree can be ignored when checking one node.

Merkle Tree Tradeoffs

Now, people only have to download the root from me. No more bandwidth issues!

​

Interesting takeaway: Untrusted parties can prove that a chunk of data is legitimate relatively cheaply, as long as the root comes from somewhere you trust.

Application: Password Hashing

Lecture 9, CS 161, Summer 2026

Intro to Cryptography

• What is Cryptography?
• Definitions

Cryptographic Hashes

• Collision-Resistant Hash Functions (CRHFs)
• Building CRHFs
• Other Cryptographic Hash Properties
• Do Cryptographic Hashes Prove Authenticity?

Hash Applications

• Merkle Trees
• Password Hashing

Password Hashing

To check passwords, the server must store each user's password.

Storing plaintext passwords is a really bad idea.

If an attacker steals the passwords file, they know everybody's password.

Storing the hash of each user's password is better.

If a one-way hash is used, the attacker cannot easily learn the plaintext password.

​

When a user enters a password, hash it and compare against database.�Works because hashes are deterministic.

Mitigating Brute-Force: Slow Hashes

Problem: People pick weak passwords, so brute-force attacks are feasible.

• Dictionary attack: Try hashing common passwords, and look for a match n the hashed password database.
• Special data structures called rainbow tables make this attack even easier.

​

Solution 1: Use a slow hash, e.g. 0.1sec instead of 0.001sec.

• Legitimate users won't notice the difference.
• But attackers will notice:�A brute-force attack now takes 1000 times as long!

Not an asymptotic change;�it's an extra large constant factor.

Mitigating Brute-Force: Salted Hashes

Solution 2: Salting. For each user, include a different value in the hash.

• The value is stored alongside the password hash (not a secret).
• Without salts: Can compute H("password123") once for every user in the table.
• With salts: Must compute H("password123" || salt) once for each in the table.

Offline vs. Online Attacks

There are two ways to perform brute-force attacks:

Offline brute-force attacks:

• Attacker performs the computation themselves.
• Example: Attacker steals the passwords file and checks hashes on their laptop.
• Defenses: Slow hashes, salting.

Online brute-force attacks:

• Attacker does not perform computation.
• Example: Attacker types guesses into the login page.
• Defenses: Rate-limiting.