9
$\begingroup$

I understand the theoretical problem with hash collision but when it comes to practice, I get very confused.

Suppose a attacker would like to forge a certificate (or any kind of structured piece of file) using hash collisions, I wonder how it is possible to find a collision (already unlikely) and moreover, this collision is "found" from relevant structured input bytes (dates, common name, dns attacker).

It sounds very strange for me, I can't understand how one can found a hash collision which helps as an attack, I can only think about a random raw bytes which could generate a same hash, but it would not be parsed (ex: x509 certificate hash collision find by an attacker, but the x509 malicious content is random bytes not understandable by browser).

$\endgroup$
  • $\begingroup$ Although X.509 certs have a good deal of structure, they do contain at least optionally quite a lot of data that can be chosen nearly arbitrarily by the cert requester -- who in this case is the attacker. The arguably worst (known!) exploit to date by Stevens et al obtaining a "rogue" (sub)CA cert is explained on win.tue.nl/hashclash/rogue-ca to use a large Netscape comment that browsers apparently ignore. $\endgroup$ – dave_thompson_085 Dec 5 '14 at 3:24
  • $\begingroup$ @kenorb I hope you noticed this accepted Q&A dates back to 2014. If, the newer would have been a duplicate of this one. Besides that, comparing boths, I do see some differences – which is why I voted this to leave open. $\endgroup$ – e-sushi Feb 27 '17 at 14:31
13
$\begingroup$

The question asks how a collision in a hash such as SHA-1 could become a practical concern, with focus on the case of a public-key certificate à la X.509.


I'll first give an example involving executable code signing. I'll assume an attacker in a position to write bootstrap code (like, the supplier of a development toolchain, or someone who compromised that toolchain), and enough resources to perform one single attack finding two distinct 128-byte colliding messages on SHA-1 with a small change: the value of the (arbitrary) 160-bit initialization value. The later is possible

Suppose an executable file format consisting of

  1. : 4-byte magic value 0x4D6F4546 (My own Executable Format)
  2. : 4-byte length of bootstrap code, allowing to locate section 4
  3. : bootstrap code with entry point at offset 8
  4. : 4-byte length of section 5, allowing to locate the signature
  5. : (anything)
  6. : PKCS#1v2 RSA-4096 signature of the SHA-1 hash of 1-2-3-4-5.

The attacker writes or adapts bootstrap code 3 so that the executable is

  1. : 4-byte magic value 0x4D6F4546 (My own Executable Format)
  2. : 4-byte length of bootstrap code, allowing to locate section 4
  3. : bootstrap code with entry point at offset 8
    1. : code that gets the value of $k$ from section 3.4, then jumps to section 3.6 or 3.5 according to if $k^\text{th}$ bit of section 3.3 is 0 or 1
    2. : filler data so that 3.3 is aligned to a 64-byte boundary
    3. : 128-byte data block
    4. : 4-byte $k<1024$ such that the two values of section 3.3 differ in the $k^\text{th}$ bit
    5. : code performing whatever the attacker wants to perform
    6. : code performing whatever the bootstrap is supposed to perform
  4. : 4-byte length of section 5, allowing to locate the signature
  5. : (anything)
  6. : PKCS#1v2 RSA-2048 signature using SHA-1 hash of 1 / 2 / 3 / 4 / 5.

The adversary needs to

  • know 1 / 2 / 3.1 / 3.2 when starting the attack
  • apply enough rounds of SHA-1 to deduce the 160-bit SHA-1 state after hashing 1 / 2 / 3.1 / 3.2, giving the 160-bit initialization value of the SHA-1 variant attacked
  • perform one of the costly attack at the beginning of this section
  • having found two 128-byte colliding data blocks, determine a bit index $k$ where they differ, and label the colliding blocks A and B according to if $k^\text{th}$ bit of the block is 0 or 1
  • construct two version 3A and 3B of the bootstrap code 3, differing only by containing block A or B in section 3.3; notice that 3.5 and 3.6 can be changed without performing the costly attack again;
  • plant version 3A of the boostrap, which does as it is supposed to perform
  • let an unsuspecting developer create an application with bootstrap 3A, and getting it signed;
  • obtain that signed original;
  • create a forgery by changing section 3.3 to block B, so that version 3B of the bootstrap is in place;
  • arrange for the forgery to be used on target machines, using the reputation of the application developer.

The forgery pass signature verification because the SHA-1 hash of 1 / 2 / 3 / 4 / 5 is unchanged, but when launched executes the code of section 3.5 performing whatever the attacker wants to perform, when the signed original did not.

Further, it is possible to encipher the code of section 3.5 using the block of section 3.4 as key, making it impossible to analyze the exact behavior of bootstrap 3B from the knowledge of bootstrap 3A. And code of section 3.1 can be of the form decipher-then-execute, so that the intention is less apparent.

Similar tricks can be pulled with some "data" format that are executables in disguise; e.g. that trick has been pulled with postcript and MD5.


