3 ms·

It's not necessarily "slow is best", but rather minimizing the ratio between how fast your production server can calculate them multiple hashes while under load

It's not necessarily "slow is best", but rather minimizing the ratio between how fast your production server can calculate them multiple hashes while under load, vs how fast your attacker can crack them on dedicated hardware. Which, for example, is why something based on SHA3 is bad, because your typical server is just going to be doing SHA3 hashes via CPU. Except SHA3 was chosen to be ASIC-friendly, so your attacker will be able to calculate SHA3 faster than you. As long as the attacker has no faster calculation method than the one you're using, the absolute speed doesn't matter. This is why scrypt, bcrypt (and to a lesser extent pbkdf2-hmac-sha256) are doing well, because running them on GPU or ASIC isn't meaningfully faster than the CPU implementation the defender is using. All that's left at that point is making it as expensive as possible for them to parallelize their attack. Which is what scrypt and other things attempt to do -- require as many non-CPU resources (memory, hd space, etc) so that the attacker's parallelization cost is also maximized. (Personally, I've been playing around with the idea of incorporating random accesses to a 2-tb file of random data, so that the attacker would have a HUGE amount of data to steal before my hashes would work. And they'd have to establish shared access to all the CPUs/etc they're attacking with)

jszymborski 12y ago
Thanks, that was a great answer!
floody-berry 12y ago
yescrypt has ROM capabilities [1], which function like your large file idea. [1] https://password-hashing.net/wiki/doku.php/yescrypt#read-only_lookup_table_rom https://password-hashing.net/wiki/doku.php/yescrypt#read-onl...
- warbiscuit 12y ago
  Ooh, that looks interesting ... and not just for ROM feature. They've packed a TON of things into there. Even SCRAM support! I'm really intrigued by one of the planned features... "Hash upgrades to higher cost settings without knowledge of passwords". I can think of a way to implement that alone, but to pack that all in with those other features will be really impressive. And would be a huge boon to systems w/ infrequently logging-in users.
  - solardiz 12y ago
    "Hash upgrades" have been added with the just-published v1 of the yescrypt submission to PHC. There is not yet an implementation of an "upgrade this hash" function (also, hash encoding needs to be finalized, including encoding of the upgrade count parameter), but now it's a matter of writing this additional code outside of the actual password hashing code (already capable of computing possibly-upgraded hashes). Unfortunately, with memory-hard schemes such upgrades involve an efficiency loss in terms of normalized area-time, and there's a tradeoff between granularity of upgrades and efficiency. For Catena (another PHC finalist that supports these), the time granularity is 2x to 3x, with efficiency down to 33.3%+ of non-upgraded hashes (after many upgrades). For yescrypt, it's 4x to 5x granularity and 60%+ efficiency, respectively. (I felt that 33.3%+ is just not good enough - in my opinion, it's usually better to postpone the upgrade until 60%+ can be achieved rather than upgrade early and prevent it from ever being achieved. The next easy step would be 77.7%+, but the granularity would be too high.) At the same time, support for ROM access frequency tuning (and thus for ROM-on-SSD, as opposed to ROM-in-RAM) has been dropped from yescrypt for now. The rationale is that builtin ROM-on-SSD didn't make enough sense without also having a ROM-in-RAM (in use cases for the former, the latter would also be easily affordable, including complexity wise, and would provide significant extra defense), and supporting two ROMs at once would be further beyond the comfort level for complexity of a hashing scheme in PHC (yescrypt is already somewhat beyond the comfort level). Support for two ROMs along with access frequency tuning might be re-added in an extended revision of yescrypt for specialized use cases at a later time, but this will be outside of PHC.
TheLoneWolfling 12y ago
> random accesses That's fairly simple to do: Do a standard password hash as usual (with salt, of course), then use the hash as an index into the data (or the low/high N bits of the hash, whatever) and use that as the final password hash. Just don't lose the data! Effectively using your password/salt as the key to a hashmap containing random data.
- warbiscuit 12y ago
  Yep... that was roughly my starting approach. Current one I'm playing with uses multiple samples (chosen as a function of the initial hash and the previous samples), to ensure the attacker has to actually take the whole file... otherwise the attacker gets away w/ 10% of file & 100 hashes, they've got good odds that one of those hashes only needs the first bit of the file. Still trying to play with it to see if I can make it harder to parallelize assuming attacker does get the file. But that gets into designing an entire password hash, not just a friendly wrapper, which is more than I'm prepare to chew on right now :)
  - TheLoneWolfling 12y ago
    I'd just do pointer-chasing through the file, xored with the initial hash each time. I.e. out = hash xor data[hash] xor data[hash xor data[hash]] ... Alternative phrasing: out_n = data[hash xor out_(n-1)] xor out_(n-1), where out_1 = data[hash] xor hash "Random" accesses throughout the file - not the easiest to run in parallel. (That being said, I haven't checked to see if this is breakable)
  - solardiz 12y ago
    You should take a look at: http://www.openwall.com/presentations/ZeroNights2012-New-In-Password-Hashing/ http://www.openwall.com/presentations/ZeroNights2012-New-In-... https://medium.com/@TapLink/the-password-defense-league-c416ceaedb33 https://medium.com/@TapLink/the-password-defense-league-c416... (I'm not happy with how Jeremy re-purposed the words "blind hashing" to mean essentially the approach I had recommended as a better alternative to his original "blind hashing", which I criticized in the ZeroNights talk, but other than that I agree with what he wrote.) To "make it harder to parallelize assuming attacker does get the file" (actually, to increase the cost per candidate password tested, not to make anything literally "hard to do"), I propose that "best of both worlds" approach (see my ZeroNights slides). And you're right, this means "designing an entire password hash, not just a friendly wrapper" (thus, different from Jeremy's work, and more similar to my work on yescrypt).

