Cryptographic hash function

• 1. Introduction

  ›

  A cryptographic hash function takes any message, long or short, and turns it into a fixed-length string that looks nothing like the original. In one illustration, Alice poses a tough math problem to Bob and claims she has already solved it. She writes down her solution, computes its hash, and tells Bob only the hash value. She keeps the actual solution secret. Days later, when Bob solves the problem himself, Alice reveals her original answer. Bob hashes it and checks that it matches the value she gave him earlier. That proves she had the solution all along, without ever showing her work in advance. The trick works because hashing runs one way only. It is quick to calculate, but essentially impossible to reverse. Change even a single character of the input, and the resulting hash looks completely different. So what actually makes a hash resistant to being reversed or forged? How is that resistance measured, and what happens when it fails? And why has this single mathematical tool ended up underneath passwords, digital signatures, Bitcoin mining, and file-sharing networks?

• 2. The Three Guarantees

  ›

  Pre-image resistance is the first of three properties theoretical cryptography demands from a hash function. Given a hash value, it should be difficult to find any message that produces it. This idea is closely related to what cryptographers call a one-way function. A function lacking this property is vulnerable to a preimage attack. Second pre-image resistance asks a narrower question: given one input, it should be difficult to find a different input that produces the same hash. This is sometimes called weak collision resistance. A function lacking it is vulnerable to a second-preimage attack.

  A hash collision is the name for two distinct messages that produce the same hash value, and collision resistance is the guarantee against finding one. This property is sometimes called strong collision resistance. Because of the birthday paradox, collision resistance needs a longer hash value than pre-image resistance does, or a birthday attack can find matches faster than expected. Collision resistance implies second pre-image resistance, but it does not imply pre-image resistance on its own. Theoretical cryptography always prefers the weaker assumption, yet in practice a hash function offering only second pre-image resistance is considered insecure.

  A length-extension attack still threatens popular cryptographic hash functions, even ones meeting all three guarantees above. An attacker who knows a hash value and the length of the original message can calculate a new hash for a longer message, without ever seeing that original content. The HMAC construction was built specifically to work around that weakness. The SWIFFT function shows that collision resistance alone is not enough either. It can be proven collision-resistant, assuming certain lattice problems are hard to solve, yet as a linear function it fails to behave like the random oracle that security proofs depend on. Whether any of these guarantees hold in practice comes down to a word cryptographers use constantly: difficult.

• 3. Defining Difficult

  ›

  Adding just a dozen bits to a hash's digest length can cancel out a thousand-fold advantage in an attacker's processing power. That is because, in cryptographic practice, difficult usually means beyond the reach of any adversary who must be kept out for as long as the system's security matters. What counts as difficult shifts with the application, since an attacker's effort tends to track their expected reward, and needed effort typically multiplies with the length of the digest.

  For messages drawn from a limited set, such as passwords or other short strings, inverting a hash can be feasible just by trying every possibility in that set. Cryptographic hash functions are usually designed to compute quickly, which makes that kind of brute-force search easier. So specialized key derivation functions have been built that demand far more computing resources, making brute-force attacks against them slower and costlier.

  Some theoretical analyses define difficult in strict mathematical terms, such as not solvable in asymptotic polynomial time. That framing matters for provably secure hash functions, but it does not always match practical security. An exponential-time algorithm can sometimes still run fast enough to succeed as a real attack. A polynomial-time algorithm, meanwhile, can be too slow for any practical use if it needs enough steps for each digit of the key. That gap between theoretical and practical difficulty is exactly where real attacks against specific hash functions have found their opening.

