Hubbry Logo
search
logo
Collision attack avatar
Collision attack
Collision attack
current hub
C

Collision attack

logo
Community Hub0 Subscribers

Wikipedia

Collision attack
View on Wikipedia
from Wikipedia

In cryptography, a collision attack on a cryptographic hash tries to find two inputs producing the same hash value, i.e. a hash collision. This is in contrast to a preimage attack where a specific target hash value is specified.

There are roughly two types of collision attacks:

Classical collision attack
Find two different messages m1 and m2 such that hash(m1) = hash(m2).

More generally:

Chosen-prefix collision attack
Given two different prefixes p1 and p2, find two suffixes s1 and s2 such that hash(p1 ∥ s1) = hash(p2 ∥ s2), where ∥ denotes the concatenation operation.

Classical collision attack

[edit]

Much like symmetric-key ciphers are vulnerable to brute force attacks, every cryptographic hash function is inherently vulnerable to collisions using a birthday attack. Due to the birthday problem, these attacks are much faster than a brute force would be. A hash of n bits can be broken in 2n/2 time steps (evaluations of the hash function).

Mathematically stated, a collision attack finds two different messages ⁠⁠ and ⁠⁠, such that . In a classical collision attack, the attacker has no control over the content of either message, but they are arbitrarily chosen by the algorithm.

More efficient attacks are possible by employing cryptanalysis to specific hash functions. When a collision attack is discovered and is found to be faster than a birthday attack, a hash function is often denounced as "broken". The NIST hash function competition was largely induced by published collision attacks against two very commonly used hash functions, MD5[1] and SHA-1. The collision attacks against MD5 have improved so much that, as of 2007, it takes just a few seconds on a regular computer.[2] Hash collisions created this way are usually constant length and largely unstructured, so cannot directly be applied to attack widespread document formats or protocols.

However, workarounds are possible by abusing dynamic constructs present in many formats. In this way, two documents would be created which are as similar as possible in order to have the same hash value. One document would be shown to an authority to be signed, and then the signature could be copied to the other file. Such a malicious document would contain two different messages in the same document, but conditionally display one or the other through subtle changes to the file:

  • Some document formats like PostScript, or macros in Microsoft Word, have conditional constructs.[3][4] (if-then-else) that allow testing whether a location in the file has one value or another in order to control what is displayed.
  • TIFF files can contain cropped images, with a different part of an image being displayed without affecting the hash value.[4]
  • PDF files are vulnerable to collision attacks by using color value (such that text of one message is displayed with a white color that blends into the background, and text of the other message is displayed with a dark color) which can then be altered to change the signed document's content.[4]

Chosen-prefix collision attack

[edit]

An extension of the collision attack is the chosen-prefix collision attack, which is specific to Merkle–Damgård hash functions. In this case, the attacker can choose two arbitrarily different documents, and then append different calculated values that result in the whole documents having an equal hash value. This attack is normally harder, a hash of n bits can be broken in 2(n/2)+1 time steps, but is much more powerful than a classical collision attack.

Mathematically stated, given two different prefixes p1, p2, the attack finds two suffixes s1 and s2 such that hash(p1 ∥ s1) = hash(p2 ∥ s2) (where ∥ is the concatenation operation).

More efficient attacks are also possible by employing cryptanalysis to specific hash functions. In 2007, a chosen-prefix collision attack was found against MD5, requiring roughly 250 evaluations of the MD5 function. The paper also demonstrates two X.509 certificates for different domain names, with colliding hash values. This means that a certificate authority could be asked to sign a certificate for one domain, and then that certificate (specially its signature) could be used to create a new rogue certificate to impersonate another domain.[5]

A real-world collision attack was published in December 2008 when a group of security researchers published a forged X.509 signing certificate that could be used to impersonate a certificate authority, taking advantage of a prefix collision attack against the MD5 hash function. This meant that an attacker could impersonate any SSL-secured website as a man-in-the-middle, thereby subverting the certificate validation built in every web browser to protect electronic commerce. The rogue certificate may not be revokable by real authorities, and could also have an arbitrary forged expiry time. Even though MD5 was known to be very weak in 2004,[1] certificate authorities were still willing to sign MD5-verified certificates in December 2008,[6] and at least one Microsoft code-signing certificate was still using MD5 in May 2012.

