5 ms·

I'm no cryptoexpert but I was under the impression that slow password hashes were best, as they are harder to generate rainbow tables for and brute force the al

I'm no cryptoexpert but I was under the impression that slow password hashes were best, as they are harder to generate rainbow tables for and brute force the algorithm. Many of these algos are put aside for being too slow or praised for speed, and CPU/GPU optimization seems to be a big goal.

shawabawa3 12y ago
Any hashing algorithm can be made slower by stretching (repeatedly running the algorithm), so speed on its own is kind of meaningless Ideally you want algorithms that are hard to design custom hardware for, or in other words, are very efficient on general purpose hardware (CPU/GPU). You can then stretch the algorithm to take 200ms on your server without it being doable in nanoseconds by dedicated hardware I'm not entirely sure what "too slow for its memory usage means", but I would guess that it doesn't use enough memory which means ASICs/FPGAs are relatively easier to make for it
- tromp 12y ago
  "Too slow for its memory usage" means that that in order to use large amounts of memory, it becomes impractically slow. One of the non-finalists (Centrifuge) was criticised for byte-grained random memory accesses. A random access to main memory causes a row activation delay of roughly 50ns, so one should access many nearby bytes to make up for that.
  - chowells 12y ago
    That slows it down on general-purpose CPUs, but not on special-purpose ASICs. That's the exact opposite of what's desired.
warbiscuit 12y ago
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.
solardiz 12y ago
Slow to the extent affordable (thus, must be tunable) yet highly efficient on defender's hardware is best. (warbiscuit is correct on this.) "Hard" is a wrong word to use - we're not trying to make things hard to do (as this would only increase the initial investment needed for attacks), we're trying to increase the attackers' cost per candidate password tested. "Rainbow tables" are made irrelevant by proper use of salts. It's kindergarten stuff, as far as PHC is concerned. "Too slow for its memory usage" refers to some of the schemes that claim to be (and possibly are) memory-hard (see the scrypt paper). For those, it is desirable to be able to tune them such that their memory usage is maximized for a given running time or hashes per second throughput. For example, a scheme that can be tuned to achieve 1000 hashes/s at 16 MB memory usage per hash computed might win competition over a scheme that only achieves at most 10 hashes/s at the same memory usage on the same server. The latter happens not to be usable for password authentication on a server at that memory cost setting. Of course, there are also applications where the absolute maximum memory usage is not desirable - e.g., 1 second of running time might be affordable for deriving an encrypted filesystem key, but only e.g. 256 MB of free RAM might be available on a mobile device. There are PHC finalists that can be tuned to limit their memory usage as well, even if tuned to run for a long time, or that don't use much memory at all. Disclosure: I am the submitter of yescrypt. I also participate on the PHC panel (non-voting, because of having my own submission), along with many others.
omgitstom 12y ago
Slow is relative to today's tech. What is slow today may not be tomorrow. That is why you see password hashing algorithms with a 'work factor' to modify how slow it is.

shawabawa3 12y ago

Any hashing algorithm can be made slower by stretching (repeatedly running the algorithm), so speed on its own is kind of meaningless Ideally you want algorithms that are hard to design custom hardware for, or in other words, are very efficient on general purpose hardware (CPU/GPU). You can then stretch the algorithm to take 200ms on your server without it being doable in nanoseconds by dedicated hardware I'm not entirely sure what "too slow for its memory usage means", but I would guess that it doesn't use enough memory which means ASICs/FPGAs are relatively easier to make for it

tromp 12y ago
"Too slow for its memory usage" means that that in order to use large amounts of memory, it becomes impractically slow. One of the non-finalists (Centrifuge) was criticised for byte-grained random memory accesses. A random access to main memory causes a row activation delay of roughly 50ns, so one should access many nearby bytes to make up for that.
- chowells 12y ago
  That slows it down on general-purpose CPUs, but not on special-purpose ASICs. That's the exact opposite of what's desired.

warbiscuit 12y ago

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.

solardiz 12y ago

Slow to the extent affordable (thus, must be tunable) yet highly efficient on defender's hardware is best. (warbiscuit is correct on this.) "Hard" is a wrong word to use - we're not trying to make things hard to do (as this would only increase the initial investment needed for attacks), we're trying to increase the attackers' cost per candidate password tested. "Rainbow tables" are made irrelevant by proper use of salts. It's kindergarten stuff, as far as PHC is concerned. "Too slow for its memory usage" refers to some of the schemes that claim to be (and possibly are) memory-hard (see the scrypt paper). For those, it is desirable to be able to tune them such that their memory usage is maximized for a given running time or hashes per second throughput. For example, a scheme that can be tuned to achieve 1000 hashes/s at 16 MB memory usage per hash computed might win competition over a scheme that only achieves at most 10 hashes/s at the same memory usage on the same server. The latter happens not to be usable for password authentication on a server at that memory cost setting. Of course, there are also applications where the absolute maximum memory usage is not desirable - e.g., 1 second of running time might be affordable for deriving an encrypted filesystem key, but only e.g. 256 MB of free RAM might be available on a mobile device. There are PHC finalists that can be tuned to limit their memory usage as well, even if tuned to run for a long time, or that don't use much memory at all. Disclosure: I am the submitter of yescrypt. I also participate on the PHC panel (non-voting, because of having my own submission), along with many others.

omgitstom 12y ago

Slow is relative to today's tech. What is slow today may not be tomorrow. That is why you see password hashing algorithms with a 'work factor' to modify how slow it is.