Collision attack

There are roughly two types of collision attacks:

Classical collision attack

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 2^{n / 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 and SHA-1. The collision attacks against MD5 have improved so much that it takes just a few seconds on a regular computer.

Hash collisions created this way are usually constant length and largely unstructured, so cannot directly be applied to attack widespread document formats or protocols. However, workarounds are possible by abusing dynamic constructs present in many formats. Such a malicious document would contain two different messages in the same document, but conditionally displays one or the other, depending on which of two collided hash values is present:

* Computer programs have conditional constructs (if-then-else) that allow testing whether a location in the file has one value or another. Some document formats like PostScript, or macros in Microsoft Word, also have conditional constructs. File formats that can include images, including TIFF and PDF, are vulnerable to collision attacks by using colliding hash values as indexed colors, such that text of one message is displayed with a bright color that blends into the background, and text of the other message is displayed with a dark color.

Perhaps the best known real-world collision attack was published 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,

Attack scenarios

Digital signatures

Note that all public key certificates, like SSL certificates, also rely on the security of digital signatures and are compromised by hash collisions.

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.

See also

References

External links

Category:Cryptographic attacks