The Flame malware successfully used a new variation of a chosen-prefix collision attack to spoof code signing of its components by a Microsoft root certificate that still used the compromised MD5 algorithm.[7][8]

In 2019, researchers found a chosen-prefix collision attack against SHA-1 with computing complexity between 266.9 and 269.4 and cost less than 100,000 US dollars. [9][10] In 2020, researchers reduced the complexity of a chosen-prefix collision attack against SHA-1 to 263.4. [11]

Attack scenarios

[edit]

Many applications of cryptographic hash functions do not rely on collision resistance, thus collision attacks do not affect their security. For example, HMACs are not vulnerable.[12] For the attack to be useful, the attacker must be in control of the input to the hash function.

Digital signatures

[edit]

Because digital signature algorithms cannot sign a large amount of data efficiently, most implementations use a hash function to reduce ("compress") the amount of data that needs to be signed down to a constant size. Digital signature schemes often become vulnerable to hash collisions as soon as the underlying hash function is practically broken; techniques like randomized (salted) hashing will buy extra time by requiring the harder preimage attack.[13]

The usual attack scenario goes like this:

  1. Mallory creates two different documents A and B that have an identical hash value, i.e., a collision. Mallory seeks to deceive Bob into accepting document B, ostensibly from Alice.
  2. Mallory sends document A to Alice, who agrees to what the document says, signs its hash, and sends the signature to Mallory.
  3. Mallory attaches the signature from document A to document B.
  4. Mallory then sends the signature and document B to Bob, claiming that Alice signed B. Because the digital signature matches document B's hash, Bob's software is unable to detect the substitution.[citation needed]

In 2008, researchers used a chosen-prefix collision attack against MD5 using this scenario, to produce a rogue certificate authority certificate. They created two versions of a TLS public key certificate, one of which appeared legitimate and was submitted for signing by the RapidSSL certificate authority. The second version, which had the same MD5 hash, contained flags which signal web browsers to accept it as a legitimate authority for issuing arbitrary other certificates.[14]

Hash flooding

[edit]

Hash flooding (also known as HashDoS[15]) is a denial of service attack that uses hash collisions to exploit the worst-case (linear probe) runtime of hash table lookups.[16] It was originally described in 2003 as an example of an algorithmic complexity attack.[17] To execute such an attack, the attacker sends the server multiple pieces of data that hash to the same value and then tries to get the server to perform slow lookups. As the main focus of hash functions used in hash tables was speed instead of security, most major programming languages were affected,[17] with new vulnerabilities of this class still showing up a decade after the original presentation.[16]

To prevent hash flooding without making the hash function overly complex, newer keyed hash functions are introduced, with the security objective that collisions are hard to find as long as the key is unknown. They may be slower than previous hashes, but are still much easier to compute than cryptographic hashes. As of 2021, Jean-Philippe Aumasson and Daniel J. Bernstein's SipHash (2012) is the most widely used hash function in this class.[18] (Non-keyed "simple" hashes remain safe to use as long as the application's hash table is not controllable from the outside.)

It is possible to perform an analogous attack to fill up Bloom filters using a (partial) preimage attack.[19]

See also

[edit]

References

[edit]
[edit]

Grokipedia

Collision attack

View on Grokipedia
from Grokipedia
In cryptography, a collision attack is a method of cryptanalysis aimed at finding two distinct inputs—typically messages—that, when processed by a given cryptographic hash function, produce the same output hash value, thereby creating a hash collision.[1] This vulnerability exploits weaknesses in the hash function's design, allowing an attacker to generate seemingly identical digests for different data, which can compromise applications relying on hash uniqueness.[2] Cryptographic hash functions are engineered with several security properties, among which collision resistance is paramount: it requires that discovering any such colliding pair should be computationally infeasible for practical purposes, even with significant resources.[3] Second preimage resistance protects against finding a second input that matches the hash of a specific given input, while collision resistance guards against finding any two colliding inputs without prior specification. These properties are crucial for ensuring data integrity in protocols like digital signatures, where a collision could enable forgery, or in blockchain and certificate validation, where altered documents might evade detection.[4] A foundational generic approach to collision attacks is the birthday attack, derived from the birthday paradox, which demonstrates that collisions can be found with high probability after evaluating approximately 2n/22^{n/2} inputs for an nn-bit hash function, rather than the naive 2n2^n exhaustive search.[5] This reduces the effective security of hash functions against collisions to half their output length in bits, explaining why even well-designed hashes like those with 256-bit outputs aim for at least 128-bit collision security.[6] Prominent real-world collision attacks have accelerated the obsolescence of legacy hash functions. In 2004, Xiaoyun Wang and colleagues published the first practical collision for MD5, achievable in about 2392^{39} operations—far more efficient than the birthday bound of 2642^{64}—using differential cryptanalysis to construct colliding message blocks.[7] Similarly, in 2017, Marc Stevens, Elie Bursztein, and a team from Google and CWI Amsterdam announced the first full collision for SHA-1 after approximately 100 GPU-years of computation, confirming its practical insecurity and prompting NIST to recommend immediate migration away from it.[8] These breakthroughs, along with subsequent chosen-prefix collisions for SHA-1 in 2019[9], underscore the need for robust, modern alternatives like SHA-256 or SHA-3, which remain resistant to known practical attacks as of 2025.[10]

