Fact-checked by Grok 2 weeks ago

Preimage attack

A preimage attack is a cryptographic attack on a hash function that attempts to find an input message producing a specified hash output, violating the function's preimage resistance property.^[1] Preimage resistance requires that, for a randomly chosen hash value, it is computationally infeasible to determine any corresponding input message.^[1] Preimage attacks are categorized into two main types: first-preimage and second-preimage. A first-preimage attack targets a known hash value h by seeking any message m such that H(m) = h, where H is the hash function.^[2] In contrast, a second-preimage attack, given an original message m₁ and its hash H(m₁), aims to identify a distinct message m₂ ≠ m₁ where H(m₂) = H(m₁), undermining the function's ability to uniquely represent inputs.^[2]^[3] These attacks pose significant risks to systems relying on hash functions for security, such as digital signatures, message authentication codes, and blockchain integrity checks, potentially enabling forgery or data tampering if successful.^[2] For standardized hash functions like those in the SHA family, preimage resistance is designed to withstand attacks requiring approximately 2ⁿ operations, where n is the output length in bits, rendering brute-force preimage searches impractical with contemporary computing resources.^[4] Although generic and theoretical preimage attacks have been developed—such as herding-based methods for second-preimages on Merkle-Damgård constructions—no practical full-round preimage attacks exist on secure, widely deployed hash functions like SHA-256 or SHA-3 as of 2025.^[5]^[2] Ongoing research focuses on analyzing vulnerabilities in reduced-round variants and enhancing constructions like the sponge function used in SHA-3 to maintain robust preimage security.^[4]

Fundamentals

Definition

A preimage attack on a cryptographic hash function H: \{0,1\}^* \to \{0,1\}^n involves finding an input m \in \{0,1\}^* such that H(m) = h for a given hash value h \in \{0,1\}^n, thereby demonstrating a violation of the function's preimage resistance.^[6] Preimage resistance is a core one-way property of hash functions, where forward computation of H(m) is efficient, but inverting it to recover a suitable m from h is computationally infeasible for all but a negligible fraction of possible outputs h.^[6] This security notion ensures that adversaries cannot practically reverse the hashing process, protecting applications like digital signatures and password storage.^[7] The concept of preimage resistance originated in the late 1970s alongside early cryptographic hash function designs, with Ralph Merkle introducing one-way hash functions in his 1979 thesis as mappings that are easy to evaluate but hard to invert.^[7] These designs emphasized providing n-bit security, meaning resistance against preimage attacks requiring approximately $2^n operations of effort.^[6] Later constructions, such as the Merkle-Damgård paradigm developed in 1989, built upon this foundation by structuring hash functions to inherit one-way properties from underlying compression functions, further solidifying the requirement for strong preimage resistance in practical implementations. Unlike full inversion attacks, which aim to recover all possible preimages or completely reverse the hash function's mapping, a preimage attack targets only a single valid input m that matches the specified output h, exploiting a targeted weakness in the one-way property without necessitating exhaustive recovery of the entire input space.^[6] Preimage resistance is a fundamental security property of cryptographic hash functions, defined as the computational infeasibility of finding any input message that produces a given hash output when the output is chosen randomly from the function's range.^[1] For an n-bit hash function, achieving this property ideally requires approximately 2^n operations, providing full n-bit security against brute-force preimage searches. Second-preimage resistance complements preimage resistance by ensuring that, given a specific input x, it is computationally infeasible to find a distinct input x' such that the hash of x equals the hash of x'.^[3] Unlike preimage resistance, which targets a fixed output without a known input, second-preimage resistance fixes the input and seeks another that collides on the same output value. Collision resistance is another core property, requiring that it is computationally infeasible to find any two distinct inputs x and x' such that their hashes are identical.^[8] This property implies second-preimage resistance, as finding any collision prevents the possibility of a second preimage for a given input. In terms of security levels, collision resistance typically offers about 2^{n/2} security due to the birthday paradox, which is weaker than the full 2^n required for preimage resistance. These properties are interrelated in the design of hash functions using structures like Merkle-Damgård, where security against collisions, preimages, and second-preimages in the overall hash function is preserved if the underlying compression function satisfies the corresponding properties. Specifically, the Merkle-Damgård construction ensures collision resistance if the compression function is collision-resistant, with analogous preservation for preimage and second-preimage resistance. NIST standardizes these properties as essential for applications such as digital signatures, which rely on collision resistance to prevent forgery, and message authentication codes (MACs), which depend on preimage resistance to ensure integrity.^[1]

