Hacker News Reader

Again: the "brute force" thing you're mentioning here is a non sequitur. It's akin to suggesting that Intel should manufacture slower chips to make passwords hard to crack. Hash functions should be as fast as possible; it's the job of a KDF construction to slow the process down to resist brute forcing.

It's the aspect of being able to change part of the data and only have to brute force that part of the data so if you have a block of data that you can modify and rehash check until you get the same hash you have a whole new issue with hashing by design of being able to work on partial block and paralise things. No I'm not suggetsing intel should make slower chips, I am suggesting that any design of hashing that allows you to modify a small part of the entire lump of data/code and you only have to recheck the hash of that small block instead of the entire lump of data/code then even if they hashing of X bytes took the same or even slower than SH-2 you will still by design induce a weaker system that is open to a easier attacks than any system were you have to rehash the entire block of data sequentualy. Nothing to do with KDF!

I can't wrap my head around the point you're trying to make so I'm just going to repeat my previous statement with slightly different words:

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.

Point I was making is if you have 100 bytes and you block that data every 10 bytes and hash those block and use those 10 block hash's to make the final hash value for those 100 bytes then if you only change data in one block then you would only have to modify that block until you got the same hash for that block knowing that the final hash will be the same.

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.

If I understand what you're saying, it's that a hash defined as e.g. (with b1, b2, ... standing for blocks) H(b1, b2, b3) = H(b1) ^ H(b2) ^ H(b3) is not very secure because it allows one to recover b2 from H(b1, b2, b3), b1 and b3 in time 2^(|b2|) ("2 to the power length-of-b2"). This is obviously true, but no sensible hash function is defined in this way, and I don't think any of the SHA candidates use blocks of a size that can easily be bruteforced.

Just to put this in perspective: SHA1 has a 512 bit block. Nobody is brute forcing 2^512. MD5 has an output size of 128 bits; nobody is brute forcing 2^128 either.

It is trivial to create constructions where changing a single bit of the data requires recomputing the hash over all of the data. A really simple option to that end is to feed the hash back into itself multiple times. Please go read a paper on PBKDF2 and/or scrypt - they are designed to work with an arbitrary hash function be impossible to parallelize.

ok read about PBKDF2 and what your desfribing/on about is key stretching or hash feedback cycles and is a great appraoch to take for what it does. Though for what I was on about it would still be a case of working out the hash for a smaller part than the sum of the entire data, but as I have thought though. If you stripe the data blocks across the sum of the data then the ability to modify a small part of the data would still result in you taking just as long to work out the hash for the entire sum of data. It is when blocking is done in contiguous blocks (100 byte data block 1 is bytes 1-10, block 2 is 11-20 etc) then is were you have the issue I describe and yes what you say about hash feedback is correct in that for any block it will add a extra time factor but it will still be less than the entire lot of data and if you can erhash 10 bytes instead of the entire 100 bytes it can only be quicker. But if those blocks are stippped then you would get the best of both worlds and have the ability to parallise your hashing without fear of being any weaker by design, but thats only if you stripe the data blocks you paralise and not if you use contiguise blocks. I'll have a good read of these finalists and more over the weekend for this, though far better brains than I wrote them so I expect this is me just learning what they already know.

Zenst - it sounds like you have a lot of interest in cryptography, and your lack of familiarity with PBKDF2 and friends suggests that you have just entered this space.

I highly recommend https://www.coursera.org/course/crypto as a great introduction into some of the more interesting elements you are working through.

Thank you and signed up. I have interests in too many things that cross over, but this is one area I do need to step back a bit and learn the lingo a bit more. Looking forward to this course now.

You can speed up the first iteration, but after that there is NO similarity in the output so you can't re-use previous computations.

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.

Actualy if the data is split in a way such as every Nth byte is used to make up a block (ie 100 byet data and 10 byte block you use bytes 1,11,21,... in block one and 2,12,22... in block 2 etc) would negate the issue I would have with this completely. Its not case of feeding hash back into itself its the case of entropy within the block and if that entrypy contains non contiguous bytes via stripeing then the abilty to modify the code or data in any nefarious way would be as hard as modifying the entire hash so I think I've eliminated my own concerns. Though of to read up on what you reference but if they refer to adding salts then that is a seperate issue to do with small data bytes. Thank you for putting up with my brain farts.

Note that anything is possible to parallelize for an attacker who has many different candidate values (e.g., password guesses) to try.

> 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]

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.

OTOH if you don't specify which hash is used, you'll be stuck using SHA1 for all time, or with a messy transition. Nobody knows yet what to do about git as SHA1 becomes more broken..

The right way to do this IMO is big version upgrades. Like V1 of protocol uses a specific hash, message format, etc., V2 might use another, etc. It's when you allow arbitrary combinations of pieces that complexity becomes absurd.

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.

Brute forcing a partial block is just as hard as bruteforcing the whole thing - you still need to create a second string which hashes to the same as the first one.

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.