SHA1 collisions proven possisble
Coworker passed this on to me. Looks like SHA1 hash collisions are now achievable in a reasonable time period https://shattered.io/ -Grant
On Thu, Feb 23, 2017 at 10:27 AM Grant Ridder <shortdudey123@gmail.com> wrote:
Coworker passed this on to me.
Looks like SHA1 hash collisions are now achievable in a reasonable time period https://shattered.io/
-Grant
Good thing we "secure" our routing protocols with MD5 :)
On Feb 23, 2017, at 2:59 PM, Ca By <cb.list6@gmail.com> wrote:
On Thu, Feb 23, 2017 at 10:27 AM Grant Ridder <shortdudey123@gmail.com> wrote:
Coworker passed this on to me.
Looks like SHA1 hash collisions are now achievable in a reasonable time period https://shattered.io/
-Grant
Good thing we "secure" our routing protocols with MD5
MD5 on BGP considered Harmful.
:)
:-) More seriously: The attack (or at least as much as we can glean from the blog post) cannot find a collision (file with same hash) from an arbitrary file. The attack creates two files which have the same hash, which is scary, but not as bad as it could be. For instance, someone cannot take Verisign’s root cert and create a cert which collides on SHA-1. Or at least we do not think they can. We’ll know in 90 days when Google releases the code. -- TTFN, patrick
On Thu, 23 Feb 2017 15:03:34 -0500, "Patrick W. Gilmore" said:
For instance, someone cannot take Verisign’s root cert and create a cert which collides on SHA-1. Or at least we do not think they can. We’ll know in 90 days when Google releases the code.
From the announce:
"It is now practically possible to craft two colliding PDF files and obtain a SHA-1 digital signature on the first PDF file which can also be abused as a valid signature on the second PDF file." So they're able to craft two objects that collide to the same unpredictable hash, but *not* produce an object that collides to a pre-specified hash.
On Thu, 23 Feb 2017 15:03:34 -0500, Patrick W. Gilmore <patrick@ianai.net> wrote:
More seriously: The attack (or at least as much as we can glean from the blog post) cannot find a collision (file with same hash) from an arbitrary file. The attack creates two files which have the same hash, which is scary, but not as bad as it could be.
Exactly. This is just more sky-is-falling nonsense. Of course collisions exist. They occur in every hash function. It's only marginally noteworthy when someone finds a collision. It's neat the Google has found a way to generate a pair of files with the same hash -- at colossal computational cost! However this in no way invalidates SHA-1 or documents signed by SHA-1. You still cannot take an existing document, modify it in a meaningful way, and keep the same hash. [Nor can you generate a blob to match an arbitrary hash (which would be death of all bittorrent)]
It's actually pretty serious in Git and the banking markets where there is high usage of sha1. Considering the wide adoption of Git, this is a pretty serious issue that will only become worse ten-fold over the years. Visible abuse will not be near as widely seen as the initial shattering but escalate over much longer periods. Take it serious ? Why wouldn't you !? -- Onward!, Jason Hellenthal, Systems & Network Admin, Mobile: 0x9CA0BD58, JJH48-ARIN On Feb 23, 2017, at 16:40, Ricky Beam <jfbeam@gmail.com> wrote:
On Thu, 23 Feb 2017 15:03:34 -0500, Patrick W. Gilmore <patrick@ianai.net> wrote: More seriously: The attack (or at least as much as we can glean from the blog post) cannot find a collision (file with same hash) from an arbitrary file. The attack creates two files which have the same hash, which is scary, but not as bad as it could be.
Exactly. This is just more sky-is-falling nonsense. Of course collisions exist. They occur in every hash function. It's only marginally noteworthy when someone finds a collision. It's neat the Google has found a way to generate a pair of files with the same hash -- at colossal computational cost! However this in no way invalidates SHA-1 or documents signed by SHA-1. You still cannot take an existing document, modify it in a meaningful way, and keep the same hash. [Nor can you generate a blob to match an arbitrary hash (which would be death of all bittorrent)]
We just need to keep the likely timeline in mind. As I saw someone say on Twitter today ... "don't panic, just deprecate". Valeria Aurora's hash-lifecycle table is very informative (emphasis mine): http://valerieaurora.org/hash.html Reactions to stages in the life cycle of cryptographic hash functions StageExpert reactionProgrammer reactionNon-expert ("slashdotter") reaction Initial proposal Skepticism, don't recommend use in practice Wait to hear from the experts before adding to your crypto library SHA-what? Peer review Moderate effort to find holes and garner an easy publication Used by a particularly adventurous developers for specific purposes Name-drop the hash at cocktail parties to impress other geeks General acceptance Top-level researchers begin serious work on finding a weakness (and international fame) Even Microsoft is using the hash function now Flame anyone who suggests the function may be broken in our lifetime Minor weakness discovered Massive downloads of turgid pre-prints from arXiv, calls for new hash functions Start reviewing other hash functions for replacement Long semi-mathematical posts comparing the complexity of the attack to the number of protons in the universe Serious weakness discovered Tension-filled CRYPTO rump sessions! A full break is considered inevitable Migrate to new hash functions immediately, where necessary Point out that no actual collisions have been found First collision found *Uncork the champagne! Interest in the details of the construction, but no surprise* *Gather around a co-worker's computer, comparing the colliding inputs and running the hash function on them* *Explain why a simple collision attack is still useless, it's really the second pre-image attack that counts* Meaningful collisions generated on home computer How adorable! I'm busy trying to break this new hash function, though Send each other colliding X.509 certificates as pranks Claim that you always knew it would be broken Collisions generated by hand Memorize as fun party trick for next faculty mixer Boggle Try to remember how to do long division by hand Assumed to be weak but no one bothers to break No one is getting a publication out of breaking this What's this crypto library function for? Update Pokemon Wikipedia pages Royce On Thu, Feb 23, 2017 at 2:11 PM, J. Hellenthal <jhellenthal@dataix.net> wrote:
It's actually pretty serious in Git and the banking markets where there is high usage of sha1. Considering the wide adoption of Git, this is a pretty serious issue that will only become worse ten-fold over the years. Visible abuse will not be near as widely seen as the initial shattering but escalate over much longer periods.
Take it serious ? Why wouldn't you !?
-- Onward!, Jason Hellenthal, Systems & Network Admin, Mobile: 0x9CA0BD58, JJH48-ARIN
On Feb 23, 2017, at 16:40, Ricky Beam <jfbeam@gmail.com> wrote:
On Thu, 23 Feb 2017 15:03:34 -0500, Patrick W. Gilmore < patrick@ianai.net> wrote: More seriously: The attack (or at least as much as we can glean from the blog post) cannot find a collision (file with same hash) from an arbitrary file. The attack creates two files which have the same hash, which is scary, but not as bad as it could be.
Exactly. This is just more sky-is-falling nonsense. Of course collisions exist. They occur in every hash function. It's only marginally noteworthy when someone finds a collision. It's neat the Google has found a way to generate a pair of files with the same hash -- at colossal computational cost! However this in no way invalidates SHA-1 or documents signed by SHA-1. You still cannot take an existing document, modify it in a meaningful way, and keep the same hash.
[Nor can you generate a blob to match an arbitrary hash (which would be death of all bittorrent)]
Git prefixes blobs with its own data. You're not going to break git with a SHA-1 binary collision. However, svn is very vulnerable to breaking. On Thu, Feb 23, 2017 at 3:11 PM, J. Hellenthal <jhellenthal@dataix.net> wrote:
It's actually pretty serious in Git and the banking markets where there is high usage of sha1. Considering the wide adoption of Git, this is a pretty serious issue that will only become worse ten-fold over the years. Visible abuse will not be near as widely seen as the initial shattering but escalate over much longer periods.
Take it serious ? Why wouldn't you !?
-- Onward!, Jason Hellenthal, Systems & Network Admin, Mobile: 0x9CA0BD58, JJH48-ARIN
On Feb 23, 2017, at 16:40, Ricky Beam <jfbeam@gmail.com> wrote:
On Thu, 23 Feb 2017 15:03:34 -0500, Patrick W. Gilmore < patrick@ianai.net> wrote: More seriously: The attack (or at least as much as we can glean from the blog post) cannot find a collision (file with same hash) from an arbitrary file. The attack creates two files which have the same hash, which is scary, but not as bad as it could be.
Exactly. This is just more sky-is-falling nonsense. Of course collisions exist. They occur in every hash function. It's only marginally noteworthy when someone finds a collision. It's neat the Google has found a way to generate a pair of files with the same hash -- at colossal computational cost! However this in no way invalidates SHA-1 or documents signed by SHA-1. You still cannot take an existing document, modify it in a meaningful way, and keep the same hash.
[Nor can you generate a blob to match an arbitrary hash (which would be death of all bittorrent)]
On Sat, 25 Feb 2017 09:26:28 -0800, Richard Hesse said:
Git prefixes blobs with its own data. You're not going to break git with a SHA-1 binary collision. However, svn is very vulnerable to breaking.
And here's the proof-of-concept for svn breakage. Somebody managed to make the WebKit svn totally lose its mind by uploading the two PoC PDFs.... https://arstechnica.com/security/2017/02/watershed-sha1-collision-just-broke...
Git prefixes blobs with its own data. You're not going to break git with a SHA-1 binary collision.
http://www.metzdowd.com/pipermail/cryptography/2017-February/031623.html
On Thu, 23 Feb 2017 17:40:42 -0500, "Ricky Beam" said:
cost! However this in no way invalidates SHA-1 or documents signed by SHA-1.
We negotiate a contract with terms favorable to you. You sign it (or more correctly, sign the SHA-1 hash of the document). I then take your signed copy, take out the contract, splice in a different version with terms favorable to me. Since the hash didn't change, your signature on the second document remains valid. I present it in court, and the judge says "you signed it, you're stuck with the terms you signed". I think that would count as "invalidates documents signed by SHA-1", don't you?
On Thu, 23 Feb 2017, valdis.kletnieks@vt.edu wrote:
On Thu, 23 Feb 2017 17:40:42 -0500, "Ricky Beam" said:
cost! However this in no way invalidates SHA-1 or documents signed by SHA-1.
We negotiate a contract with terms favorable to you. You sign it (or more correctly, sign the SHA-1 hash of the document).
I then take your signed copy, take out the contract, splice in a different version with terms favorable to me. Since the hash didn't change, your signature on the second document remains valid.
I present it in court, and the judge says "you signed it, you're stuck with the terms you signed".
I think that would count as "invalidates documents signed by SHA-1", don't you?
Depends on the format of the document. As was just pointed out, and I almost posted earlier today, that there are collisions in SHA-1, or any hash that takes an arbitrary length input and outputs a fixed length string, should be no surprise to anyone. Infinite inputs yielding a fixed number of possible outputs. There have to be collisions. Lots of them. The question then becomes how hard is it find or craft two inputs that give the same hash or one input that gives the same hash as another? Doing this with PDFs that look similar, which can contain arbitrary bitmaps or other data is kind of a cheat / parlor trick. Doing it with an ASCII document, source code, or even something like a Word document (containing only text and formatting), and having it not be obvious upon inspection of the documents that the "imposter" document contains some "specific hash influencing 'gibberish'" would be far more disturbing. ---------------------------------------------------------------------- Jon Lewis, MCP :) | I route | therefore you are _________ http://www.lewis.org/~jlewis/pgp for PGP public key_________
On Thu, 23 Feb 2017 19:28:44 -0500, Jon Lewis said:
Doing it with an ASCII document, source code, or even something like a Word document (containing only text and formatting), and having it not be obvious upon inspection of the documents that the "imposter" document contains some "specific hash influencing 'gibberish'" would be far more disturbing.
Keep in mind that there's *lots* of stuff that people might want to sign that aren't flat ASCII. For instance, the video that just came out of that police officer's bodycam. If the "gibberish" is scattered across the pixels, you'll never know. And let's face it - if you need to do an inspection because you don't trust the hash to have done its job - *the hash has failed to do its job*.
❦ 23 février 2017 19:28 -0500, Jon Lewis <jlewis@lewis.org> :
cost! However this in no way invalidates SHA-1 or documents signed by SHA-1.
We negotiate a contract with terms favorable to you. You sign it (or more correctly, sign the SHA-1 hash of the document).
I then take your signed copy, take out the contract, splice in a different version with terms favorable to me. Since the hash didn't change, your signature on the second document remains valid.
I present it in court, and the judge says "you signed it, you're stuck with the terms you signed".
I think that would count as "invalidates documents signed by SHA-1", don't you?
Depends on the format of the document. As was just pointed out, and I almost posted earlier today, that there are collisions in SHA-1, or any hash that takes an arbitrary length input and outputs a fixed length string, should be no surprise to anyone. Infinite inputs yielding a fixed number of possible outputs. There have to be collisions. Lots of them. The question then becomes how hard is it find or craft two inputs that give the same hash or one input that gives the same hash as another? Doing this with PDFs that look similar, which can contain arbitrary bitmaps or other data is kind of a cheat / parlor trick.
Doing it with an ASCII document, source code, or even something like a Word document (containing only text and formatting), and having it not be obvious upon inspection of the documents that the "imposter" document contains some "specific hash influencing 'gibberish'" would be far more disturbing.
The collision is contained in about 128 bytes. It is easy to hide this collision in almost any document. You need a common prefix between the two documents, the collision, then anything you want (you still need a lot of processing power to get the collision matching your document). It is a weakness specific to SHA-1. Another same-length hash (like RIPEMD-160) is not affected. -- The man who sets out to carry a cat by its tail learns something that will always be useful and which never will grow dim or doubtful. -- Mark Twain
On Feb 23, 2017, at 6:21 PM, valdis.kletnieks@vt.edu wrote:
On Thu, 23 Feb 2017 17:40:42 -0500, "Ricky Beam" said:
cost! However this in no way invalidates SHA-1 or documents signed by SHA-1.
We negotiate a contract with terms favorable to you. You sign it (or more correctly, sign the SHA-1 hash of the document).
I then take your signed copy, take out the contract, splice in a different version with terms favorable to me. Since the hash didn't change, your signature on the second document remains valid.
I present it in court, and the judge says "you signed it, you're stuck with the terms you signed".
I think that would count as "invalidates documents signed by SHA-1", don't you?
Doesn’t work that way. According to the blog post, you can create two documents which have the same hash, but you do not know what that hash is until the algorithm finishes. You cannot create a document which matches a pre-existing hash, i.e. the one in the signed doc. Hence my comment that you can’t take Verisign’s root key and create a new key which matches the hash. -- TTFN, patrick
On Thu, 23 Feb 2017 20:56:28 -0500, "Patrick W. Gilmore" said:
According to the blog post, you can create two documents which have the same hash, but you do not know what that hash is until the algorithm finishes. You cannot create a document which matches a pre-existing hash, i.e. the one in the signed doc.
You missed the point. I generate *TWO* documents, with different terms but the same hash. I don't care if it matches anything else's hash, as long as these two documents have the same hash. I get you to sign the hash on the *ONE* document I present to you that is favorable to you. I then take your signature and transfer it to the *OTHER* document. No, I can't create a collision to a document you produced, or do anything to a document you already signed. But if I'm allowed to take it and make "minor formatting changes", or if I can just make sure I have the last turn in the back-and-forth negotiating... because the problem is if I can get you to sign a plaintext of my choosing....
On Feb 23, 2017, at 9:08 PM, valdis.kletnieks@vt.edu wrote:
On Thu, 23 Feb 2017 20:56:28 -0500, "Patrick W. Gilmore" said:
According to the blog post, you can create two documents which have the same hash, but you do not know what that hash is until the algorithm finishes. You cannot create a document which matches a pre-existing hash, i.e. the one in the signed doc.
You missed the point. I generate *TWO* documents, with different terms but the same hash. I don't care if it matches anything else's hash, as long as these two documents have the same hash. I get you to sign the hash on the *ONE* document I present to you that is favorable to you. I then take your signature and transfer it to the *OTHER* document.
No, I can't create a collision to a document you produced, or do anything to a document you already signed. But if I'm allowed to take it and make "minor formatting changes", or if I can just make sure I have the last turn in the back-and-forth negotiating... because the problem is if I can get you to sign a plaintext of my choosing….
I did miss the point. Thanks for setting me straight. A couple things will make this slightly less useful for the attacker: 1) How many people are not going to keep a copy? Once both docs are be found to have the same hash, well, game over. 2) The headers will be very strange indeed. The way this works is Google twiddled with the headers to make them look the same. That is probably pretty obvious if you look for it. Oh, and third: Everyone should stop using SHA-1 anyway. :-) -- TTFN, patrick
❦ 23 février 2017 21:16 -0500, "Patrick W. Gilmore" <patrick@ianai.net> :
A couple things will make this slightly less useful for the attacker: 1) How many people are not going to keep a copy? Once both docs are be found to have the same hash, well, game over.
But if a transaction is automated, it may be too late. For example, if the document is a bank transfer slip. -- "You have been in Afghanistan, I perceive." -- Sir Arthur Conan Doyle, "A Study in Scarlet"
On Feb 24, 2017, at 12:04 PM, Vincent Bernat <bernat@luffy.cx> wrote:
❦ 23 février 2017 21:16 -0500, "Patrick W. Gilmore" <patrick@ianai.net> :
A couple things will make this slightly less useful for the attacker: 1) How many people are not going to keep a copy? Once both docs are be found to have the same hash, well, game over.
But if a transaction is automated, it may be too late. For example, if the document is a bank transfer slip.
If I can control the bank side of presenting an automated transfer slip, I really don’t need to worry about SHA-1 collisions. I already have all your money. -- TTFN, patrick
On Thu, 23 Feb 2017 18:21:19 -0500, <valdis.kletnieks@vt.edu> wrote:
We negotiate a contract with terms favorable to you. You sign it (or more correctly, sign the SHA-1 hash of the document). ...
When you can do that in the timespan of weeks or days, get back to me. Today, it takes years to calculate a collision, and you have to start with a document specifically engineered to be modified. (such documents are easily spotted upon inspection: why does this word doc contain two documents?) You can't take any random document, modify it to say what you want, and keep the same hash. People still haven't been able to do that with MD5, and that's been "broken" for a long time. This isn't a checksum or CRC. The changing of bits in the input has an unpredictable effect on the output -- you have to do the entire hash calculation (or most of it), there is no instantaneous shortcut. They had to do 9billion billion hashes to stumble on a solution, after all. For example, one cannot recover an SSL certificate given only the hash (MD5 or SHA-1.) One cannot change the expiration date of an existing certificate while still maintaining the same hash. The fact that modern technology can perform 9BB hashes in a realistic time frame is worth noting. (that capability is usually wasted on bitcoin mining.)
On Thu, 23 Feb 2017 21:10:42 -0500, "Ricky Beam" said:
When you can do that in the timespan of weeks or days, get back to me. Today, it takes years to calculate a collision, and you have to start with a document specifically engineered to be modified. (such documents are easily spotted upon inspection: why does this word doc contain two documents?)
That question never arises, because this word doc contains only one document. The *OTHER* word doc also contains only one document.
You can't take any random document, modify it to say what you want, and keep the same hash. People still haven't been able to do that with MD5, and that's been "broken" for a long time.
That doesn't change the fact that if I can get you to sign a document I present to you, I can still have lots of fun at your expense.
Especially if that "document" is a component of a ciphersuite exchange. --Dave -----Original Message----- From: NANOG [mailto:nanog-bounces@nanog.org] On Behalf Of valdis.kletnieks@vt.edu Sent: Thursday, February 23, 2017 9:22 PM To: Ricky Beam <jfbeam@gmail.com> Cc: nanog@nanog.org Subject: Re: SHA1 collisions proven possisble On Thu, 23 Feb 2017 21:10:42 -0500, "Ricky Beam" said:
When you can do that in the timespan of weeks or days, get back to me. Today, it takes years to calculate a collision, and you have to start with a document specifically engineered to be modified. (such documents are easily spotted upon inspection: why does this word doc contain two documents?)
That question never arises, because this word doc contains only one document. The *OTHER* word doc also contains only one document.
You can't take any random document, modify it to say what you want, and keep the same hash. People still haven't been able to do that with MD5, and that's been "broken" for a long time.
That doesn't change the fact that if I can get you to sign a document I present to you, I can still have lots of fun at your expense.
On Feb 23, 2017, at 6:10 PM, Ricky Beam <jfbeam@gmail.com> wrote:
When you can do that in the timespan of weeks or days, get back to me.
Stop thinking in the context of bits of fake news on your phone. Start thinking in the context of trans-national agreements that will soon be signed by such keys. --lyndon
* valdis kletnieks:
We negotiate a contract with terms favorable to you. You sign it (or more correctly, sign the SHA-1 hash of the document).
I then take your signed copy, take out the contract, splice in a different version with terms favorable to me. Since the hash didn't change, your signature on the second document remains valid.
I present it in court, and the judge says "you signed it, you're stuck with the terms you signed".
I think that would count as "invalidates documents signed by SHA-1", don't you?
The more immediate problem isn't that you get framed, but that someone is insinuating that you might be framing *them*, i.e. invalidation of existing signatures etc. Regarding your original scenario: You have both copies, and it is possible to analyze them and notice that they were carefully crafted to exhibit the SHA-1 collision. So it should be clear that the party who generated the document is up to to no good, and the question now is which party is responsible for the doctored document. This scenario isn't much different from abusing complex file formats to render the document differently in different contexts. There is more reliable evidence here than there is with your average disputed pen-and-paper signature. Automated processing of SHA-1-hashed data might be a problem, though. For example, a web page generator might skip proper HTML encoding if the hash of a document fragment has a known SHA-1 (assuming that this exact fragment has been checked earlier). Certification signatures (such as those found in X.509 and DNSSEC) are particularly at risk. For X.509, CAs can randomize the serial number and avoid the shared prefix, which stops these attacks AFAIK. For DNSSEC, you probably should verify that the DS records are meaningful before signing the DS RRset. If I recall correctly, there is no good way to inject randomness early into the signed data, maybe except using invalid DS records which get sorted first.
On Thu, Feb 23, 2017 at 2:03 PM, Patrick W. Gilmore <patrick@ianai.net> wrote:
For instance, someone cannot take Verisign’s root cert and create a cert which collides on SHA-1. Or at least we do not think they can. We’ll know in 90 days when Google releases the code.
Maybe. If you assume that no SHA attack was known to anybody at the time the Verisign cert was originally created, And that the process used to originally create Verisign's root cert was not tainted to leverage such attack. If it was tainted, then maybe there's another version of the certificate that was constructed with a different Subject name and Subject public key, but the same SHA1 hash, and same Issuer Name and same Issuer Public Key.
-- TTFN, -- -JH
On Feb 25, 2017, at 17:44, Jimmy Hess <mysidia@gmail.com> wrote:
On Thu, Feb 23, 2017 at 2:03 PM, Patrick W. Gilmore <patrick@ianai.net> wrote:
For instance, someone cannot take Verisign’s root cert and create a cert which collides on SHA-1. Or at least we do not think they can. We’ll know in 90 days when Google releases the code.
Maybe. If you assume that no SHA attack was known to anybody at the time the Verisign cert was originally created, And that the process used to originally create Verisign's root cert was not tainted to leverage such attack.
If it was tainted, then maybe there's another version of the certificate that was constructed with a different Subject name and Subject public key, but the same SHA1 hash, and same Issuer Name and same Issuer Public Key.
I repeat something I've said a couple times in this thread: If I can somehow create two docs with the same hash, and somehow con someone into using one of them, chances are there are bigger problems than a SHA1 hash collision. If you assume I could somehow get Verisign to use a cert I created to match another cert with the same hash, why in the hell would that matter? I HAVE THE ONE VERISIGN IS USING. Game over. Valdis came up with a possible use of such documents. While I do not think there is zero utility in those instances, they are pretty small vectors compared to, say, having a root cert at a major CA. -- TTFN, patrick
Patrick W. Gilmore wrote:
I repeat something I've said a couple times in this thread: If I can somehow create two docs with the same hash, and somehow con someone into using one of them, chances are there are bigger problems than a SHA1 hash collision.
This collision turns a theoretical aspiration into a simple matter of financials, and those financials will only reduce over time. The incident needs to be taken in the context of how md5, rc4 and other hash functions were relentlessly battered to death over time. After the first collisions are found in a hash function, exploits only improve, so NIST's advice in 2004 to retire all SHA1 usage by 2010 was sound.
From a practical point of view, the danger that this presents is hypothetical for most people right now. It's just not worth spending 6000 years of CPU time in order to steal €1000 from someone's bank. But by the same token, there are plenty of people in the world who would be happy to invest this sort of computing power if the target were valuable enough.
Nick
On Sun, Feb 26, 2017 at 12:18:48PM -0500, Patrick W. Gilmore wrote:
I repeat something I've said a couple times in this thread: If I can somehow create two docs with the same hash, and somehow con someone into using one of them, chances are there are bigger problems than a SHA1 hash collision.
If you assume I could somehow get Verisign to use a cert I created to match another cert with the same hash, why in the hell would that matter? I HAVE THE ONE VERISIGN IS USING. Game over.
Valdis came up with a possible use of such documents. While I do not think there is zero utility in those instances, they are pretty small vectors compared to, say, having a root cert at a major CA.
I want a google.com cert. I ask a CA to sign my fake google.com certificate. They decline, because I can't prove I control google.com. I create a cert for mydomain.com,that hashes to the same value as my fake google.com cret. I ask a CA to sign my mydomain.com cert. They do, because I can prove I control mydomain.com. Now I effectively have a signed google.com cert. Of course, SHA1 is already deprecated for this purpose, and the currently demonstrated attack isn't flexible enough to have much chance at getting a colliding certificate signed. So, practically speaking, this isn't a problem *today* (even if SHA1 were deprecated). So this is more of a "here's the sort of thing collision attacks can be used for" point, rather than "here's what you can do with this attack right now" point. -- Brett
On Sun, Feb 26, 2017 at 05:41:47PM -0600, Brett Frankenberger wrote:
On Sun, Feb 26, 2017 at 12:18:48PM -0500, Patrick W. Gilmore wrote:
I repeat something I've said a couple times in this thread: If I can somehow create two docs with the same hash, and somehow con someone into using one of them, chances are there are bigger problems than a SHA1 hash collision.
If you assume I could somehow get Verisign to use a cert I created to match another cert with the same hash, why in the hell would that matter? I HAVE THE ONE VERISIGN IS USING. Game over.
Valdis came up with a possible use of such documents. While I do not think there is zero utility in those instances, they are pretty small vectors compared to, say, having a root cert at a major CA.
I want a google.com cert. I ask a CA to sign my fake google.com certificate. They decline, because I can't prove I control google.com.
Even better: I want a CA cert. I convince a CA to issue me a regular, end-entity cert for `example.com` (which I control) in such a way that I can generate another cert with the same SHA1 hash, but which has `CA:TRUE` for the Basic Constraints extension. Wham! I can now generate certs for *EVERYONE*. At least until someone notices and takes away my shiny new toy... - Matt -- [M]ost of the other people here [...] drive cars that they have personally built (starting with iron ore, charcoal, and a Malaysian turn-signal tree) [...] but I wimp out on all of those points. Sometimes there are advantages to paying somebody else to do it for you. -- Matt Roberds, in the Monastery
On Sunday, 26 February, 2017 19:16 Matt Palmer <mpalmer@hezmatt.org> said:
On Sun, Feb 26, 2017 at 05:41:47PM -0600, Brett Frankenberger wrote:
On Sun, Feb 26, 2017 at 12:18:48PM -0500, Patrick W. Gilmore wrote:
I repeat something I've said a couple times in this thread: If I can somehow create two docs with the same hash, and somehow con someone into using one of them, chances are there are bigger problems than a SHA1 hash collision.
If you assume I could somehow get Verisign to use a cert I created to match another cert with the same hash, why in the hell would that matter? I HAVE THE ONE VERISIGN IS USING. Game over.
Valdis came up with a possible use of such documents. While I do not think there is zero utility in those instances, they are pretty small vectors compared to, say, having a root cert at a major CA.
I want a google.com cert. I ask a CA to sign my fake google.com certificate. They decline, because I can't prove I control google.com.
Even better: I want a CA cert. I convince a CA to issue me a regular, end-entity cert for `example.com` (which I control) in such a way that I can generate another cert with the same SHA1 hash, but which has `CA:TRUE` for the Basic Constraints extension.
Wham! I can now generate certs for *EVERYONE*. At least until someone notices and takes away my shiny new toy...
So you would need 6000 years of computer time to compute the collision on the SHA1 signature, and how much additional time to compute the trapdoor (private) key, in order for the cert to be of any use?
On Sun, 26 Feb 2017, Keith Medcalf wrote:
So you would need 6000 years of computer time to compute the collision on the SHA1 signature, and how much additional time to compute the trapdoor (private) key, in order for the cert to be of any use?
1) Wasn't the 6000 years estimate from an article >10 years ago? Computers have gotten a bit faster. 2) I suspect the sort of person interested in doing this, unburdened by ethics, would have no issues using a large botnet to speed up the process. How long does it take if you have a million PCs working on the problem? ---------------------------------------------------------------------- Jon Lewis, MCP :) | I route | therefore you are _________ http://www.lewis.org/~jlewis/pgp for PGP public key_________
On Mon, 27 Feb 2017 07:23:43 -0500, Jon Lewis said:
On Sun, 26 Feb 2017, Keith Medcalf wrote:
So you would need 6000 years of computer time to compute the collision on the SHA1 signature, and how much additional time to compute the trapdoor (private) key, in order for the cert to be of any use?
1) Wasn't the 6000 years estimate from an article >10 years ago? Computers have gotten a bit faster.
No, Google's announcement last week said their POC took 6500 CPU-years for the first phase and 110 GPU-accelerated for the second phase. You are totally on target on your second point. A million node botnet reduces it to right around 60 hours.
Composed on a virtual keyboard, please forgive typos. On Feb 26, 2017, at 21:16, Matt Palmer <mpalmer@hezmatt.org> wrote:
On Sun, Feb 26, 2017 at 05:41:47PM -0600, Brett Frankenberger wrote:
On Sun, Feb 26, 2017 at 12:18:48PM -0500, Patrick W. Gilmore wrote: I repeat something I've said a couple times in this thread: If I can somehow create two docs with the same hash, and somehow con someone into using one of them, chances are there are bigger problems than a SHA1 hash collision.
If you assume I could somehow get Verisign to use a cert I created to match another cert with the same hash, why in the hell would that matter? I HAVE THE ONE VERISIGN IS USING. Game over.
Valdis came up with a possible use of such documents. While I do not think there is zero utility in those instances, they are pretty small vectors compared to, say, having a root cert at a major CA.
I want a google.com cert. I ask a CA to sign my fake google.com certificate. They decline, because I can't prove I control google.com.
Even better: I want a CA cert. I convince a CA to issue me a regular, end-entity cert for `example.com` (which I control) in such a way that I can generate another cert with the same SHA1 hash, but which has `CA:TRUE` for the Basic Constraints extension.
Wham! I can now generate certs for *EVERYONE*. At least until someone notices and takes away my shiny new toy...
Since I have said this somewhere on the order of half a dozen times, I will assume I am missing something obvious and all of you are doing it right. So let me ask you: The attack creates two docs. You do not know the hash before the attack starts. You cannot take an existing file with a known hash and create a second file which matches the known hash. You start with nothing, run the "attack", and get two NEW docs that have the same hash. A hash which is brand new. Now, please explain how you take a cert with one hash and somehow use this attack, which creates two new docs with a new hash, to do, well, anything? In the example above, the CA knows the SHA-1 hash of the cert it issued. (We are assuming there is a CA which still does SHA-1.) How do you get that CA to believe the two OTHER certs with DIFFERENT hashes you have to create so you can have two docs with the same hash? -- TTFN, patrick
On 26 February 2017 at 22:15, Patrick W. Gilmore <patrick@ianai.net> wrote:
Composed on a virtual keyboard, please forgive typos.
On Feb 26, 2017, at 21:16, Matt Palmer <mpalmer@hezmatt.org> wrote:
On Sun, Feb 26, 2017 at 05:41:47PM -0600, Brett Frankenberger wrote:
On Sun, Feb 26, 2017 at 12:18:48PM -0500, Patrick W. Gilmore wrote: I repeat something I've said a couple times in this thread: If I can somehow create two docs with the same hash, and somehow con someone into using one of them, chances are there are bigger problems than a SHA1 hash collision.
If you assume I could somehow get Verisign to use a cert I created to match another cert with the same hash, why in the hell would that matter? I HAVE THE ONE VERISIGN IS USING. Game over.
Valdis came up with a possible use of such documents. While I do not think there is zero utility in those instances, they are pretty small vectors compared to, say, having a root cert at a major CA.
I want a google.com cert. I ask a CA to sign my fake google.com certificate. They decline, because I can't prove I control google.com.
Even better: I want a CA cert. I convince a CA to issue me a regular, end-entity cert for `example.com` (which I control) in such a way that I can generate another cert with the same SHA1 hash, but which has `CA:TRUE` for the Basic Constraints extension.
Wham! I can now generate certs for *EVERYONE*. At least until someone notices and takes away my shiny new toy...
Since I have said this somewhere on the order of half a dozen times, I will assume I am missing something obvious and all of you are doing it right.
So let me ask you: The attack creates two docs. You do not know the hash before the attack starts. You cannot take an existing file with a known hash and create a second file which matches the known hash. You start with nothing, run the "attack", and get two NEW docs that have the same hash. A hash which is brand new.
Now, please explain how you take a cert with one hash and somehow use this attack, which creates two new docs with a new hash, to do, well, anything?
1. Create a certificate C[ert] for a single domain you control with hash h(c). 2. Create a second certificate A[ttack] marked as a certificate authority such that h(C) = h(A). 3. Have a certificate authority sign cert C 4. Present the signature for A along with A for whatever nefarious purpose you want. See a similar version of this attack here using MD5 chosen-prefix collision attack: https://www.win.tue.nl/hashclash/rogue-ca/ -- Eitan Adler
1. Create a certificate C[ert] for a single domain you control with hash h(c). 2. Create a second certificate A[ttack] marked as a certificate authority such that h(C) = h(A). 3. Have a certificate authority sign cert C 4. Present the signature for A along with A for whatever nefarious purpose you want.
luckily, step 2 can be done in a minute on a raspberry pi
On Mon, Feb 27, 2017 at 01:15:28AM -0500, Patrick W. Gilmore wrote:
On Feb 26, 2017, at 21:16, Matt Palmer <mpalmer@hezmatt.org> wrote:
Even better: I want a CA cert. I convince a CA to issue me a regular, end-entity cert for `example.com` (which I control) in such a way that I can generate another cert with the same SHA1 hash, but which has `CA:TRUE` for the Basic Constraints extension.
Wham! I can now generate certs for *EVERYONE*. At least until someone notices and takes away my shiny new toy...
In the example above, the CA knows the SHA-1 hash of the cert it issued. (We are assuming there is a CA which still does SHA-1.) How do you get that CA to believe the two OTHER certs with DIFFERENT hashes you have to create so you can have two docs with the same hash?
This is doable because the data that goes into the cert is mostly predictable (or attacker controlled). The public key is provided by the attacker; the subject and sAN extension is attacker-provided, and a lot of the rest is predictable (issuer, policy OIDs, etc etc). Even the notBefore and notAfter fields are, to some degree, predictable; you can measure the average issuance delay to figure out when you need to submit your CSR(s) to get favourable timestamps, and many CAs "round" values, to make that easier. Thus, constructing a "dummy" TBSCertificate ("to-be-signed certificate") to play with isn't difficult. The mitigation to a chosen prefix attack (which is what this is) is to make the serial number a random number. The CA/Browser Forum Baseline Requirements (the agreed-upon rules between CAs and browsers) say that you need to put "at least 64 bits of randomness" into the serial number field, which supposedly mitigates this. Unfortunately, that isn't a property you can easily determine by observation, and I'll bet dollars to donuts it isn't audited, so whether that would stand up to a determined attacker is a Rumsfeldian question.. - Matt
On Mon, 27 Feb 2017 01:15:28 -0500, "Patrick W. Gilmore" said:
In the example above, the CA knows the SHA-1 hash of the cert it issued. (We are assuming there is a CA which still does SHA-1.) How do you get that CA to believe the two OTHER certs with DIFFERENT hashes you have to create so you can have two docs with the same hash?
There's only 2 certs. You generate 2 certs with the same hash, and *then* get the CA to sign one of them.
Once upon a time, valdis.kletnieks@vt.edu <valdis.kletnieks@vt.edu> said:
There's only 2 certs. You generate 2 certs with the same hash, and *then* get the CA to sign one of them.
The point is that the signed cert you get back from the CA will have a different hash, and the things that they change that cause the hash to change are outside your control and prediction. -- Chris Adams <cma@cmadams.net>
The CA signing the cert actually changes the fingerprint (and serial number, which is what is checked on revocation lists), so this is not a viable scenario. Beyond that, SHA1 signing of certificates has long been deprecated and no new public CAs will sign a CSR and cert with SHA1.
On Feb 27, 2017, at 8:18 AM, Chris Adams <cma@cmadams.net> wrote:
Once upon a time, valdis.kletnieks@vt.edu <valdis.kletnieks@vt.edu> said:
There's only 2 certs. You generate 2 certs with the same hash, and *then* get the CA to sign one of them.
The point is that the signed cert you get back from the CA will have a different hash, and the things that they change that cause the hash to change are outside your control and prediction.
-- Chris Adams <cma@cmadams.net>
Even with massive computing power, the tampering is still detectable since this attack does not allow for the creation of a hash collision from any arbitrary document. It requires specific manipulation of all items that result in a collision.
On Feb 27, 2017, at 7:39 AM, valdis.kletnieks@vt.edu wrote:
On Mon, 27 Feb 2017 07:23:43 -0500, Jon Lewis said:
On Sun, 26 Feb 2017, Keith Medcalf wrote:
So you would need 6000 years of computer time to compute the collision on the SHA1 signature, and how much additional time to compute the trapdoor (private) key, in order for the cert to be of any use?
1) Wasn't the 6000 years estimate from an article >10 years ago? Computers have gotten a bit faster.
No, Google's announcement last week said their POC took 6500 CPU-years for the first phase and 110 GPU-accelerated for the second phase.
You are totally on target on your second point. A million node botnet reduces it to right around 60 hours.
On Tue, Feb 28, 2017 at 01:16:23PM -0600, James DeVincentis via NANOG wrote:
The CA signing the cert actually changes the fingerprint
The what? RFC5280 does not contain the string "finger".
(and serial number, which is what is checked on revocation lists)
The CA doesn't "change" the serial number (a CSR doesn't have a place to even ask for a serial), they pick one, and while it's *supposed* to be at least partially random, given the largely appalling state of CA operations (and, even worse, the competence of the auditors who are supposed to be making sure they're doing the right thing), I'd be awfully surprised if there wasn't at least one CA in a commonly-used trust store which was issuing certificates with predictable serial numbers.
Beyond that, SHA1 signing of certificates has long been deprecated and no new public CAs will sign a CSR and cert with SHA1.
Except all the ones that the payment industry (there's a group with no stake in good security, huh?) have managed to convince browsers to allow (thankfully, they get a good counter-cryptanalysis over them first), and all the ones that have been issued "by mistake" to inconsequential organisations like, say, HMRC (which just appear in CT logs, and the vigilance of the community finds and brings to the attention of trust stores). - Matt -- <Igloo> I remember going to my first tutorial in room 404. I was most upset when I found it.
The what? RFC5280 does not contain the string "finger".
The CA doesn't "change" the serial number (a CSR doesn't have a place to even ask for a serial), they pick one, and while it's *supposed* to be at least partially random, given the largely appalling state of CA operations (and, even worse, the competence of the auditors who are supposed to be making sure they're doing the right thing), I'd be awfully surprised if
Except all the ones that the payment industry (there's a group with no stake in good security, huh?) have managed to convince browsers to allow (thankfully, they get a good counter-cryptanalysis over them first), and all
The fingerprint (or thumbprint) is the hash (sha1/sha256) of the certificate data in DER format, it's not part of the actual certificate. The fingerprint is largely used in the security and development community in order to quickly identify a unique certificate. Application developers (See: Google, Microsoft, Apple, etc) also hard-code fingerprints into applications to defend against anyone attempting to MITM the traffic (for obscurity or security purposes). Fingerprints are used instead of serial numbers since two CAs can issue two certificates with the same serial number. It's also the fastest way to determine the identity of a certificate without examining individual data in certificates. there wasn't at least one CA in a commonly-used trust store which was issuing certificates with predictable serial numbers. Predictable serial numbers still wouldn't help you here and certificates contain multiple unique identifiers. There's a massive brute force component to this attack as well, both the "good" and "bad" certificate would have to be brute forced. Let's also remember the ONLY example of this so far is PDF documents where massive amounts of data can be hidden in order to manipulate the hashes. This isn't the case with certificates. On the subject of the example documents. The example documents given are unbelievably basic in their differing appearances and the attack is _easily_ detected. the ones that have been issued "by mistake" to inconsequential organizations like, say, HMRC (which just appear in CT logs, and the vigilance of the community finds and brings to the attention of trust stores). Again, this attack doesn't work on any existing arbitrary item and is easily detected. So any existing item is safe until a preimage attack is found. The sky is not falling. The most this will affect is generation of unique identifiers (which is not security related) using the SHA1 algorithm. This has already been seen when trying to commit both of the example PDF documents to a git repository. This whole situation is being blown way out of proportion and significantly oversimplified. This is a PR stunt by Google to keep to their timeline from when they cried the sky was falling years ago about SHA1 (https://security.googleblog.com/2014/09/gradually-sunsetting-sha-1.html). Nine quintillion (9,223,372,036,854,775,808) SHA1 computations in total 6,500 years of CPU computation to complete the attack first phase = 56,940,000 hours CPU time 110 years of GPU computation to complete the second phase = 963,600 hours GPU time Those statistics are nowhere near real world for ROI. You'd have to invest at least 7 figures (USD) in resources. So the return must be millions of dollars before anyone can detect the attack. Except, it's already detectable. Google nullified their point of demonstrating the attack by showing it was easily detectable. -----Original Message----- From: NANOG [mailto:nanog-bounces@nanog.org] On Behalf Of Matt Palmer Sent: Wednesday, March 1, 2017 1:34 PM To: nanog@nanog.org Subject: Re: SHA1 collisions proven possisble On Tue, Feb 28, 2017 at 01:16:23PM -0600, James DeVincentis via NANOG wrote:
The CA signing the cert actually changes the fingerprint
The what? RFC5280 does not contain the string "finger".
(and serial number, which is what is checked on revocation lists)
The CA doesn't "change" the serial number (a CSR doesn't have a place to even ask for a serial), they pick one, and while it's *supposed* to be at least partially random, given the largely appalling state of CA operations (and, even worse, the competence of the auditors who are supposed to be making sure they're doing the right thing), I'd be awfully surprised if there wasn't at least one CA in a commonly-used trust store which was issuing certificates with predictable serial numbers.
Beyond that, SHA1 signing of certificates has long been deprecated and no new public CAs will sign a CSR and cert with SHA1.
Except all the ones that the payment industry (there's a group with no stake in good security, huh?) have managed to convince browsers to allow (thankfully, they get a good counter-cryptanalysis over them first), and all the ones that have been issued "by mistake" to inconsequential organisations like, say, HMRC (which just appear in CT logs, and the vigilance of the community finds and brings to the attention of trust stores). - Matt -- <Igloo> I remember going to my first tutorial in room 404. I was most upset when I found it.
On Wed, 01 Mar 2017 15:28:23 -0600, "james.d--- via NANOG" said:
Those statistics are nowhere near real world for ROI. You'd have to invest at least 7 figures (USD) in resources. So the return must be millions of dollars before anyone can detect the attack. Except, it's already detectable.
*Somebody* has to invest 7 figures in resources. Doesn't have to be you. Remember that if you have access to a 1M node botnet, you could have 56,940,000 hours of CPU time racked racked up in... under 60 hours.
Keep in mind botnets that large are comprised largely of IoT devices which have very little processing power compared to the massive multi-core, high frequency, high memory bandwidth (this is especially important for cryptographic operations) CPUs in data centers. It doesn’t take much processing power to launch DDoS attacks so that’s why IoT is perfect for botnets. Those botnets which have desktop grade systems are also comprised of typically older machines that go unpatched and do not have high end server CPUs or GPUs. A botnet is also not going to get you the high end GPUs you need for phase 2. Generally the people with hardcore GPUs are gamers and workstation users that push those GPUs. They're going to notice the GPUs being utilized abnormally. On top of that, the calculations they did were for a stupidly simple document modification in a type of document where hiding extraneous data is easy. This will get exponentially computationally more expensive the more data you want to mask. It took nine quintillion computations in order to mask a background color change in a PDF. And again, the main counter-point is being missed. Both the good and bad documents have to be brute forced which largely defeats the purpose. Tthose numbers of computing hours are a brute force. It may be a simplified brute force, but still a brute force. The hype being generated is causing management at many places to cry exactly what Google wanted, “Wolf! Wolf!”.
On Mar 1, 2017, at 6:22 PM, valdis.kletnieks@vt.edu wrote:
On Wed, 01 Mar 2017 15:28:23 -0600, "james.d--- via NANOG" said:
Those statistics are nowhere near real world for ROI. You'd have to invest at least 7 figures (USD) in resources. So the return must be millions of dollars before anyone can detect the attack. Except, it's already detectable.
*Somebody* has to invest 7 figures in resources. Doesn't have to be you.
Remember that if you have access to a 1M node botnet, you could have 56,940,000 hours of CPU time racked racked up in... under 60 hours.
James DeVincentis via NANOG wrote:
On top of that, the calculations they did were for a stupidly simple document modification in a type of document where hiding extraneous data is easy. This will get exponentially computationally more expensive the more data you want to mask. It took nine quintillion computations in order to mask a background color change in a PDF.
And again, the main counter-point is being missed. Both the good and bad documents have to be brute forced which largely defeats the purpose. Tthose numbers of computing hours are a brute force. It may be a simplified brute force, but still a brute force.
The hype being generated is causing management at many places to cry exactly what Google wanted, “Wolf! Wolf!”.
The Reaction state table described in https://valerieaurora.org/hash.html appears to be entertainingly accurate. Nick
On Thu, Mar 02, 2017 at 03:42:12AM +0000, Nick Hilliard wrote:
James DeVincentis via NANOG wrote:
On top of that, the calculations they did were for a stupidly simple document modification in a type of document where hiding extraneous data is easy. This will get exponentially computationally more expensive the more data you want to mask. It took nine quintillion computations in order to mask a background color change in a PDF.
And again, the main counter-point is being missed. Both the good and bad documents have to be brute forced which largely defeats the purpose. Tthose numbers of computing hours are a brute force. It may be a simplified brute force, but still a brute force.
The hype being generated is causing management at many places to cry exactly what Google wanted, “Wolf! Wolf!”.
The Reaction state table described in https://valerieaurora.org/hash.html appears to be entertainingly accurate.
With particular reference to the "slashdotter" column. - Matt
Let me add some context to the discussion. I run threat and vulnerability management for a large financial institution. This attack falls under our realm. We’ve had a plan in progress for several years to migrate away from SHA-1. We’ve been carefully watching the progression of the weakening of SHA-1 as computing power has increased and access to large-scale computing has become standard over the last 5 years. This does nothing to change our timeline. The attack does nothing to prove anything we already didn’t know. As computing power increases we must change hashing mechanisms every few years. This is why this is no surprise to us in the security sphere. However the presentation of this particular information has been following a very troublesome trend we’ve been seeing in the security sphere. Naming a vulnerability something silly but easily rememberable by management types. ‘HeartBleed’, ‘Shattered’, ‘CloudBleed’, ‘SomethingBleed’… This is a publicity stunt by Google to whip up a hype and it worked. Case in point, are some of the posts in this thread that completely dismiss fact for assumption and embellishment. With specific regard to SSL certificates: "Are TLS/SSL certificates at risk? Any Certification Authority abiding by the CA/Browser Forum regulations is not allowed to issue SHA-1 certificates anymore. Furthermore, it is required that certificate authorities insert at least 64 bits of randomness inside the serial number field. If properly implemented this helps preventing a practical exploitation.” (https://shattered.it/ <https://shattered.it/>). It seems not all of the news outlets read the entire page before typing up a sensationalist post claiming all your data is at risk suddenly. Here’s why this is sensationalist. If anyone with *actual* hands-on work in the *security* sphere in *recent* years disagrees, I’ll be happy to discuss. - Hardened SHA1 exists to prevent this exact type of attack. - Every hash function will eventually have collisions. It’s literally impossible to create a hashing function that will never have a collision. There are an infinite number of inputs that can go into a hash function. There are a finite number of outputs of a hash function. Hash functions create an implausibility of a collision. That’s it. There is no 100% certainty that any hash function will not have collisions. - Google created a weak example. The difference in the document they generated was a background color. They didn’t even go a full RGBA difference. They went from Red to Blue. That’s a difference of 4 bytes (R and B values). It took them nine quintillion computations to generate the correct spurious data to create a collision when they controlled both the documents with a 4 byte difference. That spurious data inflated the PDF by at least a few hundred KB. Imagine the computations it would take for the examples they give? Anyone know? No. They didn’t dare attempt it because they knew it’s not possible. - This wasn’t even an attack on a cryptographic method that utilizes SHA1. This was a unique identifier / integrity attack. Comparing an SHA1 hash is not the correct way to verify authenticity of a document. Comparing an SHA1 how you verify integrity of a document, looking for corruption. Authenticity is derived from having the data signed from a trusted source or encrypted using say PGP from a trusted source. - And last but not least.. which takes all of the bite out of the attack. Google also showed it was easily detectable. Is a weakness or attack on a hash function really viable of it’s easily and readily detectable? No. It’s not. (See: IDS, WAFs: They filter and detect attacks against systems that may be vulnerable and prevent them by checking for the attacks). So If I see a hash collision? I’ll modify the algorithm… Wait.. This sounds awfully familiar.. Oh yea… Hardened SHA1. With all of these reasons all wrapped up. It clearly shows the level of hype around this attack is the result of sensationalist articles and clickbait titles. It also appears the majority of those who embrace fact also abandoned this thread fairly early once it began to devolve into embracing sensationalism. I’m going to join them. *micdrop* *unsubscribe*
On Mar 1, 2017, at 9:49 PM, Matt Palmer <mpalmer@hezmatt.org> wrote:
On Thu, Mar 02, 2017 at 03:42:12AM +0000, Nick Hilliard wrote:
James DeVincentis via NANOG wrote:
On top of that, the calculations they did were for a stupidly simple document modification in a type of document where hiding extraneous data is easy. This will get exponentially computationally more expensive the more data you want to mask. It took nine quintillion computations in order to mask a background color change in a PDF.
And again, the main counter-point is being missed. Both the good and bad documents have to be brute forced which largely defeats the purpose. Tthose numbers of computing hours are a brute force. It may be a simplified brute force, but still a brute force.
The hype being generated is causing management at many places to cry exactly what Google wanted, “Wolf! Wolf!”.
The Reaction state table described in https://valerieaurora.org/hash.html appears to be entertainingly accurate.
With particular reference to the "slashdotter" column.
- Matt
On Wed, Mar 1, 2017 at 7:57 PM, James DeVincentis via NANOG <nanog@nanog.org> wrote: [ reasonable analysis snipped :) ]
With all of these reasons all wrapped up. It clearly shows the level of hype around this attack is the result of sensationalist articles and clickbait titles.
I have trouble believing that Sleevi, Whalley et al spent years championing the uphill slog of purging the global web PKI infrastructure of SHA-1 to culminate in a flash-in-the-pan clickbait party. Instead, consider how long it has historically taken to pry known-to-be-weak hashes and crypto from entrenched implementations. If this round of hype actually scares CxOs and compliance bodies into doing The Right Thing in advance ... then the hype doesn't bother me in the slightest. Royce
On Wed, Mar 1, 2017 at 10:57 PM, James DeVincentis via NANOG <nanog@nanog.org> wrote:
Let me add some context to the discussion.
With specific regard to SSL certificates: "Are TLS/SSL certificates at risk? Any Certification Authority abiding by the CA/Browser Forum regulations is not allowed to issue SHA-1 certificates anymore. Furthermore, it is required that certificate authorities insert at least 64 bits of randomness inside the serial number field. If properly implemented this helps preventing a practical exploitation.”
Yes, they are at risk, of course. This latest technique does not appear able to be used to attack certificates, however. Subscribers to a CA don't have sufficient control of the contents of the signed certificates a CA will issue; Even if they did, the computational requirement with the described attack is likely to be slightly out of reach. The attack is not such that certs can be directly spoiled, *YET*; However, It is almost surely a high likely possibility in the forseeable future, and the existence of this attack does serve as valid evidence further solidifying that the risk is very High now for crypto applications of the SHA1 digest, of further collision attacks against SHA1 being made practical in the forseeable future with very little or no further warning. If you are still using SHA1 and were expecting to use it forever.... This attack is what gives you your fair warning, that in 6 or 7 years, brute-forcing your SHA1 will likely be within reach of the average script kiddie. This does not fundamentally change security expectations for SHA1, such attack now being feasible with Google's resources is well-within expectations; However, the "Hype" should be a wake-up call to some developers who continue to write new software relying upon SHA1 for security under a false belief that SHA1 digest is still almost certain to be fundamentally sound crypto for many years to come. If you are writing a program expected to be in use 5 years from now, and believe SHA1 will continue to meet your existing security requirements. time to rethink that, and realize the risk is very high for SHA1 becoming insecure within a decade. If the "Hype" behind this Google thing is the catalyst that makes some developers think about the future of their choice of crypto algorithms more carefully before relying upon them, then that is a good thing.
- Hardened SHA1 exists to prevent this exact type of attack.
I suppose hardened SHA1 is a non-standard kludge of questionable durability. Sure, implement as a work-around for the current attack. But the future-going risk of continuing to use SHA1 remains qualitatively high.
- Every hash function will eventually have collisions. It’s literally impossible to create a hashing function that will never have a collision. [snip]
There may be hashing functions which are likely to never have a practical collision discovered by humans, because of their size and improbability. It's mostly a matter of the computing power currently available VS size and qualities of the hash.
- Google created a weak example. The difference in the document they generated was a background color. They didn’t even go a full RGBA difference. They went from Red to Blue. That’s a difference of 4 bytes (R and B values). It took them nine quintillion computations to generate the
With some applications; you'd be surprised what evil things you can do if you change 4 Bytes to a malicious value..... For example; If you're digitally signing a binary, 4 Bytes is maybe enough to overwrite a machine language instruction, introducing an exploitable bug into the machine code. That latest attack on SHA1 will not allow code signing following typical code signing algorithms to be attacked. -- -JH
On Wed, 01 Mar 2017 22:57:06 -0600, James DeVincentis via NANOG said:
- Google created a weak example. The difference in the document they generated was a background color. They didn’t even go a full RGBA difference. They went from Red to Blue. That’s a difference of 4 bytes (R and B values). It took them nine quintillion computations to generate the correct spurious data to create a collision when they controlled both the documents with a 4 byte difference. That spurious data inflated the PDF by at least a few hundred KB.
Note that we haven't actually seen the algorithm yet. And it's quite possible that Google intentionally limited it to a *very visible* 4 byte change, so that just opening a PDF viewer of both documents is sufficient to demonstrate that a change was made. As a result, we can't rule out the possibility that "size of altered data plus/ times size of spurious data" equals a constant - in other words, limiting the change to 4 bytes causes a lot of spurious data, but careful choice of a larger number of altered bits results in a smaller spurious pile of bits. It *may* be possible to totally stash all the spurious bits elsewhere in the object via steganographic means - consider for instance a video stream. It may be possible to splice in/out a significant segment of video (possibly CGI'ed), and hide all the spurious bits in one/two bit changes in the rest of the stream. Remember that in a good hash function, changing one input bit should on average change close to half the output bits. So how many bits get changed by 2, or 3, or 4 bit of input change? If the attack is based on the ability to bias that "on average" in one direction or another, it's quite possible that applying a bias across 128 changed input bits is actually *easier* than when you only have 32 bit of change bias to apply....
They didn’t dare attempt it because they knew it’s not possible.
As I point out above, we don't actually know that for a fact.
I like the footnote they attached specifically for SHA1. "[3] Google spent 6500 CPU years and 110 GPU years to convince everyone we need to stop using SHA-1 for security critical applications. Also because it was cool." It’s also not preimage. This isn’t even a FIRST preimage attack. That table needs an additional field type: “First non-preimage deliberate crafted collision created”. However, it proves a theory that maybe with some refining *could* turn into a preimage attack. Realistically any hash function *will* have collisions when two items are specifically crafted to collide after expending insane amounts of computing power, money, and… i wonder how much in power they burned for this little stunt.
On Mar 1, 2017, at 9:42 PM, Nick Hilliard <nick@foobar.org> wrote:
James DeVincentis via NANOG wrote:
On top of that, the calculations they did were for a stupidly simple document modification in a type of document where hiding extraneous data is easy. This will get exponentially computationally more expensive the more data you want to mask. It took nine quintillion computations in order to mask a background color change in a PDF.
And again, the main counter-point is being missed. Both the good and bad documents have to be brute forced which largely defeats the purpose. Tthose numbers of computing hours are a brute force. It may be a simplified brute force, but still a brute force.
The hype being generated is causing management at many places to cry exactly what Google wanted, “Wolf! Wolf!”.
The Reaction state table described in https://valerieaurora.org/hash.html appears to be entertainingly accurate.
Nick
On 3/1/2017 10:50 PM, James DeVincentis via NANOG wrote:
Realistically any hash function *will* have collisions when two items are specifically crafted to collide after expending insane amounts of computing power, money, and… i wonder how much in power they burned for this little stunt.
Easy enough to estimate. A dual-socket server with 2 X5675 CPUs (12 cores total) draws about 225W under full load, or about 18.75W per core. 0.01875 kW * 8766 h/y * 6500 y = about 1,070,000 kWh For the GPU side, an NVIDIA Tesla K80 GPU accelerator draws 300W at full load. 0.3 kW * 8766 h/y * 110 y = about 290,000 kWh. So the total calculation consumed about 1.36M kWh. A quick Google search tells me the US national average industrial rate for electricity is $0.0667/kWh, for a cost of $90,712. That's not counting AC-DC conversion loss, or the power to run the cooling. Or the cost of the hardware, though it's fair to assume that in Google's case they didn't have to buy any new hardware just for this.
On 23 February 2017 at 20:59, Ca By <cb.list6@gmail.com> wrote:
On Thu, Feb 23, 2017 at 10:27 AM Grant Ridder <shortdudey123@gmail.com> wrote:
Coworker passed this on to me.
Looks like SHA1 hash collisions are now achievable in a reasonable time period https://shattered.io/
-Grant
Good thing we "secure" our routing protocols with MD5
:)
One place that use sha1 seems to be some banking gateways. They sign the parameters of some request to authentificate the request has a valid one doing something like "sha1( MerchantID . secureCode . TerminalID . amount . exponent . moneyCode )". I have no idea how evil people would exploit collisions here, but I guest banking will move to the next hash algorithm (sha256?) and deprecate this one. This may affect more "Mom and Pa Online Shop" than bigger services. -- -- ℱin del ℳensaje.
participants (25)
-
Brett Frankenberger -
Ca By -
Chris Adams -
David Edelman -
Eitan Adler -
Florian Weimer -
Grant Ridder -
J. Hellenthal -
James DeVincentis -
james.d＠hexhost.net
-
Jimmy Hess -
Jon Lewis -
Keith Medcalf -
Lyndon Nerenberg -
Matt Palmer -
Nick Hilliard -
Patrick W. Gilmore -
Peter Kristolaitis -
Randy Bush -
Richard Hesse -
Ricky Beam -
Royce Williams -
Tei -
valdis.kletnieks＠vt.edu -
Vincent Bernat