Theoretical Aspects

Attack Complexity

The complexity of a generic preimage attack on an n-bit hash function, which does not exploit any structural weaknesses, is dominated by the brute-force approach. In this method, an attacker exhaustively searches through the 2^n possible inputs until finding one whose hash value matches the target output h, requiring an expected number of 2^n hash evaluations, while storage requirements remain negligible at O(1).^[9] Unlike collision attacks, where the birthday paradox reduces the effort to approximately 2^{n/2} evaluations by finding two inputs with the same hash, preimage attacks cannot benefit from this reduction because the target hash value is fixed in advance.^[9] This distinction underscores the stronger security property of preimage resistance compared to collision resistance, as briefly related in the discussion of hash function security properties. Time-memory trade-off techniques, such as Hellman's method, offer a way to potentially reduce the computational effort at the cost of increased storage. Hellman's approach achieves a time complexity of approximately 2^{2n/3} with 2^{2n/3} storage and preprocessing time of 2^n, but this becomes impractical for large n due to the massive memory demands. In the black-box model, where the hash function is treated as a random oracle without internal structure knowledge, generic preimage attacks require at least 2^n operations to succeed with constant probability, establishing the fundamental baseline for security analysis.^[9] Hash function security is thus often measured in bits, where an n-bit output provides n-bit security against preimage attacks, meaning resistance to approximately 2^n operations; for instance, 128-bit security implies infeasibility against 2^{128} effort with current technology.^[9]

Quantum Resistance Considerations

The advent of quantum computing introduces significant considerations for the security of hash functions against preimage attacks, primarily through Grover's algorithm, which provides a quadratic speedup for unstructured search problems. This algorithm reduces the computational complexity of finding a preimage for an n-bit hash function from the classical O(2^n) operations to approximately O(2^{n/2}) quantum operations by leveraging quantum superposition and interference to amplify the probability of measuring the correct input.^[10] As a result, what was previously infeasible brute-force search becomes more tractable on sufficiently powerful quantum hardware, necessitating a reevaluation of hash function output sizes for long-term security.^[11] In practical terms, for widely used hash functions like SHA-256 with n=256 bits, Grover's algorithm lowers the preimage attack complexity to roughly $2^{128} operations, halving the effective security level compared to the classical $2^{256} threshold while still maintaining substantial resistance against current and near-term quantum capabilities.^[12] This reduction implies that 256-bit hashes provide approximately 128 bits of quantum security, a level deemed adequate for many applications but prompting recommendations to double key or hash sizes where higher assurance is required.^[13] These quantum threats have influenced standardization efforts, such as the National Institute of Standards and Technology's (NIST) Post-Quantum Cryptography (PQC) initiative, launched in 2016, which advises using at least 256-bit hash functions like SHA-256 or SHA3-256 to achieve 128-bit quantum security against generic attacks.^[14] NIST's guidelines emphasize that such hashes remain suitable for post-quantum use, provided they are not vulnerable to structured quantum attacks beyond Grover's generic speedup.^[15] However, implementing Grover's algorithm for preimage attacks on hash functions faces substantial limitations, including the need for a quantum oracle that efficiently evaluates the hash function H on superimposed inputs, which remains technologically infeasible with today's noisy intermediate-scale quantum (NISQ) devices due to high qubit counts and error rates.^[10] Furthermore, no quantum algorithms are known to offer speedups greater than quadratic for unstructured preimage searches, preserving the core security model of well-designed hashes against non-generic attacks.^[16] As of 2025, practical quantum preimage attacks remain unrealized, though hybrid classical-quantum threats are projected to emerge in the 2030s according to National Security Agency (NSA) assessments, underscoring the urgency of transitioning to quantum-resistant designs.^[17]

Types of Preimage Attacks

Full Preimage Attacks

