Hubbry Logo
search
logo
Hash function security summary avatar
Hash function security summary
Hash function security summary
current hub
H

Hash function security summary

logo
Community Hub0 Subscribers
Read side by side
Hash function security summary
View on Wikipedia
from Wikipedia

This article summarizes publicly known attacks against cryptographic hash functions. Note that not all entries may be up to date. For a summary of other hash function parameters, see comparison of cryptographic hash functions.

Table color key

[edit]
See also: Security level
  No attack successfully demonstrated — attack only breaks a reduced version of the hash or requires more work than the claimed security level of the hash
  Attack demonstrated in theory — attack breaks all rounds and has lower complexity than security claim
  Attack demonstrated in practice — complexity is low enough to be actually used

Common hash functions

[edit]

Collision resistance

[edit]
Main article: Collision attack
Hash function Security claim Best attack Publish date Comment
MD5 264 218 time 2013-03-25 This attack takes seconds on a regular PC. Two-block collisions in 218, single-block collisions in 241.[1]
SHA-1 280 261.2 2020-01-08 Paper by Gaëtan Leurent and Thomas Peyrin[2]
SHA256 2128 31 of 64 rounds (265.5) 2013-05-28 Two-block collision.[3]
SHA512 2256 24 of 80 rounds (232.5) 2008-11-25 Paper.[4]
SHA-3 Up to 2512 6 of 24 rounds (250) 2017 Paper.[5]
BLAKE2s 2128 2.5 of 10 rounds (2112) 2009-05-26 Paper.[6]
BLAKE2b 2256 2.5 of 12 rounds (2224) 2009-05-26 Paper.[6]

Chosen prefix collision attack

[edit]
Hash function Security claim Best attack Publish date Comment
MD5 264 239 2009-06-16 This attack takes hours on a regular PC.[7]
SHA-1 280 263.4 2020-01-08 Paper by Gaëtan Leurent and Thomas Peyrin[2]
SHA256 2128
SHA512 2256
SHA-3 Up to 2512
BLAKE2s 2128
BLAKE2b 2256

Preimage resistance

[edit]
Main article: Preimage attack
Hash function Security claim Best attack Publish date Comment
MD5 2128 2123.4 2009-04-27 Paper.[8]
SHA-1 2160 45 of 80 rounds 2008-08-17 Paper.[9]
SHA256 2256 43 of 64 rounds (2254.9 time, 26 memory) 2009-12-10 Paper.[10]
SHA512 2512 46 of 80 rounds (2511.5 time, 26 memory) 2008-11-25 Paper,[11] updated version.[10]
SHA-3 Up to 2512
BLAKE2s 2256 2.5 of 10 rounds (2241) 2009-05-26 Paper.[6]
BLAKE2b 2512 2.5 of 12 rounds (2481) 2009-05-26 Paper.[6]

Length extension

[edit]
Main article: Length extension attack
  • Vulnerable: MD5, SHA1, SHA256, SHA512
  • Not vulnerable: SHA384, SHA-3, BLAKE2

Less-common hash functions

[edit]

Collision resistance

[edit]
Hash function Security claim Best attack Publish date Comment
GOST 2128 2105 2008-08-18 Paper.[12]
HAVAL-128 264 27 2004-08-17 Collisions originally reported in 2004,[13] followed up by cryptanalysis paper in 2005.[14]
MD2 264 263.3 time, 252 memory 2009 Slightly less computationally expensive than a birthday attack,[15] but for practical purposes, memory requirements make it more expensive.
MD4 264 3 operations 2007-03-22 Finding collisions almost as fast as verifying them.[16]
PANAMA 2128 26 2007-04-04 Paper,[17] improvement of an earlier theoretical attack from 2001.[18]
RIPEMD (original) 264 218 time 2004-08-17 Collisions originally reported in 2004,[13] followed up by cryptanalysis paper in 2005.[19]
RadioGatún Up to 2608[20] 2704 2008-12-04 For a word size w between 1-64 bits, the hash provides a security claim of 29.5w. The attack can find a collision in 211w time.[21]
RIPEMD-160 280 48 of 80 rounds (251 time) 2006 Paper.[22]
SHA-0 280 233.6 time 2008-02-11 Two-block collisions using boomerang attack. Attack takes estimated 1 hour on an average PC.[23]
Streebog 2256 9.5 rounds of 12 (2176 time, 2128 memory) 2013-09-10 Rebound attack.[24]
Whirlpool 2256 4.5 of 10 rounds (2120 time) 2009-02-24 Rebound attack.[25]

Preimage resistance

