Hacker News Reader

Comment by tptacek | Hacker News Reader

Two nits, both pedantic:

An attack on SHA1 that makes certificate forgery viable within the next few years doesn't seem very likely, although over the long term it might be. The attack on SHA1 isn't like the attacks on RSA-1024; my sense is that the literature already knows how to break RSA-1024 given enough compute, but does not know how to do that with SHA1. Further, factoring RSA-1024 provides an attacker with a total break of RSA-1024 TLS, but not every attack on SHA1 will necessarily do the same.

Second, there's a subtext that SHA-3 having been standardized somehow puts the writing on the wall (albeit, a far-away wall) for SHA-2. Not so; SHA-2 could remain secure (in its TLS certificate use case) indefinitely.

View on HN

To out-pedant you: even assuming that the differential collision attacks we know about are incorrect [1], we absolutely know how to break SHA-1 given enough compute, that is, roughly the same resources needed to break RSA-1024. The answer is generic collision finding with parallel rho [2].

[1] https://marc-stevens.nl/research/papers/EC13-S.pdf [2] http://people.scs.carleton.ca/~paulv/papers/JoC97.pdf

You haven't so much out-pedanted me as refuted me. :)

I added links to both papers to the bottom, and removed the "we'll probably need to upgrade" to SHA-3 sentence fragment.

It seems that the identical prefix collision would be good to investigate doing an ASIC on.

I don't know if "10 years" falls in your definition of "next few years".

For a viable rogue CA attack, you need a chosen-prefix attack. Current best research (https://marc-stevens.nl/research/papers/EC13-S.pdf) shows it should take 2^77.1 SHA-1 compression calls to do a chosen-prefix attack. Say this is improved to 2^65 within the next 10 years. Right now a good GPU (AMD R9 290) can do 3 billion SHA-1 compression calls per second. Say Moore's Law continues for the next 10 years and that 10 years from now a GPU can do 20 billion SHA-1 per second. So 10 year from now, 100 high-end GPUs should be able to produce a rogue CA with colliding SHA-1 signature in 7 month of compute time.

Change one little assumption and assume the best attack ends up being 2^60 instead of 2^65. In this case, a viable attack could certainly be carried out in the next 3-4 years.

You can't cross your fingers and hopes such an attack will not be discovered. The time to abandon SHA-1 is now.

I agree.

Firstly, GPUs haven't followed More.

Secondly, multiple sha1 ASIC exists.

Thirdly, WebGL has made it trivial to gain vast GPU resources. 20,000 viewers for two hours can be bought for $20.

Fourthly, I don't care.

> 20,000 viewers for two hours can be bought for $20

Is that pricing from a botnet or a company like crowdprocess.com?

> Firstly, GPUs haven't followed More.

Yes they have. Any integrated circuit that tries to pack as many transistors as possible on a die is, by definition, following Moore's Law. To convince you: http://www.mumblegrumble.com/visual/roadmap/other/nvidia_moo...

@tptacek - I tried to include enough detail to make it clear that a SHA-1 forgery isn't as trivial as a brute force. That you'd have to "coax a Certificate Authority" into issuing you a targeted forgery, and that that's what the MD5 team did.

The SHA-3 mention at the very bottom was in the spirit of "all things are broken eventually", not a specific comment on SHA-2 (though my understanding is that there are some conceptual weaknesses that have been identified). I don't think I've confused the issue there, but if I see confusion I'll definitely update it.

Another way to think about SHA2 and SHA3 is that it's entirely possible that SHA3 could fall before SHA2 does. They are unrelated algorithms.

I'm also not comparing attacks on SHA1 to brute force (which is also not how MD5 fell).

It would be helpful, when people posit attacks on SHA1, if they'd cite the literature they're referring to.

> Another way to think about SHA2 and SHA3 is that it's entirely possible that SHA3 could fall before SHA2 does. They are unrelated algorithms.

Very good point, though I would expect SHA2 to see far more research on weakening it. It's been around a lot longer, and its wider deployment makes it a much higher value target. (Is SHA-3 supported anywhere right now?)

You can easily make the converse point and claim that SHA2 has a higher probability to resist future cryptanalysis than SHA3, given that SHA2 has already had a lot more research than SHA3, but is still not broken. "Old" is a feature in this sense. The only issue I know about with SHA2 is its length extension property. And that is by design.

Why SHA-2 instead of RSA 4096 or SHA-256? Even the RSA is compromised but 4096-bit will take a lot more(maybe few more hours) resources to decrypt.

==edited==

Thank you for the reply.

SHA-256 is a form of SHA-2.

SHA-256 is one of SHA-2's hash functions: http://en.wikipedia.org/wiki/SHA-2

You use a hash function (e.g. SHA256) to make the hash of the page and a signature algorithm (like RSA 4096) to sign it.

my sense is that the literature already knows how to break RSA-1024 given enough compute

"given enough compute", we can break any crypto just with pure bruteforce, although in practice I believe there's a point at which the amount of power that would be required becomes physically impossible due to the limits of computation within the universe (i.e. Moore's Law will definitely end sometime). To me, that says using extremely large hash sizes can keep things quite secure - even attacks that reduce complexity by many orders of magnitude could be impossible in practice - e.g. a 2048-bit hash for which a 2^500 complexity attack is found won't be any less practically secure.

...unless we somehow discover that P = NP, in which case the world could become a very interesting place...

Reply on news.ycombinator.com