SHA-1 collisions - what about practical attacks?

Question

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).

Answer 1

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

• by brute force with expected effort less than $2^{81}$ hashes (about the effort devoted to bitcoin mining in a year according to that source) using Paul C. van Oorschot and Michael J. Wiener's Parallel Collision Search with Cryptanalytic Applications (in Journal of Cryptology, January 1999, Volume 12, Issue 1; free slightly earlier version available from the first author's website);
• or with less effort using complex specialized methods exploiting weaknesses in SHA-1's compression function, with an estimated effort comparable to
  • $2^{69}$ hashes, per Xiaoyun Wang, Yiqun Lisa Yin, Hongbo Yu: Finding Collisions in the Full SHA-1, in proccedings of Crypto 2005),
  • $2^{63}$ hashes, per Xiaoyun Wang, Andrew C Yao, Frances Yao: Cryptanalysis on SHA-1, rump session of Crypto 2005; see also Martin Cochran: Notes on the Wang et al. $2^{63}$ SHA-1 Differential Path, in IACR eprint archives, 2007),
  • $2^{61}$ hashes, per Marc Stevens: New collision attacks on SHA-1 based on optimal joint local-collision analysis (in proceedings of Eurocrypt 2013, also freely available from the author's website).

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.

Answer 2

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).

Answer 3

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.