7 ms·
When Will We See Collisions for SHA-1?
- SilasX 14y agoCrypto-newb question: is there any reason it takes the "number of computations" difficulty as a given, rather than estimating the rate at which attacks will get smarter and require fewer computations? The analysis that's given includes estimates of decreasing computation cost from Moore's law, but no corresponding estimate of decreasing cost from patterns found in the SHA-1 hash function. Also, why does the cost estimate focus on commodity CPUs, rather than GPUs, which are much better at the (parallel) computations that hash attacking involves?
- jpablo 14y agoHe's only providing a lower bound for this numbers, he specifically spells your concerns. He mentions that any improvement on: * number of cores per CPU * number of CPUs per server * any improvements in cryptanalysis * instruction set improvements (arm sha1, gpus) Will only make his number even scarier.
- jwegan 14y agoIt is impossible to estimate decreases from "patterns found in the SHA-1 hash function". There is a good likelihood no patterns will be found in 10 years. It is also possible (although probably unlikely) an attack could be found that utterly breaks SHA-1.
- zeeboo 14y agoI can't answer why GPUs weren't considered, though I'd guess because they weren't as familiar with the numbers and this was a "back of the envelope" calculation. The reason why I wouldn't take into account better attacks is because that's much harder to predict than Moore's law. Also, this is supposed to be more of a worst case scenario, so even if no advances are found it will cost at least that much.
- tptacek 14y agoWorth mentioning here that practical collision attacks do not automatically jeopardize all security protocols that depend on the hash. For instance, MD5 is totally broken, but there are no known practical attacks against HMAC-MD5. I hope it goes without saying that this stuff generally does not apply to password hash constructs either.
- beagle3 14y agoI need a "digital public notary" service, where I send some hash to the notary, they sign it and give me back a signed copy (with the notary's system or public key of choice, e.g. 4096 RSA or 256 bit ECDSA or whatever) If I want it to be considered reasonable valid proof that I did, indeed, have the data leading to the hash when the notary signed it, and I want stuff I sign today to be acceptable 10 years from now, would you consider HMAC-MD5 viable? How about HMAC-SHA1? I guess plain MD5 and SHA1 are out of the question according to this article. Speed is not a concern here, so I would be happy with HMAC-SHA3 or anything else... Also, I keep reading that multiple signatures (MD5 + SHA1) are only as strong as the strongest one, but that does not make any sense to me - If you have two differently seeded (initial internal state) MD5 hashes, it should already be much harder to exploit (perhaps not double the number of bits, but surely a large load factor)?
- chrisballinger 14y agoHave you seen Citizen Media Notary? https://github.com/Miserlou/CitizenMediaNotary https://github.com/Miserlou/CitizenMediaNotary
- pbsd 14y agoYou can hedge your bets with hash combiners: http://homepages.cwi.nl/~pietrzak/publications/FLP08.pdf http://homepages.cwi.nl/~pietrzak/publications/FLP08.pdf C_{4P}(SHA-2-512, SHA-3-512) should remain solid for a long long time. Your point of failure is, now, the signature scheme. To last for decades, do not use RSA or DSA. Use elliptic curve DSA or similar (EdDSA comes to mind).
- 14y ago
- notaddicted 14y agoAFAIK GPUs are far more cost effective. I've just produced this estimate. 2xAMD 7970 : 8000Mhash/s ~= 2^33 Seconds per year ~= 2^24 Total Hashes ~= 2^57 1kW * $0.15/kWh * 1 year ~= $1315 Rig cost (guess) ~= $2000 Total cost ~= $3315 Price for 2^60 hashes in a year: 2^60 / 2^57 * $3155 ~= $25000 If you assume a 6X discount in 2021, then it will be <5k. Still, it takes a year, or more money for machines. Corrections welcome. Trying to run sixteen 7970s for a year straight is probably a total crap shoot. The hash rate is from http://www.codinghorror.com/blog/2012/04/speed-hashing.html http://www.codinghorror.com/blog/2012/04/speed-hashing.html . [EDIT: I wouldn't be shocked if FPGAs could do it with 1/10th the power and heat, with the same variable cost (hardware & power) but with an additional fixed cost to build the devices; I'm basing this estimate on bitcoin mining boards like these: https://en.bitcoin.it/wiki/Mining_hardware_comparison https://en.bitcoin.it/wiki/Mining_hardware_comparison ]
- thechut 14y agoI think this is the correct way to look at. a CPU is vastly slower at performing rainboow attacks than a GPU. Many of the largest bitcoin rigs could probably find a SHA-1 collision in a matter of months.
- notaddicted 14y agoYeah, I haven't made any provision for the other calculations required by the attack, so maybe those take a lot of resources, maybe they don't.
- matthew-wegner 14y agoThe combined network hashrate of Bitcoin is currently right around 20,000Ghash/s: http://bitcoin.sipa.be/ http://bitcoin.sipa.be/ Which is about 2,500X the processing power of an AMD 7970. Bitcoin is hashing SHA256, which is about as computationally expensive as SHA-1 (or maybe even cheaper, according to comments on the linked blog post). Much of the Bitcoin computational power comes from large mining operations controlled by individuals. Their processing power is easily diverted elsewhere, if the profit motive is there...
- zdw 14y agoWhat is the use case for this? At best, I could see replacing data with something with the same hash but is gibberish. Why would a "crime syndicate" want this? Also wouldn't an n-tuple of multiple hash methods and the file size be even more impossible to replicate than a single hash, but not be that much harder to generate initially?
- alanctgardner2 14y agoBest practice when storing passwords is to hash them, then compare the hash of the user input to the stored hash. If a user can compute all the possible input->hash mappings for a given set of parameters (salt, etc.) they can figure out the password from the hash.
- zdw 14y agoWhat the article is about is hash collisions - two different pieces of data with the same hash value, not using a hash to obtain the original data. That's what I'm wonder at the value for. Otherwise your're totally accurate.
- beagle3 14y agoThere are humorous examples from the past, where there 20 PDF files prepared in advance, all having the same MD5 hash, where each one of them says "We hereby predict X is going to be president". You publish the hash in advance, and after elections you only publish the right PDF file, thereby "proving" your clairvoyance. More seriously: You can get a notary (e.g. Microsoft Authenticode) to sign one file, and then provide another with the same hash. For now, it only helps you with planned fraud, not after-the-fact forgery.
- FootballMuse 14y agoGPU's are obviously more cost efficient than general purpose x86 CPUs. But as we are learning, specialty hardware using very little power can be an extremely effective hashing device hash as butterfly labs is doing with SHA-2[1]. If a similar device were developed for SHA-1, I'm not crypto-proficient enough to know the difference, but I imagine it would be extremely efficient as well. [1]: http://news.yahoo.com/butterfly-labs-announces-next-generation-asic-lineup-054626776.html http://news.yahoo.com/butterfly-labs-announces-next-generati...
- AnotherBanned 14y agoI think we can assume that governments are capable of cracking SHA-1 today, and all common internet encryption protocols like AES-128 last year. The costs of building such a facility would be trivial and could be hidden within almost any TLA agency's budget.
- tedunangst 14y agoYou obviously know something about AES that I do not.
- frozenport 14y agoMoreover they know things that aren't available to university cryptographers. For example, the Flame virus used an unreported collision scheme. Imagine if somebody at the NSA/CIA firgures out that all pn were really p!
- rb2k_ 14y agoI wonder how the upcoming generations of Bitcoin mining hardware will change this calculation. They are all SHA1 FPGAs/ASICs that implement SHA1. It would also be interesting to see how GPUs perform.
- wcoenen 14y agoThe bitcoin network does >20 terahashes per second now in total (but SHA-2, not SHA-1). Those 2^60 hashes would take only 16 hours at that speed.
- ChuckMcM 14y agoIt is sad to see an Intel engineer misstate/misuse Moore's Observation. The actual observation was that the number of transistors you could put on a chip doubled every 18 months, not performance. For a long time more transistors meant more performance but now that isn't the case. So people put more 'cores' on to a chip to use up those transistors. That said, the ARM threat is under estimated since the power budget is so much lower and the cost per CPU is also lower. So 10,000 ARM8 cores with SHA hardware are cheaper than 10,000 x86 cores doing the calculation in software.
- wtallis 14y agoWhen talking about embarrassingly parallel problems, it is okay to equate more transistors with more performance.
- marshray 14y agoEspecially when we're talking about something like SHA-1 that was designed to be efficiently implemented in hardware.
- ChuckMcM 14y agoDisagree, more transistors does not help when the transistors are spent on another FPU (not useful for SHA) or additional L2/L3 caches (already fits in cache) for example.
- deleted 14y ago[deleted]
- jwatte 14y agoThe fallacy of "A 32-core server is fast, and I can rent servers for 4 cents an hour, so I can rent a 32-core server for 4 cents" is unfortunaltely more common than I'd wish. If that simple error is in this analysis (and affects the cost analysis by at least 2^6), what other errors are in the math that I'm not as qualified to catch?
- ben0x539 14y ago> Since this argument only takes into account commodity hardware and not instruction set improvements (e.g., ARM 8 specifies a SHA-1 instruction), [...] the need to transition from SHA-1 for collision resistance functions is probably more urgent than this back-of-the-envelope analysis suggests. So the ARM 8 SHA-1 instruction contributes to making itself obsolete? :-)
- zvrba 14y agoNot everybody agrees that Moore's law will continue, see for example "Dark silicone and end of multicore scaling" http://dl.acm.org/citation.cfm?id=2000108 http://dl.acm.org/citation.cfm?id=2000108 ftp://ftp.cs.utexas.edu/pub/dburger/papers/ISCA11.pdf They use existing data to model CPU perofrmance increase and conclude with "Through 2024, only 7.9 average speedup is possible across commonly used parallel workloads, leaving a nearly 24-fold gap from a target of doubled performance per generation."
- DanWaterworth 14y agoI imagine "dark silicone" would be quite different than "dark silicon".
- mjs 14y agoFrom the Varnish documentation, addressing an assumption of the Varnish source code that unique inputs will produce a unique SHA-1 hash: "The risk of collision is very small however, and I can all but promise you, that you will be fully offset in fame and money for any inconvenience a collision might cause, because you will be the first person to find a SHA256 collision." https://www.varnish-cache.org/docs/trunk/phk/varnish_does_not_hash.html https://www.varnish-cache.org/docs/trunk/phk/varnish_does_no...