Preimage attack
Encyclopedia
In cryptography
, the preimage attack is a classification of attacks on hash functions
for finding a message
that has a specific hash value.
There are two types of preimage attacks:
These can be compared with a collision attack
, which involves finding two arbitrarily different messages m1 and m2 such that hash(m2) = hash(m1).
. For an n-bit hash, this attack has a time complexity
2n, which is considered too high for a typical output size of n=160 bits. If such complexity is the best that can be achieved by an adversary, then the hash function is considered preimage resistant.
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 in a meaningful amount of time for a meaningful amount of money. A preimaging attack that costs trillions of dollars and takes decades to preimage one desired hash value or one message is not practical; one that costs a few thousand dollars and takes a few weeks might be very practical.
All currently known practical or almost-practical attacks on MD5
and SHA-1 are collision attack
s. In general, a collision attack is easier to mount than a preimage attack.
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
, the preimage attack is a classification of attacks on hash functions
Cryptographic hash function
A cryptographic hash function is a deterministic procedure that takes an arbitrary block of data and returns a fixed-size bit string, the hash value, such that an accidental or intentional change to the data will change the hash value...
for finding a message
Message
A message in its most general meaning is an object of communication. It is a vessel which provides information. Yet, it can also be this information. Therefore, its meaning is dependent upon the context in which it is used; the term may apply to both the information and its form...
that has a specific hash value.
There are two types of preimage attacks:
- (First-) preimage attack: given a hash h, find a message m (a preimage) such that hash(m) = h.
- Second-preimage attack: given a fixed message m1, find a different message m2 (a second preimage) such that hash(m2) = hash(m1).
These can be compared with a collision attack
Collision attack
In cryptography, a collision attack on a cryptographic hash tries to find two arbitrary inputs that will produce the same hash value, i.e. a hash collision...
, which involves finding two arbitrarily different messages m1 and m2 such that hash(m2) = hash(m1).
Applied preimage attacks
For an ideal hash function, the fastest way to compute a first or second preimage is through a brute force attackBrute force attack
In cryptography, a brute-force attack, or exhaustive key search, is a strategy that can, in theory, be used against any encrypted data. Such an attack might be utilized when it is not possible to take advantage of other weaknesses in an encryption system that would make the task easier...
. For an n-bit hash, this attack has a time complexity
Time complexity
In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the size of the input to the problem. The time complexity of an algorithm is commonly expressed using big O notation, which suppresses multiplicative constants and...
2n, which is considered too high for a typical output size of n=160 bits. If such complexity is the best that can be achieved by an adversary, then the hash function is considered preimage resistant.
Faster preimage attacks can be found by cryptanalysing
Cryptanalysis
Cryptanalysis is the study of methods for obtaining the meaning of encrypted information, without access to the secret information that is normally required to do so. Typically, this involves knowing how the system works and finding a secret key...
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 in a meaningful amount of time for a meaningful amount of money. A preimaging attack that costs trillions of dollars and takes decades to preimage one desired hash value or one message is not practical; one that costs a few thousand dollars and takes a few weeks might be very practical.
All currently known practical or almost-practical attacks on MD5
MD5
The MD5 Message-Digest Algorithm is a widely used cryptographic hash function that produces a 128-bit hash value. Specified in RFC 1321, MD5 has been employed in a wide variety of security applications, and is also commonly used to check data integrity...
and SHA-1 are collision attack
Collision attack
In cryptography, a collision attack on a cryptographic hash tries to find two arbitrary inputs that will produce the same hash value, i.e. a hash collision...
s. In general, a collision attack is easier to mount than a preimage attack.
See also
- Birthday attackBirthday attackA birthday attack is a type of cryptographic attack that exploits the mathematics behind the birthday problem in probability theory. This attack can be used to abuse communication between two or more parties...
- Cryptographic hash functionCryptographic hash functionA cryptographic hash function is a deterministic procedure that takes an arbitrary block of data and returns a fixed-size bit string, the hash value, such that an accidental or intentional change to the data will change the hash value...
- Rainbow tableRainbow tableA rainbow table is a precomputed table for reversing cryptographic hash functions, usually for cracking password hashes. Tables are usually used in recovering the plaintext password, up to a certain length consisting of a limited set of characters. It is a form of time-memory tradeoff, using less...
- Random oracleRandom oracleIn cryptography, a random oracle is an oracle that responds to every query with a random response chosen uniformly from its output domain, except that for any specific query, it responds the same way every time it receives that query...