Fundamentals of Hash Collisions

Definition and Importance

A cryptographic hash function is a mathematical algorithm that maps data of arbitrary size to a fixed-length bit string, known as the hash value or digest, serving as a digital fingerprint for the input.[https://csrc.nist.gov/glossary/term/cryptographic_hash_function] These functions are designed to be one-way, meaning it is computationally infeasible to reverse the process and recover the original input from the hash output alone, while also providing properties such as preimage resistance (infeasibility of finding any input for a given output) and second preimage resistance (infeasibility of finding a different input producing the same output as a given input).[https://doi.org/10.6028/NIST.SP.800-107r1] In this context, a collision occurs when two distinct inputs, denoted as xx and yy where x≠yx \neq y, produce the same hash value under the function hh, such that h(x)=h(y)h(x) = h(y).[https://csrc.nist.gov/glossary/term/collision] Collision resistance is a core security property requiring that finding such a pair be computationally infeasible.[https://csrc.nist.gov/glossary/term/collision_resistance] The importance of collision resistance in cryptography cannot be overstated, as collisions directly undermine the integrity and authenticity assurances provided by hash functions in protocols like digital signatures and message authentication.[https://doi.org/10.6028/NIST.SP.800-107r1] By enabling attackers to craft fraudulent data that hashes identically to legitimate content, collisions facilitate attacks on systems relying on hash-based verification, such as forging certificates or signatures without altering the perceived validity.[https://doi.org/10.6028/NIST.SP.800-107r1] For ideal hash functions with an nn-bit output, security assumes that generating a collision requires approximately 2n/22^{n/2} operations, a bound derived from probabilistic analysis known as the birthday paradox, establishing the scale of computational effort needed for robustness.[https://doi.org/10.6028/NIST.SP.800-107r1] Breaches in this resistance, as seen in weakened functions like MD5,[11] have real-world consequences including compromised software distribution and network security, highlighting the need for ongoing evaluation and transition to stronger algorithms.[https://doi.org/10.6028/NIST.SP.800-107r1]

Birthday Paradox and Attack Complexity

The birthday paradox, a principle from probability theory, demonstrates that collisions occur more frequently than intuition suggests in large sample spaces. For an n-bit hash function with 2^n possible outputs, the expected number of random inputs required to achieve a 50% probability of at least one collision is approximately \sqrt{2 \ln 2 \cdot 2^n}, or roughly 1.177 \times 2^{n/2} trials. This counterintuitive result arises because the probability of a collision depends on pairwise comparisons among the inputs, leading to a quadratic growth in potential matches relative to the number of samples. The concept was first applied to cryptographic hash functions in the context of exploiting digital signatures, highlighting how an attacker could generate colliding messages with feasible effort. The precise probability of finding at least one collision after computing k hashes can be approximated using the birthday problem formula:
P(collision)≈1−e−k(k−1)/(2⋅2n) P(\text{collision}) \approx 1 - e^{-k(k-1)/(2 \cdot 2^n)}
This approximation holds under the assumption of uniform and independent hash outputs, where the exponential term accounts for the decreasing likelihood of avoiding collisions as k increases. For k \ll 2^{n/2}, the probability is low, but it rises sharply near k \approx 1.18 \cdot 2^{n/2}, reaching about 50%. In practice, this means that generic collision searches, such as storing all computed hashes in a table and checking for matches, require O(2^{n/2}) both in time (hash computations) and space (storage for the table). This contrasts sharply with brute-force preimage attacks, which demand O(2^n) effort to find a single input mapping to a given output, underscoring the asymmetry in hash function security properties.[12] To mitigate the high space requirements of the basic birthday attack, variants like Pollard's rho method offer a time-memory trade-off, achieving the same O(2^{n/2}) time complexity with constant or low memory usage. The algorithm simulates a pseudorandom walk in the hash output space, detecting cycles via the "rho" shape formed by the sequence, where the tail and cycle intersection reveals a collision. Parallel implementations further distribute the computation across processors while maintaining efficiency. These optimizations make collision attacks practical even under resource constraints, emphasizing that an n-bit hash provides only n/2 bits of collision resistance—meaning security against such attacks is halved compared to preimage resistance. As a result, cryptographic standards recommend hash outputs of at least 256 bits to ensure 128-bit collision security against foreseeable computational power.[12][13]

Types of Collision Attacks

Classical Collision Attack

A classical collision attack on a cryptographic hash function seeks to identify two distinct arbitrary inputs, denoted as xx and yy, such that the hash outputs are identical, h(x)=h(y)h(x) = h(y), without any prior control over the structure or content of xx or yy. This type of attack targets the collision resistance property of hash functions, which assumes that finding such pairs should require exhaustive effort proportional to the output size. Unlike targeted variants, classical attacks do not impose constraints on the inputs, making them applicable to any hash function but generally limited by generic search bounds. Generic algorithms for classical collision attacks exploit the birthday paradox, which indicates that collisions in a space of 2n2^n possible outputs are likely to occur after roughly 2n/22^{n/2} random trials. The standard birthday attack proceeds as follows: (1) generate a sequence of random inputs xix_i; (2) compute and store the hash values h(xi)h(x_i) along with the corresponding inputs in a lookup table; (3) continue until a duplicate hash value is detected, yielding the colliding pair. This method has a time complexity of O(2n/2)O(2^{n/2}) and requires O(2n/2)O(2^{n/2}) storage for the table. An alternative is Pollard's rho algorithm, adapted for hash collisions, which models the hash iteration as a functional graph and uses cycle detection to find matches with low memory usage. In this approach, two sequences (a "tortoise" and "hare") are generated by iterating the hash function from a starting point, advancing the hare twice as fast; a collision in their paths indicates a hash collision, achieving the same O(2n/2)O(2^{n/2}) time complexity but constant space. Parallel variants, such as those using distinguished points (hashes ending in many zeros), further optimize for distributed computation. To illustrate, consider a toy hash function with a 4-bit output space (n=4n=4, 16 possible values). The birthday attack expects approximately 16=4\sqrt{16} = 4 random trials to find a collision with 50% probability, far fewer than exhaustively checking all pairs. In practice, for a secure 256-bit hash like SHA-256, a classical attack would require about 21282^{128} operations, rendering it infeasible with current technology. However, hash functions with poor internal mixing or structural weaknesses can succumb to faster non-generic attacks, such as differential cryptanalysis, which exploits differences in input pairs to propagate through the function's rounds. For MD5, a seminal differential attack by Wang et al. demonstrated practical collisions by constructing input differences that lead to identical outputs after 64 rounds, achievable in about 2392^{39} time—orders of magnitude faster than the generic 2642^{64} bound. This vulnerability arises from MD5's inadequate avalanche effect and compressible differences, allowing attackers to bypass ideal randomness assumptions. Building on differential cryptanalysis techniques, the 2017 SHAttered attack by Stevens, Bursztein, and a team from Google and CWI Amsterdam demonstrated the first practical identical-prefix collision for full SHA-1 (a variant where a common prefix is extended with colliding suffixes), with a complexity of 263.12^{63.1} SHA-1 compression function evaluations, equivalent to roughly 6,500 CPU-years and 100 GPU-years of computation.[8]

Chosen-Prefix Collision Attack

A chosen-prefix collision attack involves finding two distinct messages with attacker-chosen prefixes PP and P′P' (where P≠P′P \neq P') and corresponding suffixes SS and S′S' such that the hash function H(P∥S)=H(P′∥S′)H(P \parallel S) = H(P' \parallel S'). This variant extends beyond classical collision attacks, which seek any two colliding messages without prefix control, by enabling the attacker to target specific message structures. The method employs differential cryptanalysis to construct near-collision blocks that align intermediate hash values (IHVs) from the differing prefixes, often using bicliques—sets of colliding message pairs that cancel differences across multiple steps—or tailored differential paths. These near-collisions are connected via birthday-like searches on modified message blocks, exploiting the hash function's structure to bridge IHV gaps with reduced effort compared to full brute force. The overall complexity exceeds that of classical collisions, typically on the order of 2n/2+α2^{n/2 + \alpha} compression function evaluations, where nn is the hash output size and α>0\alpha > 0 accounts for the added prefix freedom. A historical breakthrough occurred in 2009 when Stevens et al. developed the first practical chosen-prefix collision for MD5, requiring approximately 2492^{49} MD5 compression function calls, achievable in about one day on a cluster of PlayStation 3 consoles.[14] In 2020, Gaëtan Leurent and Thomas Peyrin from Inria demonstrated the first practical chosen-prefix collision for SHA-1, with a complexity of approximately 263.42^{63.4} SHA-1 evaluations on an Nvidia GTX 970 GPU, confirming the vulnerability and prompting further deprecation efforts.[15] Technically, the attack uses iterative birthday searches (e.g., targeting 64- to 96-bit differences) on expandable message cores to generate a small number of near-collision blocks—often three for MD5—that propagate collisions without disrupting the prefixes. This relies on hash function weaknesses, such as MD5's compressible nonlinear operations and block expandability, allowing insertion of colliding bitstrings (e.g., via padding or comments) while preserving message validity. For SHA-1, biclique constructions further optimize local collisions to handle the function's larger state differences. Compared to classical collisions, chosen-prefix attacks offer greater practical utility by permitting the forgery of distinct, attacker-specified documents—such as appending colliding suffixes to different prefixes in digital certificates or files—without needing identical starting content.