• 4. When Trust Breaks

  ›

  A cyclic redundancy check, or CRC, was used for message integrity in the WEP encryption standard. Attackers readily found a way to exploit the linearity of that checksum, since non-cryptographic functions like CRC offer no real resistance to a deliberate attack. Cryptographic hash functions are held to a much higher standard precisely because of failures like that one.

  In August 2004, researchers found collisions in several then-popular hash functions, including MD5. On the 12th of August 2004, Joux, Carribault, Lemuel, and Jalby announced a collision for the full SHA-0 algorithm. They reached it using a generalization of the Chabaud and Joux attack, reaching a complexity of 251 and using about 80,000 CPU hours on a supercomputer built from 256 Itanium 2 processors. That amounted to roughly 13 days of the supercomputer running full-time.

  In February 2005, researchers reported an attack able to find a SHA-1 collision in about 269 hashing operations, far fewer than the 280 operations expected for a 160-bit hash. In August 2005, another attack cut that further, finding collisions in about 263 operations. Other theoretical weaknesses in SHA-1 kept surfacing, and in February 2017 Google announced an actual collision in SHA-1. Security researchers now recommend that new applications move to later members of the SHA family, such as SHA-2, or adopt techniques such as randomized hashing that do not depend on collision resistance.

  A successful, practical attack broke MD5 in 2008, undermining certificates used within Transport Layer Security. Many cryptographic hashes rely on the Merkle-Damgård construction, and any hash that directly exposes the full output of that construction is vulnerable to length-extension attacks. That list includes MD5, SHA-1, RIPEMD-160, Whirlpool, and the SHA-256 and SHA-512 algorithms. SHA-3, BLAKE2, BLAKE3, and the truncated SHA-2 variants are not vulnerable to that particular attack, a distinction that becomes clearer once you see how each of these algorithms was actually built.

• 5. From Ciphers To Constructions

  ›

  The Merkle-Damgård construction breaks an arbitrary-length message into equally sized blocks and processes them in sequence through a one-way compression function. A hash built this way is exactly as resistant to collisions as its underlying compression function. Any collision in the full hash traces back to a collision in that compression function. The final block must be unambiguously length-padded, a detail crucial to the construction's security. Most common classical hash functions, including SHA-1 and MD5, take this form.

  Many well-known hash functions, including MD4, MD5, SHA-1, and SHA-2, are built from block-cipher-like components with feedback added to keep the function from being invertible. When NIST ran its SHA-3 competition, finalists such as Skein and BLAKE still used block-cipher-like components. The function eventually chosen, Keccak, was built on a cryptographic sponge instead. A standard block cipher such as AES could, in theory, stand in for these custom designs, which can help an embedded system that needs both encryption and hashing with minimal code size. But AES has key and block sizes that make it awkward for generating long hash values. It also grows less efficient in this role, since encryption performance drops every time the key changes each block.

  A straightforward Merkle-Damgård design, where the hash output is the same size as the internal state between compression steps, produces what is called a narrow-pipe hash. That narrow-pipe design invites a long list of flaws: length-extension, multicollisions, long message attacks, and generate-and-paste attacks, and it cannot be parallelized. Modern hash functions instead use wide-pipe constructions with a larger internal state, ranging from tweaked Merkle-Damgård designs to newer approaches like the sponge and HAIFA constructions. None of the entrants in the NIST hash function competition used a classical Merkle-Damgård construction. Truncating the output of a longer hash, as SHA-512/256 does, also defeats many of these same attacks.

  Message authentication codes, sometimes called keyed hash functions, are often built from hash functions in exactly this way. Just as block ciphers can build hash functions, hash functions can build block ciphers in return. Luby-Rackoff constructions can build a provably secure block cipher from a hash function, as long as the underlying hash function itself is secure. Many hash functions, including SHA-1 and SHA-2, are themselves built by running a special-purpose block cipher through a Davies-Meyer construction. That same cipher can also run in a conventional mode, without the same security guarantees, in ciphers such as SHACAL, BEAR, and LION.

  Pseudorandom number generators can also be built from hash functions, typically by combining a secret random seed with a counter and hashing the result. Some hash functions, such as Skein, Keccak, and RadioGatún, can output an arbitrarily long stream and double as a stream cipher. The stream cipher SEAL uses SHA-1 to generate its internal tables, feeding a keystream generator only loosely tied to the hash algorithm itself. SEAL is not guaranteed to be as strong, or as weak, as SHA-1. The key expansion inside the HC-128 and HC-256 stream ciphers likewise leans heavily on the SHA-256 hash function.

  Older versions of Transport Layer Security and Secure Sockets Layer used a concatenated combination of MD5 and SHA-1 sums. Concatenating outputs from multiple hash functions gives collision resistance as good as the strongest algorithm among them, since a method for finding collisions in one function alone would not defeat data protected by both. For a Merkle-Damgård hash function, though, the concatenated result is only as collision-resistant as its strongest component, never more. Antoine Joux made a key observation: a single two-way collision leads to many more collisions. If an attacker can find two messages sharing an MD5 hash, they can find many more messages sharing that same hash just as easily. Among a large enough set of those MD5-colliding messages, a collision in SHA-1 becomes likely too. Finding that SHA-1 collision needs only polynomial time, beyond the exponential birthday search already spent finding the MD5 collisions. MD5 itself, the algorithm at the center of Joux's discovery, was designed by a single named cryptographer decades earlier.