A full preimage attack seeks to find an arbitrary input message m such that the hash function H(m) = y for a given target hash value y, without any constraints on the domain or structure of m. This contrasts with second-preimage attacks, which fix one message and seek another with the same hash, and is a core measure of a hash function's one-wayness. For an n-bit hash output, the generic attack complexity is $2^n hash evaluations, making full preimage resistance essential for applications like digital signatures and password storage.^[1] In Merkle-Damgård hash functions, which iterate a compression function f over message blocks chained with an initial value, full preimage attacks typically target inverting the compression function to reconstruct valid inputs block by block. Common cryptanalytic techniques include differential analysis to identify propagatable differences across rounds and meet-in-the-middle approaches that partition the computation to match intermediate states efficiently. For instance, attackers can exploit the message expansion process—where input bits are linearly combined to fill internal state arrays—to generate local collisions in early rounds, then extend these differences to recover a full preimage by solving for the chaining values backward from the target hash. These methods break the compression function's assumed one-way property, enabling forgery of preimages for the overall hash.^[18]^[19] Theoretical attacks on reduced-round variants illustrate the potential vulnerabilities. A meet-in-the-middle preimage attack on SHA-256 reduced to 24 out of 64 rounds achieves a complexity of $2^{240} operations, far below the ideal $2^{256} generic bound for the full function, using partial-matching and splice-and-cut techniques on the compression steps. Similarly, advanced variants extend to 41 rounds of SHA-256 with $2^{253.5} complexity, still approaching but not undercutting the full generic threshold significantly. Such results highlight how structural weaknesses in the compression function can lower attack costs relative to brute force for weakened designs.^[20]^[18] As of November 2025, no practical full preimage attacks have been developed for complete rounds of secure hash functions like SHA-256, with all breakthroughs confined to toy examples, reduced-round models, or deliberately weakened implementations. The best known efforts rely on specialized solvers like SAT or MILP for limited rounds but fail to scale to full versions due to the robust diffusion in later rounds. Attack success is benchmarked against the generic $2^n complexity; reductions below this level signal a meaningful break, though none threaten production use of standardized hashes.^[18]^[21]

Restricted Preimage Attacks

Restricted preimage attacks focus on finding a preimage for a hash value within a deliberately limited subset of the input space, such as human-chosen passwords of restricted length or predictable formats, which reduces the effective search complexity far below the full 2^n operations required for an n-bit hash function's preimage resistance. This approach exploits the low entropy of real-world inputs, like short alphanumeric strings, rather than attempting to invert the hash over its entire domain. For instance, passwords limited to 8 characters from a 62-character set (lowercase, uppercase, and digits) yield an effective space of approximately 2^{48} possibilities, making exhaustive search feasible despite the hash's theoretical strength. Key techniques include dictionary attacks, which test common words and phrases augmented by brute-force variations like capitalization or substitutions, and rainbow tables, which apply time-memory tradeoffs to precompute and store chains of hash iterations for efficient offline cracking of unsalted hashes. Rainbow tables, an optimization of Hellman's 1980 time-memory tradeoff method, reduce storage needs by using varied reduction functions across chains, enabling recovery of preimages for billions of candidates with modest memory. Salts, random values prepended to inputs before hashing, thwart rainbow table reuse by forcing unique computations per user, though early 12-bit salts in Unix systems only expanded the table space by 4,096-fold. In terms of complexity, the cost of a restricted preimage attack approximates 2^k operations for an effective k-bit input space, with success rates hinging on the target's entropy; low-entropy passwords (e.g., dictionary words) succumb rapidly, while random high-entropy ones resist longer. Historically, these attacks gained prominence in the 1990s targeting Unix password systems, which employed DES-based hashing (crypt) introduced in the 1970s, where early tools like Crack (1991) demonstrated dictionary-based breaks on weak inputs stored in accessible files. The approach evolved with GPU acceleration starting around 2007, enabling tools like Hashcat to achieve speeds exceeding 4 billion hashes per second on modern hardware for DES crypt, rendering 8-character passwords with ~2^{48} space crackable in hours to days via brute-force or hybrid methods. To counter such attacks on low-entropy inputs, password hashing uses adaptive functions like bcrypt or Argon2, which intentionally slow down computations.)^[22]

Practical Examples

Attacks on Legacy Hash Functions

