01Overview
In 1979 Merkle introduced hash trees and a security definition for one-way hash functions. MD4 appeared in 1990, followed by MD5 (1992) and SHA-1 (1995). Hashes went into password storage, data integrity, digital signatures and blockchains.
Hash functions age: in 2004 Wang Xiaoyun’s team broke the collision resistance of MD5 and SHA-1, accelerating the move to SHA-2 and SHA-3. Password storage evolved from salted hashes to bcrypt, scrypt and Argon2, which use computational cost against brute force. A hash is not encryption — it is irreversible, and should not be used as one.
02History
- 1979
Merkle trees
A structure for verifying integrity.
- 1992
MD5
Widely used, later found to collide.
- 1995
SHA-1
The basis of TLS and Git.
- 2004
MD5 and SHA-1 collisions
Attacks by Wang Xiaoyun's team.
- 2015
SHA-3
Keccak is standardised.
03Core concepts
Collision resistance
It is hard to find two different inputs with the same hash.
Salting
Add a random value per password to defeat rainbow tables.
Hash tree
A tree structure that verifies the integrity of large data efficiently.
04Hands-on
Do it once — it beats reading it ten times
Break a toy 24-bit hash by brute force, then redo it with a salted hash and compare the effort
05Self-check
Say it in your own words first, then open the answer. Whatever you cannot explain is what to review next.
Can you explain "Collision resistance"?
It is hard to find two different inputs with the same hash.
Can you explain "Salting"?
Add a random value per password to defeat rainbow tables.
Can you explain "Hash tree"?
A tree structure that verifies the integrity of large data efficiently.
What problem did it solve, and why was there nothing better at the time?
Go back to the history section: how was this done before, and what did it cost?
If you had to build it today, how would you break it down?
Use the hands-on task above: write a plan of at most three steps before you start.
06Key people
Ralph Merkle
1952 –
A pioneer of hash trees and public-key cryptography.
Wang Xiaoyun
1966 –
Found the collision attacks on MD5 and SHA-1.
07Further reading
- Handbook of Applied Cryptography
- On the Security of Hash Functions