Re: SHA1 collisions proven possisble

[valdis . kletnieks]

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.



pgpfckjU84d31.pgp
Description: PGP signature

Re: SHA1 collisions proven possisble

[Jimmy Hess]

On Wed, Mar 1, 2017 at 10:57 PM, James DeVincentis via NANOG
 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

Re: SHA1 collisions proven possisble

[Peter Kristolaitis]

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.

Re: SHA1 collisions proven possisble

[Royce Williams]

On Wed, Mar 1, 2017 at 7:57 PM, James DeVincentis via NANOG
 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

Re: SHA1 collisions proven possisble

[James DeVincentis via NANOG]

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/ ). 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  wrote:
> 
> On Thu, Mar 02, 2017 at 03:42:12AM +, 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 

Re: SHA1 collisions proven possisble

[James DeVincentis via NANOG]

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  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

Re: SHA1 collisions proven possisble

[Matt Palmer]

On Thu, Mar 02, 2017 at 03:42:12AM +, 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

Re: SHA1 collisions proven possisble

[Nick Hilliard]

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

Re: SHA1 collisions proven possisble

[James DeVincentis via NANOG]

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.kletni...@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.
> 

Re: SHA1 collisions proven possisble

[valdis . kletnieks]

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.



pgpjrUioHTAsh.pgp
Description: PGP signature

RE: SHA1 collisions proven possisble

[james.d--- via NANOG]

> The what?  RFC5280 does not contain the string "finger".

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. 

> 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.

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.  

> 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 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-boun...@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 

Re: SHA1 collisions proven possisble

[Matt Palmer]

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

-- 
 I remember going to my first tutorial in room 404. I was most upset
when I found it.

Re: SHA1 collisions proven possisble

[James DeVincentis via NANOG]

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  wrote:
> 
> Once upon a time, valdis.kletni...@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 


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.kletni...@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.

Re: SHA1 collisions proven possisble

[Chris Adams]

Once upon a time, valdis.kletni...@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 

Re: SHA1 collisions proven possisble

[valdis . kletnieks]

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.


pgpPefENeKROE.pgp
Description: PGP signature

RE: SHA1 collisions proven possisble

[Jon Lewis]

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_

Re: SHA1 collisions proven possisble

[valdis . kletnieks]

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.


pgp0_PR3wBTEZ.pgp
Description: PGP signature

Re: SHA1 collisions proven possisble

[Randy Bush]

> 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

Re: SHA1 collisions proven possisble

[Matt Palmer]

On Mon, Feb 27, 2017 at 01:15:28AM -0500, Patrick W. Gilmore wrote:
> On Feb 26, 2017, at 21:16, Matt Palmer  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

Re: SHA1 collisions proven possisble

[Eitan Adler]

On 26 February 2017 at 22:15, Patrick W. Gilmore  wrote:
> Composed on a virtual keyboard, please forgive typos.
>
> On Feb 26, 2017, at 21:16, Matt Palmer  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

Re: SHA1 collisions proven possisble

[Patrick W. Gilmore]

Composed on a virtual keyboard, please forgive typos. 

On Feb 26, 2017, at 21:16, Matt Palmer  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

Re: SHA1 collisions proven possisble

[Randy Bush]

> 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

RE: SHA1 collisions proven possisble

[Keith Medcalf]

On Sunday, 26 February, 2017 19:16 Matt Palmer  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?

Re: SHA1 collisions proven possisble

[Matt Palmer]

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

Re: SHA1 collisions proven possisble

[Brett Frankenberger]

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

Re: SHA1 collisions proven possisble

[Nick Hilliard]

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

Re: SHA1 collisions proven possisble

[Patrick W. Gilmore]

On Feb 25, 2017, at 17:44, Jimmy Hess  wrote:
>> On Thu, Feb 23, 2017 at 2:03 PM, Patrick W. Gilmore  
>> 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

Re: SHA1 collisions proven possisble

[Jimmy Hess]

On Thu, Feb 23, 2017 at 2:03 PM, Patrick W. Gilmore  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

Re: SHA1 collisions proven possisble

[valdis . kletnieks]

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-the-webkit-repository-others-may-follow/


