Hacker News Reader

Comment by veonik | Hacker News Reader

It would scale linearly right? Double the amount of computing thrown at it, you'd half the time on average. Or am I mistaken?

View on HN

And of course double the compute for half the time = same cost (more or less). I would imagine the NSA has sunk enough into hardware to do this fairly cheaply per-pass, and very quickly (hours not weeks).

Cloud computing makes this true for everybody else too now, at least within a practical range. Now I can easily afford a multi-million dollar distributed compute facility... for a few hours, rented from Amazon.

I'd be surprised if the NSA has a clear purpose for bulk colliding SHA-1. It's a pretty niche thing to want to do even compared to say, "cracking" DES. For MD5 we know such government agencies made some collisions to exploit various technologies that didn't stop trusting MD5 in a timely fashion, but it wasn't something they did a lot just one collision here or there as necessary. e.g. https://en.wikipedia.org/wiki/Flame_(malware)

This isn't actually true in practice though. Most of the cloud providers have quota's on accounts and actually won't let you provision that many resources without getting the quota's increased, which you are unlikely to be able to do unless you're actually regularly spending that much money.

I do think it's amazing that we can now script out a million dollar data center, build up, tear down for just an hour of use (and just a fraction of the cost). And that's available to ordinary people (with a little budget obviously). Compare what we had 20 years ago. Mind blown.

In theory [0], this problem is fully parallelizable, so you would be correct. Each mutation and hash calculation is fully independent so it can scale forever. On a national lab sized cluster, you could probably generate a collision in minutes.

[0] Have not read the paper thoroughly enough to determine if this is true for this technique

Depending on the algorithm, you might be able to skip from GPGPU straight to ASIC.

At this scale - I’m not convinced that $5,000 worth of ASICs would have the same performance as $5,000 worth of GeForce cards - especially after factoring in lead-time to design the ASIC.

As for FPGAs - forgive my ignorance - but can they even handle that kind of load? In my head I just see them breaking-down under the sheer thermal load.

> As for FPGAs - forgive my ignorance - but can they even handle that kind of load? In my head I just see them breaking-down under the sheer thermal load.

They worked for Bitcoin before miners switched to ASICS; I imagine they'd be fine in this application as well.

Reply on news.ycombinator.com