6 ms·

A few considerations though: - Google used GPUs, much of the Bitcoin network relies on fully custom ASICs now and mining without them isn't really profitable a

A few considerations though: - Google used GPUs, much of the Bitcoin network relies on fully custom ASICs now and mining without them isn't really profitable anymore - SHA1 hashes can also be computed over twice as fast as SHA256 even on GPUs, so if someone were to go out and build SHA1 ASICs, you could probably do this very, very fast. It's almost certain that intelligence agencies could invest this effort to say, break SHA1 SSL certs.

jakob223 10y ago
> say, break SHA1 SSL certs Maybe, and probably, but probably not within the scope of this attack. This attack relies on being able to have a large similar prefix and a lot of control over further internal data; SSL certs are somewhat more constrainted.
- problems 10y ago
  Would a TLS certificate not offer such a large similar prefix? Just change the domain to a wildcard or something like the RapidSSL MD5 attack from a few years back.
  - JoshTriplett 10y ago
    > Just change the domain to a wildcard or something Or change a CA:FALSE certificate to CA:TRUE, so you have your own intermediate certificate.
  - schoen 10y ago
    In https://www.win.tue.nl/hashclash/rogue-ca/ https://www.win.tue.nl/hashclash/rogue-ca/, Sotirov et al. were able to use the ability to create MD5 collisions to create a pair of colliding certificates because the content of an about-to-be-issued certificate was almost completely predictable. In response to this, the industry added requirements for CAs to include unpredictable values (such as an unpredictable serial number) in certificates. For example, the certificate for HN has serial number 00:EA:21:7C:EA:6C:1F:97:9E:6A:91:90:B7:68:52:D6:63, which is at least in part nonsequential and random, specifically in order to prevent an attacker who knows a collision attack in the hash function used by the CA from being able to exploit it. This precaution means that an attack like this isn't immediately directly usable against TLS, because the work factor has been increased dramatically. Edit: the adopted change to the rules is at https://cabforum.org/2016/07/08/ballot-164/ https://cabforum.org/2016/07/08/ballot-164/ and requires at least 64 bits of CSPRNG entropy in the serial number, specifically as a response to Sotirov. I forgot the history of the section that it replaced (which recommended at least 20 unpredictable bits), but I think that may also have been a response to Sotirov; if the old recommendation had been in use then Sotirov's original attack would not have worked.
    - jwilk 10y ago
      Also, they used a chosen-prefix attack for creating colliding certificates. The SHA-1 attack is identical-prefix, which gives you much less flexibility.
