5 ms·

So to be clear about what this is (because the website doesn’t quite clarify): this collision lets you pick two different prefixes P1, P2, then calculates some

So to be clear about what this is (because the website doesn’t quite clarify): this collision lets you pick two different prefixes P1, P2, then calculates some pseudorandom data C1, C2 such that SHA1(P1+C1) = SHA1(P2+C2). The length extension property of SHA1 (and MD5) means that now SHA1(P1+C1+X) = SHA1(P2+C2+X) for any X. A similar attack (which requires only a few hours on modest hardware nowadays) has been known for a long time for MD5, but this is the first time it’s been demonstrated for SHA-1. The previous attack, called Shattered (https://shattered.io https://shattered.io) was a regular collision, that is, they chose a single prefix P and found different C1, C2 such that SHA1(P+C1) = SHA1(P+C2). This can also be length extended, so that SHA1(P+C1+X) = SHA1(P+C2+X). However, this attack is more limited because there is little to no control over the pseudorandom C1 and C2 (the only differing parts of the messages). With a chosen prefix collision, though, things are way worse. Now you can create two documents that are arbitrarily different, pad them to the same length, and tack on some extra blocks to make them collide. Luckily, the first collision should have already warned people to get off of SHA1. It’s no longer safe to use for many applications. (Note, generally for basic integrity operations it might be OK since there’s no preimage attack, but I’d still be a bit wary myself).

tptacek 7y ago
Squeamish Osssifrage's answer to this Crypto Stack Exchange question does a predictably excellent job of putting these attacks in context. https://crypto.stackexchange.com/questions/60640/does-shattered-actually-show-sha-1-signed-certificates-are-unsafe https://crypto.stackexchange.com/questions/60640/does-shatte...
- ReidZB 7y ago
  Agreed. It's a great loss to the community that they have decided to step away from Stack Exchange: https://crypto.meta.stackexchange.com/questions/1361/im-leaving-crypto-se-indefinitely https://crypto.meta.stackexchange.com/questions/1361/im-leav...
  - gowld 7y ago
    * that the owners of Stack Exchange drove them and others away.
    - lightedman 7y ago
      Yup, that's pretty much what happened in reading that posted link, so why you're being downvoted I don't know.
RickHull 7y ago
Actually, the website does cover this in the '''Q&A''' section: > What is a chosen-prefix collision? > A classical collision (or identical-prefix collision) for a hash function H is simply two messages M and M’ that lead to the same hash output: H(M) = H(M’). Even though this security notion is fundamental in cryptography, exploiting a classical collision for attacks in practice is difficult. > A chosen-prefix collision is a more constrained (and much more difficult to obtain) type of collision, where two message prefixes P and P’ are first given as challenge to the adversary, and his goal is then to compute two messages M and M’ such that H(P || M) = H(P’ || M’), where || denotes concatenation. > With such an ability, the attacker can obtain a collision even though prefixes can be chosen arbitrarily (and thus potentially contain some meaningful information). This is particularly impactful when the hash function is used in a digital signature scheme, one of the most common usage of a hash function.
- nneonneo 7y ago
  The confusing thing is that the team behind SHAttered did choose a prefix - they just had to choose a common prefix rather than two different prefixes (choosing a common prefix simply changes the initial state used by SHA-1). So I'm hoping that my post clarifies this point a bit. The SHAttered attack (classical collision) can be used in practice - for example, my project https://github.com/nneonneo/sha1collider https://github.com/nneonneo/sha1collider exploits their collision to turn any two PDFs into documents with identical SHA-1 hashes.
  - gowld 7y ago
    Is any practical application safe from Shattered but not Shambles?
    - saagarjha 7y ago
      Applications which don't accept the specific Shattered PDF prefix given there. In general Shattered could work for e.g. ELF executables with the same prefix, but the attack here lets you collide the hashes even if the prefixes are different.
dickjocke 7y ago
Can you give a specific example of the danger here? I understand the principle behind the attack (kinda). I just don't understand what danger being able to pad two documents to make them collide poses? edit: My guess is that it can be abused to make something that I believe to be library X actually be library Y when I download it from the internet. Lets say I want to download something, and I check the signature provided. Assuming the attacker is able to send me the wrong library via a MITM attack, how can this prefix collision work? It seems that the original library AND the original signature on the library's website have not been altered, so their efforts to use this and make them match are impossible. And it seems like if they can alter the signature on the website and stuff, then all bets are off--why not just send the malicious library at that point?
- femto113 7y ago
  It’s a step on the same path that led to being able to spoof a CA for MD5 signed certs. https://www.google.com/amp/s/techcrunch.com/2008/12/30/md5-collision-creates-rogue-certificate-authority/amp/ https://www.google.com/amp/s/techcrunch.com/2008/12/30/md5-c...
  - ThePowerOfFuet 7y ago
    Please don't feed the cancer which is AMP. https://techcrunch.com/2008/12/30/md5-collision-creates-rogue-certificate-authority/ https://techcrunch.com/2008/12/30/md5-collision-creates-rogu...
    - sofaofthedamned 7y ago
      Please don't overegg the issue with AMP by comparing it to cancer.
      - andrewstuart2 7y ago
        Don't make cancer anything it's not, either. Cancer is just growth of abnormal cells, unconstrained, to the point that it causes harm to the host. That said, maybe AMP is more like a virus. A non-living organism that spreads by infecting living organisms and repurposing them to replicate itself instead of sustaining the organism they were a part of. The more sites adopt AMP, the more everyone else says "well I guess we have to now." Seems pretty viral.
userbinator 7y ago
Note, generally for basic integrity operations it might be OK since there’s no preimage attack, but I’d still be a bit wary myself AFAIK there's still no practical preimage attack for MD5, for which you can generate collisions in seconds on hardware that's a decade old, so it seems making a hash function collision resistant is in general quite a bit harder than making it resistant to preimage attacks.
- nneonneo 7y ago
  To some extent that’s just a function of the brute-force search space: due to the birthday paradox a 128-bit hash like MD5 only requires testing around 2^64 hashes to find a collision. However, to find a preimage you would need to search through 2^128 possible messages. Attacks generally improve on brute force by factors; for example, MD5 collision finding is some 2^40 times more efficient than 2^64 brute force, but being 2^40 times more efficient than 2^128 brute force for preimage finding is still well outside of anyone’s capabilities. MD5 also appears to be unusually preimage-resistant; the best attack requires something like 2^123 operations which is really infeasible.

tptacek 7y ago

Squeamish Osssifrage's answer to this Crypto Stack Exchange question does a predictably excellent job of putting these attacks in context. https://crypto.stackexchange.com/questions/60640/does-shattered-actually-show-sha-1-signed-certificates-are-unsafe https://crypto.stackexchange.com/questions/60640/does-shatte...

ReidZB 7y ago
Agreed. It's a great loss to the community that they have decided to step away from Stack Exchange: https://crypto.meta.stackexchange.com/questions/1361/im-leaving-crypto-se-indefinitely https://crypto.meta.stackexchange.com/questions/1361/im-leav...
- gowld 7y ago
  * that the owners of Stack Exchange drove them and others away.
  - lightedman 7y ago
    Yup, that's pretty much what happened in reading that posted link, so why you're being downvoted I don't know.

RickHull 7y ago

Actually, the website does cover this in the '''Q&A''' section: > What is a chosen-prefix collision? > A classical collision (or identical-prefix collision) for a hash function H is simply two messages M and M’ that lead to the same hash output: H(M) = H(M’). Even though this security notion is fundamental in cryptography, exploiting a classical collision for attacks in practice is difficult. > A chosen-prefix collision is a more constrained (and much more difficult to obtain) type of collision, where two message prefixes P and P’ are first given as challenge to the adversary, and his goal is then to compute two messages M and M’ such that H(P || M) = H(P’ || M’), where || denotes concatenation. > With such an ability, the attacker can obtain a collision even though prefixes can be chosen arbitrarily (and thus potentially contain some meaningful information). This is particularly impactful when the hash function is used in a digital signature scheme, one of the most common usage of a hash function.

nneonneo 7y ago
The confusing thing is that the team behind SHAttered did choose a prefix - they just had to choose a common prefix rather than two different prefixes (choosing a common prefix simply changes the initial state used by SHA-1). So I'm hoping that my post clarifies this point a bit. The SHAttered attack (classical collision) can be used in practice - for example, my project https://github.com/nneonneo/sha1collider https://github.com/nneonneo/sha1collider exploits their collision to turn any two PDFs into documents with identical SHA-1 hashes.
- gowld 7y ago
  Is any practical application safe from Shattered but not Shambles?
  - saagarjha 7y ago
    Applications which don't accept the specific Shattered PDF prefix given there. In general Shattered could work for e.g. ELF executables with the same prefix, but the attack here lets you collide the hashes even if the prefixes are different.

dickjocke 7y ago

Can you give a specific example of the danger here? I understand the principle behind the attack (kinda). I just don't understand what danger being able to pad two documents to make them collide poses? edit: My guess is that it can be abused to make something that I believe to be library X actually be library Y when I download it from the internet. Lets say I want to download something, and I check the signature provided. Assuming the attacker is able to send me the wrong library via a MITM attack, how can this prefix collision work? It seems that the original library AND the original signature on the library's website have not been altered, so their efforts to use this and make them match are impossible. And it seems like if they can alter the signature on the website and stuff, then all bets are off--why not just send the malicious library at that point?

femto113 7y ago
It’s a step on the same path that led to being able to spoof a CA for MD5 signed certs. https://www.google.com/amp/s/techcrunch.com/2008/12/30/md5-collision-creates-rogue-certificate-authority/amp/ https://www.google.com/amp/s/techcrunch.com/2008/12/30/md5-c...
- ThePowerOfFuet 7y ago
  Please don't feed the cancer which is AMP. https://techcrunch.com/2008/12/30/md5-collision-creates-rogue-certificate-authority/ https://techcrunch.com/2008/12/30/md5-collision-creates-rogu...
  - sofaofthedamned 7y ago
    Please don't overegg the issue with AMP by comparing it to cancer.
    - andrewstuart2 7y ago
      Don't make cancer anything it's not, either. Cancer is just growth of abnormal cells, unconstrained, to the point that it causes harm to the host. That said, maybe AMP is more like a virus. A non-living organism that spreads by infecting living organisms and repurposing them to replicate itself instead of sustaining the organism they were a part of. The more sites adopt AMP, the more everyone else says "well I guess we have to now." Seems pretty viral.

userbinator 7y ago

Note, generally for basic integrity operations it might be OK since there’s no preimage attack, but I’d still be a bit wary myself AFAIK there's still no practical preimage attack for MD5, for which you can generate collisions in seconds on hardware that's a decade old, so it seems making a hash function collision resistant is in general quite a bit harder than making it resistant to preimage attacks.

nneonneo 7y ago
To some extent that’s just a function of the brute-force search space: due to the birthday paradox a 128-bit hash like MD5 only requires testing around 2^64 hashes to find a collision. However, to find a preimage you would need to search through 2^128 possible messages. Attacks generally improve on brute force by factors; for example, MD5 collision finding is some 2^40 times more efficient than 2^64 brute force, but being 2^40 times more efficient than 2^128 brute force for preimage finding is still well outside of anyone’s capabilities. MD5 also appears to be unusually preimage-resistant; the best attack requires something like 2^123 operations which is really infeasible.