Practical Applications and Vulnerabilities

Impact on Digital Signatures

Digital signature schemes, such as those based on RSA or DSA, typically involve hashing the message with a cryptographic hash function and then signing the resulting hash value using the signer's private key. A collision attack undermines this process by enabling an attacker to find two distinct messages, $ m_1 $ and $ m_2 $, that produce the same hash value, $ h(m_1) = h(m_2) $. If the signer approves and signs a benign message $ m_1 $, the attacker can substitute the malicious $ m_2 $ while retaining the valid signature, as the verification process checks only the hash against the signed value, bypassing integrity checks and allowing forgery.[16] This vulnerability is particularly acute in schemes like RSA-PSS, where the signature's security relies on the hash function's collision resistance to prevent existential forgeries, and in DSA variants, where hash collisions can create key-collisions that weaken non-repudiation by enabling plausible deniability for forged signatures. In RSA-PSS, a collision in the underlying hash (e.g., MD5) allows an attacker to craft messages that pass verification despite differing content, as the probabilistic signature scheme assumes a collision-resistant hash to maintain tight security bounds under the random oracle model. Similarly, in (EC)DSA, collisions facilitate the generation of colliding key instances, permitting an attacker to forge a signature on a different message without access to the private key, thus compromising the scheme's unforgeability.[17][18] The attack workflow generally proceeds as follows: an attacker first computes a pair of colliding messages using a classical collision-finding method, such as differential cryptanalysis on vulnerable hashes like MD5, ensuring $ m_1 $ appears innocuous (e.g., a legitimate contract or software update) and $ m_2 $ contains malicious content (e.g., altered terms or malware code). The signer is tricked into signing $ m_1 $, producing a signature $ \sigma $ on $ h(m_1) $. The attacker then presents $ m_2 $ paired with $ \sigma $, which verifies successfully since $ h(m_2) = h(m_1) $, enabling undetected forgery in applications like certificate signing or document authentication.[16] A prominent real-world example is the 2012 Flame malware attack, where attackers exploited an MD5 chosen-prefix collision to forge Windows Update certificates. By crafting colliding certificate files—one legitimate and signed by a Microsoft intermediate CA, the other malicious without the critical "Microsoft Hydra" extension—they created a code-signing certificate valid across all Windows versions, allowing Flame to masquerade as a legitimate update and spread undetected. This incident highlighted MD5's practical break, prompting Microsoft to revoke affected certificates via Security Advisory 2718704.[19] Mitigating these risks requires transitioning to collision-resistant hash functions like SHA-256 or SHA-3, which offer 128-bit security against collisions, far exceeding MD5's broken ~39-bit resistance and SHA-1's ~63-bit vulnerability. Post-MD5 and SHA-1 breaks, standards bodies such as NIST have recommended this shift for digital signatures to restore security, often combined with randomized hashing techniques—where a fresh random salt is prepended to the message before hashing—to further thwart offline collision searches by requiring target-collision resistance instead. However, legacy systems using vulnerable hashes remain exposed until fully migrated, underscoring ongoing gaps in deployment.[20][21][22][23]

