Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

blog.cloudflare.com

Post reply on HN
Print view View original

21–30 of 46 posts

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

#21

Post by mmozeiko »

tromp wrote: post #20
agwa wrote: post #18

Earlier quoted context omitted.

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.

That's not half. Its square root of n. By cutting effort in half of 2^n you get only 2^(n-1).

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

#22

Post by droffel »

mmozeiko wrote: post #21
tromp wrote: post #20

Earlier quoted context omitted.

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

That's not half. Its square root of n. By cutting effort in half of 2^n you get only 2^(n-1).

The effective number of bits of entropy are cut in half.

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

#23

Post by mmozeiko »

droffel wrote: post #22
mmozeiko wrote: post #21

Earlier quoted context omitted.

That's not half. Its square root of n. By cutting effort in half of 2^n you get only 2^(n-1).

The effective number of bits of entropy are cut in half.

Well he said "in terms of the effort needed to find a pre-image". For that effort won't be half.

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

#24

Post by agwa »

tromp wrote: post #20
agwa wrote: post #18

Earlier quoted context omitted.

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.

That's true, but it's easy to fix by using longer hashes (e.g. SHA-512). RSA and ECC are broken beyond hope.

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

#26

Post by tromp »

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.

Hashcash, the proof of work system employed by Bitcoin with hash function SHA256, is also vulnerable. Where a current mining chip might search a space of 6e13 nonces in 10mins, a quantum computer employing Grover's algorithm might be able to search a space of 1e18 nonces, even with much fewer circuits and slower cycle time (although in Bitcoin this is complicated by having limited nonce entropy in the header)

Note that the potential for speedup is due to the extremely small time needed for a single proof attempt. A PoW that only allowed a hundred proof attempts in the block interval time would hardly be vulnerable.

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

#27

Post by jud_white »

KirinDave wrote: post #2

It's worth noting that SHA1 is also suitable for use in HMAC on older hardware, security is not significantly compromised by SHA1's properties. You can move to more modern algorithms, but there isn't a pressing need to remove SHA1 implementations for that application.

I have a question I haven't been able to find an answer to, hopefully someone here can help.

Why is HMAC+(hash) considered secure, while being considerably faster than say bcrypt with a cost of 12? For example, if a service used a user provided password to validate a "secret" (what would normally be the signed message), is that less secure than bcrypt? If so, what makes guessing the secret used in HMAC difficult?

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

#28

Post by viraptor »

I don't get the issue with serial numbers. For the browser, it's a completely opaque random number - it doesn't matter what it is and how it changes.

Is the issue here that they're talking about CA collisions and need the "authority key identifier" extension to match? This shouldn't matter when colliding with service certificates.

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

#29

Post by viraptor »

jud_white wrote: post #27
KirinDave wrote: post #2

It's worth noting that SHA1 is also suitable for use in HMAC on older hardware, security is not significantly compromised by SHA1's properties. You can move to more modern algorithms, but there isn't a pressing need to remove SHA1 implementations for that application.

I have a question I haven't been able to find an answer to, hopefully someone here can help. Why is HMAC+(hash) considered secure, while being considerably faster than say bcrypt with a cost of 12? For example, if a service used a user provided password to validate a "secret" (what would normally be the signed message), is that less secure than bcrypt? If so, what makes guessing the secret used in HMAC difficult?

I'm not a crypto master, but as I understand it, while it's possible to find md5 collision, it's many times more difficult in hmac, because it's:

    hash((secret+pad1) | hash((secret+pad2) | message))
so you would have to find a collision of one key that matches collision of another key, so you're back to relying on basic birthday attack rather than any specific hash weakness.

If you're looking for an actual proof, it's at http://cseweb.ucsd.edu/~mihir/papers/hmac-new.html

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

#30

Post by richardwhiuk »

schoen wrote: post #19
pcl wrote: post #11

Earlier quoted context omitted.

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.

Apparently sometimes the CDN is stripping the EXIF data
Post reply on HN