[Figure: FiveStudy logo]
FiveStudy
Cybersecurity · Unit 4 · 4.2.a
AP Cybersecurity · Securing Devices
Why Hashes Store Passwords
A service should never know your password — only enough to recognize it.
key ideaA service should never know your password. It stores a one-way hash, salted so identical passwords look different.
exam-day recap
- Services should not store passwords in plaintext, so a stolen user:password directory does not immediately reveal them.
- A hash is collision resistant: it is hard to find two inputs with the same output.
- A hash is one-way: hard to recover the input from the output, so the stored value does not reveal the password.
- A hash is deterministic: the same input always gives the same output, which is what makes verification possible.
- An n-bit hash has 2ⁿ possible outputs while inputs are infinite, so collisions must exist.
- A hash function is broken when an efficient algorithm exists to force a collision — not because collisions exist.
- A salt is a few random bits, unique to each user, hashed together with the password.
- Salt makes identical passwords produce different hashes, so password reuse is invisible in the file.
- Verify by recomputing and comparing, never by reversing: a hash is never reversed, only recomputed and matched.
The syntax
Password-based authentication services should not store passwords in plaintext, so that an adversary who obtains the user:password directory does not immediately know the passwords. A hash makes verification possible without storage.
| Property | What it means | Why it matters |
|---|
| collision resistant | hard to find two inputs with the same output | an adversary cannot substitute a different password |
| one-way | hard to recover the input from the output | the stored value does not reveal the password |
| deterministic | the same input always gives the same output | verification is possible at all |
| fixed length | an n-bit hash has 2ⁿ possible outputs | inputs are infinite, so collisions must exist |
The fourth row is a mathematical certainty rather than a flaw: infinitely many inputs, finitely many outputs. A hash function is broken when an efficient algorithm exists to force a collision — not because collisions exist.
what a password directory actually holdssalt and hash per user — no passwords anywhere
user salt stored hash (truncated)
------------------------------------------------
a.rivera 9f2c81e4 3b1f...c07a
t.okafor 17bd0a55 9e4d...21f6
m.singh c4e91b02 77aa...bd38
# a.rivera and t.okafor chose the SAME password.
# different salts -> different hashes -> the reuse is invisible.
salt columna few random bits, unique to each user, stored alongside the hashstored hashthe output of hashing salt + password togethersame passwordtwo users chose the same one, and the hashes still differwhy that matterswithout salt, identical hashes would advertise the reuse to anyone who stole the file
HashAlso called a hash output, checksum, message digest or digest — a fixed-length one-way output.
CollisionTwo different inputs producing the same hash. Inevitable, because inputs are infinite and outputs are 2ⁿ.
SaltA few random bits hashed together with a user's password so that identical passwords produce different hashes.
Named algorithmsMD5, SHA-1, SHA-256, SHA-512, NTHash, RIPEMD-160 — SHA stands for Secure Hash Algorithm.
Broken hash functionOne for which an efficient algorithm exists to force a collision.
Doing it step by step
1
Never store the password
Storing plaintext means a stolen directory hands over every account immediately — and, given password reuse, accounts elsewhere too.
in a password out a decision not to keep it
2
Generate a salt for this user
A few random bits, unique to the user. It is not secret — it is stored alongside the hash — but it must be different for every user.
out a per-user salt
3
Hash the salt together with the password
The hash function is one-way and deterministic: the same pair always yields the same output, and the output does not reveal the pair.
out a fixed-length digest
4
Store the salt and the hash
Both go in the directory. The password itself is discarded.
out a directory with no passwords in it
5
Verify by recomputing, never by reversing
On each login, look up the salt, hash it with the supplied password, and compare. A hash is never reversed — only recomputed and matched.
out accept or reject
verifying a loginlookup, recompute, compare
login attempt: user=a.rivera password="hunter-cyclone-14"
1. look up a.rivera -> salt = 9f2c81e4
2. hash( 9f2c81e4 + "hunter-cyclone-14" )
3. compare with the stored hash
4. equal -> accept not equal -> reject
# the stored hash is never reversed. it is only ever recomputed.
step 1the salt is stored in the clear — it does not need to be secretstep 2the same function, over salt + supplied passwordstep 3a comparison of two fixed-length valuesstep 4equality is the whole test — no decryption anywhere
Worked analysis
EX 1
Why not just store the password?
An engineer proposes storing passwords in plaintext because “the database is protected anyway”. Evaluate.
1
Ask what a breach yields
Every password, immediately usable, with no work required.
2
Extend beyond this service
Because users reuse passwords, the breach hands over accounts elsewhere too.
3
State the CED position
Services should not store passwords in plaintext, precisely so that a stolen directory does not immediately reveal them.
4
Note what hashing costs
Nothing operationally — verification still works by recomputation.
5
Conclude
Hash and salt. ‘The database is protected’ is a claim about a control that may fail; hashing assumes it already has.
EX 2
What salt actually fixes
Two users choose the same password. Without salt, what does an adversary learn from the stolen directory?
1
State the unsalted behavior
Identical passwords produce identical hashes.
2
Say what that reveals
Which users share a password — so cracking one cracks several accounts.
3
Note the second gain for the adversary
Precomputed tables can be checked against the whole file at once.
4
Apply salt
A few random bits hashed with each password make the two hashes different.
5
State the property gained
Each password must now be attacked individually, and the reuse is invisible in the file.
EX 3
When is a hash function broken?
A student says MD5 is broken “because collisions exist”. Correct the reasoning.
1
Grant that collisions exist
An n-bit hash has 2ⁿ outputs and infinitely many inputs, so collisions are unavoidable for every hash function.
2
State the real criterion
A function is broken when an efficient algorithm exists to force a collision on demand.
3
Apply it
That is true of MD5, which is why it is unsuitable — not the mere existence of collisions.
4
Name the property being lost
Collision resistance — it should be difficult to find two inputs with the same output.
5
State the correction
Collisions existing is mathematics; collisions being findable is a break.
Verify the result
four checks
- The directory should contain a salt and a hash per user — and no passwords.
- Every user's salt should be different; identical salts undo the benefit.
- Verification must recompute and compare, never attempt to reverse.
- The algorithm should be one with no efficient collision-forcing attack against it.
Check yourself
Why do services store hashes instead of passwords?
Show answer
So that if an adversary gains access to the user:password directory they will not immediately know the passwords. Hashing lets the service verify without ever storing what the user typed.
Why are collisions inevitable?
Show answer
An n-bit hash has 2ⁿ possible outputs, while the number of possible inputs is infinite — so two different inputs must eventually share an output.
Name the properties of a cryptographic hash function.
Show answer
Collision resistant — hard to find two inputs with the same output; one-way — hard to recover the input from the output; and deterministic, so the same input always gives the same result.
What problem does salt solve?
Show answer
Without it, two users with the same password would have identical hashes in the directory. A few random bits hashed with each password make the stored hashes differ.