A hash function takes an input of any size and produces a fixed-length output, often called a digest or hash value. This seemingly simple operation underpins an enormous range of modern technology, from the password check that happens when you log in to a website, to the data structures that let databases retrieve records in near-instant time, to the cryptographic chains securing billions of dollars in blockchain transactions. The reason hash functions are so ubiquitous is that they solve several distinct problems at once: verifying data integrity, organizing information for fast lookup, and making certain computations practically irreversible. But not all hash functions are created equal, and understanding what separates a good one from a broken one matters more than ever.
What a Hash Function Actually Does
Think of a hash function as a meat grinder for data. You feed in a file, a password, a message, or any string of bits, and out comes a fixed-size string of characters. Feed in a 10-gigabyte video, and you get a hash that might be 256 bits long. Feed in a single letter, and you still get a 256-bit output. The process is deterministic: the same input always produces the same output. But even the tiniest change to the input, flipping a single bit, produces a wildly different output. This sensitivity to small changes is sometimes called the avalanche effect, and it is what makes hash functions useful for detecting tampering.
Crucially, the process is one-way. You cannot reconstruct the original input from the hash output alone. If you hash the word “hello” with a modern algorithm, there is no mathematical shortcut to look at the resulting digest and work backward to discover the word was “hello.” The only option is brute force: guess inputs, hash each one, and see if the output matches. For well-designed hash functions with large output sizes, this brute-force search is computationally infeasible.
The Three Security Properties
Cryptographers evaluate hash functions against three core properties, and understanding them helps clarify why some algorithms get retired while others remain trusted. A formal treatment by Rogaway and Shrimpton laid out these properties and the relationships among them within a concrete-security framework.1ResearchGate. Cryptographic Hash-Function Basics: Definitions, Implications, and Separations for Preimage Resistance, Second-Preimage Resistance, and Collision Resistance
- Preimage resistance: Given a hash output, it should be infeasible to find any input that produces that output. This is what makes password hashing work. Even if an attacker steals a database of hashed passwords, they cannot simply reverse the hashes to get the originals.
- Second-preimage resistance: Given a specific input and its hash, it should be infeasible to find a different input that produces the same hash. Without this property, an attacker could swap a legitimate document for a forged one that hashes to the same value.
- Collision resistance: It should be infeasible to find any two different inputs that produce the same hash. This is the strongest of the three properties. If an attacker can generate collisions at will, they can undermine digital signatures and certificates.
These properties are related but not identical. Collision resistance implies second-preimage resistance in practice, but the reverse is not necessarily true. A hash function can lose collision resistance, meaning researchers can find two inputs with the same output, while still being strong enough that you cannot reverse a specific hash. That is roughly what happened with MD5 and SHA-1: both had their collision resistance broken years before anyone could efficiently reverse individual hashes.
Cryptographic Versus Non-Cryptographic Hash Functions
Not every hash function needs to resist a determined attacker. In many software applications, the goal is simply speed and even distribution of values, not security. These non-cryptographic hash functions are designed to be fast, spreading data evenly across a table so that lookups stay efficient. Functions like MurmurHash, CityHash, and xxHash are widely used in compilers, databases, video games, and networking code. A study evaluating the most common non-cryptographic hash functions found that while many performed well on speed and distribution, some had notable weaknesses in collision resistance and the avalanche effect.2ResearchGate. Performance of the most common non-cryptographic hash functions
The trade-off is straightforward. Cryptographic hash functions like SHA-256 or SHA-3 are deliberately slow and computationally expensive compared to their non-cryptographic cousins. That expense is a feature, not a bug: it makes brute-force attacks harder. But if you are building an in-memory hash table to look up user sessions, you do not need brute-force resistance. You need a function that runs in nanoseconds and distributes keys evenly. Using SHA-256 for a hash table lookup would work correctly but waste enormous processing time. Using MurmurHash to protect passwords would be fast but catastrophically insecure.
Choosing the wrong type is a real-world mistake that happens more often than you might expect. In 2011, researchers demonstrated that many web frameworks used predictable non-cryptographic hash functions for internal data structures, making them vulnerable to denial-of-service attacks. An attacker could craft inputs designed to cause hash collisions, degrading a hash table’s performance from near-instant to painfully slow, effectively taking down the server.
How Cryptographic Hash Functions Are Built
Most cryptographic hash functions you have heard of, including MD5, SHA-1, and the SHA-2 family, are built on a design pattern called the Merkle-Damgård construction. The idea is to break the input message into fixed-size blocks and then process each block sequentially through a compression function, chaining the output of one step into the next. The final output of the chain is the hash digest. This approach is elegant and well-studied, but it has known structural weaknesses. One of the most notable is the length-extension attack: if you know the hash of a message but not the message itself, you can compute the hash of that message with additional data appended to it, without ever learning the original message. This property has caused real security vulnerabilities in systems that used raw SHA-256 hashes as authentication tokens.
SHA-3, the newest member of the SHA family, takes a fundamentally different approach called the sponge construction. Instead of using a compression function, the sponge design uses a fixed-length permutation and can produce output of arbitrary length.3Journal of Information and Organizational Sciences. Merkle-Damgård Construction Method and Alternatives: A Review The sponge absorbs the input data in chunks and then squeezes out the desired amount of output. This design sidesteps the length-extension vulnerability entirely. The same review notes that inner collisions remain the only known theoretical weakness of the sponge approach, a property it shares in concept with all iterated hash constructions but which has not led to practical attacks against SHA-3.4Journal of Information and Organizational Sciences. Merkle-Damgård Construction Method and Alternatives: A Review
Hash Tables and the Software You Use Every Day
The most common use of hash functions has nothing to do with security. Hash tables, sometimes called hash maps or dictionaries, are one of the most fundamental data structures in computer science. They work by using a hash function to convert a key, such as a username or a product ID, into an index in an array. When the function distributes keys evenly across the array, lookups take roughly constant time regardless of how much data is stored. That is why your web browser can check whether a URL is in your history almost instantly, and why database engines can retrieve a row from millions of records without scanning them one by one.
The catch is collisions. Because a hash function maps a potentially infinite set of inputs to a finite set of outputs, two different keys will occasionally hash to the same slot. How the system handles those collisions has a big impact on performance. The two main strategies are chaining, where each slot holds a linked list of all items that hashed there, and open addressing, where the system probes other slots until it finds an empty one. Research on parallel computing environments found that traditional collision-resolution strategies like linear probing and double hashing performed poorly on massively parallel systems due to communication overhead and queuing delays.5Journal of Parallel and Distributed Computing. Parallel Hashing: Collision Resolution Strategies and Performance The researchers developed a new strategy called hypercube hashing that combined the randomness of double hashing with the low communication cost of linear probing, outperforming other open-addressing methods across the board. When the hash table was heavily loaded, chaining still performed best.6Journal of Parallel and Distributed Computing. Parallel Hashing: Collision Resolution Strategies and Performance
For most everyday software, the collision-handling strategy is invisible to the user. But the choice matters a great deal to the engineers building these systems, especially at scale. A poorly chosen hash function that clusters keys into the same few slots can turn a fast hash table into something barely better than a linear search.
Blockchains and Distributed Systems
Hash functions are the structural backbone of blockchain technology. Every block in a blockchain contains the hash of the previous block, creating a chain where altering any historical block would change its hash, which would invalidate every subsequent block. This is what makes blockchains tamper-resistant. Within each block, individual transactions are typically organized into a Merkle tree, a binary tree structure where each leaf node is the hash of a transaction and each internal node is the hash of its two children. The root hash at the top summarizes all the transactions in the block, allowing anyone to verify that a specific transaction is included without downloading the entire block.
The security of this structure depends heavily on the collision resistance of the underlying hash function and the length of the hash output. A study of Merkle trees found that as the tree’s path length increases, the probability of root-level collisions grows, creating potential vulnerabilities. Longer hash outputs counteract this effect significantly, reinforcing why modern blockchains use 256-bit hash functions rather than shorter ones.7ScienceDirect. Merkle trees in blockchain: A Study of collision probability and security implications Researchers have also proposed hybrid structures like the T-Merkle hash tree, which combines properties of balanced search trees with Merkle trees to improve storage efficiency on-chain and support faster lookups while still providing data integrity verification for cloud storage.8Mobile Information Systems. Enabling Decentralized and Dynamic Data Integrity Verification for Secure Cloud Storage via T-Merkle Hash Tree Based Blockchain
Beyond blockchains, hash functions play a key role in distributed systems more broadly. Consistent hashing is a technique used to distribute data across multiple servers in a way that minimizes disruption when servers are added or removed. Rather than reassigning all data when the number of servers changes, consistent hashing only moves a small fraction of the data. This approach is widely adopted in networks and distributed systems for load balancing.9ACM Transactions on Internet Technology. DxHash: A Memory-saving Consistent Hashing Algorithm If you use a content delivery network, a distributed cache, or a cloud database, consistent hashing is almost certainly running under the hood.
Perceptual Hashing and Fuzzy Matching
Cryptographic hash functions are designed so that the tiniest change to an input produces a completely different output. But sometimes you want the opposite behavior. Perceptual hash functions are designed to produce similar outputs for inputs that are similar to a human observer. Two copies of the same photograph, one compressed and one with slightly adjusted brightness, should produce nearly identical perceptual hashes even though their underlying bit patterns are quite different.10Procedia Computer Science. Analysis of Perceptual Hashing Algorithms in Image Manipulation Detection
This property makes perceptual hashing useful for detecting duplicate images, identifying copyrighted content, and flagging known illegal material. Social media platforms use perceptual hashing at enormous scale to check uploaded images against databases of known content. However, the technology has clear limitations. The same study evaluating perceptual hashing algorithms found that they performed less than ideally at distinguishing maliciously manipulated images from legitimately modified ones.11Procedia Computer Science. Analysis of Perceptual Hashing Algorithms in Image Manipulation Detection An attacker who understands how a perceptual hash works can make targeted edits that change the meaning of an image while keeping its perceptual hash close to the original. This is a fundamental tension: the more tolerant a perceptual hash is of innocent changes, the easier it is to slip malicious changes past it.
Perceptual hashing is also not limited to images. Audio fingerprinting services like Shazam use a related concept to identify songs from short noisy clips. Video platforms apply similar techniques to detect re-uploads of copyrighted content. In each case, the core idea is the same: reduce the input to a compact fingerprint that captures perceptual identity rather than bit-for-bit exactness.
Salted Hashing and Password Storage
When a website stores your password, it should never store the password itself. Instead, it stores the hash of your password. When you log in, the system hashes what you typed and compares the result to the stored hash. If they match, you are in. If an attacker steals the database, they get a list of hashes, not passwords. But this basic approach has a weakness: if two users pick the same password, their hashes are identical. An attacker can precompute hashes for millions of common passwords, creating what is known as a rainbow table, and then simply look up stolen hashes in that table.
Salting solves this problem by appending a random string, the salt, to each password before hashing. Even if two users choose the same password, their salts are different, so their stored hashes are different. The salt does not need to be secret; it just needs to be unique per user. What does need to stay secret is any additional key material used in the process. Research on privacy-preserving anonymization using salt-based hashing demonstrated that the security of the entire scheme depends critically on the secrecy and randomness of the salt. If the salt is compromised, an attacker can reconstruct the mapping between original values and hashes by exhaustively hashing all possible inputs with the known salt.12arXiv. Privacy-Preserving Anonymization of System and Network Event Logs Using Salt-Based Hashing and Temporal Noise
Modern best practice goes beyond simple salting. Algorithms like bcrypt, scrypt, and Argon2 are deliberately designed to be slow and memory-intensive, making brute-force attacks expensive even with specialized hardware. They incorporate salting automatically, and they allow the difficulty to be tuned upward over time as hardware gets faster. If you are building a system that stores passwords and you are using plain SHA-256 even with a salt, you are doing it wrong. Dedicated password-hashing functions exist for a reason.
What Happens When a Hash Function Breaks
A hash function “breaks” when someone finds a way to violate one of its core security properties faster than brute force. MD5 was designed in 1991 and was the standard for years. By 2004, researchers demonstrated practical collision attacks against it. By 2008, a team used an MD5 collision to forge a rogue certificate authority certificate, meaning they could impersonate any website on the internet. SHA-1 followed a similar trajectory: theoretical weaknesses appeared in 2005, and by 2017, researchers at Google and CWI Amsterdam produced the first public SHA-1 collision, demonstrating that the algorithm was no longer safe for digital signatures.
The practical consequences of a broken hash function depend on how it is being used. For digital signatures and certificates, collision attacks are devastating because they allow forgery. For password storage, collision attacks are less immediately dangerous; what matters more is preimage resistance, and both MD5 and SHA-1 remain reasonably resistant to preimage attacks even today. That does not mean you should keep using them for passwords. They are far too fast, which makes brute-force guessing trivially easy with modern GPUs. The problem is speed, not collision weakness.
The migration away from broken hash functions is slow and painful. Years after MD5 was conclusively broken for signatures, it remained embedded in countless systems, libraries, and protocols. Legacy software often has MD5 hardcoded in ways that are difficult to update. The lesson the security community has absorbed is that hash agility, designing systems to swap out their hash function without a complete rewrite, is essential. You should assume that any hash function will eventually be weakened and plan accordingly.
Quantum Computing and Hash Functions
Quantum computers threaten many areas of cryptography, most famously public-key encryption. Their impact on hash functions is real but less dramatic. Grover’s algorithm, a quantum search technique, can speed up brute-force search over a hash function’s output space, effectively halving the security level. A hash function with a 256-bit output that provides 256 bits of security against classical brute force would provide roughly 128 bits against a quantum attacker using Grover’s algorithm. For modern hash functions with 256-bit or larger outputs, 128 bits of security is still considered far beyond practical attack ranges.
The practical difficulty of mounting quantum attacks on hash functions also varies by algorithm. A study applying Grover’s algorithm to real hash functions in software found that the computational cost of a quantum attack against SHA-3 was much lower than against MD5, SHA-1, or SHA-2. This is because SHA-3 uses operations that translate more naturally to a quantum computing context, while the older algorithms rely heavily on arithmetic addition, which is expensive on quantum hardware.13arXiv. Applying Grover’s Algorithm to Hash Functions: A Software Perspective However, when measuring the number of qubits required, SHA-3 is comparable to SHA-2 functions with a 256-bit internal state. Functions with a 512-bit internal state, like SHA-512, require substantially more qubits, suggesting that SHA-512 variants may actually be more quantum-resistant than their 256-bit counterparts despite using a theoretically older construction.14arXiv. Applying Grover’s Algorithm to Hash Functions: A Software Perspective
This is a good example of how security analysis can produce counterintuitive results. The newer, more theoretically elegant algorithm (SHA-3) turns out to be easier to attack on a quantum computer than the older, structurally messier one (SHA-512) simply because its internal operations map more cleanly to quantum gates. For now, none of these attacks are practical because the required quantum computers do not exist at the necessary scale. But the research informs long-term planning for governments and organizations that need their data to remain secure for decades.
Hash Functions Outside of Computing
The concept behind hash functions, reducing a large input to a compact fingerprint for fast comparison, shows up in places you might not expect. DNA sequence databases use hashing techniques to quickly compare genetic sequences against massive reference libraries. Forensic tools hash the contents of hard drives to create a fingerprint that proves the data has not been tampered with during an investigation. Version control systems like Git use SHA-1 hashes (with a migration to SHA-256 underway) to identify every commit, file, and directory tree in a repository. When you run a Git command, you are interacting with a content-addressable storage system built entirely on hash functions.
File deduplication in cloud storage is another quiet application. Services like Dropbox and Google Drive hash uploaded files and compare the hashes against existing stored files. If the hash matches a file already on the server, the service can simply point your account to the existing copy instead of storing a duplicate. This technique saves enormous amounts of storage space. It also raised privacy concerns when researchers demonstrated that services using this approach could infer whether a specific file existed on the platform by attempting to upload it and observing whether deduplication kicked in.
Even the humble check digit on a credit card number is a distant relative of hashing. The Luhn algorithm computes a simple digest of the card number to catch typos and transcription errors. It is not a cryptographic hash by any stretch, but the underlying principle, compress data into a small value that reveals whether something has changed, is the same idea that scales all the way up to the algorithms protecting global financial infrastructure.