• 6. A Family Of Algorithms

  ›

  Ronald Rivest designed MD5 in 1991 to replace an earlier hash function, MD4, and the design was specified in 1992 as RFC 1321. Collisions against MD5 can now be calculated within seconds, which rules the algorithm out for most uses that need a cryptographic hash. MD5 produces a digest of 128 bits, or 16 bytes.

  SHA-1 grew out of the United States government's Capstone project. Its original specification, now usually called SHA-0, was published in 1993 under the title Secure Hash Standard, FIPS PUB 180. The National Institute of Standards and Technology issued it, and the NSA withdrew it shortly after publication. A revised version followed in 1995 as FIPS PUB 180-1, commonly known as SHA-1. Collisions against the full SHA-1 algorithm can now be produced using the shattered attack. SHA-1 produces a hash digest of 160 bits, or 20 bytes. Documents sometimes call it simply SHA, which can be confused with the other Secure Hash Algorithms, SHA-0, SHA-2, and SHA-3.

  Hans Dobbertin, Antoon Bosselaers, and Bart Preneel built RIPEMD, short for RACE Integrity Primitives Evaluation Message Digest. They worked at the COSIC research group at the Katholieke Universiteit Leuven, in Leuven, Belgium, and first published it in 1996. RIPEMD followed design principles from MD4 and performs similarly to the more popular SHA-1. RIPEMD-160 has not been broken, and as its name implies, it produces a hash digest of 160 bits, or 20 bytes.

  Vincent Rijmen and Paulo S. L. M. Barreto designed Whirlpool, first describing it in 2000. Whirlpool is based on a substantially modified version of the Advanced Encryption Standard. It produces a hash digest of 512 bits, or 64 bytes.

  The United States National Security Agency designed SHA-2, first publishing it in 2001. It is built on the Merkle-Damgård structure, using a one-way compression function. That function itself relies on a Davies-Meyer structure, built from a classified, specialized block cipher. SHA-2 consists mainly of two algorithms, SHA-256 and SHA-512. SHA-224 is a variant of SHA-256 with different starting values and a truncated output, while SHA-384, SHA-512/224, and SHA-512/256 are all variants of SHA-512. SHA-512 is considered more secure than SHA-256 and typically runs faster on 64-bit machines such as AMD64. Output size tracks the number in each algorithm's name. SHA-224 produces 28 bytes, SHA-256 produces 32, SHA-384 produces 48, and SHA-512 produces 64.

  NIST released SHA-3 on the 5th of August 2015. SHA-3 is a subset of the broader Keccak family of cryptographic primitives, the work of Guido Bertoni, Joan Daemen, Michael Peeters, and Gilles Van Assche. Keccak relies on a sponge construction, the same approach that can build other primitives such as a stream cipher. SHA-3 offers the same output sizes as SHA-2: 224, 256, 384, and 512 bits. Its SHAKE-128 and SHAKE-256 functions allow configurable output sizes instead. There, the 128 and 256 in the name describe security strength, not output length.

  BLAKE2, an improved version of BLAKE, was announced on the 21st of December 2012. Jean-Philippe Aumasson, Samuel Neves, Zooko Wilcox-O'Hearn, and Christian Winnerlein built it aiming to replace the widely used but broken MD5 and SHA-1. Run on 64-bit x64 and ARM architectures, BLAKE2b outperforms SHA-3, SHA-2, SHA-1, and MD5 for speed. It has since been adopted in protocols including the Argon2 password hash, thanks to its efficiency on modern CPUs. BLAKE3 followed as an improved version of BLAKE2, announced on the 9th of January 2020. Jack O'Connor, Jean-Philippe Aumasson, Samuel Neves, and Zooko Wilcox-O'Hearn built it. Unlike BLAKE and BLAKE2, which are families with multiple variants, BLAKE3 is a single algorithm. Its compression function closely follows BLAKE2s, but cuts the number of rounds from 10 to 7. Internally, BLAKE3 forms a Merkle tree, giving it higher parallelism than BLAKE2.

  Several hashing algorithms are used mainly in specific countries. SM3 is used in China, and Streebog, also called GOST R 34.11-2012, is used in Russia. The older GOST R 34.11-94 served the Soviet Union and Russia before being deprecated. LSH is used in South Korea, and Kupyna in Ukraine. When NIST ran the first round of its SHA-3 competition, it selected 51 candidate hash functions. Of those, 10 were considered broken and 16 showed significant weaknesses, so neither group advanced to the next round. Even hash functions that survived that competition still face one especially stubborn adversary: the ordinary human habit of choosing a weak password.