jszymborski 12y ago

Thanks, that was a great answer!

floody-berry 12y ago

yescrypt has ROM capabilities [1], which function like your large file idea. [1] https://password-hashing.net/wiki/doku.php/yescrypt#read-only_lookup_table_rom https://password-hashing.net/wiki/doku.php/yescrypt#read-onl...

warbiscuit 12y ago
Ooh, that looks interesting ... and not just for ROM feature. They've packed a TON of things into there. Even SCRAM support! I'm really intrigued by one of the planned features... "Hash upgrades to higher cost settings without knowledge of passwords". I can think of a way to implement that alone, but to pack that all in with those other features will be really impressive. And would be a huge boon to systems w/ infrequently logging-in users.
- solardiz 12y ago
  "Hash upgrades" have been added with the just-published v1 of the yescrypt submission to PHC. There is not yet an implementation of an "upgrade this hash" function (also, hash encoding needs to be finalized, including encoding of the upgrade count parameter), but now it's a matter of writing this additional code outside of the actual password hashing code (already capable of computing possibly-upgraded hashes). Unfortunately, with memory-hard schemes such upgrades involve an efficiency loss in terms of normalized area-time, and there's a tradeoff between granularity of upgrades and efficiency. For Catena (another PHC finalist that supports these), the time granularity is 2x to 3x, with efficiency down to 33.3%+ of non-upgraded hashes (after many upgrades). For yescrypt, it's 4x to 5x granularity and 60%+ efficiency, respectively. (I felt that 33.3%+ is just not good enough - in my opinion, it's usually better to postpone the upgrade until 60%+ can be achieved rather than upgrade early and prevent it from ever being achieved. The next easy step would be 77.7%+, but the granularity would be too high.) At the same time, support for ROM access frequency tuning (and thus for ROM-on-SSD, as opposed to ROM-in-RAM) has been dropped from yescrypt for now. The rationale is that builtin ROM-on-SSD didn't make enough sense without also having a ROM-in-RAM (in use cases for the former, the latter would also be easily affordable, including complexity wise, and would provide significant extra defense), and supporting two ROMs at once would be further beyond the comfort level for complexity of a hashing scheme in PHC (yescrypt is already somewhat beyond the comfort level). Support for two ROMs along with access frequency tuning might be re-added in an extended revision of yescrypt for specialized use cases at a later time, but this will be outside of PHC.

TheLoneWolfling 12y ago

> random accesses That's fairly simple to do: Do a standard password hash as usual (with salt, of course), then use the hash as an index into the data (or the low/high N bits of the hash, whatever) and use that as the final password hash. Just don't lose the data! Effectively using your password/salt as the key to a hashmap containing random data.

warbiscuit 12y ago
Yep... that was roughly my starting approach. Current one I'm playing with uses multiple samples (chosen as a function of the initial hash and the previous samples), to ensure the attacker has to actually take the whole file... otherwise the attacker gets away w/ 10% of file & 100 hashes, they've got good odds that one of those hashes only needs the first bit of the file. Still trying to play with it to see if I can make it harder to parallelize assuming attacker does get the file. But that gets into designing an entire password hash, not just a friendly wrapper, which is more than I'm prepare to chew on right now :)
- TheLoneWolfling 12y ago
  I'd just do pointer-chasing through the file, xored with the initial hash each time. I.e. out = hash xor data[hash] xor data[hash xor data[hash]] ... Alternative phrasing: out_n = data[hash xor out_(n-1)] xor out_(n-1), where out_1 = data[hash] xor hash "Random" accesses throughout the file - not the easiest to run in parallel. (That being said, I haven't checked to see if this is breakable)
- solardiz 12y ago
  You should take a look at: http://www.openwall.com/presentations/ZeroNights2012-New-In-Password-Hashing/ http://www.openwall.com/presentations/ZeroNights2012-New-In-... https://medium.com/@TapLink/the-password-defense-league-c416ceaedb33 https://medium.com/@TapLink/the-password-defense-league-c416... (I'm not happy with how Jeremy re-purposed the words "blind hashing" to mean essentially the approach I had recommended as a better alternative to his original "blind hashing", which I criticized in the ZeroNights talk, but other than that I agree with what he wrote.) To "make it harder to parallelize assuming attacker does get the file" (actually, to increase the cost per candidate password tested, not to make anything literally "hard to do"), I propose that "best of both worlds" approach (see my ZeroNights slides). And you're right, this means "designing an entire password hash, not just a friendly wrapper" (thus, different from Jeremy's work, and more similar to my work on yescrypt).