Fact-checked by Grok 2 weeks ago

Collision attack

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 $2^{n/2} inputs for an n-bit hash function, rather than the naive $2^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 $2^{39} operations—far more efficient than the birthday bound of $2^{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.^[11] 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).^[12] In this context, a collision occurs when two distinct inputs, denoted as x and y where x \neq y, produce the same hash value under the function h, such that h(x) = h(y).^[13] Collision resistance is a core security property requiring that finding such a pair be computationally infeasible.^[14] 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.^[12] 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.^[12] For ideal hash functions with an n-bit output, security assumes that generating a collision requires approximately $2^{n/2} operations, a bound derived from probabilistic analysis known as the birthday paradox, establishing the scale of computational effort needed for robustness.^[12] Breaches in this resistance, as seen in weakened functions like MD5,^[15] have real-world consequences including compromised software distribution and network security, highlighting the need for ongoing evaluation and transition to stronger algorithms.^[12]

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(\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.^[16] 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.^[16]^[17]

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 x and y, such that the hash outputs are identical, h(x) = h(y), without any prior control over the structure or content of x or y. 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 $2^n possible outputs are likely to occur after roughly $2^{n/2} random trials. The standard birthday attack proceeds as follows: (1) generate a sequence of random inputs x_i; (2) compute and store the hash values 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(2^{n/2}) and requires 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(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=4, 16 possible values). The birthday attack expects approximately \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 $2^{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 $2^{39} time—orders of magnitude faster than the generic $2^{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 $2^{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 P and P' (where P \neq P') and corresponding suffixes S and S' such that the hash function 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 $2^{n/2 + \alpha} compression function evaluations, where n is the hash output size and \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 $2^{49} MD5 compression function calls, achievable in about one day on a cluster of PlayStation 3 consoles.^[18] 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 $2^{63.4} SHA-1 evaluations on an Nvidia GTX 970 GPU, confirming the vulnerability and prompting further deprecation efforts.^[19] 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.^[20] 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.^[21]^[22] 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.^[20] 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.^[23] 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.^[24]^[25]^[26]^[27]

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.^[28] 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.^[29]^[30]^[31] 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.^[28] 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.^[31]^[32]^[33] 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.^[34]

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.^[35] This work laid foundational insights into differential cryptanalysis techniques applicable to MD5-like designs.^[36] Practical breakthroughs followed in 2004, when Xiaoyun Wang and colleagues announced the first full collision attack on MD5, achievable with a complexity of approximately $2^{39} operations using differential paths and message modification methods.^[37] 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.^[37] 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 $2^{69}, which underscored growing concerns about SHA-1's long-term viability despite its then-standard status.^[38] 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.^[39] 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.^[23] 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 $2^{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 $2^{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.^[40] 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.^[41] 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.^[17]

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.^[42] 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.^[43] 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.^[41] 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.^[44] 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.^[45]^[46]

References

[1]
https://scholarworks.sjsu.edu/cgi/viewcontent.cgi?article=1020&context=etd_projects
[2]
[PDF] Avoiding collisions Cryptographic hash functions - Computer Science
Collisions are not good for data-retrieval complexity. They are disastrous in cryptographic applications. Introduction. Collision resistance. Birthday attacks.<|control11|><|separator|>
[3]
[PDF] Collision-Resistant Hash Functions
Collisions can be found in time 260 (better than "birthday attack") (2005). • SHA-3. Selected by NIST in 2012 based on public competition. Output lengths 256 ...
[4]
[PDF] Lecture 11: Hash Functions and Random Oracle Model
Oct 16, 2017 · A collision-resistant hash functions (CRHF) is a function that “shrinks” a long message to a short output called the digest of the message.<|control11|><|separator|>
[5]
RFC 4270 - Attacks on Cryptographic Hashes in Internet Protocols
This document summarizes the use of hashes in many protocols, discusses how the collision attacks affect and do not affect the protocols, shows how to thwart ...
[6]
[PDF] Cryptographic Hash Functions - Columbia CS
• Very important property for collision-resistance. ◇ Brute-force inversion requires 2160 ops, birthday attack on collision resistance requires 280 ops.
[7]
[PDF] Cryptography - Washington
Oct 23, 2020 · Expect “collision” after selecting approximately 264 random values. • 64 bits of security against collision attacks, not 128 bits. 10/23 ...
[8]
[PDF] How to Break MD5 and Other Hash Functions - Merlot
In this paper we present a new powerful attack on MD5 which allows us to find collisions efficiently. We used this attack to find collisions of MD5 in about 15 ...
[9]
[PDF] The first collision for full SHA-1 - Cryptology ePrint Archive
Fig. 2: The main steps for each near-collision attack. This section describes the overall procedure of each of the two near-collision attacks.
[10]
Research Results on SHA-1 Collisions | CSRC
A team of researchers from the CWI Institute in Amsterdam and Google have successfully demonstrated an attack on the SHA-1 hash algorithm.
[11]
[PDF] Parallel Collision Search with Cryptanalytic Applications
Sep 23, 1996 · Parallel Collision Search with Cryptanalytic Applications. Paul C. van Oorschot and Michael J. Wiener. Nortel, P.O. Box 3511 Station C, Ottawa ...
[12]
Hash Functions | CSRC - NIST Computer Security Resource Center
Jan 4, 2017 · Collision resistance: It is computationally infeasible to find two different inputs to the hash function that have the same hash value.NIST Policy · News & Updates · Events · SHA-3 Standardization
[13]
[PDF] Hash functions: Theory, attacks, and applications - Microsoft
Nov 14, 2005 · A generic attack is an attack that applies to all hash functions, no matter how good they are, as opposed to specific attacks that exploit ...
[14]
[PDF] birthday attack - Columbia Math Department
BIRTHDAY ATTACK. The birthday attack is a method to find collisions in a cryptographic hash function. It is based on the well known “birthday paradox” which ...Missing: formula | Show results with:formula
[15]
Parallel Collision Search with Cryptanalytic Applications
Parallel Collision Search with Cryptanalytic Applications. 5 ciphertexts to ... [41] P.C. van Oorschot and M.J. Wiener, A known-plaintext attack on two ...
[16]
[PDF] Chosen-prefix collisions for MD5 and applications Marc Stevens
(Stevens et al., 2009)). Here we present a full description of our improved chosen-prefix collision attack. We show how any pair of IHVs can be made to ...
[17]
None
### Summary of Chosen-Prefix Collision Attack on MD5 (Stevens et al., 2009)
[18]
[PDF] Practical Attacks on Digital Signatures Using MD5 Message Digest
Dec 2, 2004 · Finally, we point out the consequences resulting from such attack for signature schemes based on MD5 message digest on an example using GPG.Missing: impact | Show results with:impact
[19]
[PDF] On the Security of RSA-PSS in the Wild - Cryptology ePrint Archive
Oct 31, 2019 · We are able to show that this joint usage is indeed secure, and achieves a security level that closely matches that of PKCS#1 v1.5 signatures ...
[20]
[PDF] Key-collisions in (EC)DSA: Attacking Non-repudiation*
Both of these collision-based attacks significantly weaken the non-repudiation property of signature schemes. Moreover, they weaken the non-repudiation of ...Missing: impact | Show results with:impact
[21]
Flame malware collision attack explained - Microsoft
Jun 6, 2012 · Given the risk for copycat attacks on systems pre-dating Windows Vista, without the complexity of a collision attack, we took action to release ...
[22]
Why We Need to Move to SHA-2 | PKI Consortium
Jan 30, 2014 · Collision attacks can be mitigated by putting entropy into the certificate, which makes it difficult for the attacker to guess the exact ...
[23]
[PDF] Strengthening Digital Signatures via Randomized Hashing - CSRC
May 12, 2005 · (1) Modify applications that rely on collision resistance such that the particular use of CRHF in these applications will be less vulnerable to ...
[24]
https://cjl.dev/md5-collision/
[25]
About that hash flooding vulnerability in Node.js… · V8
Aug 11, 2017 · Node.js suffered from a hash flooding vulnerability. This post provides some background, and explains the solution in V8.
[26]
Carbyne: An Ultra-Lightweight DoS-Resilient Mempool for Bitcoin
Sep 26, 2025 · In this paper, we present Carbyne, a novel mempool optimization scheme, which uses counting bloom filter constructions to adapt to increased ...
[27]
Algorithmic Complexity Attacks and the Linux Networking Code
Collision chaining is used to store different entries which hash to the same bucket. ... Note that there are additional hash tables in the networking code.
[28]
Denial of service via hash collisions - LWN.net
Jan 12, 2012 · What about the naive hash tables used in the linux kernel? Has someone analyzed whether any of them are sensitive to this sort of chosen-key ...Missing: DoS | Show results with:DoS
[29]
[PDF] Hash-flooding DoS reloaded: attacks and defenses
Jun 28, 2025 · “We present a new class of low-bandwidth denial of service attacks ::: if each element hashes to the same bucket, the hash table will also.Missing: seminal | Show results with:seminal
[30]
Technical Advisory – Hash Denial-of-Service Attack in Multiple QUIC ...
Hash DoS attacks are algorithmic attacks on data structures that exploit collisions in weak hash functions, triggering the worst-case performance of hash tables ...
[31]
VU#836068 - MD5 vulnerable to collision attacks
Dec 31, 2008 · Cryptanalytic research published in 1996 described a weakness in the MD5 algorithm that could result in collision attacks, at least in principle ...Missing: history | Show results with:history
[32]
[PDF] Improved Collision Attack on MD5
In 1996, Dobbertin proposed a collision attack on MD5 [1]. However, since this attack used modified initial value, this attack was not real attack for MD5.
[33]
[PDF] Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD
Moreover, our attack works for any given initial value. The following are two pairs of 1024-bit messages producing collisions, the two examples ...
[34]
NIST Brief Comments on Recent Cryptanalytic Attacks | CSRC
NIST Brief Comments on Recent Cryptanalytic Attacks on Secure Hashing Functions and the Continued Security Provided by SHA-1. August 25, 2004.
[35]
Improved Collision Attack on Hash Function MD5 - ResearchGate
Aug 7, 2025 · In this paper, we present a fast attack algorithm to find two-block collision of hash function MD5. The algorithm is based on the two-block ...
[36]
[SECURITY] [DSA 1571-1] New openssl packages fix predictable ...
May 13, 2008 · ... Debian's openssl package is predictable. This is caused by an incorrect Debian-specific change to the openssl package (CVE-2008-0166). ... MD5 ...
[37]
NIST Retires SHA-1 Cryptographic Algorithm
Dec 15, 2022 · As today's increasingly powerful computers are able to attack the algorithm, NIST is announcing that SHA-1 should be phased out by Dec. 31, 2030 ...
[38]
Hash Functions | CSRC - NIST Computer Security Resource Center
NIST recommends that federal agencies transition away from SHA-1 for all applications as soon as possible. Federal agencies should use SHA-2 or SHA-3 as an ...
[39]
[PDF] fips pub 202 - federal information processing standards publication
The SHA-3 standard specifies the SHA-3 family of functions, based on KECCAK, including four hash functions and two extendable-output functions.
[40]
[PDF] Third-Round Report of the SHA-3 Cryptographic Hash Algorithm ...
NIST made the selection announcement on October 2, 2012 [29], and officially ended the SHA-3 competition. Table 2 shows the competition timeline, including ...
[41]
[PDF] Random Oracles are Practical: A Paradigm for Designing Efficient ...
They use the random oracle model to define and prove exact, non-asymptotic security. In another paper [29] the same authors use hash functions viewed as random ...
[42]
[PDF] An Efficient Quantum Collision Search Algorithm and Implications on ...
Using Grover's algorithm as a subroutine, they showed that the collision problem for a 2-to-1 function f could be solved using eO(2n/3) queries to Of and eO(2n ...
[43]
Post-Quantum Cryptography | CSRC
NIST initiated a process to solicit, evaluate, and standardize one or more quantum-resistant public-key cryptographic algorithms. Full details can be found in ...NIST FAQ · Workshops and Timeline · Post-Quantum · Presentations