Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Preimage attack
Summary
In cryptography, a preimage attack on cryptographic hash functions tries to find a message that has a specific hash value. A cryptographic hash function should resist attacks on its (set of possible inputs).
In the context of attack, there are two types of preimage resistance:
preimage resistance: for essentially all pre-specified outputs, it is computationally infeasible to find any input that hashes to that output; i.e., given , it is difficult to find an such that () = .
second-preimage resistance: for a specified input, it is computationally infeasible to find another input which produces the same output; i.e., given , it is difficult to find a second input ′ ≠ such that () = (′).
These can be compared with a collision resistance, in which it is computationally infeasible to find any two distinct inputs , ′ that hash to the same output; i.e., such that () = (′).
Collision resistance implies second-preimage resistance, but does not guarantee preimage resistance. Conversely, a second-preimage attack implies a collision attack (trivially, since, in addition to ′, is already known right from the start).
By definition, an ideal hash function is such that the fastest way to compute a first or second preimage is through a brute-force attack. For an -bit hash, this attack has a time complexity 2^, which is considered too high for a typical output size of = 128 bits. If such complexity is the best that can be achieved by an adversary, then the hash function is considered preimage-resistant. However, there is a general result that quantum computers perform a structured preimage attack in , which also implies second preimage and thus a collision attack.
Faster preimage attacks can be found by cryptanalysing certain hash functions, and are specific to that function. Some significant preimage attacks have already been discovered, but they are not yet practical. If a practical preimage attack is discovered, it would drastically affect many Internet protocols. In this case, "practical" means that it could be executed by an attacker with a reasonable amount of resources.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Ontological neighbourhood
Related courses (1)
COM-401: Cryptography and security
This course introduces the basics of cryptography. We review several types of cryptographic primitives, when it is safe to use them and how to select the appropriate security parameters. We detail how
Related lectures (32)
Applied Cryptography: Hash Functions
Explores hash functions and their crucial role in cryptography, digital signatures, and blockchain technology.
ROS Attack: Security Analysis
Explores the (in)security of ROS, k-sum problems, blind signatures, and Schnorr's Blind Signature.
Inverse Limits and Topologies
Explores inverse limits, profinite completions, and Hausdorff topologies in group theory and topology.
Related publications (54)
Related people (18)
Related units (1)
Related concepts (16)
Cryptography
Cryptography, or cryptology (from κρυπτός "hidden, secret"; and γράφειν graphein, "to write", or -λογία -logia, "study", respectively), is the practice and study of techniques for secure communication in the presence of adversarial behavior. More generally, cryptography is about constructing and analyzing protocols that prevent third parties or the public from reading private messages. Modern cryptography exists at the intersection of the disciplines of mathematics, computer science, information security, electrical engineering, digital signal processing, physics, and others.
MD4
The MD4 Message-Digest Algorithm is a cryptographic hash function developed by Ronald Rivest in 1990. The digest length is 128 bits. The algorithm has influenced later designs, such as the MD5, SHA-1 and RIPEMD algorithms. The initialism "MD" stands for "Message Digest". The security of MD4 has been severely compromised. The first full collision attack against MD4 was published in 1995, and several newer attacks have been published since then. As of 2007, an attack can generate collisions in less than 2 MD4 hash operations.
SHA-2
SHA-2 (Secure Hash Algorithm 2) is a set of cryptographic hash functions designed by the United States National Security Agency (NSA) and first published in 2001. They are built using the Merkle–Damgård construction, from a one-way compression function itself built using the Davies–Meyer structure from a specialized block cipher. SHA-2 includes significant changes from its predecessor, SHA-1. The SHA-2 family consists of six hash functions with digests (hash values) that are 224, 256, 384 or 512 bits: SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224, SHA-512/256.