[edit]
Hash function Security claim Best attack Publish date Comment
GOST 2256 2192 2008-08-18 Paper.[12]
MD2 2128 273 time, 273 memory 2008 Paper.[26]
MD4 2128 2102 time, 233 memory 2008-02-10 Paper.[27]
RIPEMD (original) 2128 35 of 48 rounds 2011 Paper.[28]
RIPEMD-128 2128 35 of 64 rounds
RIPEMD-160 2160 31 of 80 rounds
Streebog 2512 2266 time, 2259 data 2014-08-29 The paper presents two second-preimage attacks with variable data requirements.[29]
Tiger 2192 2188.8 time, 28 memory 2010-12-06 Paper.[30]

Attacks on hashed passwords

[edit]
Main article: Password cracking

Hashes described here are designed for fast computation and have roughly similar speeds.[31] Because most users typically choose short passwords formed in predictable ways, passwords can often be recovered from their hashed value if a fast hash is used. Searches on the order of 100 billion tests per second are possible with high-end graphics processors.[32][33] Special hashes called key derivation functions have been created to slow brute force searches. These include pbkdf2, bcrypt, scrypt, argon2, and balloon.

See also

[edit]

References

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Hash function security summary

View on Grokipedia
from Grokipedia
A cryptographic hash function is a mathematical algorithm that transforms an input of arbitrary length into a fixed-size output, called a hash value or digest, which serves as a unique digital fingerprint for verifying data integrity and authenticity in information security applications.[1] The security of these functions is fundamentally assessed through three core properties: preimage resistance, where it is computationally infeasible to reverse the hash to find the original input from a given output; second-preimage resistance, where finding a different input that produces the same output as a given input is infeasible; and collision resistance, where discovering any two distinct inputs that yield the same output is computationally infeasible.[1][2] These properties ensure that hash functions resist common attacks, such as brute-force inversion or deliberate forgery, making them essential for protocols like digital signatures, message authentication codes (MACs), and key derivation.[3] For instance, preimage resistance protects against attempts to forge inputs for known hashes, as used in password verification systems, while collision resistance safeguards against creating fraudulent data that matches legitimate hashes, critical in certificate authorities.[4] Second-preimage resistance complements this by preventing targeted substitutions, such as altering a specific document without detection.[2] The implications of these properties are interconnected: collision resistance implies second-preimage resistance, but not necessarily preimage resistance, highlighting the need for functions robust across all three for high-security use cases.[4] In practice, the U.S. National Institute of Standards and Technology (NIST) approves hash functions based on their demonstrated security strengths, measured in bits (e.g., 128-bit collision resistance for SHA-256).[3] Approved algorithms include the SHA-2 family (SHA-224, SHA-256, SHA-384, SHA-512) from FIPS 180-4 and the SHA-3 family (SHA3-224, SHA3-256, SHA3-384, SHA3-512) from FIPS 202, with SHA-1, which was progressively deprecated starting in 2011 due to theoretical weaknesses and fully broken by practical collision attacks in 2017, with NIST requiring phase-out by December 31, 2030 as announced in 2022.[3][2][5] These standards specify that approved functions provide at least 112 bits of security for the shortest variants, scaling up to 256 bits or more, ensuring resistance against quantum-assisted threats where applicable.[3] Additionally, extendable-output functions (XOFs) like SHAKE128 and SHAKE256 offer flexible digest lengths while maintaining similar security guarantees.[3] Historical vulnerabilities, such as collisions in MD5 (1996 theoretical, 2004 practical) and SHA-1, underscore the importance of ongoing cryptanalysis and transitions to stronger primitives like SHA-3, selected in 2012 via NIST's competition to replace aging standards.[3] Overall, hash function security evolves with computational advances, emphasizing the need for functions with output sizes of at least 256 bits to achieve 128-bit security levels against modern adversaries.[4]

Fundamental Security Properties

Preimage Resistance

Preimage resistance, a core security property of cryptographic hash functions, ensures that given a hash output $ h $, it is computationally infeasible for an adversary to find any input message $ m $ such that $ \hash(m) = h $. This property, also referred to as one-wayness, underpins the irreversibility of the hashing process and is essential for preventing inversion attacks.[6][7] The theoretical security level of preimage resistance is quantified by the expected work factor required to succeed, which for a brute-force attack on an $ n $-bit hash output is $ 2^n $ operations. This complexity arises because an attacker must effectively search the entire input space to reverse the hash, assuming the function behaves like a random oracle. In practice, this makes preimage attacks impractical for sufficiently large $ n $, such as 256 bits in modern standards.[8] Preimage resistance differs from other hash properties like collision resistance, as it specifically targets the reversal of a single given output rather than finding pairs of inputs that map to the same output. In the Merkle-Damgård construction, collision resistance of the compression function implies collision resistance for the full hash function, which in turn implies second-preimage resistance, but not necessarily preimage resistance.[7][9] The notion was first formalized in the late 1970s by Ralph Merkle, who introduced one-way hash functions as a cryptographic primitive in his doctoral thesis, emphasizing their role in secure protocols. This idea was extended in the 1980s through the independent works of Merkle and Ivan Damgård, establishing design principles for iterative hash constructions that inherit one-wayness from underlying components.[10][11] In digital signatures, preimage resistance is vital, as it guarantees that an attacker cannot construct a fraudulent message from a legitimately signed hash value, thereby preserving the integrity and authenticity of signed documents. Without this property, signature schemes relying on hashed messages would be vulnerable to forgery.[4]

