4 ms·

I believe they worked towards speed mostly and whilst AES is in alot of hardware the basis of there design was to be hardware independant and with that in mind

by Zenst 14y ago

I believe they worked towards speed mostly and whilst AES is in alot of hardware the basis of there design was to be hardware independant and with that in mind you can see why no design bias was placed upon what is or not currently enabled in some hardware. In a world were we still have no standard in ragards of BIG or LITTLE ENDIAN then you can see they took the right approach. 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.

tptacek 14y ago
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.
- Zenst 14y ago
  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!
  - ryan-c 14y ago
    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.
    - marshray 14y ago
      Note that anything is possible to parallelize for an attacker who has many different candidate values (e.g., password guesses) to try.
    - Zenst 14y ago
      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.
    - Zenst 14y ago
      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.
rdl 14y ago
> 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.
- joeyh 14y ago
  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..
  - rdl 14y ago
    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.
deleted 14y ago
[deleted]
jgeralnik 14y ago
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.

by Zenst 14y ago

tptacek 14y ago

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.

Zenst 14y ago
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!
- ryan-c 14y ago
  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.
  - marshray 14y ago
    Note that anything is possible to parallelize for an attacker who has many different candidate values (e.g., password guesses) to try.
  - Zenst 14y ago
    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.
  - Zenst 14y ago
    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.

rdl 14y ago

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

joeyh 14y ago
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..
- rdl 14y ago
  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.

deleted 14y ago

[deleted]

jgeralnik 14y ago

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.