An attack on SHA1 that makes certificate forgery viable within the next few years doesn't seem very likely, although over the long term it might be. The attack on SHA1 isn't like the attacks on RSA-1024; my sense is that the literature already knows how to break RSA-1024 given enough compute, but does not know how to do that with SHA1. Further, factoring RSA-1024 provides an attacker with a total break of RSA-1024 TLS, but not every attack on SHA1 will necessarily do the same.
Second, there's a subtext that SHA-3 having been standardized somehow puts the writing on the wall (albeit, a far-away wall) for SHA-2. Not so; SHA-2 could remain secure (in its TLS certificate use case) indefinitely.
To out-pedant you: even assuming that the differential collision attacks we know about are incorrect [1], we absolutely know how to break SHA-1 given enough compute, that is, roughly the same resources needed to break RSA-1024. The answer is generic collision finding with parallel rho [2].
I don't know if "10 years" falls in your definition of "next few years".
For a viable rogue CA attack, you need a chosen-prefix attack. Current best research (https://marc-stevens.nl/research/papers/EC13-S.pdf) shows it should take 2^77.1 SHA-1 compression calls to do a chosen-prefix attack. Say this is improved to 2^65 within the next 10 years. Right now a good GPU (AMD R9 290) can do 3 billion SHA-1 compression calls per second. Say Moore's Law continues for the next 10 years and that 10 years from now a GPU can do 20 billion SHA-1 per second. So 10 year from now, 100 high-end GPUs should be able to produce a rogue CA with colliding SHA-1 signature in 7 month of compute time.
Change one little assumption and assume the best attack ends up being 2^60 instead of 2^65. In this case, a viable attack could certainly be carried out in the next 3-4 years.
You can't cross your fingers and hopes such an attack will not be discovered. The time to abandon SHA-1 is now.
@tptacek - I tried to include enough detail to make it clear that a SHA-1 forgery isn't as trivial as a brute force. That you'd have to "coax a Certificate Authority" into issuing you a targeted forgery, and that that's what the MD5 team did.
The SHA-3 mention at the very bottom was in the spirit of "all things are broken eventually", not a specific comment on SHA-2 (though my understanding is that there are some conceptual weaknesses that have been identified). I don't think I've confused the issue there, but if I see confusion I'll definitely update it.
my sense is that the literature already knows how to break RSA-1024 given enough compute
"given enough compute", we can break any crypto just with pure bruteforce, although in practice I believe there's a point at which the amount of power that would be required becomes physically impossible due to the limits of computation within the universe (i.e. Moore's Law will definitely end sometime). To me, that says using extremely large hash sizes can keep things quite secure - even attacks that reduce complexity by many orders of magnitude could be impossible in practice - e.g. a 2048-bit hash for which a 2^500 complexity attack is found won't be any less practically secure.
...unless we somehow discover that P = NP, in which case the world could become a very interesting place...
A while back I launched a SSL scanner [1] and got tons of feedback from people at Facebook, Google, Microsoft.
The most divisive item was how to represent SHA1 deprecation. The OPs article doesn't really touch on it, but the reason that Google and everyone else haven't moved on is that there still exist a sizeable number of clients that can only accept SHA1 (and will error on anything else).
I actually suspect that large sites like Facebook, etc will maintain multiple certs at the different levels and dynamically serve the best one up that the client can support. They're already doing things like only serving HSTS to browsers that identify as Chrome, etc.
> I actually suspect that large sites like Facebook, etc will maintain multiple certs at the different levels and dynamically serve the best one up that the client can support.
How would you do that? When the TLS connection is established you know nothing about the client except its IP address. All of the interesting information about the browser is transported via the HTTP stream which is tunneled inside the TLS connection.
HSTS is simple by comparison, as it's only an HTTP header.
I'd like to see them gradually downgrade all non-PFS connections. Non-PFS connections should be considered medium-to-highly vulnerable, and shouldn't receive a green icon in browsers.
Unfortunately, they've just recommended everyone to use "2048-bit keys" when they announced the HTTPS Google ranking policy. A lot of developers won't understand the difference between a 2048-bit RSA key and a 256-bit ECC key, so they'll just pick RSA, since "Google said 2048-bit keys!". Sooo...maybe this policy will come in 10 years.
So where is the fully automated solution for rotating certificates?
I've been looking for a CA who will provide an API to send the cert request, an easy way to prove the domain ownership which doesn't involve SMTP, and the signed cert handed straight back from the API, but haven't found it.
So far the most I've been able to streamline my certificate requests is to automate generating the CSR, skip setting the MX record, just bind SMTP to www.domain.com, get the validation email at '[email protected]' and auto-forward to my actual email address... so it's mostly automated, but I still have to copy/paste the cert request string into the CA's webform, click the 'Approve' link in the forwarded DV mail, and then copy/paste the final cert from inside email back to the shell where it can finish the import.
Right now it's just a command line client, but a public API is in the works. And this week we'll be announcing a solution to the cert rotation problem (basically, you'll be able to drive your renewals from cron - it's going to be really cool). You might want to follow @sslmate on Twitter - this is just the beginning of some very exciting stuff for automating SSL cert deployment. Also feel free to email me (address is in my profile).
Sadly, we're still SHA-1 only, because that's all that our certificate authority (RapidSSL) supports at the moment. On the other hand, once we make renewals dead simple, you can just buy 1 year certs and it won't be a big deal upgrading to SHA-2 in a year's time. (After all, even Google is still using SHA-1, but they can easily switch thanks to their 3 month certs and well-oiled cert deployment machinery.)
Commercial solutions exist too; the company I work for (Venafi https://www.venafi.com) makes certificate management software that is designed to solve this very problem.
Understanding that this is a naive outsider perspective, I find it strange that it's any sort of emergency when a single collision has yet to be produced. And then, does the latest hash collision attack allow you to make a collision with a _specific_ target or just make a collision in general? Finally, even if you hit the target with some junk that happens to hash to the same thing, is it going to be in correct file format, and within an acceptable size? It seems like there are a handful of hurdles for the bad guys to go over before we're in danger.
I know crypto is not to be taken lightly, and I'm glad people would rather be safe than sorry, and I'll avoid SHA-1 in my own personal security use (`sha256sum` is sha-2 right?). I'm just curious.
The point is that currently producing a single collision may cost a couple million dollars of brute force for now. So we should expect it to be used (there are attacks where that much money is invested, either a very valuable target or very many low-value targets), but we should expect to see one only after a highly targeted attack is detected and analyized - in the case of Flame, those steps took a few years.
Some government agency MITM'ing major social sites or email providers would be rather possible at that cost.
An unrelated annoying thing: I want to disable TLSv1 support for my site, for obvious reasons. I don't care about backwards compatibility for my personal site, but I still can't flip the switch... because Googlebot doesn't support anything newer than TLSv1.
I'm a developer, but I'm not responsible for SSL cert acquisition.
The ONLY way I can get the people responsible for that to stop using SHA-1, is to tell them that user's browsers are sending a warning/error message on it.
It's surprising how much energy Certificate Authorities invest into arguing about this. Instead, they should invest that energy into improving their SHA-2 support and helping their customers migrate.
They are businesses. Their customers are mostly businesses. SHA1 is, for most businesses that only want a padlock to reassure their customers, just peachy. A CA that hassles their customers and says "you need to do complicated extra work" is put at a disadvantage to other CA's that have a "customer is always right" kind of attitude. Combined with tools that default to SHA1, and customers that may depressingly actually have Windows XP SP2 terminals still in production use, and you get feet dragging.
I don't think this is inherently a problem with the CA model. Rather it's what you'd expect in a competitive market that is basically selling a binary commodity product (a padlock icon), given textbook economics.
Google's decisions with respect to certificates don't really affect git much. But, if you're curious about how git handles pulling from repositories containing malicious hash collisions, Linus has talked about that in the past:
> If it has the same SHA1, it means that when we receive the object from the other end, we will not overwrite the object we already have.
> So what happens is that if we ever see a collision, the "earlier" object in any particular repository will always end up overriding. But note that "earlier" is obviously per-repository, in the sense that the git object network generates a DAG that is not fully ordered, so while different repositories will agree about what is "earlier" in the case of direct ancestry, if the object came through separate and not directly related branches, two different repos may obviously have gotten the two objects in different order.
> However, the "earlier will override" is very much what you want from a security standpoint: remember that the git model is that you should primarily trust only your own repository.
> So if you do a "git pull", the new incoming objects are by definition less trustworthy than the objects you already have, and as such it would be wrong to allow a new object to replace an old one.
...
> in this case, the collision is entirely a non-issue: you'll get a "bad" repository that is different from what the attacker intended, but since you'll never actually use his colliding object, it's literally no different from the attacker just not having found a collision at all, but just using the object you already had (ie it's 100% equivalent to the "trivial" collision of the identical file generating the same SHA1).
I assume you would need to forge a meaningful (and potentially harmful) commit with the same SHA-1 as an existing one to do arm. That's probably more difficult than forging an SSL certificate (since the actual contents of the blob are more constrained that the certificate file, probably). I'm also not really sure what would happen if commits made after the "compromised" one happened to conflict with it but I'm pretty sure the devs would notice something fishy going on pretty quickly.
That being said git/mercurial and friends will have to transition to an other hashing algorithm sooner or later but it's not as urgent as web certificates security-wise.
This is for SSL and certificate validation - Google's move won't affect git in any way.
Git uses it to ensure that the data that comes out is exactly what went in (like a much better checksum than md5 or crc32 etc).
I don't know what the security implications are on the git side... I suppose an attacker could try to figure out how to change source code in a way that it preserves a commit log.
One would think it would have been a good opportunity to change to SHA-2 after Heartbleed, since most websites had to get reissued certificates anyway. Since this process is a pain in the * then one could have killed two birds with one stone at the time. Alas
Also its not exactly fair to compare the Flame attack on MD5 and compare it immediately to SHA-1. Unless you are the US or China you likely don't have the resources necessary to pull off that sort of attack.
The Flame attack's math was invented by an internal government cryptographic think tank. And still had to leverage massive computational power, just not in the order of 100's of millions.
The idea a rogue group who have access to (both of) these resources is slightly idiotic. It would be far easier for them to attack RSA directly if you had 10's of millions of dollars of computers. There are a lot of 1024 bit certs you could pick off for easy profit.
Is it not far easier to acquire the necessary computing power than it was in past? As more and more people converge on the internet, the attack vector increases dramatically as well. How much easier is it today to get the same botnet the government used for Flame? Furthermore, the idea of safety behind computational difficulty is going to be eroding away quicker than ever, in the future.
The issue here is old clients... Does anyone know how old clients would handle SHA-2 certs, would they just get a warning saying the site is insecure but still be able to visit the site over an encrypted connection or do they break completely... I guess - I'll have to run a few tests this afternoon and see how windows XP performs.
"SHA1 and other hash algorithms generate a digital fingerprint that in theory is unique for each different file or text input they sign."
... and there it goes, any credibility I would give the author. There's dumbing down the content for a non-technical audience, and there's not understanding.
What does stop Google Chrome simply disallow new SHA-1 hashes that collide with known list of SHA-1 hashes for existing certificates?
That would allow non-colliding SHA-1 certificates function as usual and prevent millions of people from major headaches related to speedy certificate migration.
[+] [-] tptacek|11 years ago|reply
An attack on SHA1 that makes certificate forgery viable within the next few years doesn't seem very likely, although over the long term it might be. The attack on SHA1 isn't like the attacks on RSA-1024; my sense is that the literature already knows how to break RSA-1024 given enough compute, but does not know how to do that with SHA1. Further, factoring RSA-1024 provides an attacker with a total break of RSA-1024 TLS, but not every attack on SHA1 will necessarily do the same.
Second, there's a subtext that SHA-3 having been standardized somehow puts the writing on the wall (albeit, a far-away wall) for SHA-2. Not so; SHA-2 could remain secure (in its TLS certificate use case) indefinitely.
[+] [-] pbsd|11 years ago|reply
[1] https://marc-stevens.nl/research/papers/EC13-S.pdf [2] http://people.scs.carleton.ca/~paulv/papers/JoC97.pdf
[+] [-] cgjaro|11 years ago|reply
For a viable rogue CA attack, you need a chosen-prefix attack. Current best research (https://marc-stevens.nl/research/papers/EC13-S.pdf) shows it should take 2^77.1 SHA-1 compression calls to do a chosen-prefix attack. Say this is improved to 2^65 within the next 10 years. Right now a good GPU (AMD R9 290) can do 3 billion SHA-1 compression calls per second. Say Moore's Law continues for the next 10 years and that 10 years from now a GPU can do 20 billion SHA-1 per second. So 10 year from now, 100 high-end GPUs should be able to produce a rogue CA with colliding SHA-1 signature in 7 month of compute time.
Change one little assumption and assume the best attack ends up being 2^60 instead of 2^65. In this case, a viable attack could certainly be carried out in the next 3-4 years.
You can't cross your fingers and hopes such an attack will not be discovered. The time to abandon SHA-1 is now.
[+] [-] konklone|11 years ago|reply
The SHA-3 mention at the very bottom was in the spirit of "all things are broken eventually", not a specific comment on SHA-2 (though my understanding is that there are some conceptual weaknesses that have been identified). I don't think I've confused the issue there, but if I see confusion I'll definitely update it.
[+] [-] xkiwi|11 years ago|reply
==edited==
Thank you for the reply.
[+] [-] userbinator|11 years ago|reply
"given enough compute", we can break any crypto just with pure bruteforce, although in practice I believe there's a point at which the amount of power that would be required becomes physically impossible due to the limits of computation within the universe (i.e. Moore's Law will definitely end sometime). To me, that says using extremely large hash sizes can keep things quite secure - even attacks that reduce complexity by many orders of magnitude could be impossible in practice - e.g. a 2048-bit hash for which a 2^500 complexity attack is found won't be any less practically secure.
...unless we somehow discover that P = NP, in which case the world could become a very interesting place...
[+] [-] michaelbuckbee|11 years ago|reply
The most divisive item was how to represent SHA1 deprecation. The OPs article doesn't really touch on it, but the reason that Google and everyone else haven't moved on is that there still exist a sizeable number of clients that can only accept SHA1 (and will error on anything else).
I actually suspect that large sites like Facebook, etc will maintain multiple certs at the different levels and dynamically serve the best one up that the client can support. They're already doing things like only serving HSTS to browsers that identify as Chrome, etc.
1 - https://www.expeditedssl.com/simple-ssl-scanner/scan?target_...
[+] [-] Perseids|11 years ago|reply
How would you do that? When the TLS connection is established you know nothing about the client except its IP address. All of the interesting information about the browser is transported via the HTTP stream which is tunneled inside the TLS connection.
HSTS is simple by comparison, as it's only an HTTP header.
[+] [-] konklone|11 years ago|reply
b) I think its SHA-1 scanner is mistaken - it flags my site as using SHA-1, but it's SHA-2 in every cert in its chain: https://www.expeditedssl.com/simple-ssl-scanner/scan?target_...
[+] [-] higherpurpose|11 years ago|reply
Unfortunately, they've just recommended everyone to use "2048-bit keys" when they announced the HTTPS Google ranking policy. A lot of developers won't understand the difference between a 2048-bit RSA key and a 256-bit ECC key, so they'll just pick RSA, since "Google said 2048-bit keys!". Sooo...maybe this policy will come in 10 years.
http://googlewebmastercentral.blogspot.com/2014/08/https-as-...
[+] [-] kajarya|11 years ago|reply
[+] [-] mathias|11 years ago|reply
[+] [-] zaroth|11 years ago|reply
I've been looking for a CA who will provide an API to send the cert request, an easy way to prove the domain ownership which doesn't involve SMTP, and the signed cert handed straight back from the API, but haven't found it.
So far the most I've been able to streamline my certificate requests is to automate generating the CSR, skip setting the MX record, just bind SMTP to www.domain.com, get the validation email at '[email protected]' and auto-forward to my actual email address... so it's mostly automated, but I still have to copy/paste the cert request string into the CA's webform, click the 'Approve' link in the forwarded DV mail, and then copy/paste the final cert from inside email back to the shell where it can finish the import.
[+] [-] agwa|11 years ago|reply
Right now it's just a command line client, but a public API is in the works. And this week we'll be announcing a solution to the cert rotation problem (basically, you'll be able to drive your renewals from cron - it's going to be really cool). You might want to follow @sslmate on Twitter - this is just the beginning of some very exciting stuff for automating SSL cert deployment. Also feel free to email me (address is in my profile).
Sadly, we're still SHA-1 only, because that's all that our certificate authority (RapidSSL) supports at the moment. On the other hand, once we make renewals dead simple, you can just buy 1 year certs and it won't be a big deal upgrading to SHA-2 in a year's time. (After all, even Google is still using SHA-1, but they can easily switch thanks to their 3 month certs and well-oiled cert deployment machinery.)
[+] [-] wgoulet|11 years ago|reply
[+] [-] orblivion|11 years ago|reply
I know crypto is not to be taken lightly, and I'm glad people would rather be safe than sorry, and I'll avoid SHA-1 in my own personal security use (`sha256sum` is sha-2 right?). I'm just curious.
[+] [-] paulannesley|11 years ago|reply
No collisions published to the public doesn't mean no collisions have been found.
As the article says; “we should assume that the worst vulnerabilities go undisclosed.”
[+] [-] spatz|11 years ago|reply
[+] [-] PeterisP|11 years ago|reply
Some government agency MITM'ing major social sites or email providers would be rather possible at that cost.
[+] [-] sbierwagen|11 years ago|reply
[+] [-] jrochkind1|11 years ago|reply
I'm a developer, but I'm not responsible for SSL cert acquisition.
The ONLY way I can get the people responsible for that to stop using SHA-1, is to tell them that user's browsers are sending a warning/error message on it.
I will eagerly await Chrome doing that.
[+] [-] bla2|11 years ago|reply
[+] [-] mike_hearn|11 years ago|reply
I don't think this is inherently a problem with the CA model. Rather it's what you'd expect in a competitive market that is basically selling a binary commodity product (a padlock icon), given textbook economics.
[+] [-] tptacek|11 years ago|reply
[+] [-] tux1968|11 years ago|reply
[+] [-] slavik81|11 years ago|reply
> If it has the same SHA1, it means that when we receive the object from the other end, we will not overwrite the object we already have.
> So what happens is that if we ever see a collision, the "earlier" object in any particular repository will always end up overriding. But note that "earlier" is obviously per-repository, in the sense that the git object network generates a DAG that is not fully ordered, so while different repositories will agree about what is "earlier" in the case of direct ancestry, if the object came through separate and not directly related branches, two different repos may obviously have gotten the two objects in different order.
> However, the "earlier will override" is very much what you want from a security standpoint: remember that the git model is that you should primarily trust only your own repository.
> So if you do a "git pull", the new incoming objects are by definition less trustworthy than the objects you already have, and as such it would be wrong to allow a new object to replace an old one.
...
> in this case, the collision is entirely a non-issue: you'll get a "bad" repository that is different from what the attacker intended, but since you'll never actually use his colliding object, it's literally no different from the attacker just not having found a collision at all, but just using the object you already had (ie it's 100% equivalent to the "trivial" collision of the identical file generating the same SHA1).
http://stackoverflow.com/q/9392365
[+] [-] simias|11 years ago|reply
That being said git/mercurial and friends will have to transition to an other hashing algorithm sooner or later but it's not as urgent as web certificates security-wise.
[+] [-] atonse|11 years ago|reply
Git uses it to ensure that the data that comes out is exactly what went in (like a much better checksum than md5 or crc32 etc).
I don't know what the security implications are on the git side... I suppose an attacker could try to figure out how to change source code in a way that it preserves a commit log.
[+] [-] hevsuit|11 years ago|reply
[+] [-] konklone|11 years ago|reply
[+] [-] valarauca1|11 years ago|reply
The Flame attack's math was invented by an internal government cryptographic think tank. And still had to leverage massive computational power, just not in the order of 100's of millions.
The idea a rogue group who have access to (both of) these resources is slightly idiotic. It would be far easier for them to attack RSA directly if you had 10's of millions of dollars of computers. There are a lot of 1024 bit certs you could pick off for easy profit.
[+] [-] crazypyro|11 years ago|reply
[+] [-] brador|11 years ago|reply
[+] [-] vtlynch|11 years ago|reply
@konklone, have you followed the CAB Forum's mailing on this topic? Its the most I've seen them argue in well over a year.
[+] [-] konklone|11 years ago|reply
[+] [-] Cyranix|11 years ago|reply
[+] [-] kilovoltaire|11 years ago|reply
Anyone know if they're planning to upgrade to SHA-2?
[+] [-] taf2|11 years ago|reply
[+] [-] brongondwana|11 years ago|reply
... and there it goes, any credibility I would give the author. There's dumbing down the content for a non-technical audience, and there's not understanding.
[+] [-] dennisgorelik|11 years ago|reply
That would allow non-colliding SHA-1 certificates function as usual and prevent millions of people from major headaches related to speedy certificate migration.
[+] [-] unknown|11 years ago|reply
[deleted]
[+] [-] foomen|11 years ago|reply
http://en.wikipedia.org/wiki/DNS-based_Authentication_of_Nam...