Second Preimage Resistance

Second preimage resistance, also known as weak collision resistance, is a core security property of cryptographic hash functions. It requires that, given a message $ m_1 $ and its hash value $ h = \text{hash}(m_1) $, it is computationally infeasible for an adversary to find a distinct message $ m_2 \neq m_1 $ such that $ \text{hash}(m_2) = h $.[12] This property targets the difficulty of generating a specific alternative input that collides with the hash of a known input, distinguishing it from preimage resistance, which concerns finding any input mapping to a given output without reference to a particular input. The theoretical security level of second preimage resistance aligns with the output size of the hash function. For an $ n $-bit hash output, a brute-force search to find a second preimage requires approximately $ 2^n $ hash computations, as the attacker must evaluate hashes until matching the target value.[13] This complexity assumes no structural weaknesses, making it comparable to preimage resistance in generic attacks but more targeted in practice. Although weaker than collision resistance—since collision resistance implies second preimage resistance but not vice versa—this property remains essential for protocols relying on hash-based integrity verification, where swapping one verified input for another must be prevented.[9] For instance, in software distribution and integrity checks, it ensures that a legitimate file cannot be replaced by a malicious variant sharing the same hash, thwarting tampering attempts during validation.[14] Many second preimage attacks exploit vulnerabilities in the compression function underlying common hash constructions, such as those in the Merkle-Damgård paradigm, allowing attackers to manipulate intermediate states more efficiently than brute force.[15]

Collision Resistance

Collision resistance is a fundamental security property of cryptographic hash functions, defined as the computational infeasibility of finding two distinct inputs $ m_1 \neq m_2 $ such that $ \hash(m_1) = \hash(m_2) $.[16] This property ensures that the hash function behaves like a random oracle in mapping inputs to outputs, making it extremely difficult for an adversary to deliberately produce colliding messages without exhaustive search. Unlike preimage resistance, which targets reversing a specific output, collision resistance focuses on discovering any pair of inputs that share the same hash value, regardless of the target.[17] The theoretical complexity of breaking collision resistance is significantly reduced by the birthday attack, which exploits the birthday paradox to find collisions with effort approximately $ 2^{n/2} $ for an $ n $-bit hash output, rather than the full $ 2^n $ expected for brute force.[17] This attack involves generating roughly $ \sqrt{2^n} $ random inputs and storing their hashes until a match occurs, leveraging the probabilistic nature of hash outputs. The probability $ P $ of at least one collision among $ k $ samples from a hash function with $ 2^n $ possible outputs is approximated by:
P≈1−e−k2/2n+1 P \approx 1 - e^{-k^2 / 2^{n+1}}
This formula highlights how collisions become likely when $ k $ approaches $ 2^{n/2} $, underscoring the need for sufficiently large output sizes in hash function design to withstand such generic attacks.[17] Collision resistance is crucial because, in the ideal case, it implies second preimage resistance: if finding any collision is hard, then finding a second input colliding with a specific one is at least as difficult.[17] This property is essential for applications like digital certificates, where colliding certificates could allow fraudulent substitutions without detection, and blockchain systems, where it ensures the integrity of chained blocks by preventing alterations that preserve hash linkages.[18][19] The first practical concerns about collision resistance emerged in the 1990s with MD4, when attacks demonstrated vulnerabilities in its design, prompting advancements in hash function construction.[20]

Summary Tables

Color Key

The color key provides a visual legend for interpreting the status tables that follow, using standardized color coding to indicate the severity of known cryptanalytic attacks against specific security properties of hash functions. Green signifies that no attacks better than the generic security bounds are known, meaning the hash function remains secure against the property in question with current computational resources. Yellow denotes theoretical weaknesses, such as attacks with complexity exceeding practical feasibility or partial breaks that do not fully compromise the property. Red indicates practical attacks that are feasible with contemporary hardware and resources, rendering the hash function unsuitable for security-critical applications relying on that property.[21] This coding system is applied to individual cells within the tables, where rows represent attack types (e.g., collision resistance) and columns correspond to specific hash functions, allowing for a matrix-style overview of vulnerabilities. For instance, a red cell in the collision resistance row for MD5 highlights the real-world exploitability demonstrated by the first practical collision attack constructed in 2004, which requires only about 2^{39} operations—far below the generic birthday bound of 2^{64}. The rationale for this color key lies in its ability to enable rapid visual assessment of a hash function's suitability for cryptographic use, prioritizing those with predominantly green entries for new protocols while flagging deprecated ones with red or yellow markings. As of November 2025, the color assignments in the tables reflect the state of known attacks, incorporating recent reduced-round analyses up to 2025, with no major new practical breaks reported on full rounds of widely used standards like SHA-2 or SHA-3.[21]

