SHA-1 collisions - what about practical attacks? 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).
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


: 4-byte magic value 0x4D6F4546 (My own Executable Format)
: 4-byte length of bootstrap code, allowing to locate section 4
: bootstrap code with entry point at offset 8
: 4-byte length of section 5, allowing to locate the signature
: (anything)
: 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


: 4-byte magic value 0x4D6F4546 (My own Executable Format)
: 4-byte length of bootstrap code, allowing to locate section 4
: bootstrap code with entry point at offset 8


: 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
: filler data so that 3.3 is aligned to a 64-byte boundary
: 128-byte data block
: 4-byte $k&lt;1024$ such that the two values of section 3.3 differ in the $k^\text{th}$ bit
: code performing whatever the attacker wants to perform
: code performing whatever the bootstrap is supposed to perform

: 4-byte length of section 5, allowing to locate the signature
: (anything)
: 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


: identity of the certificate holder, in ASCII on 44 bytes right padded with spaces
: public modulus $N$ of a 2048-bit RSA key, on 256 bytes (big-endian)
: (other certificate data, including public exponent, attributes..)
: 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.