After completing this tutorial, you should be able to:
Cryptographic hash functions are fundamental building blocks of modern cryptography. They serve as the "fingerprint" of data, producing a fixed-size digest that uniquely represents an input of arbitrary length. Hash functions are used for data integrity verification, password storage, digital signatures, message authentication, and blockchain technology.
Unlike encryption, hash functions are one-way—it is computationally infeasible to recover the input from the hash output. This one-way property makes them invaluable for security applications. The security of a hash function depends on three key properties: preimage resistance, second preimage resistance, and collision resistance.
In this tutorial, we explore the theory and practice of cryptographic hash functions. We begin by defining the essential properties and examining the design principles behind popular hash functions. We then survey the SHA family (SHA-1, SHA-2, SHA-3), discussing their structures, security strengths, and vulnerabilities. We examine other algorithms such as MD5 and BLAKE2, and we explore practical applications including password storage, file integrity, digital signatures, and blockchain.
We also analyze the security of hash functions, including the historical attacks on MD5 and SHA-1, the implications of collision attacks, and the importance of choosing appropriate hash algorithms for different applications. Finally, we discuss standards and recommendations for hash function usage in modern systems.
In Tutorials 2.1–2.8, we studied encryption, modes, and random number generation. This tutorial introduces a different class of cryptographic primitive—hash functions—which provide integrity rather than confidentiality. Tutorial 2.10 will cover Message Authentication Codes (MACs), which build on hash functions. Tutorials 2.11–2.15 will use hash functions in digital signatures and public-key infrastructure.
A cryptographic hash function must be:
Figure 1: The hash function model.
Given a hash value h, it is computationally infeasible to find any input M such that H(M) = h.
Formal definition: For a randomly chosen hash value h, the probability that an attacker can find M such that H(M) = h is negligible.
Importance: This property ensures that an attacker cannot recover the original data from its hash. This is crucial for password storage—even if an attacker obtains the password hash, they cannot determine the password.
Given an input M1, it is computationally infeasible to find a different input M2 such that H(M1) = H(M2).
Formal definition: For a randomly chosen M1, the probability of finding M2 ≠ M1 with H(M1) = H(M2) is negligible.
Importance: This prevents an attacker from substituting one document for another with the same hash. For example, in digital signatures, if an attacker can find a second preimage, they could forge a signature on a different document.
It is computationally infeasible to find any two distinct inputs M1 and M2 such that H(M1) = H(M2).
Formal definition: The probability that any attacker can find a collision is negligible.
Importance: Collision resistance is the strongest property. If collisions can be found, an attacker can create two documents with the same hash—one benign and one malicious—and have the signature on the benign document be valid for the malicious one.
Collision resistance implies second preimage resistance, but not vice versa. Preimage resistance is independent of the other two, though a function that is not collision-resistant may still be preimage-resistant.
The Merkle-Damgård construction is the most common design for hash functions, used in MD5, SHA-1, and SHA-2. It builds a hash function from a compression function (which processes fixed-size blocks) by applying it iteratively to the message, which is padded to a multiple of the block size.
Process:
Figure 2: Merkle-Damgård construction.
The sponge construction is used in SHA-3. It operates on a state of fixed size (the "sponge") and uses two phases: absorption and squeezing.
The sponge construction provides flexibility: any output length can be produced by squeezing the appropriate number of bits.
Figure 3: Sponge construction (used in SHA-3).
The Secure Hash Algorithm (SHA) family is a set of cryptographic hash functions published by NIST. The family includes SHA-1, SHA-2, and SHA-3.
| Algorithm | Output Size (bits) | Internal State (bits) | Block Size (bits) | Construction | Status |
|---|---|---|---|---|---|
| SHA-1 | 160 | 160 | 512 | Merkle-Damgård | Broken (deprecated) |
| SHA-224 | 224 | 256 | 512 | Merkle-Damgård | Secure |
| SHA-256 | 256 | 256 | 512 | Merkle-Damgård | Secure |
| SHA-384 | 384 | 512 | 1024 | Merkle-Damgård | Secure |
| SHA-512 | 512 | 512 | 1024 | Merkle-Damgård | Secure |
| SHA-3 | 224/256/384/512 | 1600 | N/A (sponge) | Sponge | Secure |
SHA-1 (Secure Hash Algorithm 1) was designed by the NSA and published by NIST in 1995 as FIPS 180-1. It produces a 160-bit hash value.
SHA-1 is a Merkle-Damgård hash with:
SHA-1 has been broken in practice:
SHA-2 was published by NIST in 2001 (FIPS 180-2) to replace SHA-1. It is a family of hash functions with different output sizes, based on the same design principles but with stronger security.
SHA-256 produces a 256-bit hash value. It uses:
Security: SHA-256 provides 128 bits of collision resistance (birthday bound) and 256 bits of preimage resistance. No practical attacks exist.
SHA-512 produces a 512-bit hash value. It uses:
Security: SHA-512 provides 256 bits of collision resistance and 512 bits of preimage resistance.
These are truncated versions of SHA-256 and SHA-512, respectively. They provide output sizes that match the key sizes of certain ciphers (e.g., SHA-224 with 3DES).
SHA-2 is considered secure and is the current standard for most applications. The U.S. government mandates SHA-2 for cryptographic applications (FIPS 180-4).
SHA-3 was selected by NIST in 2015 (FIPS 202) after a public competition. The winning algorithm was Keccak, designed by Guido Bertoni, Joan Daemen, Michaël Peeters, and Gilles Van Assche.
SHA-3 uses the sponge construction with the Keccak-p permutation, which operates on a 1600-bit state. It supports output sizes of 224, 256, 384, and 512 bits.
| Variant | Output Size (bits) | Security Level (bits) |
|---|---|---|
| SHA3-224 | 224 | 112 (collision), 224 (preimage) |
| SHA3-256 | 256 | 128 (collision), 256 (preimage) |
| SHA3-384 | 384 | 192 (collision), 384 (preimage) |
| SHA3-512 | 512 | 256 (collision), 512 (preimage) |
SHA-3 also includes SHAKE128 and SHAKE256, which are extendable-output functions (XOFs). They produce variable-length output, similar to a random oracle.
Use: SHAKE is useful when a variable-length output is needed, such as in key derivation.
MD5 produces a 128-bit hash value. It was designed by Ron Rivest in 1991.
BLAKE2 is a cryptographic hash function designed by Jean-Philippe Aumasson, Samuel Neves, Zooko Wilcox-O'Hearn, and Christian Winnerlein. It is faster than SHA-2 and SHA-3 and provides security comparable to SHA-3.
| Algorithm | Output Size | Speed (Software) | Security Status |
|---|---|---|---|
| MD5 | 128 bits | Fast | Broken |
| SHA-1 | 160 bits | Fast | Broken |
| SHA-256 | 256 bits | Moderate | Secure |
| SHA-512 | 512 bits | Moderate | Secure |
| SHA3-256 | 256 bits | Slower (software) | Secure |
| BLAKE2b | 512 bits | Very fast | Secure |
Instead of storing passwords in plaintext, systems store a hash of the password. When a user enters a password, it is hashed and compared to the stored hash.
Key Concepts:
salt = random(16 bytes)hash = SHA256(salt + password)store(salt, hash)SHA256(retrieved_salt + input_password) == stored_hash
Hash functions are used to verify that a file or message has not been altered.
In digital signatures, the message is hashed and the hash is signed, rather than signing the entire message. This is more efficient because the hash is much smaller than the message.
Figure 4: Digital signature with hashing.
HMAC (Hash-based Message Authentication Code) uses a hash function with a secret key to provide message authentication. We will cover MACs in detail in Tutorial 2.10.
Hash functions are fundamental to blockchain technology:
Figure 5: Merkle tree structure.
The birthday paradox states that for an n-bit hash, the expected number of hashes needed to find a collision is approximately 2n/2. For SHA-256 (n=256), this is 2128 operations, which is infeasible.
This is why hash functions need to be at least 256 bits to provide 128 bits of collision security.
In Merkle-Damgård hash functions (MD5, SHA-1, SHA-2), given H(M) and the length of M, it is possible to compute H(M || padding || X) without knowing M. This is the length extension attack.
Mitigation: Use HMAC (which hashes the key before and after the message) or use a hash function with a different construction (SHA-3 is immune to length extension attacks).
Hash functions can be vulnerable to side-channel attacks (timing, power consumption) if not implemented with constant-time code. Most hash functions are designed to run in constant time, but implementation bugs can introduce vulnerabilities.
Quantum computers using Grover's algorithm can find a preimage in 2n/2 operations (instead of 2n). This means that SHA-256 provides 128 bits of preimage resistance against quantum attacks, while SHA-512 provides 256 bits.
| Algorithm | Collision Resistance | Preimage Resistance | Status |
|---|---|---|---|
| MD5 | Broken (216) | Weak (2122) | Deprecated |
| SHA-1 | Broken (263) | 2160 (theoretical) | Deprecated |
| SHA-256 | 2128 (secure) | 2256 (secure) | Recommended |
| SHA-512 | 2256 (secure) | 2512 (secure) | Recommended |
| SHA3-256 | 2128 (secure) | 2256 (secure) | Recommended |
In 2004, researchers demonstrated practical collisions for MD5. In 2012, the Flame malware used an MD5 collision to forge a Microsoft certificate, allowing it to masquerade as a legitimate Windows Update. This demonstrated that MD5 was not only theoretically broken but practically exploitable.
Lesson: Hash functions with known weaknesses must be replaced immediately. Relying on them for security-critical applications is dangerous.
In 2017, Google and CWI Amsterdam announced the first practical SHA-1 collision. They produced two different PDF files with the same SHA-1 hash. The attack required about 263.1 operations (110 GPU years, costing about $110,000).
Impact: Major browsers stopped accepting SHA-1 certificates. Certificate authorities stopped issuing SHA-1 certificates. NIST officially deprecated SHA-1.
Lesson: Even with a large security margin (280), advances in cryptanalysis and computing power can break algorithms sooner than expected.
In 2012, LinkedIn suffered a data breach where 6.5 million passwords were stolen. The passwords were stored using SHA-1 hashes without salts. Attackers were able to crack many of the passwords using rainbow tables and brute-force attacks.
Lesson: Hashing passwords without salts is insecure. Use salted hashes with key stretching functions (bcrypt, scrypt, Argon2).
Using the SHA-256 algorithm conceptually, explain what happens when you hash the string "Hello, World!". What output size is produced, and why is it a fixed size?
SHA-256 processes the input by padding it to a multiple of 512 bits, then iteratively applies a compression function to 512-bit blocks, updating an internal 256-bit state. The final state is the 256-bit hash output. The output is fixed at 256 bits regardless of the input size.
For a hash function with a 160-bit output (like SHA-1), how many hashes need to be computed to find a collision with 50% probability? How about for a 256-bit hash (like SHA-256)?
For an n-bit hash, the birthday bound is approximately 2n/2 hashes.
For SHA-1 (n=160): 280 ≈ 1.2×1024 hashes.
For SHA-256 (n=256): 2128 ≈ 3.4×1038 hashes.
This shows that SHA-256 provides vastly stronger collision resistance than SHA-1.
Explain why simply hashing a password with SHA-256 is insufficient for password storage. What additional mechanisms should be used?
Simply hashing a password with SHA-256 is insufficient because:
Additional mechanisms:
Explain how a length extension attack works on SHA-256 and how HMAC mitigates it.
In SHA-256 (Merkle-Damgård construction), the state after processing message M can be used to continue hashing with additional data, without knowing M. Given H(M) and the length of M, an attacker can compute H(M || padding || X).
HMAC mitigates this by hashing the key in two passes: HMAC(K, M) = H(K ⊕ opad || H(K ⊕ ipad || M)). The outer hash prevents the length extension attack because the attacker does not know the inner hash state (it depends on the key).
In a Merkle tree with 8 transactions (Tx1 to Tx8), how many hashes are needed to verify that Tx5 is in the tree? Explain the process.
To verify Tx5, you need:
Path for Tx5: Tx5 → Hash56 → Hash5678 → Root
You need H(Tx6) (sibling of Tx5), Hash78 (sibling of Hash56), and Hash1234 (sibling of Hash5678) to compute the root. That's 3 hashes plus the root to verify. So 3 hashes are needed (log₂(8) = 3).
Research the NIST SHA-3 competition (2007-2015). Write a 500-word report that covers:
Complete answer would describe that the competition was motivated by the need for a new design in case SHA-2 was broken, and to provide diversity. Finalists included Keccak, BLAKE, Grøstl, JH, and Skein. Keccak was chosen for its security margin, performance in hardware, and simplicity. Advantages of SHA-3 include immunity to length extension attacks, and support for extendable-output functions (SHAKE).
Compare PBKDF2, bcrypt, scrypt, and Argon2. Create a table showing:
Write a summary recommending which to use and why.
Complete answer would include a table with the four algorithms. PBKDF2 is hash-based, not memory-hard, susceptible to GPU attacks; bcrypt is better but still memory-limited; scrypt is memory-hard; Argon2 is the most advanced and memory-hard. Recommendation: Argon2id for new systems (winner of the Password Hashing Competition), otherwise bcrypt or PBKDF2 with high iteration counts.
Research how Bitcoin uses SHA-256. Write a 500-word report that explains:
Complete answer would explain that SHA-256 is used in block hashing (proof-of-work), Merkle trees (transaction verification), and address generation (RIPEMD-160 after SHA-256). Double SHA-256 is used to protect against length extension attacks (though SHA-256 is vulnerable, double hashing mitigates). SHA-256 was chosen for its security and widespread adoption. The security of Bitcoin relies on the collision and preimage resistance of SHA-256.
Research how a length extension attack could be used against a simple authentication scheme that uses H(K || M) where K is a secret key. Describe the attack and how to prevent it.
Complete answer would explain that an attacker who knows H(K || M) and the length of M can compute H(K || M || padding || X) without knowing K. This allows the attacker to forge messages with the same authentication tag. Prevention: use HMAC (which hashes the key both before and after the message) or use a hash function immune to length extension attacks (SHA-3).
Write a program in your preferred language that:
Test it with files of different sizes. Write a report on your implementation and any performance observations.
Complete answer would include source code, test results (showing that the program detects any modification to the file), and a discussion of performance (e.g., SHA-256 processing speed, the effect of file size on computation time). Observations might include that hashing large files (e.g., > 1 GB) takes a few seconds and is I/O-bound.
This tutorial has provided a comprehensive examination of cryptographic hash functions and their role in data integrity. We began by defining hash functions and their essential properties: preimage resistance, second preimage resistance, and collision resistance. We explored the design principles behind hash functions, including the Merkle-Damgård construction (used in MD5, SHA-1, SHA-2) and the sponge construction (used in SHA-3).
We surveyed the SHA family in detail, from SHA-1 (now broken) to SHA-2 (secure and recommended) to SHA-3 (a modern alternative with a different design). We also discussed other algorithms such as MD5 (broken) and BLAKE2 (secure and fast).
We examined real-world applications of hash functions, including password storage (with salts and key stretching), data integrity verification, digital signatures, message authentication codes, and blockchain (Merkle trees). Each application demonstrates the versatility and importance of hash functions in modern security.
We analyzed security considerations, including the birthday attack (which reduces collision resistance to 2n/2), length extension attacks (affecting Merkle-Damgård constructions), and side-channel attacks. We discussed the importance of using appropriate hash functions for different contexts and the standards that guide their use.
The case studies illustrated the practical consequences of hash function weaknesses: the MD5 collision attack used in Flame malware, the SHA-1 collision demonstrated in SHAttered, and the LinkedIn password breach. These incidents underscore the importance of using secure hash functions and following best practices for password storage.
With this foundation, you are now equipped to select and use hash functions appropriately in cryptographic systems, understand their security properties, and recognize the risks associated with weaker algorithms.
In Tutorial 2.10: Message Authentication Codes (MACs), we will build on hash functions to provide message authentication. HMAC (Hash-based Message Authentication Code) uses hash functions to provide both integrity and authentication, addressing the limitations of hash functions alone.