- timeal 10y ago
  This attack is applicable to SSL certs. Not most CAs as they have deployed counter-measures (such as using a long, random serial number) after the publication of the colliding MD5 rogue CA (https://www.win.tue.nl/hashclash/rogue-ca/ https://www.win.tue.nl/hashclash/rogue-ca/) but I'm sure there are tons of companies with IT department and internal CAs who don't follow best practices and could be attacked with SHA1 collisions.
  - pfg 10y ago
    Even root CAs have been known to not comply with the randomized serial number requirement occasionally, see [1] for a recent example, with the most recent (SHA-1) certificate being issued in August of last year. [1]: https://bugzilla.mozilla.org/show_bug.cgi?id=1267332#c5 https://bugzilla.mozilla.org/show_bug.cgi?id=1267332#c5
stepik777 10y ago
> break SHA1 SSL certs. It's not possible to break existing SHA1 certificates because this attack is to generate collisions, not finding preimages.
- xyzzyz 10y ago
  You are thinking about this in a wrong way. It is in fact true that being able to generate collisions allows you to break SSL. What you do is this: generate two certificates with colliding hashes, one for google.com, the other for your own domain. Verisign will gladly sign the second one, since you own the domain, but since the hashes match, you can also use the same signature for the first one. Now you can impersonate google.com. Of course, the real certificate issuance process is more complicated and has some extra precautions to protect from it, my point is that you don't need preimage, collisions should suffice for breaking SSL.
  - mike_hearn 10y ago
    Moreover, how quickly we forget! An intelligence agency did in fact carry out such an attack on code signing certificates using an MD5 collision as part of the FLAME malware.
    - deleted 10y ago
      [deleted]
  - agrajag 10y ago
    Those extra precautions are designed explicitly to prevent the ability to get a certificate using a collision attack. CA's now must explicitly introduce entropy into a certificate to prevent exactly this, and will not sign a certificate exactly to the specifications of a client. There's a great deal of handwaving there saying that a collision attack alone is sufficient for breaking SSL.
btilly 10y ago
It's almost certain that intelligence agencies could invest this effort to say, break SHA1 SSL certs. To the contrary, it is unlikely that they can do so. There is a world of difference between "come up with two things that hash to the same value" and "come up with something that hashes to a particular known value". It gets harder still if you're trying to add constraints about the format of your text (such as making them look like a potentially valid SSL cert). To illustrate the difference, suppose that you can constrain the algorithm to produce one of a trillion values. If you generate a million possibilities, odds are good that 2 of them will have the same hash value. You've generated a collision! But you need to do a million times as much work to have good odds of generating any particular value. That said, attacks only improve over time. While it is highly unlikely that intelligence agencies can break SHA1 certs today, it is extremely likely that they will eventually. Where eventually is 5-20 years.
- problems 10y ago
  > There is a world of difference between "come up with two things that hash to the same value" and "come up with something that hashes to a particular known value". Doesn't the PDF on their site pretty much prove they can do both of these - at least, in a way? They were able to change the color without impacting the contents of the PDF and get the same SHA1. They probably have a fair bit of garbage data to work with in the PDF format, but it seems likely that you might be able to do similar in certificate formats. Remember, you only need a very small modification to change a valid web cert into a CA cert or a global wildcard.
  - jsolson 10y ago
    No. I don't know the details of the attack, but a third possibility (as I read it) is that both PDF documents are modified in the process until they arrive at a collision. PDF has the convenient property that you can inject arbitrary bogus data into the middle of it with a constant head and tail and it will still be valid. The tail of the file contains a trailer that points to the dictionary that describes where all of the resources in the file are located. The entire file need not be covered by the dictionary (and typically won't be for PDFs that have gone through several rounds of annotation/modification). This leaves the opportunity "dead chunks" that can be modified arbitrarily without changing the rendered result.

jakob223 10y ago

> say, break SHA1 SSL certs Maybe, and probably, but probably not within the scope of this attack. This attack relies on being able to have a large similar prefix and a lot of control over further internal data; SSL certs are somewhat more constrainted.

problems 10y ago
Would a TLS certificate not offer such a large similar prefix? Just change the domain to a wildcard or something like the RapidSSL MD5 attack from a few years back.
- JoshTriplett 10y ago
  > Just change the domain to a wildcard or something Or change a CA:FALSE certificate to CA:TRUE, so you have your own intermediate certificate.
- schoen 10y ago
  In https://www.win.tue.nl/hashclash/rogue-ca/ https://www.win.tue.nl/hashclash/rogue-ca/, Sotirov et al. were able to use the ability to create MD5 collisions to create a pair of colliding certificates because the content of an about-to-be-issued certificate was almost completely predictable. In response to this, the industry added requirements for CAs to include unpredictable values (such as an unpredictable serial number) in certificates. For example, the certificate for HN has serial number 00:EA:21:7C:EA:6C:1F:97:9E:6A:91:90:B7:68:52:D6:63, which is at least in part nonsequential and random, specifically in order to prevent an attacker who knows a collision attack in the hash function used by the CA from being able to exploit it. This precaution means that an attack like this isn't immediately directly usable against TLS, because the work factor has been increased dramatically. Edit: the adopted change to the rules is at https://cabforum.org/2016/07/08/ballot-164/ https://cabforum.org/2016/07/08/ballot-164/ and requires at least 64 bits of CSPRNG entropy in the serial number, specifically as a response to Sotirov. I forgot the history of the section that it replaced (which recommended at least 20 unpredictable bits), but I think that may also have been a response to Sotirov; if the old recommendation had been in use then Sotirov's original attack would not have worked.
  - jwilk 10y ago
    Also, they used a chosen-prefix attack for creating colliding certificates. The SHA-1 attack is identical-prefix, which gives you much less flexibility.
