4 ms·

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

by veonik 6y ago

sansnomme 6y ago
Depending on the algorithm, you might be able to skip from GPGPU straight to ASIC.
- DaiPlusPlus 6y ago
  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.
  - nordsieck 6y ago
    > 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.
finnh 6y ago
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).
- deleted 6y ago
  [deleted]
- tialaramex 6y ago
  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) https://en.wikipedia.org/wiki/Flame_(malware)
  - minhazm 6y ago
    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.
  - rhacker 6y ago
    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.
eyegor 6y ago
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

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

by veonik 6y ago

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

sansnomme 6y ago

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

DaiPlusPlus 6y ago
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.
- nordsieck 6y ago
  > 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.

finnh 6y ago

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

deleted 6y ago
[deleted]
tialaramex 6y ago
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) https://en.wikipedia.org/wiki/Flame_(malware)
- minhazm 6y ago
  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.
- rhacker 6y ago
  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.

eyegor 6y ago

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