Cryptographic Hash Function
1. Overview
Definition: A cryptographic hash function is a one-way function that maps an arbitrary-length input message to a fixed-length digest (hash value), designed so that preimages, second preimages, and collisions are computationally hard to find.
In information systems, questions such as "has this data been altered in transit or storage?", "does the password this user presented match the one on record?", and "is this document the same one that was signed?" arise constantly. All of these become practical only if sameness can be decided from a short fingerprint without re-comparing the entire original. A cryptographic hash function produces exactly this fingerprint as a basic primitive, and it permeates nearly every layer of modern security — digital signatures, message authentication, integrity verification, password storage, blockchain, and deduplication.
Simple checksums (CRC, parity) also produce fixed-length digests, but they target only detection of accidental errors, so an attacker can craft a different piece of data that yields the same value. A cryptographic hash, by contrast, makes deliberate forgery prevention a core requirement: even with vast computational resources, an attacker cannot easily find an input satisfying a desired digest. This distinction creates radically different assurance levels under the same word "hash."
Cryptographic hashes matter because they enable the compression of trust. A multi-gigabyte disk image, millions of transactions, or an arbitrary-length certificate chain can be summarized into a single 256-bit value; transmit only that value over a trusted channel and the vast remaining data can travel over untrusted paths while tampering is still detectable. For example, a Linux distribution publishes only a single SHA-256 value (a 64-digit hexadecimal string) for a multi-GB ISO file on its official site, and users hash the file received from a mirror and compare. The problem of comparing ten million records becomes a 32-byte comparison.
Background and necessity
Early cryptography focused on confidentiality (encryption), but as networks spread, demand exploded for integrity and authentication — proving "the content has not changed" and "the sender is genuine" rather than merely hiding content. Public-key signatures made signing cost constant by signing not the whole message but its hash, and hashing thereby became a mandatory preprocessing step of signature schemes.
Also, storing passwords in plaintext means every account is instantly compromised on a database breach, so passwords must be kept in an unrecoverable form. A one-way hash offers a storage method that is "stored but cannot be reversed," making it the standard means of password protection. As we will see, using a general-purpose hash directly is dangerous and a dedicated password hash is needed — an important advanced point.
Problem definition from the professional engineer's view
In an essay answer, describing a hash function merely as "a function that shortens to a fixed length" is a failure. The key is to connect the three security properties (preimage, second-preimage, collision resistance) to the applications that collapse when each is broken, and to distinguish the halving of security strength due to the birthday paradox, the length-extension vulnerability of the Merkle–Damgård structure, and the difference in purpose between general-purpose hashes and password hashes. In short, the axis should be "which property is needed, and why, for which application."
2. Core security properties and required characteristics
To call a cryptographic hash function H secure, it must satisfy three computational hardness conditions. The structure diagram below shows the flow of input, processing, and output together with the attacks each property defends against.
flowchart TD
M["Arbitrary-length message M"] --> P["Padding + block splitting"]
P --> C["Compression/absorption (iterated rounds)"]
C --> D["Fixed-length digest H(M)"]
D --> U1["Integrity verification (file/firmware)"]
D --> U2["Digital signature preprocessing"]
D --> U3["Password storage"]
D --> U4["Blockchain/Merkle root"]
A1["Preimage attack: recover M from H(M)"] -. defends .-> C
A2["Second preimage: find different M' with same hash"] -. defends .-> C
A3["Collision: any pair with H(M1)=H(M2)"] -. defends .-> C
A. Preimage resistance
Preimage resistance means that, given a hash value y, it must be hard to find an input M such that H(M)=y; it is commonly called one-wayness. Password storage relies on this property. From a digest stored in a database alone, the original password must not be recoverable, so that an attacker cannot log in with a leaked hash.
An ideal hash's preimage attack cost is about 2^n attempts for an n-bit output. Thus SHA-256 requires about 2^256 cost against a preimage attack, infeasible with current and near-future computing power. However, if the input space itself is small (the entropy of human-chosen passwords is typically 20–40 bits), it is broken by brute force regardless of the theoretical strength of the hash. This is the basis of the practical lesson that "a strong hash still cannot protect a weak password."
In practice, overconfidence in preimage resistance commonly leads to storing sensitive identifiers (national ID numbers, emails) hashed without salt; when the value distribution is narrow, it is traced back with precomputed tables, so one-wayness is effectively broken. In other words, preimage resistance is a conditional property that must be evaluated together with the input distribution.
B. Second-preimage resistance and collision resistance
Second-preimage resistance means that, given a specific message M, it must be hard to find a different M' with the same hash. Collision resistance, by contrast, is a stronger requirement: it must be hard for an attacker to freely find any pair with H(M1)=H(M2).
The difference between the two properties is stark in attack cost. Second preimage is close to 2^n, but collision drops sharply to about 2^(n/2) due to the birthday paradox. Just as the intuition that a 50% chance of a shared birthday arises with only 23 people, gathering about 2^(n/2) random values makes a match likely. So to target 128-bit security strength, the hash output must be at least 256 bits. This is why SHA-256 is rated as "128-bit-grade collision resistance."
The place where collision resistance is most critically required is digital signatures. If an attacker can make a "benign contract" and a "malicious contract" share the same hash, the signature value the victim produced over the former remains valid over the latter. In fact, the 2012 Flame malware exploited an MD5 collision to forge a code-signing certificate and spread via Windows Update — a flagship case showing how loss of collision resistance can lead to a global attack.
C. Avalanche effect, determinism, and efficiency
A good hash exhibits an avalanche effect, in which flipping even a single input bit flips about half the output bits unpredictably. This removes statistical correlation between input and output, preventing an attacker from inferring partial information. At the same time, a hash is deterministic — the same input must always yield the same value (the premise of verifiability) — and must be computationally efficient so it can be applied even to large volumes of data.
An interesting tension lies here. An integrity/signature hash is better the faster it is, but a password hash should instead be deliberately slow to make an attacker's brute force harder. Even for the same "hash," the design goal is the opposite depending on purpose. Failing to recognize this tension and storing passwords with SHA-256 leaves almost no defense on a breach, since GPUs can compute billions of hashes per second.
3. Representative algorithms and internal structure
The internal structure of hashes divides broadly into the Merkle–Damgård (MD) structure and the sponge structure. The detailed process diagram below shows the difference in processing flow between the two structures.
flowchart LR
subgraph MD["Merkle-Damgard structure (MD5/SHA-1/SHA-2)"]
direction LR
IV["Initial value IV"] --> F1["Compression f (block1)"]
F1 --> F2["Compression f (block2)"]
F2 --> F3["Compression f (block n)"]
F3 --> OUT1["Final chaining value = digest"]
end
subgraph SP["Sponge structure (SHA-3/Keccak)"]
direction LR
S0["State initialization"] --> AB["Absorb: XOR message then permutation f"]
AB --> SQ["Squeeze: extract output from state"]
SQ --> OUT2["Variable-length digest"]
end
A. Generational evolution of algorithms
Hash algorithms have gone through repeated generational turnover, chased by advances in attack techniques. MD5 (128-bit) and SHA-1 (160-bit) were de facto standards for a long time, but collisions were demonstrated and they were retired from security use; SHA-2 is now the workhorse, and SHA-3 was standardized as an alternative for structural diversity. The table below compares the main algorithms.
| Algorithm | Output length (bits) | Internal structure | Collision resistance (bits) | Status |
|---|---|---|---|---|
| MD5 | 128 | Merkle–Damgård | effectively 0 (collision in seconds) | deprecated |
| SHA-1 | 160 | Merkle–Damgård | broken (≤≈2^63) | deprecated |
| SHA-256 | 256 | Merkle–Damgård | 128 | recommended |
| SHA-512 | 512 | Merkle–Damgård | 256 | recommended |
| SHA-3-256 | 256 | sponge (Keccak) | 128 | recommended |
| SHAKE128/256 | variable | sponge (XOF) | 128/256 | recommended |
B. The Merkle–Damgård structure and the length-extension vulnerability
The MD structure splits a message into fixed-size blocks and applies the compression function f iteratively like a chain, passing the previous block's output (the chaining value) as input to the next block. It was widely used for its simple implementation and the ability to reduce collision resistance to the security of the compression function as a proof.
However, this structure has a unique weakness called the length-extension attack. If an attacker knows the value H(secret || M) and the message length, they can compute H(secret || M || padding || M') without knowing the secret value secret. For this reason, using "hash(secret||message)" directly for message authentication allows forgery; to prevent this, the double-hash structure HMAC (H(key⊕opad || H(key⊕ipad || M))) became the standard. The fact that SHA-512/256 (a truncated SHA-512) and the sponge-structured SHA-3 are immune to length extension is also an important consideration in algorithm choice.
C. The sponge structure and the significance of SHA-3
SHA-3 (Keccak) is an algorithm that NIST standardized as FIPS 202 in 2015 after a public competition from 2007 to 2012, and its core value is that it is structurally different from SHA-2. Even if a future breakthrough targets SHA-2's MD structure, SHA-3 with its entirely different sponge structure exists immediately as a replacement — providing an insurance of crypto-agility.
The sponge structure XOR-absorbs a message into a large internal state, applies a permutation, and squeezes out as much output as needed, so it naturally supports variable-length output (XOF: SHAKE128/256). This variable-output characteristic is used flexibly in post-quantum signatures (SPHINCS+) and key derivation.
4. Main applications and password storage
Hash applications are easiest to understand classified by required property. Integrity verification (comparing file/firmware hashes) relies on second-preimage resistance, digital signatures and certificates on collision resistance, message authentication (HMAC) on pseudorandomness, and blockchain proof-of-work and Merkle roots on preimage/collision resistance. Data deduplication and content-addressable storage also use the property that "same content means same hash" as the address.
A. Password storage: salt, pepper, and key stretching
Password storage is the flagship area where a general-purpose hash must not be used directly. First, if the same password yields the same hash, an attacker can mass-trace it with a precomputed rainbow table. The device that prevents this is a per-user random salt; mixing salt into the hash input makes even identical passwords different digests, neutralizing precomputation attacks. Second, a fast hash like SHA-256 is tried billions of times per second on a GPU, so key stretching that deliberately makes it slow is needed.
To meet this requirement, dedicated password hashes evolved. PBKDF2 raises cost with iteration count but is relatively weak to GPUs/ASICs; bcrypt is Blowfish-based and uses a little memory; scrypt and Argon2 use a memory-hard design that greatly raises the cost of massively parallel hardware attacks. Argon2 (especially the side-channel-resistant Argon2id), winner of the 2015 Password Hashing Competition, is the top recommendation today. OWASP guides configuring Argon2id with about 19 MiB memory, 2 iterations, and parallelism 1, or PBKDF2-HMAC-SHA256 with about 600,000 iterations. Operating organizations additionally combine a server-only secret value — a pepper — in HMAC form to add one more defensive line in case only the database is leaked.
B. Hashing in digital signatures and certificates
A digital signature signs not the whole message but its digest, so the hash's collision resistance directly equals the signature's unforgeability. Public certificates, code signing, and TLS certificate chains all specify the hash algorithm to be signed, and the industry's bulk deprecation of SHA-1-signed certificates around 2017 was a direct response to the demonstrated collision seen earlier.
5. Comparison and attack cases
Simplifying algorithm choice to "longer output is better" ruins practical design. Length-extension immunity, hardware-acceleration support, standards/regulatory fitness, and performance are all variables. The table below organizes the axes of consideration at selection time and their reasons.
| Consideration axis | Core question | Practical implication |
|---|---|---|
| Security strength | How many bits of collision resistance are needed | For 128-bit grade use SHA-256; for long-term retention / high value use SHA-384/512 |
| Structural diversity | Is it immune to length extension | Use HMAC for authentication, or choose SHA-3/SHA-512-256 |
| Purpose fit | Is faster better or slower better | SHA-2 for integrity, Argon2id for passwords |
| Regulatory fit | Is it a domestically/internationally approved algorithm | Domestic e-signature requires SHA-256 or higher; internationally, FIPS approval |
Attack cases vividly show the basis for this choice. After Wang Xiaoyun's team announced a practical collision for MD5 in 2004, generating a collision in seconds became possible, and in 2008 a forged CA certificate was produced. SHA-1 had a demonstrated collision disclosed in 2017 via the SHAttered attack by Google and CWI, with two different PDFs sharing the same SHA-1 hash at a cost of about 9.2×10^18 (about 2^63) operations, and by 2020 the cost of a chosen-prefix collision had fallen to the tens-of-thousands-of-dollars level. These figures teach that the distance between "theoretically broken" and "practically exploitable" is shorter than one might think.
6. Advanced: standards change and hashes in the post-quantum era
The latest issues surrounding cryptographic hashes are the threat of quantum computing and the consequent re-evaluation of standards. Public-key cryptography (RSA, ECC) can be broken in polynomial time by Shor's algorithm and thus effectively needs full replacement, but symmetric keys and hashes are only accelerated to a square-root degree by Grover's algorithm, which speeds up preimage search from 2^n to 2^(n/2). Thus SHA-256's preimage resistance drops only to about the 128-bit grade in a quantum environment, so combined with collision resistance (already 128-bit), a conservative recommendation is an upgrade to SHA-384/SHA-512. That is, even in the quantum era, a hash is a relatively robust primitive to which one responds not with "deprecation" but with "longer output."
Paradoxically, hashes are also a solution for post-quantum cryptography. Among the post-quantum signatures NIST standardized in 2024, SPHINCS+ (FIPS 205, SLH-DSA) is a hash-based signature that relies solely on the security of the hash function, without new mathematical assumptions like lattices or codes, and is trusted most conservatively because it has fewer mathematical assumptions. Stateful hash signatures such as XMSS and LMS are also being adopted for firmware signing and the like. In this way, a hash holds the dual status of "a target under attack" and "a foundation of defense."
On the standards side, NIST FIPS 180-4 (SHA-1/2) and FIPS 202 (SHA-3) are the basis, and in 2022 NIST announced a phased push to fully discontinue SHA-1 by 2030. Domestically too, the use of SHA-256 or higher is increasingly mandated in e-signatures and public systems, and TLS 1.3 removes vulnerable hash/MAC combinations at the protocol level to enforce safe hash use.
7. Considerations and implications
- Securing crypto-agility: Hardcoding a specific hash algorithm into code and data formats makes replacement cost explode when a future breakthrough occurs. Separate the algorithm identifier as metadata and design to support multiple algorithms in parallel, on the premise that the MD5→SHA-1→SHA-256 replacement history will repeat.
- Principle of per-purpose algorithm separation: Abandon the fantasy of "a single good hash" and codify use-based selection as governance — a fast SHA-2/3 for integrity/signatures, a slow memory-hard Argon2id for passwords, and HMAC for authentication. The anti-pattern of storing passwords with SHA-256 remains common — a warning.
- Combining input entropy with salt and pepper: Do not trust the hash's theoretical strength alone; for low-entropy inputs (passwords, identifiers), always combine a per-user salt, a server-side pepper, and a sufficient work factor. The work factor needs an operational process to be raised periodically in line with hardware progress.
- Trade-offs and a long-term retention strategy: Lengthening the output is safer but increases storage/transmission cost and lowers performance. Long-term retained documents and electronic records may see the algorithm at signing time become weak decades later, so include re-hashing and re-signing procedures (long-term archival signatures, e.g., timestamp-token renewal) in the architecture.
- Related technologies and outlook: Hashes are tightly woven with Merkle trees, blockchain, HMAC, digital signatures, KDFs, deduplication, and content-addressable storage, so track the ripple effect of a single algorithm replacement on upper protocols through impact analysis. From a quantum-resistance view, it is advisable to reflect an upgrade to SHA-384 or higher and the introduction of hash-based signatures (SPHINCS+) in the mid-term roadmap.
References
- NIST, FIPS 180-4 Secure Hash Standard(SHS), https://doi.org/10.6028/NIST.FIPS.180-4
- NIST, FIPS 202 SHA-3 Standard, https://doi.org/10.6028/NIST.FIPS.202
- NIST, FIPS 205 Stateless Hash-Based Digital Signature Standard(SLH-DSA), https://doi.org/10.6028/NIST.FIPS.205
- OWASP, Password Storage Cheat Sheet, https://cheatsheetseries.owasp.org/cheatsheets/Password_Storage_Cheat_Sheet.html
- Stevens et al., The first collision for full SHA-1(SHAttered), https://shattered.io/
- NIST, Transitioning the Use of Cryptographic Algorithms and Key Lengths(SP 800-131A), https://csrc.nist.gov/pubs/sp/800/131/a/r2/final
In one line: A cryptographic hash function is a one-way summarizing function with preimage, second-preimage, and collision resistance; understanding the halving of security strength from the birthday paradox and the length-extension vulnerability of Merkle–Damgård, one applies SHA-2/3 and HMAC for integrity/signatures/authentication and salt, pepper, and memory-hard Argon2id for passwords by purpose, and responds in the quantum era with longer output and hash-based signatures — a core primitive of modern security.