The first practical preimage attack on the full 128-bit MD5 hash function was demonstrated in 2009 by Sasaki and Aoki, achieving a complexity of $2^{123.4} through the use of differential paths and biclique techniques.^[23] This attack remains theoretical in practice due to its high computational demands, but it demonstrated MD5's vulnerability to preimage recovery faster than brute force, with implications for forging data in legacy systems reliant on MD5 certificates.^[23] For SHA-1, no practical full preimage or pseudo-preimage attacks exist on the full 80-round function as of 2025. Theoretical attacks target reduced rounds, with the best covering 57 steps at complexities exceeding $2^{150}. The 2017 SHAttered collision attack further eroded confidence in SHA-1 by enabling practical collisions in $2^{63} time, indirectly facilitating preimage-related weaknesses through structural insights, though no full preimage has been realized.^[24] Among other legacy functions, RIPEMD-160 faced a reduced-round preimage attack in 2013 by Landelle and Peyrin, targeting 31 steps out of 80 with a complexity of approximately $2^{80}, exploiting internal state differences in the compression function. DES-based hash functions, such as those in early FIPS standards using DES in modes like CBC-MAC for hashing, were fully broken for preimage resistance in the 1990s; differential cryptanalysis reduced the effective security to below $2^{47} by 1994, rendering them trivially invertible with available computing power. Preimage attacks on legacy hash functions originated with theoretical analyses in the 1980s, focusing on early designs like MD4, but practical breakthroughs surged after 2004, as collision attacks on MD5 and SHA-1 provided differential paths that informed preimage strategies.^[25] As of 2025, NIST has deprecated MD5 since 1999, SHA-1 since 2011 with full phase-out mandated by 2030, and similar legacies like RIPEMD-160 are no longer recommended; no new full preimage attacks on SHA-1 have been reported.^[26] As of 2025, no further improvements in full preimage attacks on SHA-1 or MD5 have been reported, maintaining classical security near $2^{160} operations for SHA-1.^[27]

Applications in Real-World Scenarios

In password storage systems, preimage attacks pose a significant threat when unsalted or weakly hashed passwords are used, enabling offline recovery of original credentials through brute-force or dictionary methods. For instance, the legacy LAN Manager (LM) hash employed in older Windows systems splits passwords into two 7-character halves, DES-encrypts them with fixed keys, and concatenates the results, making it highly susceptible to preimage recovery for weak passwords due to its limited entropy and vulnerability to exhaustive search.^[28] Microsoft documentation emphasizes that LM hashes can be cracked rapidly via brute-force attacks, often within seconds for short passwords, underscoring the need to disable their storage in modern environments.^[29] This vulnerability has historically allowed attackers to recover user credentials from compromised SAM files, compromising entire networks. Preimage resistance is also critical in digital signature schemes, where a break could enable forging a valid signature for an arbitrary message by finding a preimage of the target hash value under the signature. In RSA-MD5 schemes, while no practical full preimage attack on MD5 exists (best theoretical complexity ~~$2^{123}), real-world exploits in 2008-2009 primarily leveraged collisions (~~ $2^{39} operations) to create rogue certificates mimicking legitimate certificate authorities.^[23] These incidents, including the forgery of an Equifax Secure Global eBusiness CA-1 certificate, allowed attackers to impersonate websites and issue fraudulent SSL certificates, highlighting how weakened hash security undermines signature integrity in protocols like HTTPS.^[30] In blockchain protocols and message authentication codes (MACs), failures in preimage resistance can facilitate transaction malleability or message forgery by allowing adversaries to compute inputs yielding specific hash outputs. For Bitcoin, a preimage attack on SHA-256 would enable finding block headers with predetermined hashes, potentially allowing chain extensions that mimic valid transactions and exacerbate malleability issues, such as altering transaction IDs without invalidating signatures, leading to double-spending risks in unmitigated systems. Similarly, in MAC constructions like HMAC-SHA256 used for transaction verification, preimage vulnerability would permit forging authenticated messages, as an attacker could recover the input from a given tag, bypassing integrity checks in distributed ledgers. Although Bitcoin's SegWit upgrade addressed signature malleability, underlying hash preimage weaknesses remain a concern for protocol security. A notable case study is the 2012 LinkedIn data breach, where over 117 million unsalted SHA-1 password hashes were stolen and subjected to preimage attacks using GPU-accelerated cracking tools, resulting in the recovery of millions of plaintext passwords. Attackers exploited SHA-1's relative weakness to collision and preimage resistance, combined with the absence of salting, to perform efficient dictionary and brute-force searches, with tools like those from KoreLogic cracking over 1 million common passwords from the dump.^[31] This incident, analyzed in subsequent cryptographic studies, exposed how legacy unsalted hashing amplifies preimage attack success rates in large-scale breaches.^[32] Such vulnerabilities persist in legacy systems, with the OWASP Top 10 2025 identifying identification and authentication failures—including weak password hashing—as a prevalent risk, affecting a substantial portion of web applications scanned across industries. Surveys from security firms like Veracode indicate that nearly half of applications contain OWASP-related flaws, many tied to outdated hash functions like MD5 or SHA-1 in authentication mechanisms. This ongoing prevalence underscores the real-world impact of preimage attacks in unpatched environments.^[33]

Implications and Mitigations

Security Consequences

