Why it’s harder to forge a SHA-1 certificate than to find a SHA-1 collision • Hacker News Board

Re: Why it’s harder to forge a SHA-1 certificate than to find a SHA-1 collision

#11

Post by pcl » Tue, Dec 22, 2015, 7:53 PM UTC

TazeTSchnitzel wrote: post #8

$ curl -s https://blog.cloudflare.com/content/images/2015/08/white.jpg | md5 ccf22bc377846166ed65cd3cd58d2e3d $ curl -s https://blog.cloudflare.com/content/images/2015/08/brown.jpg | md5 810cac197d97da7b216c7883be523495 $ curl -s https://blog.cloudflare.com/content/images/2015/08/black.jpg | md5 6bede506abffe08d0c2406d92fbff393 Let me guess, the CloudFlare CDN is recompressing the images? :D

If you download the files to disk, you'll get the right values:

    $ curl -s https://blog.cloudflare.com/content/images/2015/08/white.jpg > file && md5 file                                                 
    MD5 (file) = b69dd1fd1254868b6e0bb8ed9fe7ecad

I've seen this same sort of thing happen with curl in other contexts, but I've never tracked down the details. I assume it has something to do with file stream handling in certain versions of curl. You'll see a discrepancy if you look at the output of piping to 'wc' vs. examining the downloaded file.

Re: Why it’s harder to forge a SHA-1 certificate than to find a SHA-1 collision

#12

Post by gue5t » Tue, Dec 22, 2015, 7:53 PM UTC

bracewel wrote: post #3

Guh, until CF/FB can provide some data that shows users with no upgrade path are genuinely going to be effected by this, and not connections MITM'd by some crappy AV or other random middlebox the LV proposal seems like a pretty silly idea... https://www.cabforum.org/pipermail/public/2015-December/0064...

Software "with no upgrade path" that hasn't been proven correct relative to a formal specification and deployed in an appropriate context (sufficient conditions to consider it a "not software" black box) should be considered a mistake and the responsible parties should be held accountable for reparations. Complacency with its continued existence is unsustainable.

Obviously this is an idealistic "should", but we need to take every available step to move towards this stance because a policy of limiting the networked universe based on the worst common denominator client results in an inescapable black hole of technical debt.

Open-source software plays into this model beautifully because it makes it much easier to propagate improvements across the entire space of systems. There remain some problems such as langauge interoperability ("best implementation of protocol X is in language Y but our system is written in Z and the Y-Z interop story is bad") which I'd like to see people give more attention. We need to address the quadratic workload of porting/binding every library to every language.

Re: Why it’s harder to forge a SHA-1 certificate than to find a SHA-1 collision

#13

Post by grittygrease » Tue, Dec 22, 2015, 7:58 PM UTC

TazeTSchnitzel wrote: post #8

$ curl -s https://blog.cloudflare.com/content/images/2015/08/white.jpg | md5 ccf22bc377846166ed65cd3cd58d2e3d $ curl -s https://blog.cloudflare.com/content/images/2015/08/brown.jpg | md5 810cac197d97da7b216c7883be523495 $ curl -s https://blog.cloudflare.com/content/images/2015/08/black.jpg | md5 6bede506abffe08d0c2406d92fbff393 Let me guess, the CloudFlare CDN is recompressing the images? :D

Good catch. CloudFlare's optimizations are often too good for their own good. Fixing.

Re: Why it’s harder to forge a SHA-1 certificate than to find a SHA-1 collision

#14

Post by davesque » Tue, Dec 22, 2015, 8:03 PM UTC

ben174 wrote: post #7

Odd, I'm getting completely different MD5s from the three example images. ~ curl -s https://blog.cloudflare.com/content/images/2015/08/white.jpg | md5 ccf22bc377846166ed65cd3cd58d2e3d ~ curl -s https://blog.cloudflare.com/content/images/2015/08/brown.jpg | md5 810cac197d97da7b216c7883be523495 ~ curl -s https://blog.cloudflare.com/content/images/2015/08/black.jpg | md5 6bede506abffe08d0c2406d92fbff393

Cloud flare is mucking around with the payload to save some bytes, probably.

Re: Why it’s harder to forge a SHA-1 certificate than to find a SHA-1 collision

#15

Post by dsp1234 » Tue, Dec 22, 2015, 8:05 PM UTC

ademarre wrote: post #5

Nice write-up, but it's slightly misleading or confusing to not explain that Nat McHugh's image collisions were chosen-prefix attacks. The post makes it sound like the images were the product of some unexplained collision, and then goes on to explain how chosen prefix can be used to forge certificates.

to not explain that Nat McHugh's image collisions were chosen-prefix attacks.

In the paragraph right before those images, it says:

"This was cleverly demonstrated by Nat McHugh, who used a chosen-prefix hash collision"

