( 11th August 2019 )
An extension of the collision attack is the chosen-prefix collision attack, which is specific to Merkle Damgard hash functions. In this case, the attacker can choose two arbitrarily different documents, and then append different calculated values that result in the whole documents having an equal hash value. This attack is much more powerful than a classical collision attack.
Mathematically stated, given two different prefixes p1, p2, the attack finds two appendages m1 and m2 such that hash (p1 ∥ m1) = hash (p2 ∥ m2) (where ∥ is the concatenation operation).
In 2007, a chosen-prefix collision attack was found against MD5, requiring roughly 250 evaluations of the MD5 function. The paper also demonstrates two X.509 certificates for different domain names, with colliding hash values. This means that a certificate authority could be asked to sign a certificate for one domain, and then that certificate could be used to impersonate another domain.
A real-world collision attack
A 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 impersonate a 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 a man-in-the-middle, thereby subverting the certificate validation built in every web browser to protect electronic commerce. The rogue certificate may 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, certificate authorities were still willing to sign MD5-verified certificates in December 2008, and at least one Microsoft code-signing certificate was still using MD5 in May 2012.
The Flame malware successfully used a new variation of a chosen-prefix collision attack to spoof code signing of its components by a Microsoft root certificate that still used the compromised MD5 algorithm.
Attack scenarios
Many applications of cryptographic hash functions do not rely on collision resistance; thus collision attacks do not affect their security. For example, HMACs are not vulnerable. For the attack to be useful, the attacker must be in control of the input to the hash function.
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.
The usual attack scenario goes like this:
Mallory creates two different documents A and B that have an identical hash value, i.e., a collision. Mallory seeks to deceive Bob into accepting document B, ostensibly from Alice. Mallory sends document A to Alice, who agrees to what the document says, signs its hash, and sends the signature to Mallory.
Mallory attaches the signature from document A to document B.
Mallory then sends the signature and document B to Bob, claiming that Alice signed B. Because the digital signature matches document B's hash, Bob's software is unable to detect the substitution.
In 2008, researchers used a chosen-prefix collision attack against MD5 using this scenario, to produce a rogue certificate authority certificate. They created two versions of a TLS public key certificate, one of which appeared legitimate and was submitted for signing by the RapidSSL certificate authority. The second version, which had the same MD5 hash, contained flags which signal web browsers to accept it as a legitimate authority for issuing arbitrary other certificates.
Comments