A successful preimage attack on a cryptographic hash function fundamentally undermines its one-way property, allowing adversaries to reverse-engineer inputs from given outputs and thereby compromise the integrity of systems relying on hashes for authentication and verification. This enables forgery of digital signatures by crafting arbitrary messages that produce a target hash value, which can impersonate legitimate signers in protocols like public key infrastructures (PKIs). For instance, attackers could generate fraudulent certificates that validate malicious software updates or transactions, evading integrity checks in supply chain security. Such vulnerabilities have been analyzed in the context of hash-based signatures, where preimage weakness directly facilitates unauthorized alterations without detection.^[34]^[35] In password-based systems, preimage attacks pose severe confidentiality risks by enabling the recovery of plaintext credentials from stored hashes, leading to widespread account compromises. Without robust preimage resistance, attackers can systematically crack hashes using techniques like rainbow tables, exposing user data across interconnected services and amplifying the scale of breaches. The 2012 LinkedIn incident exemplifies this, where 6.5 million accounts were affected by the leak of unsalted SHA-1 password hashes, which were cracked en masse, resulting in the exposure of credentials and heightened risks of identity theft and phishing due to password reuse.^[36]^[37] Preimage vulnerabilities can precipitate protocol failures in security mechanisms like HMAC, where hash functions underpin message authentication, potentially allowing tag forgery and integrity violations that cascade into denial-of-service (DoS) or replay attacks. In TLS/SSL handshakes, weak preimage resistance in underlying hashes could compromise digital envelopes by enabling reconstruction of session keys or payloads from authenticated digests, disrupting secure communications and enabling man-in-the-middle interceptions. Although HMAC constructions mitigate some risks through keying, a full preimage break on the inner hash would still erode the overall assurance of protocol integrity.^[38]^[39] The economic ramifications of preimage attacks extend beyond immediate breaches, with costs including remediation, legal settlements, and operational disruptions. In sectors like finance and IoT, where hash functions secure firmware and transactions, such attacks persist as threats, incurring ongoing expenses for vulnerability assessments and upgrades; for example, the LinkedIn breach contributed to industry-wide improvements in password hashing practices. Over the long term, these failures erode trust in established standards, necessitating costly migrations—such as the 2020 browser deprecation of SHA-1 certificates, which forced widespread certificate revocations and protocol updates to restore confidence in web security ecosystems.^[40]^[41]

Defensive Strategies

To mitigate preimage attacks, cryptographic systems should prioritize the adoption of secure hash functions that provide full preimage resistance proportional to their output size, such as SHA-256 from the SHA-2 family or SHA-3 based on the Keccak sponge construction standardized in 2012.^[42]^[43] These functions are designed to require approximately $2^n operations to find a preimage for an n-bit output, ensuring computational infeasibility for foreseeable classical adversaries.^[42] NIST guidelines recommend transitioning away from legacy hash functions like MD5 and SHA-1, which have demonstrated vulnerabilities to preimage-related attacks, with deprecation timelines extending through 2030 for non-security-critical uses.^[42] In password storage and key derivation scenarios, where preimage attacks often target low-entropy inputs, salting combined with key derivation functions (KDFs) significantly increases resistance by inflating the computational cost beyond brute-force limits. PBKDF2, defined in RFC 2898, applies a configurable number of iterations (typically thousands) using a pseudorandom function like HMAC to derive keys, effectively raising the preimage search space to $2^{100+} equivalent operations depending on iteration count and hardware constraints.^[44] For enhanced memory-hard properties that deter parallelized attacks, Argon2—the winner of the 2015 Password Hashing Competition—incorporates tunable memory usage alongside iterations, making GPU-accelerated preimage searches prohibitively expensive.^[45]^[46] Both mechanisms rely on unique, randomly generated salts per input to prevent rainbow table precomputations and ensure domain-specific security.^[44] Domain separation techniques further bolster defenses by preventing attackers from exploiting structural similarities across different message types or contexts, a common vector in preimage attacks. HMAC, specified in RFC 2104, achieves this through keyed hashing, where a secret key is integrated into the hash computation via nested applications of the underlying hash function, isolating computations and resisting extension or multi-target preimage recovery.^[47] Randomized padding schemes, such as those in probabilistic constructions, introduce nonce-based variability to disrupt deterministic patterns that could aid preimage searches, ensuring that even identical inputs yield distinct outputs under repeated evaluations.^[47] Keyed message authentication codes (MACs) provide an additional layer of protection in protocols requiring integrity verification, as they transform plain hash functions into authenticated primitives resistant to preimage forgery. Poly1305, introduced by Bernstein in 2005, uses a one-time key to compute a polynomial evaluation over the message in a finite field, offering provable security against preimage attacks when paired with a secure cipher like AES for key generation, with performance advantages in software implementations.^[48] This approach is particularly effective in authenticated encryption modes, where the MAC prevents tampering that could expose hash preimages.^[48]^[49] Ongoing monitoring through regular cryptanalysis reviews is essential to detect emerging weaknesses in deployed hash functions, involving periodic independent audits and updates aligned with evolving threats. Best practices include adhering to NIST's continuous cryptography evaluation frameworks, which emphasize vulnerability assessments and timely migrations. For quantum threats, where Grover's algorithm could reduce classical preimage resistance to \sqrt{2^n}, systems should migrate to hash outputs of at least 256 bits (e.g., SHA-256 or SHA3-256) by 2030 to maintain post-quantum security levels equivalent to 128-bit classical strength.^[50] NIST's transition roadmap mandates such upgrades for federal systems, with broader industry adoption recommended to avoid disruptions from quantum-enabled attacks.^[50]

