Yes, when the SHA-3 process was launched—in the exciting time when MD5 and SHA-1 had been dramatically shown to be weak—it seemed like we were in danger of waking up one day and finding out that we had no strong hash functions left. It was prudent to get started on SHA-3 ASAP in order to have an alternative ready for that eventuality. NIST explicitly called for hash functions which were different from SHA-256 and which seemed likely to survive a breakthrough that would destroy SHA-256.
Now these few years later *my* feelings, at least, have kind of flip-flopped. SHA-256 feels a lot *less* likely to suddenly succumb, now that it has weathered the Wang attacks for half a decade. I was, frankly, disappointed that the SHA-3 project didn't produce something *both* safer *and* faster than SHA-1 (not to mention SHA-2), in the same way that AES provided an algorithm both safer and faster than DES (not to mention 3-DES). But I can understand where NIST, and the many cryptographers involved, were coming from. Again, they were starting from a position of uncertainty about whether there were critical flaws in our basic assumptions, so conservatism reined. I overheard one SHA-3 designer (who reads this list) comment "At that time, we weren't sure that we knew how to build secure hash functions.". The major result of the SHA-3 process appears to be that not only is it quite possible for cryptographers to build new secure hash functions [*], but also that SHA-256 is a secure hash function. [*] All five of the SHA-3 Round 3 candidates (finalists) seem quite secure. In addition, all nine of the Round 2 candidates seem quite secure. In addition, there were eleven Round 1 candidates without published attacks, plus five Round 1 candidates without attacks better than brute force (counting time*memory), plus twelve Round 1 candidates without attacks that were demonstrated in practice (some of them nearly practical e.g 2⁶⁷ work, and others extremely far from practical, e.g. 2¹⁴³ work). In addition there was at least one (a personal favorite), EnRUPT, which was practically vulnerable with the proposed parameters, but might be counted as "evidence that we know how to build secure hash functions" with slightly larger parameters [¹]. See the SHA-3 Zoo [²] for a catalogue of these candidates and published attacks on them. So the SHA-3 project has shown that cryptographers could, in about a year, come up with, depending on how you count, somewhere between twenty-five and fortyish different functions which cryptographers, in about four years, couldn't (practically) break. Perhaps once the SHA-3 project wraps up, cryptographers will start searching for the limit on how efficient they can make hash functions before they break. The "lightweight cryptography" research (Quark, Spongent, Photon) is a step in that direction. Another approach would be cataloguing attacks on reduced-round variants of otherwise believed-good functions. For example, SHA-256 runs at about 25 cycles/byte [³] and has 64 rounds, and the best known attack on reduced SHA-256 is on 41 rounds (according to wikipedia), which suggests that a 42-round variant of SHA-256, which would run at about 17 cpb, ought to be safe. Then there is Skein. It runs at 23 cpb and has 72 rounds, and there is no published attack of any kind (even the unreasonable kind) on more than 57 rounds of Skein [⁴], so if you used 58-round Skein it would cost about 19 cpb. Then Blake [⁵] (my current favorite). 14 rounds, 31 cpb, no attacks known on more than 6 rounds, so it ought to be possible to have a cut-down version of Blake that runs at about 16 cpb. Note that all of these numbers above are still pretty conservative! For example, I said that there were no known attacks on Blake with more than 6 rounds, but the known "attacks" on Blake with 6 rounds are not really "attacks", but more like "interesting theoretical observations". If you only count attacks which are actually computable in the real world, which apply to the full hash function (not just to some internal component of it), and which are a full collision (not just some "near miss" like a "partial pseudo-collision"), then I don't think there is an attack on even 1 round of Blake. If 1-round Blake is actually secure, then that would mean you can have a secure hash function in about 2 cpb! A similar argument goes for Skein and even SHA-256. Another approach would be to look at the most efficient full hash functions that have been studied. If you look at the most efficient hash functions on [³], they are: md4 -- 7 cpb -- insecure md5 -- 8 cpb -- insecure edonr -- 11 cpb -- secure! It was rejected from the SHA-3 contest, not because it was shown to be insecure but from an abundance of caution (in my humble opinion -- I know others who know a lot more than I do about this would disagree). shabal -- 15 cpb -- secure! ditto sha-1 -- 15 cpb -- insecure bmw -- 15 cpb -- secure! ditto All this makes me think that it really ought to be possible to have a function more efficient than SHA-256 and is still secure, and perhaps even possible to have a function more efficient than SHA-1 or even MD5 and is still secure. I guess it is going to be quite a few years before we gain confidence in any such function, though, unfortunately. To be clear, I'm not exactly recommending that you should *use* a reduced-round SHA-256, a reduced-round SHA-3 finalist like Blake, or a SHA-3 reject like Edon-R. I'm not saying you shouldn't use such a thing either. What I'm saying is: their existence is reason to believe that a secure hash function with this kind of efficiency could exist. Regards, Zooko [¹] http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/Feb2009/documents/EnRUPT_2009.pdf [²] http://ehash.iaik.tugraz.at/wiki/The_SHA-3_Zoo [³] http://bench.cr.yp.to/results-hash.html#h6dragon ; 32-bit ARM "h6dragon", 4096 byte input, worst quartile [⁴] http://ehash.iaik.tugraz.at/wiki/Skein [⁵] http://ehash.iaik.tugraz.at/wiki/BLAKE _______________________________________________ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