Status of Common Hash Functions

The security status of common hash functions, including MD5, SHA-1, and the SHA-2 family, is assessed based on their resistance to core attacks such as finding collisions, preimages, and second preimages. Claimed security levels derive from the output size and generic attack bounds (collision resistance at n/2 bits, preimage and second preimage at n bits for an n-bit output), while best-known attacks reflect cryptanalytic advances that reduce effective security. The table below presents these for widely used functions, with complexities expressed in equivalent hash computations; values below the claimed level indicate partial or full breaks.
PropertyMD5 (128-bit)SHA-1 (160-bit)SHA-224 (224-bit)SHA-256 (256-bit)SHA-384 (384-bit)SHA-512 (512-bit)
Collision ResistanceClaimed: 64 bits
Best attack: ~2^{21} (practical since 2004; further optimized to 2^{18.8} in 2006)		Claimed: 80 bits
Best attack: 2^{63} (practical collision, 2017); chosen-prefix variant at 2^{61.2} (practical, 2020)[22]		Claimed: 112 bits
Best attack: Generic (2^{112})[23]		Claimed: 128 bits
Best attack: Generic (2^{128}); reduced-round (31/64 steps) at 2^{49.8} (2024, not full)[23]		Claimed: 192 bits
Best attack: Generic (2^{192})[23]		Claimed: 256 bits
Best attack: Generic (2^{256})[23]
Preimage ResistanceClaimed: 128 bits
Best attack: 2^{123.4} (2013)[24]		Claimed: 160 bits
Best attack: Generic (2^{160}); reduced-round (48/80 steps) at 2^{146} (2009, not full)[23]		Claimed: 224 bits
Best attack: Generic (2^{224})[23]		Claimed: 256 bits
Best attack: Generic (2^{256}); reduced-round (52/64 steps) at 2^{254.4} (2011, not full)[23]		Claimed: 384 bits
Best attack: Generic (2^{384})[23]		Claimed: 512 bits
Best attack: Generic (2^{512}); reduced-round (57/80 steps) at 2^{509} (2011, not full)[23]
Second Preimage ResistanceClaimed: 128 bits
Best attack: Generic (2^{128})		Claimed: 160 bits
Best attack: Generic (2^{160}); reduced-round (34 steps) at 2^{100} (2010, not full)[23][25]		Claimed: ≥224 bits (message-dependent)
Best attack: Generic (≥224 bits)[23]		Claimed: ≥256 bits (message-dependent)
Best attack: Generic (≥256 bits)[23]		Claimed: 384 bits
Best attack: Generic (2^{384})[23]		Claimed: ≥512 bits (message-dependent)
Best attack: Generic (≥512 bits)[23]
MD5 is fully broken for collisions, rendering it unsuitable for any security purpose, while SHA-1's practical collisions and chosen-prefix attacks compromise its use in protocols like digital signatures and certificates. In contrast, the SHA-2 variants (SHA-224, SHA-256, SHA-384, SHA-512) maintain full claimed security against known attacks as of 2025 and are recommended by NIST for general cryptographic applications, with phase-out of SHA-1 mandated by 2030.[26]

Status of Less Common Hash Functions

