7 ms·

Password Hashing Competition

72 points by LaSombra 12y ago

jszymborski 12y ago
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
  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.
cmiller1 12y ago
I wonder how these compare with bcrypt and scrypt. Anyone have any insight?
- sarciszewski 12y ago
  Yescrypt is derived from scrypt with extra tunable parameters. As for security margins? That remains to be seen.
- solardiz 12y ago
  Differently! The goal of PHC is to improve upon the current state-of-the-art, which includes bcrypt and scrypt, but there are many tradeoffs involved. A scheme that is better in one aspect might be worse (or just different) in another. These finalists try to improve upon scrypt (increase attack/defense cost ratio or/and avoid cache-timing side-channels while building upon ideas from scrypt and more): Argon, Catena, Lyra2, yescrypt, and maybe POMELO. Ditto for some non-finalists: Gambit, RIG, TwoCats. (Arguably some other non-finalists fall in this category as well.) These finalists include bcrypt-like components or properties while being scalable (to a varying extent) to larger than bcrypt's memory usage: battcrypt, POMELO, Pufferfish, yescrypt. And a non-finalist: TwoCats. Unlike bcrypt itself, battcrypt is likely to be implementable in scripting languages that offer native Blowfish. These finalists are totally different from bcrypt and scrypt, not trying to improve upon them nor even be on par with them: Makwa and Parallel. They are for different applications than bcrypt and scrypt. Parallel can be said to try to improve upon PBKDF2, though. As to more specific comparisons, with benchmarks and cost estimates for various settings on various types of hardware, this goes beyond a comment reply like this (or I'd need to focus on one PHC candidate, like mine, which would be unfair). It is a topic for the PHC discussions list and for materials included with each PHC candidate (some do include various numbers or/and claims to this extent).
yowmamasita 12y ago
Are there any pure Python implementation of these algorithms? I am looking for something that would work with Google App Engine.

72 points by LaSombra 12y ago

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

cmiller1 12y ago

I wonder how these compare with bcrypt and scrypt. Anyone have any insight?

sarciszewski 12y ago
Yescrypt is derived from scrypt with extra tunable parameters. As for security margins? That remains to be seen.
solardiz 12y ago
Differently! The goal of PHC is to improve upon the current state-of-the-art, which includes bcrypt and scrypt, but there are many tradeoffs involved. A scheme that is better in one aspect might be worse (or just different) in another. These finalists try to improve upon scrypt (increase attack/defense cost ratio or/and avoid cache-timing side-channels while building upon ideas from scrypt and more): Argon, Catena, Lyra2, yescrypt, and maybe POMELO. Ditto for some non-finalists: Gambit, RIG, TwoCats. (Arguably some other non-finalists fall in this category as well.) These finalists include bcrypt-like components or properties while being scalable (to a varying extent) to larger than bcrypt's memory usage: battcrypt, POMELO, Pufferfish, yescrypt. And a non-finalist: TwoCats. Unlike bcrypt itself, battcrypt is likely to be implementable in scripting languages that offer native Blowfish. These finalists are totally different from bcrypt and scrypt, not trying to improve upon them nor even be on par with them: Makwa and Parallel. They are for different applications than bcrypt and scrypt. Parallel can be said to try to improve upon PBKDF2, though. As to more specific comparisons, with benchmarks and cost estimates for various settings on various types of hardware, this goes beyond a comment reply like this (or I'd need to focus on one PHC candidate, like mine, which would be unfair). It is a topic for the PHC discussions list and for materials included with each PHC candidate (some do include various numbers or/and claims to this extent).

yowmamasita 12y ago

Are there any pure Python implementation of these algorithms? I am looking for something that would work with Google App Engine.