• 7. Guarding Passwords

  ›

  Storing every user password as plain, readable text can turn a single stolen file into a massive security breach. Systems reduce that risk by storing only a hash digest of each password instead. To authenticate a user, the system hashes the password just presented and compares it against the stored hash. Because the original password cannot be recalculated from that stored hash, a password reset process becomes necessary whenever hashing is used this way.

  Standard cryptographic hash functions, such as the SHA series, are no longer considered safe for password storage on their own. They are built to compute quickly, so if the hashed values leak, guessed passwords can be tested at very high speed. Common graphics processing units can try billions of possible passwords every second. Password hash functions that apply key stretching, such as PBKDF2, scrypt, and Argon2, repeat the underlying cryptographic hash many times over. That repetition burns extra computing time, and in some cases extra memory, to slow brute-force attacks.

  A password hash also needs a large, random, non-secret value called a salt, stored alongside the hash itself. Hashing the salt together with the password changes the resulting hash mapping for every single password. That makes it infeasible for an attacker to precompute tables of hash values, commonly called rainbow tables, or to test many stolen hashes in parallel. Even so, searches running at roughly 100 billion tests per second are possible on high-end graphics processors, making direct attacks on salted hashes possible too. The National Institute of Standards and Technology recommends storing passwords with dedicated key derivation functions built to slow brute-force searches. Among them are PBKDF2, bcrypt, scrypt, Argon2, Balloon, and some recent modes of Unix crypt. For functions that repeat their hashing step to slow execution, NIST recommends an iteration count of 10,000 or more. That same repeated-hashing idea, applied in reverse, is also what keeps networks like Bitcoin honest.

• 8. Proof, Provenance, And Everyday Use

  ›

  MD5, SHA-1, or SHA-2 hash digests are often published on websites or forums. That lets people verify the integrity of files they download, including files shared through mirroring. That practice builds a chain of trust, as long as the hashes sit on a trusted, usually originating, site authenticated by HTTPS. A cryptographic hash combined with that chain of trust can catch malicious changes to a file. Non-cryptographic checks like cyclic redundancy checks only catch non-malicious alterations, since a deliberate spoof can be crafted to keep the same checksum value.

  Almost every digital signature scheme requires a cryptographic hash to be calculated over the message first. That lets the actual signature calculation run on the small, fixed-size hash digest rather than the whole message. A message counts as authentic only if signature verification succeeds against the signature and the freshly recalculated digest.

  A proof-of-work system deters denial-of-service attacks and abuses such as spam by demanding real computing work from whoever requests a service. These schemes hinge on asymmetry: the work must be moderately hard for the requester but easy for the service provider to check. Bitcoin mining and Hashcash both rely on partial hash inversions to prove that work was actually done. In Bitcoin, that unlocks a mining reward; in Hashcash, it serves as a good-will token for sending an email. A sender must find a message whose hash value starts with a set number of zero bits. In Hashcash specifically, a sender generates a header whose 160-bit SHA-1 hash has its first 20 bits set to zero. The average work needed grows exponentially with the number of required zero bits. The recipient, though, can verify a valid message with a single hash calculation.

  Git, Mercurial, and Monotone all rely on a message digest to identify files reliably. They use the sha1sum of file content, directory trees, and ancestry information to uniquely identify them. Hashes also identify files on peer-to-peer file-sharing networks. In an ed2k link, for example, an MD4-variant hash is combined with the file's size. That combination gives enough information to locate sources, download the file, and verify its contents. Magnet links work the same way. These file hashes are often the top hash of a larger hash list or hash tree.

  Hash tables rely on hash functions for one of their core jobs: the fast look-up of data. Cryptographic hash functions can fill that role too, despite being far more computationally expensive than ordinary ones. That expense is worth paying wherever users need protection against forgery by a malicious participant. An open-source project offering downloads from multiple sources is a good example. There, a malicious file could otherwise be swapped in, looking identical to the real one. One more use is named directly alongside these: content-addressable storage. It is one more place, alongside hash tables and file identifiers, where a cryptographic hash quietly tells one piece of data from another.