Back to certificates in X.509-like format: consider a simplified certificate format with

  1. : identity of the certificate holder, in ASCII on 44 bytes right padded with spaces
  2. : public modulus $N$ of a 2048-bit RSA key, on 256 bytes (big-endian)
  3. : (other certificate data, including public exponent, attributes..)
  4. : PKCS#1v2 RSA-2048 signature using SHA-1 hash of 1 / 2 / 3

and one of two relevant attack models

  • An attacker legitimately purchases from an honest certification authority a certificate with her identity Alice and a public modulus $N_a$, modify it into a certificate with the identity of Bob and public modulus $N_b$, and holds the private keys $d_a$ and $d_b$ corresponding to $N_a$ and $N_b$ ($d_a$ is necessary to obtain the certificate; $d_b$ allows Alice to impersonate Bob);
  • A rogue certification authority knowingly supplies to Alice a certificate with the identity of Bob and a public modulus $N$ with factorization known to Alice (and perhaps having relatively easily found prime factors, making it more plausible that the above attack occurred), allowing Alice to impersonate Bob; and if word ever leaks that Alice impersonated Bob using a certificate issued by this authority, pretends that it has fallen to the above attack.

Note: something close to one of the above things has actually occurred with MD5-based X.509 certificates, per the evidence given here. This had been publicly described circa 2009.

