Collision attack
From Wikipedia, the free encyclopedia
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. In contrary to a preimage attack, neither the hash value nor one of the inputs is specified.
Contents |
[edit] Attacks
Much like symmetric-key ciphers are vulnerable to brute force attacks, every cryptographic hash function is inherently vulnerable to collisions using a birthday attack. Due to the birthday problem, these attacks are much faster than a brute force would be. A hash of n bits can be broken in 2n / 2 time (evaluations of the hash function).
More efficient attacks are possible by employing cryptanalysis to specific hash functions. When there exist collision attacks that are faster than a birthday attack, a hash function is often denounced as "broken". The NIST hash function competition was largely induced by published collision attacks against two very commonly used hash functions, MD5[1] and SHA-1.
[edit] Attack scenarios
Many applications of crytographic hash functions do not rely on collision resistance, thus collision attacks do not affect their security. For example, password hashing and HMACs are not vulnerable.[2] For the attack to be useful, the attacker must be in control of the input to the hash function.
[edit] Digital signatures
Because digital signature algorithms cannot sign a large amount of data efficiently, most implementations use a hash function to reduce ("compress") the amount of data that needs to be signed down to a constant size. Digital signature schemes are often vulnerable to hash collisions, unless using techniques like randomized hashing.[3]
The usual attack scenario goes like this:
- Mallory creates two different documents A and B, that have an identical hash value (collision).
- Mallory then sends document A to Alice, who agrees to what the document says, signs it and sends it back to Mallory.
- He copies the signature sent by Alice from document A to document B.
- Then he sends document B to Bob, claiming that Alice signed the different document. Because the digital signature matches the document hash, Bob's software is unable to detect the modification.
Perhaps the best known real-world collision attack was in December 2008 when a group of security researchers published a forged X.509 signing certificate that could be used to launch a rogue certificate authority, taking advantage of a prefix collision attack against the MD5 hash function. This meant that an attacker could impersonate any SSL-secured website as man-in-the-middle, subverting certificate validation in web browsers. What's worse, the rogue certificate would not be revokable by real authorities, and could also have an arbitrary forged expiry time. Even though MD5 was known to be very weak in 2004,[1] certificate authorities were still willing to sign MD5-verified certificates in December 2008.[4]
[edit] See also
[edit] References
- ^ a b Xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu: Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD, Cryptology ePrint Archive Report 2004/199, 16 Aug 2004, revised 17 Aug 2004. Retrieved July 27, 2008.
- ^ "Hash Collision Q&A". Cryptography Research Inc. 2005-02-15. http://www.cryptography.com/cnews/hash.html. "Because of the way hash functions are used in the HMAC construction, the techniques used in these recent attacks do not apply"
- ^ Shai Halevi and Hugo Krawczyk, Randomized Hashing and Digital Signatures
- ^ Alexander Sotirov et al (2008-12-30). "Creating a rogue CA certificate". http://www.phreedom.org/research/rogue-ca/.
[edit] External links
 |
This cryptography-related article is a stub. You can help Wikipedia by expanding it. |
|
|||||||||||||||||||||||||||||||||||