Hash Flooding in Network Protocols

Hash flooding in network protocols refers to a class of denial-of-service (DoS) attacks where an adversary exploits weaknesses in hash table implementations within protocol stacks to degrade performance. In these attacks, the attacker crafts and sends network packets or messages containing inputs that cause multiple entries to collide in the same hash table bucket, forcing the use of collision resolution mechanisms like linked lists or chains. This transforms the expected average-case O(1) lookup and insertion time into a worst-case O(n complexity, where n is the number of colliding elements, leading to excessive CPU consumption and potential service disruption.[24] Such vulnerabilities are particularly prevalent in protocols that rely on hash tables for efficient data handling, such as HTTP/1.1, where servers parse and store request headers in hash-based structures for quick access. An attacker can flood a server with HTTP requests featuring specially constructed header names or values that hash to the same buckets, overwhelming the parser and causing request processing to slow dramatically or halt. Similarly, blockchain transaction pools (mempools) use hash tables to index pending transactions by their identifiers, making them susceptible to spam attacks that generate colliding hashes to bloat specific buckets and delay legitimate transaction validation. In TCP implementations, hash tables within the networking stack, such as those for managing peer connections or route caches, can be targeted to amplify latency in sequence number handling and packet routing. These exploits often involve deliberately crafting inputs to collide in the same hash buckets, exploiting the predictability of the hash functions and enabling low-bandwidth attacks.[25][26][27] The mechanics of these attacks typically involve generating inputs that produce near-identical or targeted hash values to concentrate collisions in few buckets, without necessarily requiring full cryptographic collisions. Unlike cryptanalytic attacks needing second-preimage resistance breaches, hash flooding exploits non-cryptographic or weakly randomized hashes common in performance-oriented protocol code, where predictability allows precomputation of colliding strings using tools like those for MD5 or custom hash functions. Attackers can automate this with scripts that iteratively find collisions offline and embed them in protocol payloads, such as HTTP POST parameters or TCP options, to chain collisions progressively. This approach demands minimal resources from the attacker but scales poorly for victims, as each new colliding input exacerbates chain lengths.[24] A notable real-world incident occurred in 2003, when vulnerabilities in the Linux kernel's networking stack, including hash tables for the destination cache (dst cache) and inetpeer structures, were exploited for DoS via crafted packets inducing collisions. These flaws, stemming from predictable hashing in netfilter and routing code, allowed remote attackers to trigger excessive memory allocation and CPU spikes, leading to kernel panics or severe slowdowns in packet processing. The issue highlighted broader risks in open-source protocol implementations, prompting patches across distributions. Mitigations commonly involve introducing randomized salting or seeds to hash functions at runtime, such as per-process or per-table randomization, which thwarts precomputed collisions by altering the hash space unpredictably for each instance. Algorithms like SipHash, designed specifically for DoS resistance, have been adopted in kernels and libraries to replace vulnerable hashes.[27][28][29] The broader impact of hash flooding extends to systemic failures in networked systems, where degraded hash table performance cascades to server crashes, increased latency for legitimate traffic, or complete unavailability of protocol services. In high-volume environments like web servers or blockchain nodes, even moderate collision rates can amplify to affect thousands of connections, consuming disproportionate resources compared to the attacker's effort. Critically, these attacks target operational efficiency rather than data authenticity or integrity, distinguishing them from forgery-based exploits and underscoring the need for robust, randomized data structures in protocol designs.[30]

Historical Developments and Mitigations

Key Milestones in Collision Discoveries

The study of hash function collisions began gaining traction in the mid-1990s with early theoretical advances on MD5. In 1996, Hans Dobbertin demonstrated a collision attack on the compression function of MD5, revealing vulnerabilities in its internal structure, though this did not yet constitute a full hash collision due to the use of a modified initialization vector.[31] This work laid foundational insights into differential cryptanalysis techniques applicable to MD5-like designs.[32] Practical breakthroughs followed in 2004, when Xiaoyun Wang and colleagues announced the first full collision attack on MD5, achievable with a complexity of approximately 2392^{39} operations using differential paths and message modification methods.[33] That same year, the team extended their techniques to RIPEMD, constructing collisions for the original 128-bit version in a single block, demonstrating similar weaknesses in its design and prompting evaluations of related hash functions.[33] These attacks shifted focus from theoretical compression function breaks to feasible full-hash collisions, influencing the security assessment of widely deployed algorithms. By 2005, attention turned to SHA-1, with Wang's group reporting a partial collision on a reduced-round version (around 58 out of 80 rounds), estimating a full collision complexity of 2692^{69}, which underscored growing concerns about SHA-1's long-term viability despite its then-standard status.[34] Advancements in MD5 continued, culminating in practical full collisions achievable in seconds on commodity hardware by the late 2000s through optimized differential paths and parallel computing. The Debian OpenSSL vulnerability in 2008, caused by a packaging error that reduced the random number generator's entropy, led to predictable keys and duplicate signatures, compromising certificate uniqueness and affecting millions of systems; separately, MD5 collisions were exploited in demonstrations of rogue certificate authority attacks.[35] In 2012, the Flame malware further illustrated these threats by employing a novel MD5 collision variant to forge Microsoft update certificates, allowing the payload to masquerade as legitimate software and spread via Windows Update mechanisms on pre-Vista systems.[19] The most significant SHA-1 milestone occurred in 2017, when a collaborative team from Google and CWI Amsterdam executed the first practical chosen-prefix collision attack—dubbed SHAttered—producing two distinct PDFs with identical SHA-1 hashes after approximately 2632^{63} operations using advanced differential cryptanalysis and GPU acceleration.[8] In 2019, Leurent and Peyrin published the first practical chosen-prefix collision for full SHA-1 with complexity around 2662^{66} operations, enabling attacks such as impersonation in PGP/GnuPG.[9] This breakthrough directly prompted NIST to deprecate SHA-1 for all uses by 2030, accelerating its retirement in standards like TLS.[36] Post-2017 developments emphasized the resilience of stronger hashes like SHA-256, with no practical collisions found despite intensive scrutiny, aligning with NIST's guidelines to transition away from MD5 and SHA-1 toward SHA-2 and SHA-3 families for collision resistance.[37] Overall, these milestones trace a progression from theoretical vulnerabilities to computationally feasible and exploit-ready attacks, hastening the obsolescence of insecure hash functions in cryptographic ecosystems.[13]

Modern Hash Function Designs

Modern hash function designs emphasize constructions that inherently resist collision attacks by leveraging larger internal states and alternative architectures to the vulnerable Merkle-Damgård paradigm. The sponge construction, utilized in SHA-3 derived from the Keccak algorithm, operates by absorbing input data into a fixed-width state via a permutation and then squeezing out the hash value, with the capacity $ c $ (state width minus rate) dictating collision security. For instance, SHA3-256 employs a 512-bit capacity, yielding 256 bits of collision resistance while avoiding Merkle-Damgård's susceptibility to length-extension attacks through non-chaining absorption and no exposure of intermediate chain values.[38] NIST formalized SHA-3 in 2012 by selecting Keccak as the winner of its cryptographic hash competition, valuing its substantial security margin—demonstrated by no practical collisions on the full 24-round permutation—and hardware efficiency that complements SHA-2's design principles.[39] In response to SHA-1's practical collision vulnerability, NIST policy mandates phasing out SHA-1 for collision-dependent uses and endorses SHA-2 or SHA-3 variants with at least 256-bit outputs to ensure 128-bit collision resistance, aligning with contemporary security needs.[37] Resistance techniques in these designs include wide-pipe configurations for Merkle-Damgård-based functions, where the internal state exceeds the output length (e.g., double the output size) to thwart internal collisions and Joux-style multi-collisions by diluting attack propagation. Finalization steps, such as multi-rate padding and output truncation tweaks, further fortify the structure against differential attacks. Under the random oracle model, these hash functions achieve provably tight collision resistance of $ n/2 $ bits for $ n $-bit outputs, modeling the hash as an ideal random function to bound adversary success probabilities.[40] Implementation guidance prioritizes keyed modes like HMAC, which maintains integrity even against collisions in the underlying hash by relying on preimage resistance and a secret key of sufficient length (e.g., at least 256 bits for 128-bit security). Salting—appending unique random values to inputs—mitigates precomputed collision attacks, such as rainbow tables, by rendering stored collision pairs inapplicable across distinct salts. Looking ahead, quantum threats via Grover's algorithm halve preimage resistance to $ 2^{n/2} $ operations but preserve classical $ 2^{n/2} $ collision complexity, though advanced quantum birthday methods like Brassard-Høyer-Tapp could reduce it to $ O(2^{n/3}) $; existing standards like SHA-3 remain viable, with NIST's post-quantum efforts targeting signatures rather than hash redesigns.[41][42]

References

  1. https://scholarworks.sjsu.edu/cgi/viewcontent.cgi?article=1020&context=etd_projects
  2. [PDF] Avoiding collisions Cryptographic hash functions - Computer Science
  3. [PDF] Collision-Resistant Hash Functions
  4. [PDF] Lecture 11: Hash Functions and Random Oracle Model
  5. RFC 4270 - Attacks on Cryptographic Hashes in Internet Protocols
  6. [PDF] Cryptographic Hash Functions - Columbia CS
  7. [PDF] Cryptography - Washington
  8. [PDF] How to Break MD5 and Other Hash Functions - Merlot
  9. [PDF] The first collision for full SHA-1 - Cryptology ePrint Archive
  10. Research Results on SHA-1 Collisions | CSRC
  11. [PDF] Parallel Collision Search with Cryptanalytic Applications
  12. Hash Functions | CSRC - NIST Computer Security Resource Center
  13. [PDF] Hash functions: Theory, attacks, and applications - Microsoft
  14. [PDF] birthday attack - Columbia Math Department
  15. Parallel Collision Search with Cryptanalytic Applications
  16. [PDF] Chosen-prefix collisions for MD5 and applications Marc Stevens
  17. None
  18. [PDF] Practical Attacks on Digital Signatures Using MD5 Message Digest
  19. [PDF] On the Security of RSA-PSS in the Wild - Cryptology ePrint Archive
  20. [PDF] Key-collisions in (EC)DSA: Attacking Non-repudiation*
  21. Flame malware collision attack explained - Microsoft
  22. Why We Need to Move to SHA-2 | PKI Consortium
  23. [PDF] Strengthening Digital Signatures via Randomized Hashing - CSRC
  24. https://www.ocert.org/advisories/ocert-2011-003.html
  25. About that hash flooding vulnerability in Node.js… · V8
  26. Carbyne: An Ultra-Lightweight DoS-Resilient Mempool for Bitcoin
  27. Algorithmic Complexity Attacks and the Linux Networking Code
  28. Denial of service via hash collisions - LWN.net
  29. [PDF] Hash-flooding DoS reloaded: attacks and defenses
  30. Technical Advisory – Hash Denial-of-Service Attack in Multiple QUIC ...
  31. VU#836068 - MD5 vulnerable to collision attacks
  32. [PDF] Improved Collision Attack on MD5
  33. [PDF] Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD
  34. NIST Brief Comments on Recent Cryptanalytic Attacks | CSRC
  35. Improved Collision Attack on Hash Function MD5 - ResearchGate
  36. [SECURITY] [DSA 1571-1] New openssl packages fix predictable ...
  37. NIST Retires SHA-1 Cryptographic Algorithm
  38. Hash Functions | CSRC - NIST Computer Security Resource Center
  39. [PDF] fips pub 202 - federal information processing standards publication
  40. [PDF] Third-Round Report of the SHA-3 Cryptographic Hash Algorithm ...
  41. [PDF] Random Oracles are Practical: A Paradigm for Designing Efficient ...
  42. [PDF] An Efficient Quantum Collision Search Algorithm and Implications on ...
  43. Post-Quantum Cryptography | CSRC
User Avatar
No comments yet.