4 ms·

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

by 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.
- ryan-c 14y ago
  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.
- ghshephard 14y ago
  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 https://www.coursera.org/course/crypto as a great introduction into some of the more interesting elements you are working through.
  - Zenst 14y ago
    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.
ballard 14y ago
Scrypt is far-and-away superior to either bcrypt or PBKDF2 on simple financial basis alone... the shit that really counts. This is why I'm currently porting tarsnap's scrypt as a standalone "libscrypt" with a cleaner-than-chromiumos fork. Any good hash algorithm should require a minimum of effort and resources (time, storage, $, electricity, etc.) during both hash computation and rekeying events such that attacking to discover the secret would be much too expensive in the required secrecy lifetime (the most basic core of security).

by ryan-c 14y ago

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.

ryan-c 14y ago
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.
ghshephard 14y ago
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 https://www.coursera.org/course/crypto as a great introduction into some of the more interesting elements you are working through.
- Zenst 14y ago
  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.

ballard 14y ago

Scrypt is far-and-away superior to either bcrypt or PBKDF2 on simple financial basis alone... the shit that really counts. This is why I'm currently porting tarsnap's scrypt as a standalone "libscrypt" with a cleaner-than-chromiumos fork. Any good hash algorithm should require a minimum of effort and resources (time, storage, $, electricity, etc.) during both hash computation and rekeying events such that attacking to discover the secret would be much too expensive in the required secrecy lifetime (the most basic core of security).