pgpPrkgPY4ePX.pgp
Description: PGP signature

Re: SHA1 collisions proven possisble

[Richard Hesse]

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 
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  wrote:
>
> > On Thu, 23 Feb 2017 15:03:34 -0500, Patrick W. Gilmore <
> patr...@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)]
>

Re: SHA1 collisions proven possisble

[Patrick W. Gilmore]

On Feb 24, 2017, at 12:04 PM, Vincent Bernat  wrote:
> ❦ 23 février 2017 21:16 -0500, "Patrick W. Gilmore"  :
> 
>> 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

Re: SHA1 collisions proven possisble

[Vincent Bernat]

 ❦ 23 février 2017 21:16 -0500, "Patrick W. Gilmore"  :

> 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"

Re: SHA1 collisions proven possisble

[Vincent Bernat]

 ❦ 23 février 2017 19:28 -0500, Jon Lewis  :

>>> 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

Re: SHA1 collisions proven possisble

[Florian Weimer]

* 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.

Re: SHA1 collisions proven possisble

[Tei]

On 23 February 2017 at 20:59, Ca By  wrote:

> On Thu, Feb 23, 2017 at 10:27 AM Grant Ridder 
> 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.

RE: SHA1 collisions proven possisble

[David Edelman]

Especially if that "document" is a component of a ciphersuite exchange.

--Dave

-Original Message-
From: NANOG [mailto:nanog-boun...@nanog.org] On Behalf Of
valdis.kletni...@vt.edu
Sent: Thursday, February 23, 2017 9:22 PM
To: Ricky Beam <jfb...@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.

Re: SHA1 collisions proven possisble

[Lyndon Nerenberg]

> On Feb 23, 2017, at 6:10 PM, Ricky Beam  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

Re: SHA1 collisions proven possisble

[valdis . kletnieks]

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.




pgpG0C2y9fYJL.pgp
Description: PGP signature

Re: SHA1 collisions proven possisble

[Patrick W. Gilmore]

On Feb 23, 2017, at 9:08 PM, valdis.kletni...@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



signature.asc
Description: Message signed with OpenPGP

Re: SHA1 collisions proven possisble

[Ricky Beam]

On Thu, 23 Feb 2017 18:21:19 -0500,  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.)

Re: SHA1 collisions proven possisble

[valdis . kletnieks]

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




pgpaKcy9lQzuO.pgp
Description: PGP signature

Re: SHA1 collisions proven possisble

[Patrick W. Gilmore]

On Feb 23, 2017, at 6:21 PM, valdis.kletni...@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

Re: SHA1 collisions proven possisble

[valdis . kletnieks]

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*.


pgp9FXqhe7BGY.pgp
Description: PGP signature

Re: SHA1 collisions proven possisble

[Jon Lewis]

On Thu, 23 Feb 2017, valdis.kletni...@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_

Re: SHA1 collisions proven possisble

[Royce Williams]

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 
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  wrote:
>
> > On Thu, 23 Feb 2017 15:03:34 -0500, Patrick W. Gilmore <
> patr...@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)]
>

Re: SHA1 collisions proven possisble

[valdis . kletnieks]

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?


pgpOh0RfsKd9Y.pgp
Description: PGP signature

Re: SHA1 collisions proven possisble

[J. Hellenthal]

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  wrote:

> On Thu, 23 Feb 2017 15:03:34 -0500, Patrick W. Gilmore  
> 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)]

Re: SHA1 collisions proven possisble

[Ricky Beam]

On Thu, 23 Feb 2017 15:03:34 -0500, Patrick W. Gilmore   
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)]

Re: SHA1 collisions proven possisble

[valdis . kletnieks]

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.


pgpnNFrBlLfFP.pgp
Description: PGP signature

Re: SHA1 collisions proven possisble

[Patrick W. Gilmore]

On Feb 23, 2017, at 2:59 PM, Ca By  wrote:
> On Thu, Feb 23, 2017 at 10:27 AM Grant Ridder  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

Re: SHA1 collisions proven possisble

[Ca By]

On Thu, Feb 23, 2017 at 10:27 AM Grant Ridder 
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

:)


>