Less common hash functions encompass specialized designs for particular applications or older constructions that have been largely supplanted but remain in legacy systems. This section summarizes their security status using the color key for visual indicators of resistance levels (secure, vulnerable, broken). The following table presents key security properties, focusing on claimed strengths versus best-known attacks as of 2025, with no new practical breaks on full versions reported beyond prior analyses.[27]
PropertySHA-3 (Keccak)BLAKE2GOST R 34.11-2012 (Streebog)MD2MD4HAVAL (128-bit, 3-pass)
Preimage ResistanceClaimed: 2^{256} (SHA-3-256); Best attack: ~2^{254} bit operations on 5 reduced rounds (2025)[28]Claimed: 2^{256} (BLAKE2b); No attacks better than generic 2^{128}Claimed: 2^{256}; No significant attacks, resistant to algebraic methods up to full roundsClaimed: 2^{128}; Best attack: 2^{104} preimages[29]Claimed: 2^{128}; Best attack: 2^{92} preimages[30]Claimed: 2^{128}; Best attack: 2^{112} on full 4/5 passes[31]
Second Preimage ResistanceClaimed: 2^{256}; Best attack: Generic (2^{256})Claimed: 2^{256}; Indifferentiable from random oracle, no structural flawsClaimed: 2^{256}; No known breaks, meets standard requirements[32]Vulnerable: 2^{73} message blocks[33]Vulnerable: 2^{78}[30]Vulnerable: 2^{104} on 3 passes[34]
Collision ResistanceClaimed: 2^{128}; Best attack: None on full; 2^{185} on 5 reduced rounds (2023)[35]Claimed: 2^{128}; No collisions beyond birthday bound 2^{128}[36]Claimed: 2^{128}; Resistant, no practical collisions found[32]Broken: Practical collisions in 2^{18} time[33]Broken: Deterministic collisions (2^2 probability)Broken: 2^{16} on 3 passes; 2^{32} on 4 passes[31]
SHA-3, standardized by NIST in 2015 as a sponge-based construction, remains unbroken in its full form with no practical attacks on its core security properties, though reduced-round analyses highlight differential paths up to 5 of 24 rounds.[27] BLAKE2, a high-speed variant of the SHA-3 finalist BLAKE, provides robust security without known structural weaknesses, achieving indifferentiability from a random oracle and suitability for software implementations. GOST R 34.11-2012, the Russian federal standard also known as Streebog, demonstrates resistance to known cryptanalytic techniques, including algebraic attacks, and is used in official protocols without reported full breaks.[32] Legacy functions like MD2 and MD4 are severely compromised, with MD2 vulnerable to collisions in negligible time relative to its 128-bit output and MD4 allowing near-deterministic collisions, rendering both unsuitable for any security application.[33] HAVAL, a variable-pass design from 1992, suffers from efficient collisions on its common 3-pass variant and weakened resistance in higher passes, contributing to its obsolescence.[31] As of November 2025, no novel practical attacks have emerged on these full functions beyond established reduced-round or theoretical bounds. Sponge constructions like SHA-3 offer enhanced quantum resistance, with proofs of quantum indifferentiability ensuring security against Grover's and other quantum algorithms up to the capacity limit. For forward-looking deployments, SHA-3 is recommended over legacy options due to its post-quantum margins and standardization.[27]

Attacks on Common Hash Functions

Collision Resistance Attacks

Collision resistance attacks target the property that it is computationally infeasible to find two distinct inputs producing the same hash output for a hash function. For MD5, a practical collision attack was demonstrated in 2004 by Xiaoyun Wang and colleagues, with a complexity of approximately 2392^{39} MD5 operations, allowing the creation of colliding messages differing in a few bits. This rendered MD5 unsuitable for collision-dependent applications like digital signatures.[37] For SHA-1, the first practical collision attack, known as SHAttered, was achieved in 2017 by Marc Stevens et al., with an estimated complexity of 263.22^{63.2} SHA-1 compression function evaluations. The attack required about 6,500 GPU-years but was completed in 2 months using 100 GPUs, producing two colliding PDFs.[38] In contrast, the SHA-2 family (SHA-256, SHA-512) and SHA-3 family have no known collision attacks below the generic birthday bound of 21282^{128} and 22562^{256}, respectively. BLAKE2, a modern hash function family designed for high performance and security, also withstands collision attacks at the generic birthday bound of 21282^{128} for its 256-bit variants, with no cryptanalytic advances improving upon this level despite thorough analysis.

Chosen-Prefix Collision Attacks

A chosen-prefix collision attack is a variant of a collision attack in which an adversary selects two arbitrary prefixes PP and P′P', then finds short suffixes SS and S′S' such that hash(P∣∣S)=hash(P′∣∣S′)\text{hash}(P || S) = \text{hash}(P' || S').[39] This differs from a standard collision attack by allowing control over meaningful, distinct starting content, making it particularly threatening for structured data like certificates or files.[39] Chosen-prefix collisions build on generic collision resistance techniques as a prerequisite but extend them to targeted scenarios.[40] The method typically combines standard collision-finding with multicollision techniques, such as those introduced by Joux, to generate near-collisions and connect them efficiently. A key advancement is the herding technique, which enables the construction of colliding extensions by building a "herd" of colliding blocks that bridge the prefixes to a common hash value. For MD5, chosen-prefix collisions were demonstrated in 2007 with a practical complexity of approximately 2392^{39} MD5 compression function calls, leveraging differential paths and birthday attacks on the suffixes, though these are less studied today due to MD5's broader vulnerabilities.[41] For SHA-1, the first practical chosen-prefix collision was achieved in 2020, with an estimated complexity of 261.22^{61.2} SHA-1 compression function evaluations using optimizations like Joux's multicollision method and herding to handle the 80-round structure.[22] This attack required about 6,610 GPU-years of computation but was executed in two months using 900 Nvidia GTX 1060 GPUs, demonstrating real-world feasibility.[42] The resulting colliding messages were used to forge PDF signatures by appending malicious content that preserved the hash while altering the document.[42] The primary impact of chosen-prefix collisions targets certification authorities and signed file formats, enabling forgery of valid-looking documents or certificates. For instance, in MD5, such attacks forged SSL certificates from a legitimate authority by creating colliding certificate chains, compromising HTTPS trust. Similarly, for SHA-1, the 2020 attack impersonated PGP/GnuPG keys, with analogous risks to JAR files and certified PDFs where attackers can inject code or approvals without invalidating the signature.[22] These vulnerabilities have prompted deprecation of SHA-1 in protocols like TLS and PDF signing to prevent widespread abuse.[42]