References

[1]
Preimage resistance - Glossary | CSRC
Preimage resistance means it is computationally infeasible to find a preimage of a message digest given a randomly chosen message digest.
[2]
Attacks on Cryptographic Hashes in Internet Protocols
Nov 6, 2012 · The two preimage attacks are very similar. In a first-preimage attack, you know a hash value but not the message that created it, and you ...
[3]
Second preimage resistance - Glossary | CSRC
An expected property of a cryptographic hash function whereby it is computationally infeasible to find a second preimage of a known message digest.
[4]
Hash Functions | CSRC - NIST Computer Security Resource Center
Jan 4, 2017 · The preimage resistance strength in bits is equal to the output size of the hash function. The second preimage resistance strength in bits is ...NIST Policy · News & Updates · Events · SHA-3 Standardization
[5]
New Second-Preimage Attacks on Hash Functions | CSRC
Jun 23, 2015 · We present several new generic second-preimage attacks on hash functions. Our first attack is based on the herding attack and applies to various Merkle–Damgård ...
[6]
[PDF] Design Principles for Hash Functions Revisited
Oct 15, 2005 · Informal definitions (2) preimage resistant ⇒≥ 2nd preimage resistant. • take a preimage resistant hash function; add an input bit b and. ...
[7]
[PDF] Cryptographic Hash-Function Basics: Definitions, Implications, and ...
Abstract. We consider basic notions of security for cryptographic hash functions: collision resistance, preimage resistance, and second-preimage resistance.
[8]
[PDF] Secrecy, Authentication, And Public Key Systems - Ralph C. Merkle
Jun 4, 1979 · Intuitively, a one way hash function F is one which is easy to compute but difficult to invert and can m?p arbitrarily large data fields onto ...
[9]
[PDF] Recommendation for Applications Using Approved Hash Algorithms
This Recommendation provides security guidelines for supporting the required or desired security strengths of several cryptographic applications that employ ...
[10]
[PDF] Hash functions: Theory, attacks, and applications - Microsoft
Nov 14, 2005 · In the black-box model the problem of finding a second preimage is just as hard as inverting the hash function. Finding collisions is a ...
[11]
[PDF] Applying Grover's Algorithm to Hash Functions - arXiv
Feb 22, 2022 · The challenge in applying Grover's Algorithm to a hash function lies in translating the classical algorithm into a quantum one. Referring again ...
[12]
[PDF] On the practical cost of Grover for AES key recovery
Mar 22, 2024 · In most cases, the best-known quantum key recovery attack uses. Grover's algorithm [14] which provides a generic square-root speed-up over ...
[13]
[PDF] Low-communication parallel quantum multi-target preimage search
Aug 18, 2017 · To save time for larger values of t we combine Grover's algorithm with the parallel rho method offering a speed up on the quantum attacks. This ...<|separator|>
[14]
Grover's Algorithm and Its Impact on Cybersecurity - PostQuantum.com
A 256-bit symmetric cipher thus drops to an effective 128-bit security against quantum attacks (i.e. the attack needs 2^128 operations instead of 2^256 – the ...
[15]
Security (Evaluation Criteria) - Post-Quantum Cryptography
Jan 3, 2017 · ... 256-bit hash function (e.g. SHA256/ SHA3-256); Any attack that breaks the relevant security definition must require computational resources ...
[16]
Post-Quantum Cryptography | CSRC
Provides classical security strength of 128, 192, and 256 bits, respectively, AND. Is not subject to quantum attacks, other than classical attacks sped up by ...
[17]
Cryptographic hash functions | IBM Quantum Learning
Pre-image resistance means that given a digest, it should be infeasible to find the input. This is related to the one-way property of CHFs. A good CHF is ...
[18]
[PDF] Announcing the Commercial National Security Algorithm Suite 2.0
May 30, 2025 · These algorithms (also referred to as post-quantum algorithms) are analyzed as being secure against both classical and quantum computers. They ...
[19]
What are preimage resistance and collision resistance, and how can ...
Nov 12, 2011 · A preimage attack gives the ability to create an input that produces a specified result. A feasible preimage attack basically means that (as a ...Pre-image attack on non-cryptographic hash functionsWhat are the “costs” to find a pre-image, weak collision, or strong ...More results from crypto.stackexchange.com
[20]
Quantum algorithms for hash preimage attacks - Wiley Online Library
Apr 7, 2020 · ... preimage computable faster than of the brute-force attack, 2128 hash computation. The computation complexity of MD4 and MD5 is 2107 and 2121.<|control11|><|separator|>
[21]
[PDF] Preimage Attacks on 41-Step SHA-256 and 46-Step SHA-512
This changes the required memory of the pseudo-preimage attack to 232 ·10 words, and the attack becomes faster than the brute force attack by a factor of 232.
[22]
[PDF] Higher-Order Differential Meet-in-The-Middle Preimage Attacks on ...
At CRYPTO 2012, Knellwolf and Khovratovich presented a differential formulation of advanced meet-in-the-middle techniques for preimage attacks on hash functions ...<|separator|>
[23]
Preimage Attacks on Reduced Tiger and SHA-2 - SpringerLink
We present a one-block preimage attack on SHA-256 and SHA-512 reduced to 24 (out of 64 and 80) steps with a complexity of 2240 and 2480, respectively. To the ...
[24]
secp8x32/preimage-attacks: SAT-based, MILP, and belief ... - GitHub
This repository contains Python and C++ code which attempts to reverse one-way cryptographic hash functions, with specific focus on SHA-256.
[25]
Of History & Hashes: A Brief History of Password… - TrustedSec
May 30, 2015 · The history of using crypt for Unix passwords is a bit confusing. ... Unix DES password format. This idea to use the password as the key ...
[26]
Hashcat v6.1.1 benchmark on the Nvidia RTX 3090 - GitHub Gist
Speed.#1.........: 4170.0 MH/s (82.24ms) @ Accel:4 Loops:1024 Thr:1024 Vec:1. Hashmode: 1500 - descrypt, DES (Unix), Traditional DES. Speed.#1 ...
[27]
Finding Preimages in Full MD5 Faster Than Exhaustive Search
In this paper, we present the first cryptographic preimage attack on the full MD5 hash function. This attack, with a complexity of 2 116.9 , generates a pseudo ...
[28]
SHA-1 gets SHAttered — Blog - Evervault
Mar 23, 2023 · The generic preimage attack requires about 2n steps. For example ... For a complete description of collision attacks, we recommend Marc ...
[29]
SHAttered
We have broken SHA-1 in practice. This industry cryptographic hash function standard is used for digital signatures and file integrity verification.
[30]
Lessons From The History Of Attacks On Secure Hash Functions
Almost all older secure hash functions have fallen to collision attacks. Almost none have ever fallen to pre-image attacks.
[31]
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 ...
[32]
Prevent Windows from storing a LAN Manager (LM) hash of the ...
Jan 15, 2025 · The LM hash is relatively weak compared to the NT hash, and it's prone to fast brute force attack. So you may want to prevent Windows from ...
[33]
Protecting Privileged Domain Accounts: LM Hashes: The Good, the ...
Feb 29, 2012 · ... attacks are so effective against LM hashes. The most effective pre-computed attack against LM hashes that I have seen was brought to my ...
[34]
Preimage Attacks on One-Block MD4, 63-Step MD5 and More
Aug 7, 2025 · This paper shows preimage attacks on one-block MD4 and MD5 reduced to 63 (out of 64) steps. Our attacks are based on the meet-in-the-middle ...
[35]
MD5 considered harmful today - Marc Stevens
Dec 30, 2008 · Our attack takes advantage of a weakness in the MD5 cryptographic hash function that allows the construction of different messages with the same ...
[36]
LinkedIn Password Leak: Salt Their Hide - ACM Queue
Jun 7, 2012 · 6.5 million unsalted SHA1 hashed LinkedIn passwords have ... attack that weakens your password scrambler, you can switch to a stronger one.
[37]
[PDF] The Cryptographic Implications of the LinkedIn Data Breach - arXiv
Mar 20, 2017 · Security firm KoreLogic's dump of the most common passwords exposed in the LinkedIn attack revealed that over 1 million users used the phrase.
[38]
[PDF] 2025 State of Software Security - Veracode
Now the bad news... the percentage of apps with high severity flaws has increased by 181%... ...and 70% of it comes from third party code and the software supply ...Missing: password hashes
[39]
[PDF] Backdoored Hash Functions: Immunizing HMAC and HKDF
Aug 20, 2018 · Preimage resistance, also known as one-wayness, concerns the infeasibility of finding a message that hashes to a given random digest of the hash ...Missing: consequences | Show results with:consequences
[40]
Adobe Data Breach - Have I Been Pwned
In October 2013, 153 million Adobe accounts were breached with each containing an internal ID, username, email, encrypted password and a password hint in plain ...
[41]
Analysing the Adobe hack and poor password security - Scott Helme
Nov 16, 2013 · The data that was leaked in the Adobe hack is now widely available as a file called users.tar.gz across the Internet.
[42]
[PDF] The Sum Can Be Weaker Than Each Part - Cryptology ePrint Archive
Besides, we also provide concrete preimage attacks on the XOR combiner. (and the concatenation combiner) when one or both of the compression functions are weak; ...
[43]
RFC 6066 - Transport Layer Security (TLS) Extensions
This document provides specifications for existing TLS extensions. It is a companion document for RFC 5246, "The Transport Layer Security (TLS) Protocol ...
[44]
Adobe Fined $1M in Multistate Suit Over 2013 Breach; No Jail for ...
Nov 17, 2016 · Adobe will pay just $1 million to settle a lawsuit filed by 15 state attorneys general over its huge 2013 data breach that exposed payment ...
[45]
Intent to Deprecate: SHA-1 certificates - Google Groups
Using SHA-1 in 2020 is unacceptable. Using SHA-1 in 2015 is not desirable. By degrading the UI, we wish to provide negative reinforcement that SHA-1 is no ...
[46]
[PDF] SHA-1 is a Shambles∗ - Cryptology ePrint Archive
1.2 SHA-1 Usage and Impact Our work shows that SHA-1 is now fully and practically broken for use in digital signatures. GPU technology improvements and general ...
[47]
Hash Functions | CSRC - NIST Computer Security Resource Center
After 12/31/2030, any FIPS 140 validated cryptographic module that has SHA-1 as an approved algorithm will be moved to the historical list. NIST recommends that ...
[48]
[PDF] fips pub 202 - federal information processing standards publication
This Standard specifies the Secure Hash Algorithm-3 (SHA-3) family of functions on binary data. Each of the SHA-3 functions is based on an instance of the ...
[49]
RFC 2898: Password-Based Cryptography Specification, Version 2.0
PBKDF2 is recommended for new applications; PBKDF1 is included only for compatibility with existing applications, and is not recommended for new applications. A ...
[50]
[PDF] Argon2: the memory-hard function for password hashing and other ...
Dec 26, 2015 · The Password Hashing Competition, which started in 2014, highlighted the following problems: • Should the memory addressing (indexing ...
[51]
[PDF] Open Sesame - Cryptology ePrint Archive
Such attackers can generate password candidates on the basis of harvested personal information [76] or use smart, adaptive password cracking strategies or tech-.
[52]
RFC 2104 - HMAC: Keyed-Hashing for Message Authentication
This document describes HMAC, a mechanism for message authentication using cryptographic hash functions.Missing: domain separation
[53]
[PDF] The Poly1305-AES message-authentication code
Mar 29, 2005 · Abstract. Poly1305-AES is a state-of-the-art message-authentication code suitable for a wide variety of applications. Poly1305-AES computes.
[54]
RFC 8439 - ChaCha20 and Poly1305 for IETF Protocols
This document defines the ChaCha20 stream cipher as well as the use of the Poly1305 authenticator, both as stand-alone algorithms and as a combined mode.
[55]
[PDF] NIST IR 8547 initial public draft, Transition to Post-Quantum ...
Nov 12, 2024 · This report describes NIST's approach to transitioning from quantum-vulnerable to post-quantum cryptography, identifying standards for IT ...