Re: Why it’s harder to forge a SHA-1 certificate than to find a SHA-1 collision

#16

Post by EGreg » Tue, Dec 22, 2015, 8:18 PM UTC

agwa wrote: post #4

We're lucky that hash collision attacks have a relatively simple mitigation like this. (Although you have to trust CAs to follow the rules and implement it properly, and events of the last few years indicate that CAs need to have as few things to screw up as possible.) However, we're not always going to be so lucky. The next major transition in digital certificates could very well be to post-quantum crypto due to adv…

Can someone explain to me in plain language / layman's terms how a quantum computer is supposed to reverse cryptographic hash functions? What would be the process EXACTLY?

Re: Why it’s harder to forge a SHA-1 certificate than to find a SHA-1 collision

#17

Post by ademarre » Tue, Dec 22, 2015, 8:20 PM UTC

dsp1234 wrote: post #15

ademarre wrote: post #5

Nice write-up, but it's slightly misleading or confusing to not explain that Nat McHugh's image collisions were chosen-prefix attacks. The post makes it sound like the images were the product of some unexplained collision, and then goes on to explain how chosen prefix can be used to forge certificates.

to not explain that Nat McHugh's image collisions were chosen-prefix attacks. In the paragraph right before those images, it says: "This was cleverly demonstrated by Nat McHugh, who used a chosen-prefix hash collision"

Thanks for pointing that out. It was updated after initial publication.

Originally it said:

> This was cleverly demonstrated by Nat McHugh, who used the broken hash function MD5 to create two images with the same hash...

Re: Why it’s harder to forge a SHA-1 certificate than to find a SHA-1 collision

#18

Post by agwa » Tue, Dec 22, 2015, 8:28 PM UTC

EGreg wrote: post #16

agwa wrote: post #4

We're lucky that hash collision attacks have a relatively simple mitigation like this. (Although you have to trust CAs to follow the rules and implement it properly, and events of the last few years indicate that CAs need to have as few things to screw up as possible.) However, we're not always going to be so lucky. The next major transition in digital certificates could very well be to post-quantum crypto due to adv…

Can someone explain to me in plain language / layman's terms how a quantum computer is supposed to reverse cryptographic hash functions? What would be the process EXACTLY?

It has nothing to do with "reversing" hashes. The attacker would use the quantum computer to determine the CA's private key (e.g. by factoring the RSA modulus using Shor's Algorithm), and would then be able to sign any hash they want. No need to attack the hash function; in fact hashes remain secure under quantum computing.

Re: Why it’s harder to forge a SHA-1 certificate than to find a SHA-1 collision

#19

Post by schoen » Tue, Dec 22, 2015, 8:43 PM UTC

pcl wrote: post #11

TazeTSchnitzel wrote: post #8

$ curl -s https://blog.cloudflare.com/content/images/2015/08/white.jpg | md5 ccf22bc377846166ed65cd3cd58d2e3d $ curl -s https://blog.cloudflare.com/content/images/2015/08/brown.jpg | md5 810cac197d97da7b216c7883be523495 $ curl -s https://blog.cloudflare.com/content/images/2015/08/black.jpg | md5 6bede506abffe08d0c2406d92fbff393 Let me guess, the CloudFlare CDN is recompressing the images? :D

If you download the files to disk, you'll get the right values: $ curl -s https://blog.cloudflare.com/content/images/2015/08/white.jpg > file && md5 file MD5 (file) = b69dd1fd1254868b6e0bb8ed9fe7ecad I've seen this same sort of thing happen with curl in other contexts, but I've never tracked down the details. I assume it has something to do with file stream handling in certain versions of curl. You'll see a discrepan…

I ran the same curl command twice in a row and got files with different sizes! I think it actually does have to do with Cloudflare rather than with curl in this case.

Re: Why it’s harder to forge a SHA-1 certificate than to find a SHA-1 collision

#20

Post by tromp » Tue, Dec 22, 2015, 8:51 PM UTC

agwa wrote: post #18

EGreg wrote: post #16

Earlier quoted context omitted.

Can someone explain to me in plain language / layman's terms how a quantum computer is supposed to reverse cryptographic hash functions? What would be the process EXACTLY?

It has nothing to do with "reversing" hashes. The attacker would use the quantum computer to determine the CA's private key (e.g. by factoring the RSA modulus using Shor's Algorithm), and would then be able to sign any hash they want. No need to attack the hash function; in fact hashes remain secure under quantum computing.

> in fact hashes remain secure under quantum computing.

Hashes will see their security cut in half, in terms of the effort needed to find a pre-image. (EDIT: security in bits = log of #evaluations needed)

E.g. finding a SHA256 pre-image, which amounts to a search over a space of 2^256 candidates, can be sped up using Grover's algorithm, to roughly 2^128 hash evaluations.