Preimage Resistance Attacks

Preimage resistance requires that, for a given hash value y, it is computationally infeasible to find a message m such that h(m) = y, with the expected complexity being 2^n for an n-bit hash output. Widely deployed hash functions like MD5 and SHA-1 have known preimage attacks on reduced rounds, but full versions remain closer to the generic bound, though not recommended due to other weaknesses. The SHA-3 family, based on the Keccak sponge construction, provides strong preimage resistance. The full 24-round SHA-3-256 remains secure against preimage attacks up to the generic 2^256 complexity, with the best known attacks on reduced rounds (up to 5 rounds) having complexities around 2^200 or higher for variants like Keccak-224/256.[43] The SHA-2 family also maintains full preimage resistance at the generic bound, with no practical attacks known below 2^256 for SHA-256.

Length Extension Attacks

Length extension attacks exploit a structural weakness in hash functions based on the Merkle-Damgård construction, allowing an attacker who knows the hash of a message $ H(m) $ and the length of $ m $ to compute the hash of an extended message $ H(m || \text{pad} || \text{extra}) $, where pad\text{pad} is the standard padding appended to $ m $ (including the length encoding), and extra\text{extra} is arbitrary attacker-chosen data.[44] This is possible because the hash output $ H(m) $ serves as the intermediate chaining value (internal state) after processing $ m $, which can be reused as the starting point for further iterations of the compression function, combined with the known initial vector (IV).[44] The attack requires only the computational effort to hash the additional blocks in extra\text{extra}, making it highly efficient—essentially negligible compared to the full security level of the hash function.[44] This vulnerability affects all widely used Merkle-Damgård-based hash functions, including MD5, SHA-1, and the SHA-2 family (SHA-224, SHA-256, SHA-384, SHA-512).[44] A practical example arises in naive message authentication schemes that compute a hash as $ H(\text{secret prefix} || \text{message}) $; if an attacker observes the hash value and knows the message length, they can forge a valid hash for $ H(\text{secret prefix} || \text{message} || \text{pad} || \text{extra}) $ without learning the secret prefix, potentially leading to unauthorized modifications in protocols like API authentication or integrity checks.[45] The attack does not directly violate preimage resistance, as it does not recover the original message, but it undermines the hash's role in ensuring data integrity for concatenated inputs.[44] In contrast, SHA-3, based on the Keccak sponge construction, is inherently immune to length extension attacks.[46] The sponge design absorbs the input into a fixed-size state via a permutation function and squeezes out the output without exposing intermediate chaining values that could be extended, ensuring that computing a hash extension requires full knowledge of the prior input rather than just the output hash.[46] To mitigate length extension attacks in Merkle-Damgård hashes, protocols should avoid direct use of the hash for prefix-secret constructions and instead employ keyed modes like HMAC, which nests the hash function with a secret key XORed into inner and outer pads, preventing attackers from reusing internal states without the key.[45] Alternatively, prefix-free encodings—such as explicitly including the message length or using domain separators—can ensure that appended data cannot mimic valid padding extensions.[45]

Attacks on Less Common Hash Functions

Collision Resistance Attacks

Collision resistance attacks target the property that it is computationally infeasible to find two distinct inputs producing the same hash output for a hash function. For the MD4 hash function, a practical collision attack was demonstrated in 1995 by Hans Dobbertin, achieving collisions with a complexity of approximately 2202^{20} operations, rendering MD4 completely broken for this property.[47] The HAVAL hash family, designed with variable rounds (3, 4, or 5 passes totaling 52 to 80 rounds), suffered significant weakening through collision attacks presented in 2004 by Xiaoyun Wang and colleagues, who found practical collisions for the full 3-, 4-, and 5-pass versions of HAVAL-128 with a complexity of about 262^6 compression function evaluations, far below the expected 2642^{64} security for 128-bit outputs. GOST R 34.11-94, the Russian national hash standard from the 1990s producing 256-bit outputs, has no known practical collision attacks on the full 32-round function, with the best full-round attack requiring approximately 21052^{105} compression function evaluations, which remains infeasible.[48] On reduced-round variants, the strongest collision attack targets 5 rounds of GOST-256 and GOST-512 using a super-Sbox technique combined with multicollisions, achieving complexity 2102^{10} time and 242^{4} memory.[49] In contrast, BLAKE2, a modern hash function family designed for high performance and security, withstands collision attacks at the generic birthday bound of 21282^{128} for its 256-bit variants, with no cryptanalytic advances improving upon this level despite thorough analysis as of November 2025. These attacks on less common hash functions predominantly employ differential cryptanalysis methods, exploiting differences propagated through specific rounds to construct colliding message pairs.[47]

Preimage Resistance Attacks