In order to actually perform the attack, Alice

  • searches one SHA-1 collision between two 64-byte data blocks $M_a=I_a\|J_a$ and $M_b=I_b\|J_b$ with the first 44 bytes $I_a$ and $I_b$ corresponding to Alice's and Bob's identity; and 20 other bytes $J_a$ and $J_b$ arbitrary except for having the first bit set
    • the brute force Parallel Collision Search referenced earlier allows that with expected effort less than $2^{82}$ hashes: the function iterated can map a 160-bit value to a 64-byte block with either Alice's or Bob's identity in $I$ according to one bit; and map the other 159 bits to the unconstrained bits of $J$; when a collision is found, there is a 50% chance that it will be between a 64-byte block with different identities, thus usable;
    • it is conceivable to adapt some specialized methods exploiting weaknesses in SHA-1's compression function (in particular Marc Steven's publication referenced earlier describes a chosen-prefix collision attacks with expected effort about $2^{77.1}$ hashes);
  • finds a 236-byte value $K$ so that $N_a=J_a\|K$ and $N_b=J_b\|K$ (big-endian) are 2048-bit integers with known factorization, squarefree, and odd (and if necessary, with $N_a$ passing whatever other test the certification authority may perform, and $N_b$ passing whatever other test the entity to which Alice wants to represent herself as Bob may perform); given our message format, it is even feasible (though not required) to ensure that both $N_a$ and $N_b$ have exactly two large primes factors: we can choose $p_a$ and $p_b$ arbitrary primes about 900 bits, then systematically construct and explore $K$ such that $p_a$ divides $N_a$ and $p_b$ divides $N_b$, until both $N_a/p_a$ and $N_b/p_b$ are primes.
  • finds a public exponent $e$ acceptable for both $N_a$ and $N_b$ (there's a fair chance that the common $e=2^{16}+1$ will do) and compute private exponents per RSA as defined in PKCS#1, as $d_a=e^{-1}\bmod\lambda(N_a)$ and $d_b=e^{-1}\bmod\lambda(N_b)$, which is easy knowing the factorization of $N_a$ and $N_b$;
  • legitimately obtain the certificate with identity $I_a$, public modulus $N_a$, public exponent $e$ (which typically requires signing the certification request using $d_a$);
  • change $I_a$ to $I_b$ and $N_a$ to $N_b$ in the certificate (this will not change the SHA-1 hash, thus the forgery is a certificate that pass the verification procedure);
  • impersonate Bob using the forged certificate and $d_b$.

A countermeasure would be that certification services enforce the insertion of some unpredictable data in the beginning of certified data.

$\endgroup$
  • $\begingroup$ Thanks, such a great answer ! But "thus allowing forgery of a slightly different certificate beneficial to the attacker" , when it is about hash fonction, "slightly" difference in input doesn't mean "near output", so why is it an advantage to have chosen fields and "slightly" different ? $\endgroup$ – crypto-learner Dec 5 '14 at 20:40
  • $\begingroup$ @crypto-learner: I now give a lot more details, especially for the second example. $\endgroup$ – fgrieu Dec 6 '14 at 8:33
  • 1
    $\begingroup$ I've created an answer that basically says: see MD5. In what sense are these the same attacks against MD5? Are there differences? $\endgroup$ – Maarten - reinstate Monica Dec 6 '14 at 11:50
  • 1
    $\begingroup$ @owlstead: I see no difference in principle about attacks exploiting MD5 collisions, and attacks exploiting SHA-1 collisions; feasibility is about operational details, and the cost of the search given the constraints. However MD5 is significantly more badly broken than SHA-1 is, in particular 1-block (64-byte) MD5 collisions are possible when the minimum is 2-block (128-byte) for SHA-1; and significantly constrained MD5 collisions can be built, when we do not have even a single SHA-1 collision. $\endgroup$ – fgrieu Dec 6 '14 at 12:58
  • 1
    $\begingroup$ Yeah, IAIK did try a distributed collision finding approach some time ago, and I even spend some CPU cycles on it, but it didn't lead to a collision in the end. SHA-1 is fiercely resisting deprecation, although it is losing out in the end :) $\endgroup$ – Maarten - reinstate Monica Dec 6 '14 at 13:50
2
$\begingroup$

As indicated, SHA-1 is not broken in the sense that practical attacks apply (as of 2014-12-06) [EDIT: and now it is, as of 2017, as everybody will have noticed]. So until practical attacks become feasible it is unclear against what scenarios they can be mounted.

Probably the best thing to do is to have a look at what is happening with MD5. It is likely - but not certain - that attacks on SHA-1 would have largely the same characteristics. The early signs seem to point to a strong similarity in attacks. This is to be expected as the internal structure of the hash functions has many similarities as well. [EDIT: and the break is rather similar to those mounted to MD5 although MD5 is still much more broken than SHA-1; breaking the collision resistance of SHA-1 requires a lot more resources and some mitigations are still possible].

More information here (How does shattered work, at this site, Crypto.SE).

$\endgroup$
-2
$\begingroup$

Let me add these paragraphs for clarity, but I still stand behind my below answer, as your question does not specifically address what you already understand Crypto-learner.

MD5 as an example of an older uses the Merkle-Damgard construction as do SHA1 and SHA2, however, MD5 have some intrinsic vulnerabilities like the chosen prefix collision attack which is more potent than a typical collision attack.

In 2005 an attack was successful placed upon SHA1 in less rounds than a brute force attack 2^69 as opposed to 2^80 for brute force. and this was made possible due to mathematical weaknesses within the first 20 rounds.Later in 2008-2009 similar vulnerabilities were found within the upgraded SHA1.

Note: no, the plaintext does not matter here, only the more abundant outputs from less inputs matter in relation to hash collisions.

Now below the overview of hash functions, tables and salting in my mind is relevant still because there are vulnerabilities in these areas too that can lead to hash collisions and digital security forgeries.

Crypto-learner good question so let's start with some basics and then delve a little deeper into the underlying structure of both hash functions and hash collisions.

First a hash function can utilize various tables for storage of a given series of data, each with specific benefits and detriments, like a rainbow table versus a normal data scale hash table. The hash function itself just maps an input string to some integer string. This input-output mapping applies an arbitrary length of input to a short output known as a digest. Unfortunately as a result, a minimum of two issues can occur:

  1. Two different strings will generate the same integer output.

  2. The same name or data identifier will cause the same integer output to occur.

The so called collision is related to the mathematical problem coined the birthday problem via the pigeonhole principle within probability: as the sample size of hashes goes up representing n bit strings so too does a hash collision.

I would like to add two links if I may but I can answer any questions left after your reading them or add clarification.

  1. http://www.codeproject.com/Articles/608860/Understanding-and-Implementing-Password-Hashing

  2. http://research.cs.vt.edu/AVresearch/hashing/introduction.php

Salting helps make hashing less likely to suffer a collision via adding a random string for each n bit strings (passwords, names, etc...) and then hash them separately.

If the links are not clear or you feel you understand them and need more robust mathematical proofs I can write them out for you and explain them, but I do not want to assume what you understand or not until we talk this issue of hashing collisions out.

$\endgroup$
  • $\begingroup$ I think you may have misread his question, he is concerned about malicious collisions in a cryptographic hash function, which will allow forgery of a digital signature. $\endgroup$ – Richie Frame Dec 5 '14 at 1:37
  • $\begingroup$ Richie I believe I understand his question. However, with only a little to go on I wanted to start with the underlying basics first and expand from there when he clarifies his question. My response is still relevant, but we need to move in the right direction regarding cryptographic hash functions malicious collisions and forgery of a given digital signature. Regards. $\endgroup$ – Jacob E Mack Dec 5 '14 at 1:39
  • $\begingroup$ For example digital signatures are susceptible to collisions unless the randomized hashing is used as touched upon above. In addition. heartbleed SSL holes, old SSLV3/TLS protocols can make keys vulnerable to digital signature forgery. win.tue.nl/hashclash/rogue-ca $\endgroup$ – Jacob E Mack Dec 5 '14 at 1:46
  • $\begingroup$ Brief history of Hashing algorithm vulnerabilities: security.blogoverflow.com/2013/09/about-secure-password-hashing $\endgroup$ – Jacob E Mack Dec 5 '14 at 1:52
  • $\begingroup$ @JacobEMack: Well, I don't think you understand his question. The answer is in my opinion pretty useless. The comment of dave_thompson_085 is more like a correct answer would look. $\endgroup$ – Nova Dec 5 '14 at 8:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.