timeal 10y ago
This attack is applicable to SSL certs. Not most CAs as they have deployed counter-measures (such as using a long, random serial number) after the publication of the colliding MD5 rogue CA (https://www.win.tue.nl/hashclash/rogue-ca/ https://www.win.tue.nl/hashclash/rogue-ca/) but I'm sure there are tons of companies with IT department and internal CAs who don't follow best practices and could be attacked with SHA1 collisions.
- pfg 10y ago
  Even root CAs have been known to not comply with the randomized serial number requirement occasionally, see [1] for a recent example, with the most recent (SHA-1) certificate being issued in August of last year. [1]: https://bugzilla.mozilla.org/show_bug.cgi?id=1267332#c5 https://bugzilla.mozilla.org/show_bug.cgi?id=1267332#c5

stepik777 10y ago

> break SHA1 SSL certs. It's not possible to break existing SHA1 certificates because this attack is to generate collisions, not finding preimages.

xyzzyz 10y ago
You are thinking about this in a wrong way. It is in fact true that being able to generate collisions allows you to break SSL. What you do is this: generate two certificates with colliding hashes, one for google.com, the other for your own domain. Verisign will gladly sign the second one, since you own the domain, but since the hashes match, you can also use the same signature for the first one. Now you can impersonate google.com. Of course, the real certificate issuance process is more complicated and has some extra precautions to protect from it, my point is that you don't need preimage, collisions should suffice for breaking SSL.
- mike_hearn 10y ago
  Moreover, how quickly we forget! An intelligence agency did in fact carry out such an attack on code signing certificates using an MD5 collision as part of the FLAME malware.
  - deleted 10y ago
    [deleted]
- agrajag 10y ago
  Those extra precautions are designed explicitly to prevent the ability to get a certificate using a collision attack. CA's now must explicitly introduce entropy into a certificate to prevent exactly this, and will not sign a certificate exactly to the specifications of a client. There's a great deal of handwaving there saying that a collision attack alone is sufficient for breaking SSL.

btilly 10y ago

It's almost certain that intelligence agencies could invest this effort to say, break SHA1 SSL certs. To the contrary, it is unlikely that they can do so. There is a world of difference between "come up with two things that hash to the same value" and "come up with something that hashes to a particular known value". It gets harder still if you're trying to add constraints about the format of your text (such as making them look like a potentially valid SSL cert). To illustrate the difference, suppose that you can constrain the algorithm to produce one of a trillion values. If you generate a million possibilities, odds are good that 2 of them will have the same hash value. You've generated a collision! But you need to do a million times as much work to have good odds of generating any particular value. That said, attacks only improve over time. While it is highly unlikely that intelligence agencies can break SHA1 certs today, it is extremely likely that they will eventually. Where eventually is 5-20 years.

problems 10y ago
> There is a world of difference between "come up with two things that hash to the same value" and "come up with something that hashes to a particular known value". Doesn't the PDF on their site pretty much prove they can do both of these - at least, in a way? They were able to change the color without impacting the contents of the PDF and get the same SHA1. They probably have a fair bit of garbage data to work with in the PDF format, but it seems likely that you might be able to do similar in certificate formats. Remember, you only need a very small modification to change a valid web cert into a CA cert or a global wildcard.
- jsolson 10y ago
  No. I don't know the details of the attack, but a third possibility (as I read it) is that both PDF documents are modified in the process until they arrive at a collision. PDF has the convenient property that you can inject arbitrary bogus data into the middle of it with a constant head and tail and it will still be valid. The tail of the file contains a trailer that points to the dictionary that describes where all of the resources in the file are located. The entire file need not be covered by the dictionary (and typically won't be for PDFs that have gone through several rounds of annotation/modification). This leaves the opportunity "dead chunks" that can be modified arbitrarily without changing the rendered result.