Preimage resistance requires that, for a given hash value y, it is computationally infeasible to find a message m such that h(m) = y, with the expected complexity being 2^n for an n-bit hash output. Less common hash functions generally exhibit stronger preimage resistance compared to widely deployed ones, as they receive less intensive cryptanalytic scrutiny, resulting in fewer reported advances in breaking this property. For MD2, in 2008, an improved full preimage attack with time complexity 2732^{73} was published, building on earlier differential analysis of the compression function.[50] This is significantly below the generic 21282^{128} bound for its 128-bit output. RIPEMD-160 maintains full preimage resistance close to the generic bound of 2^160 as of November 2025. Preimage attacks on reduced rounds exist, such as on 48 out of 80 steps with complexity 21162^{116}, using meet-in-the-middle techniques on the compression function.[51] The best known preimage attack on SHA-3 (based on Keccak) targets 5 out of 24 rounds with a complexity of 2^58 in 2012, employing rotational cryptanalysis on the permutation. The full 24-round SHA-3-256 remains secure against preimage attacks up to the generic 2^256 complexity as of November 2025.[52] GOST R 34.11-2012, the current Russian hash standard with 256-bit output, is designed to provide preimage resistance up to 2^256 and has no known attacks below this bound as of November 2025.

Password Hashing Security

Offline Attacks

Offline attacks on hashed passwords occur when an attacker obtains a database of password hashes and attempts to reverse them without interacting with the live system, exploiting the computational feasibility of common hash functions like MD5 and SHA-1 when used without salts or slow-down mechanisms. These attacks target the preimage resistance property in an offline setting, where the attacker can perform unlimited attempts at high speeds. Brute-force attacks involve exhaustively trying all possible passwords until a match is found, which is particularly effective against weak passwords with low entropy, such as those around 40 bits, where unsalted MD5 hashes can be cracked in feasible time on modern hardware due to the algorithm's speed.[53] Dictionary attacks and rainbow tables enhance efficiency by focusing on likely passwords rather than pure exhaustion. Rainbow tables, introduced by Philippe Oechslin in 2003, use precomputed chains of hash reductions to store mappings between plaintexts and hashes in a compact form, drastically reducing storage needs compared to full tables while maintaining high success rates; this method can break unsalted hashes from fast functions like MD5 in seconds for common passwords by resolving chains on-the-fly.[54] Advancements in hardware have accelerated these attacks further. With 2025-era GPUs like the NVIDIA RTX 4090, attackers can compute over 80 billion MD5 hashes per second, enabling the cracking of unsalted common passwords almost instantaneously and underscoring the vulnerability of non-iterated hashes.[55] The impact of such vulnerabilities is evident in real-world breaches, such as the 2012 LinkedIn incident, where over 117 million unsalted SHA-1 hashed passwords were stolen and exposed, allowing attackers to crack hundreds of thousands using offline techniques like rainbow tables shortly after the leak.[56] In general, unsalted SHA-1 and MD5 hashes of common passwords are fully crackable offline with readily available tools and hardware, rendering them insecure for password storage.[57]

Mitigation Techniques

To counter offline attacks on password hashes, such as brute-force and dictionary attacks enabled by stolen databases, several best practices and specialized key derivation functions (KDFs) are employed to make hashing computationally expensive and resistant to parallelization on specialized hardware.[58] These techniques prioritize slowness, randomness, and resource intensity to extend the time required for an attacker to verify candidate passwords, often turning feasible cracks into multi-year endeavors even with high-end GPUs or ASICs.[59] A fundamental mitigation is the use of salting, where a unique, randomly generated value (typically 128 bits or more) is appended to each user's password before hashing. This per-user salt prevents precomputed rainbow table attacks, as tables must be regenerated for each distinct salt, rendering them impractical for large user bases.[60] Salts are stored alongside the hash in the database, ensuring they are available for verification without compromising security. For enhanced protection, password-based key derivation functions iteratively apply a underlying hash function (like HMAC-SHA256) a large number of times to amplify computational cost. PBKDF2, introduced in 2000, uses at least 10,000 iterations to slow down guessing attempts, making it suitable for CPU-bound environments though less ideal against modern parallel hardware.[60] Bcrypt, developed in 1999, builds on the Blowfish cipher with an adaptive work factor (log2 cost, starting at 4 for ~16ms per hash) that can be increased over time to maintain security against faster processors.[61] Scrypt, proposed in 2009, introduces memory-hardness by requiring significant RAM (e.g., 1 MiB or more) during computation, hindering efficient parallelization on GPUs and ASICs by forcing sequential memory access patterns.[59] Argon2, the winner of the 2015 Password Hashing Competition, further advances this by combining data-dependent memory access with tunable parameters for time, memory, and parallelism, offering strong resistance to side-channel and hardware-accelerated attacks; its hybrid variant, Argon2id, balances these for general use. Argon2id, recommended by OWASP and recognized by NIST as a suitable example of a password hashing function, uses a time cost of at least 2 iterations, a memory cost of 64 MiB, and parallelism of 1, tuned to take approximately 0.5-1 second on standard hardware, while avoiding fast general-purpose hashes like SHA-256 without derivation.[62][63] These parameters should be tuned based on available resources, with regular increases to match advancing threats. Additionally, peppering involves incorporating a server-side secret (a fixed, high-entropy value not stored with the hashes) into the input before derivation, providing an extra layer of protection if the database is compromised, as the attacker lacks the pepper to compute valid hashes offline. By design, these slow, resource-intensive hashing approaches ensure that even with ASIC-optimized cracking rigs capable of billions of attempts per second on fast hashes, verifying a single password against a properly configured KDF like Argon2 can require years of effort per user.

