SHA-3 to Be Announced
schneier.com
schneier.com
On the other hand, as Mr. Schneier points out in the article, the Skein hash utilizes a modified Threefish block cipher, while many of the SHA-3 contestants were AES-based (edit: seems like none of the finalists are). Now we have a hardware AES implementation shipping in mainstream processors, so it gives an edge to the AES-based hash functions out there.
edit: I went through the list of finalists and it seems none of them actually use the whole AES block cipher, although several of them use AES S-boxes or other parts of AES.
http://eprint.iacr.org/2012/476.pdf [PDF]
As for AES instruction -- Skein and BLAKE are still faster http://bench.cr.yp.to/results-sha3.html
Only aspect that Mr Schneier has not highlighted and which you touched upon is that some of the hashing finalists are faster and in that they will in brute force comparisions be not as good. That is another consideration, albeit one of limited time as you already said AES is now in some hardware as instructions and how long since AES being a standard has that taken.
But the whole ability to work on partial blocks and that is what you need to do to gain from parallelisation does open up a while new ballgame in modifiying hashed code and returning the same hash. Now if you can pick a partial block size and then do a brute force test modifying from 0-FF each byte of the block incrementaly for the every permutation and only get a match on the original then that will by design be the one I'd be picking, i'm sure they will be testing each parallel finalist in that way. But personaly if they all pass that test then why pick one winner and have them all as part of the standard SH-3.[1-5]. After all if they all work well then having the choice can only add to the entropy we call security these days.
Also, as other posters pointed out, faster hashes are good for everything except password hashing, which is not the biggest use. In the case of password hashing, if the hash algorithm is twice as fast you can just run it twice as may times, so it doesn't hurt for it to be faster.
I highly recommend https://www.coursera.org/course/crypto as a great introduction into some of the more interesting elements you are working through.
In the field of cryptography, holding all else constant, faster hash functions are better.
It is not the job of a hash function to resist incremental brute force attacks on the input domain of the function; that is a job left to higher-level constructions.
It is exactly misconceptions like this one that are the reason we lobby for "high level" cryptography interfaces that don't expose things like hash function cores to programmers.
Now having thought this thru I concluded that if you blocked in a striped fashion every Nth bytes then you could still have the ability to paralise the hashing without compromising security. So in the same example of 100 bytes you would have in block 1 bytes 1,11,21,31,... and in block 2 it would be 2,12,22,32,42... etc. In this way the ability to modify the data/program in a data/program meaningful way and maintain the overall hash would be as hard as hashing the entire lot of 100 bytes.
However having said that a quick look at the skien hash it would appear it uses threefish for its blocking and from what I can tell the aspect of striping the blocks or using contiguase blocks is something that is not defined and down to how it is implemented and in that I suspect they don't strip the data blocks as that appraoch would not be conducive to hashing small communications or rolling data like streamed data were you only know the block of data you have and in that without padding the data you have little scope of breaking it up into procesable blocks as it already is the block size. But that is a issue that stands currently, it is only for example say a fat Linux.ISO say with nice hash check were the approach of striping the data blocks would be benificial to negate the ability to work on just the blocks you are changing to maintain the overall same hash value for the entire file.
I hope that explains the point I was trying to make, nothing to do with cyptoanalysts vs programmers at all. But if programmers don't know about such issues then they will feed the data a block at a time contigiously. I agree that data in and data out is all a programmer should need at API level as anything else is adding the role of cryptographer to a job which is paid at programmer rates.
That would be horrible for security and ease of implementation. Anyone implementing hashes would then need to implement 10 different hashes, some way to specify hash used, keep them all performant and patched against risks like DPA, ... . It is exactly that kind of kitchen-sink approach which is responsible for many flaws in SSL, PGP, etc. to date, and which makes implementing real-world systems such a pain.
A lot of this happened due to the ITAR export crap where you needed to offer pluggable keylengths and algorithms for compliance, and then people had the insane idea of supporting arbitrary algorithms in every protocol.
Simply trying all the values from 0x00 to 0xFF will (statistically) never result in 2 blocks with the same value since you are only bruteforcing 8 bits and the output of the hash is 512. The chance of two arbitrary blocks matching, regardless of length, is 1/2^512.
While I agree with you that this is an immediately important feature, I don't think Bruce's premise (that SHA-2 is still pretty good) is invalid.
Perhaps like you though, I don't understand why a new standard can't be incremental. I think it's silly to wait until something major happens to change.
Interesting, is that because they only return part of the final state (by slicing sha-256 and sha-512) where unsliced 256 and 512 return all of the algorithm's running state as its result?
NIST has also specified several other truncated hash functions such as SHA-2-512/256.
There's a risk of creating hype among people who don't know enough to be able to make a decision, but who do have power to make that decision.
What does this mean, well in effect no extra value is being directly offered, sure some have extra abilities by design like being more able to liberate parallel processing by sbeing able to split the data to be hashed into chunks and work on partial blocks of the final data and use the results to get the final hash result. That is nice.
But when it comes to brute forcing then being faster works against you, also the ability to work on partial chunks of the data allows you to modify the code and rechecking the partial hash for the part your changing until you get the same result, this alows you to do nasty things to code and get the official hash answear alot easier than having to rehash the end result every time and getting the same result or modifying the code to get the same result (usualy have area you jump over all nop and modify that to influence the hash, but more sane ways to do this but offtopic).
So in essence any hash that can be run faster in any way will make it weaker in terms of brut forcing (yes I know people assume there passwords will be the last one on the list to be checked bia brute forcing and assume if it takes 10 years to test all variations then there password is 10 years strong, you see the flaw in mentality there).
Now NIST still have an opertunity here and it is a simple, tried and tested approach and that would be to have all finalists winners and have them all in the standard as variations. This then allows end users/admins to pick there variation of choice or even perish the thought allow mixed usage so say your /etc/password file could have some users using one variation, others using another, etc. Whilst it add's no obvious extra benifit, it will allow more variations and in that fallbacks/choice and that is what n BIT encryption/hashing is all about, each bit being a choice in a way.
So in summary I believe NIST should let them all win and have SH3.n with n being the variation of finalist, let them all win, choice is good and that is what n bit encryption is after all, extra choices.
What you're thinking of are password hashes, which are a variant/application of key derivation functions (KDFs). KDFs often use secure hash functions, which is where the confusion comes from.
You want your core crypto to be as fast as it conceivably can be, because you want to be making progress towards a state where all communications are encrypted by default.
The point I was making is that it is a concideration and the general mentality is that the larger the version number then the better it is and a point the original article was making in that none of them are any better than what is on offer with regards to security. Its is tha aspect of being able to get a large hashed file and modify part of that file and recheck just that partial HASH without having to rehash the whole thing. This for comminucations starts to open up a faster way to modify encrypted communications as by changing a small part you only have to rehash that part and know the final block is still ok. This is a area which makes by design any hash function can work with partial blocks, less secure.
So fast is good but it often comes as a compromise against security and any new standard should at least be better than what it is designed to replace and not open up whole new avenues of attack.
In this case, possibly. It is quite clear by now that SHA-1 and MD5 are flawed, so the 'higher version' SHA-2 variants (especially the bigger ones) should be preferred.
> So fast is good but it often comes as a compromise against security and any new standard should at least be better than what it is designed to replace and not open up whole new avenues of attack.
Brute force attacks against 512 bit hashes are not practical today, and won't be practical for a long time. The concern with password storage is seldom pure brute force attacks, but rather attacks against a dictionary. This is because, for password storage, the input entropy is typically much less than 512 bits (or even 128 bits). It's a completely different use case.
> Its is tha aspect of being able to get a large hashed file and modify part of that file and recheck just that partial HASH without having to rehash the whole thing.
Is this an argument against hash trees? Can you explain more about the this potential attack? It seems to be to be equivalently hard to finding preimages.
If you only have to rehash a branch as apoosed to the entire tree and match hash's then you have a easier time as it is alot faster by design.
Now if the way the hashing work is that only say 1234567 will get the hash value 11 and no other variation then i will have no issues and welcome this as a great achievement and pure brilliance. But I dont feel this is the case and nor could it be by reducing any large amount of entropy into a shorter definition and that is what a hash function does after all and one hash value will match more than the original data.
The only issue with this approach of blocking is that it works on all the data and as such would for example be no use for streaming which is a terrable exmaple but you get the idea.
I would never have thought of a password hash as a KDF, because you don't use the key for anything except to compare equality. I also wouldn't have thought that an important property of a KDF is for it to be slow. In the case that you're using a KDF to compute an actual encryption/decryption key, this property does not seem important, because the output (the key) is just as sensitive as the input (the password).
In practice, though, it's desirable for password hashes to maximize entropy, which makes them usable as key derivation functions; and the key derivation functions that you usually need take passwords as input.
Hash functions have many, many uses beyond password storage. For most of those uses they become more, not less, useful with speed. Fast hash functions are good for everybody. If you explicitly want a slow expensive construct, then chose one properly designed to be slow and expensive. Don't just chose a crappy hash function.
> So in summary I believe NIST should let them all win and have SH3.n with n being the variation of finalist, let them all win, choice is good and that is what n bit encryption is after all, extra choices.
I completely disagree. An organization like NIST has a responsibility to have an opinion on what the 'best' hash function is. They then need to track the state of the art of research that might invalidate that decision, and clearly communicate changes in the decision. While there is a defense-in-depth argument to be made for multiple options, the pattern seems to have been that there are a lot more systems broken because they chose a poorly studied or known bad algorithm than by breaks being found in previously known-good algorithms. We have a lot to lose from everybody making it up as they go along.
That all said if everybody agreed on everything then life as we know it would be boring and we would all be fighting over the same women at some stage, which would not work out well.
This would be especially awkward, since apparently she would also be fighting over herself and presumably would just elope with herself.
We are probably still talking less than an order of magnitude. So that slowness isn't going to save the day in theory. It might in practice but if it comes that close, the implementation will be deemed broken and something else will be advocated.
However a slow function means a lot of cumulative power and time wasted in the years to come to execute this new hash function. So I'd opt for a faster one.
"> When will SHA3 be announced? Were you given special information the rest of us don't have access to?
I have no inside information on when SHA-3 will be announced. My guess is that they've made the decision, and are going over the final rationale again and again. My guess is that it won't be Skein."
Even though this is the original title, I'd prefer the HN title be edited to something about Schneier hoping NIST will pick no SHA-3.
But it does make you reliase how much empressive stuff you can do in just a few bytes and what else is out there.