6 ms·

I implemented the Skein hash in a crypto class at my uni. What is remarkable about that hash is that it has a "hash tree" mode which provides an interesting opp

by exDM69 14y ago

I implemented the Skein hash in a crypto class at my uni. What is remarkable about that hash is that it has a "hash tree" mode which provides an interesting opportunity for parallelization and doing hashing of partial data. In contrast, many traditional hash algorithms are inherently sequential by nature. 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.

dchest 14y ago
We show that the 4-lanes SHA-256 is faster than the two SHA3 finalists (BLAKE and Keccak) that have a published tree mode implementation. http://eprint.iacr.org/2012/476.pdf 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 http://bench.cr.yp.to/results-sha3.html
- exDM69 14y ago
  Good stuff, thanks for getting out some good sources.
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.

by exDM69 14y ago

dchest 14y ago

We show that the 4-lanes SHA-256 is faster than the two SHA3 finalists (BLAKE and Keccak) that have a published tree mode implementation. http://eprint.iacr.org/2012/476.pdf 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 http://bench.cr.yp.to/results-sha3.html

exDM69 14y ago
Good stuff, thanks for getting out some good sources.

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.