References

  1. Cryptographic hash function - Glossary | CSRC
  2. [PDF] fips pub 180-4 - federal information processing standards publication
  3. Hash Functions | CSRC - NIST Computer Security Resource Center
  4. [PDF] Cryptographic Hash-Function Basics: Definitions, Implications, and ...
  5. Preimage resistance - Glossary | CSRC
  6. [PDF] Hash functions: Theory, attacks, and applications - Microsoft
  7. https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-107r1.pdf
  8. (PDF) A Design Principle for Hash Functions - ResearchGate
  9. [PDF] Secrecy, Authentication, And Public Key Systems - Ralph Merkle
  10. A Design Principle for Hash Functions - SpringerLink
  11. Second preimage resistance - Glossary | CSRC
  12. [PDF] Updates on (Second) Preimage Attacks on Hash Combiners
  13. [PDF] Cryptographic Hash-Function Basics: Definitions, Implications, and ...
  14. [PDF] Chapters 20.1 -- 20.3
  15. [PDF] Second Preimage Attacks on Dithered Hash Functions
  16. Collision resistance - Glossary | CSRC
  17. [PDF] Chapter 9 - Hash Functions and Data Integrity
  18. [PDF] Domain Extender for Collision Resistant Hash Functions
  19. [PDF] Blockchains from Non-Idealized Hash Functions
  20. Cryptanalysis of MD4 - SpringerLink
  21. A Survey on Cryptographic Hash Functions and Their Security ...
  22. SHA-1 is a Shambles - First Chosen-Prefix Collision on SHA-1 and ...
  23. [PDF] fips pub 202 - federal information processing standards publication
  24. Finding Preimages in Full MD5 Faster Than Exhaustive Search
  25. Second-Preimage Analysis of Reduced SHA-1 - SpringerLink
  26. NIST Retires SHA-1 Cryptographic Algorithm
  27. SHA-3 Project - Hash Functions | CSRC
  28. Preimage Attacks on up to 5 Rounds of SHA-3 Using Internal ...
  29. [PDF] The MD2 Hash Function Is Not One-Way - Semantic Scholar
  30. [PDF] MD4 is Not One-Way
  31. Cryptanalysis of the full HAVAL with 4 and 5 passes
  32. Collision Attacks on Round-Reduced SHA-3 Using Conditional ...
  33. RFC 6986 - GOST R 34.11-2012: Hash Function - IETF Datatracker
  34. Cryptanalysis of MD2
  35. [PDF] A Comprehensive Review on Broken Hashing Algorithms
  36. Analysis of BLAKE2 | SpringerLink
  37. Cryptanalysis of MD4 | Journal of Cryptology
  38. Cryptanalysis of the GOST Hash Function - SpringerLink
  39. Cryptanalysis of the Round-Reduced GOST Hash Function
  40. [PDF] From Collisions to Chosen-Prefix Collisions Application to Full SHA-1
  41. [PDF] A Survey of Chosen-Prefix Collision Attacks - Marc Stevens
  42. [PDF] First Chosen-Prefix Collision on SHA-1 and Application to the PGP ...
  43. Rotational cryptanalysis of round-reduced Keccak
  44. [PDF] CERIAS Tech Report 2007-20 DYNAMIC CRYPTOGRAPHIC HASH ...
  45. RFC 2104: HMAC: Keyed-Hashing for Message Authentication
  46. None
  47. The 2025 Hive Systems Password Table Is Here
  48. Making a Faster Cryptanalytic Time-Memory Trade-Off - SpringerLink
  49. GPU Password Cracking Benchmarks 2025: RTX vs CPUs
  50. 117 million LinkedIn emails and passwords from a 2012 hack just ...
  51. LinkedIn Data Breach - Have I Been Pwned
  52. NIST Special Publication 800-63B
  53. [PDF] stronger key derivation via sequential memory-hard functions colin ...
  54. RFC 2898: Password-Based Cryptography Specification, Version 2.0
  55. [PDF] A Future-Adaptable Password Scheme - USENIX
  56. [PDF] NIST SP 800-63B-4 ipd (initial public draft), Digital Identity Guidelines
User Avatar
No comments yet.