Preimage attack: Difference between revisions
fmt |
Quuxplusone (talk | contribs) m reword for clarity; remove reference that doesn't seem to have anything to do with this particular claim |
||
| Line 13: | Line 13: | ||
Some significant preimaging attacks have already been discovered, but they are not yet practical. If a practical preimaging 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. |
Some significant preimaging attacks have already been discovered, but they are not yet practical. If a practical preimaging 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 attacks. A [[collision attack]] is easier to mount than a preimage attack |
All currently known practical or almost-practical attacks on [[MD5]] and [[SHA-1]] are collision attacks. A [[collision attack]] is easier to mount than a preimage attack; in fact, any hash function which is resistant to first or second preimage attacks is by definition collision-resistant. |
||
== See also == |
== See also == |
||
Revision as of 00:53, 2 September 2010
 |
In cryptography, a preimage attack on a cryptographic hash is an attempt to find a message that has a specific hash value.
There are two types of preimage attacks:
- First preimage attack: given a hash h, find a message m such that hash(m) = h.
- Second preimage attack: given a fixed message m1, find a different message m2 such that hash(m2) = hash(m1).
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 ideal hash function, finding a first preimage or a second preimage has 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 first and second preimage resistant.
Some significant preimaging attacks have already been discovered, but they are not yet practical. If a practical preimaging 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 attacks. A collision attack is easier to mount than a preimage attack; in fact, any hash function which is resistant to first or second preimage attacks is by definition collision-resistant.
See also
References
- IETF RFC 4270: Attacks on Cryptographic Hashes in Internet Protocols
| |||||||||||||||||||||||||||||
 | This cryptography-related article is a stub. You can help Wikipedia by expanding it. |