5 ms·

As a quick summary of the previous discussion: - use PBKDF2 if you deal with a pointy haired boss who needs standards and accreditations - use scrypt if a

by gommm 13y ago

As a quick summary of the previous discussion: - use PBKDF2 if you deal with a pointy haired boss who needs standards and accreditations - use scrypt if a reliable implementation is available for your platform of choice - use bcrypt otherwise PKDF2 is worse than bcrypt (by roughly a factor of 5) and depends entirely on the security of hash functions; hash functions are more poorly studied than block ciphers. Scrypt is better than bcrypt (by roughly a factor of 4000 according to cperciva). It's memory hard and it would be much harder to build an effective system to hash as fast as possible due to this. Regardless, using adaptive hashing is what's important and you'll be good any of the three alternatives. Thanks to the comments from cperciva, moxie and tptacek. All errors in this summary are mine.

derefr 13y ago
> Scrypt is ... memory hard Haven't seen the answer to this: does scrypt being "memory hard" imply that you'll need a ton of RAM for your server if you get lots of users logging in concurrently?
- cschneid 13y ago
  In this case, it means that lots of memory accesses are required in mostly random order. This makes parallelizing on GPU hardware much more difficult than something like an MD5 or SHA hash, which don't require much memory access during the computation. This also boosts the cost of making dedicated cracking hardware (ASIC or FPGA type hardware) I'm having a hard time finding actual memory usage of a single password verification though. After a bit more reading just now, it looks like you can also adjust the memory-work-factor of scrypt as well, which doesn't appear to be available for bcrypt (very unsure on this one though, please dont' take my word on it). Does anybody out there have a good side-by-side comparison of practicalities like "memory usage", "flexibility", "can it be parallelized on CPU/GPU/FPGA/ASIC" and so on across all the popular hashing setups?
- lambda 13y ago
  Not really. In the scrypt paper, cperciva recommends parameters that allow it to do a single password hash in 64 ms, and in the process use only 4k of RAM. Nowadays, as processors are faster and ram is cheaper, you'd probably want to up the parameters a bit, so that the encryption time will be similar (between 50-100 ms) on modern hardware, and the RAM usage will scale proportionally (probably 128k, based on the ratio of RAM prices between 2002 and now). That means that you would be able to handle 10-20 logins per second per core, using no more than 2.5 MB in the process (if they were all run in parallel on separate threads and so all of that memory was needed at once; that's obviously a worst case, most likely they would be scheduled more sequentially and use proportionally less RAM as you would free the memory after finishing an encryption). On a 12 core machine, you might wind up using 30 MB at at time, to support 240 logins per second. If you need to handle 240 logins per second (which presumably means many many more requests per second, as there are usually many requests per login), 30 MB of RAM is the least of your worries. Note that these numbers are simply extrapolations from the ones in the original scrypt paper, I haven't actually tried this on modern hardware. Regardless, there are parameters that allow you to trade off CPU time and RAM usage, so you can tweak it to provide the level of performance that you require (with the understanding that the faster it is and less RAM it uses, the faster cracking it would be).
  - derefr 13y ago
    > If you need to handle 240 logins per second (which presumably means many many more requests per second, as there are usually many requests per login), 30 MB of RAM is the least of your worries. Well, if you have a large system of nodes, and until now you arranged things as an SOA where there's one node-cluster in particular that serves as an authentication service, doing all the hashing and table-lookup and comparison, and handing out session tokens for your other services to use--then with scrypt, that auth service will now be have the combined "memory hard"ness of every user's login requests on it for your entire system. With bcrypt, that level of CPU+memory load isn't so bad--but with scrypt, I think I'd think about pushing the hashing step into the client library part of that service's API, before the RPC call, so that the load gets distributed throughout the system back to where it's being "spent."
mbenjaminsmith 13y ago
Question: How can algorithms with an adjustable work factor be better or worse than each other? Answer: They can't be. They each provide an arbitrary amount of work (or entropy if you want to look at it that way) to a non-ideal key (e.g. a password). Moreover, any discussion of 'how much is enough' is a guess. How powerful the system used to brute force your keys will be is unknown. I've read things like 'adjust it until it takes 0.5 seconds on your computer'. That makes sense if and only if your key can only be attacked on that same machine, which is probably seldom the case. The rule of thumb is that it should be as expensive as you can make it (weighing user experience, operating costs, etc) and that more is better than less. There is no definite level of security provided by these algorithms (or families of) and their relative value can't be easily compared. Scrypt is an exception as it can use an arbitrary amount of memory, which adds a dimension to the cost added. Having said that, unless you're actually using these for what they were intended (deriving keys) and encrypting something then you're probably adding little actual security to your users' lives. I would consider this topic firmly in the realm of security theater. There's entirely too much handwringing about hashing passwords and entirely too little about encrypting user information or providing anonymity (where appropriate). I think we'd all be better off putting notices on signup pages that say "please don't reuse passwords" and spending more time on other more important security issues. Better, where we can we should move to zero-knowledge, bad-password tolerant protocols like SRP and bypass this issue entirely.
- nikic 13y ago
  > They can't be. That's not exactly right. What "better" or "worse" here refer to is how much the advantage the attacker with specialized hardware has over you running on a standard server. This advantage is largely dependent on how much memory the algorithm uses. The more memory, the better. In that regard the order is scrypt > bcrypt > PBKDF2. More memory is better because this makes running on a graphics card or ASIC harder or nigh impossible.
nullc 13y ago
> PKDF2 is worse than bcrypt (by roughly a factor of 5) Both Bcrytpt and PBKDF2 have security parameters. You can make them whatever ratio you want. (also scrypt)

by gommm 13y ago

derefr 13y ago

> Scrypt is ... memory hard Haven't seen the answer to this: does scrypt being "memory hard" imply that you'll need a ton of RAM for your server if you get lots of users logging in concurrently?

cschneid 13y ago
In this case, it means that lots of memory accesses are required in mostly random order. This makes parallelizing on GPU hardware much more difficult than something like an MD5 or SHA hash, which don't require much memory access during the computation. This also boosts the cost of making dedicated cracking hardware (ASIC or FPGA type hardware) I'm having a hard time finding actual memory usage of a single password verification though. After a bit more reading just now, it looks like you can also adjust the memory-work-factor of scrypt as well, which doesn't appear to be available for bcrypt (very unsure on this one though, please dont' take my word on it). Does anybody out there have a good side-by-side comparison of practicalities like "memory usage", "flexibility", "can it be parallelized on CPU/GPU/FPGA/ASIC" and so on across all the popular hashing setups?
lambda 13y ago
Not really. In the scrypt paper, cperciva recommends parameters that allow it to do a single password hash in 64 ms, and in the process use only 4k of RAM. Nowadays, as processors are faster and ram is cheaper, you'd probably want to up the parameters a bit, so that the encryption time will be similar (between 50-100 ms) on modern hardware, and the RAM usage will scale proportionally (probably 128k, based on the ratio of RAM prices between 2002 and now). That means that you would be able to handle 10-20 logins per second per core, using no more than 2.5 MB in the process (if they were all run in parallel on separate threads and so all of that memory was needed at once; that's obviously a worst case, most likely they would be scheduled more sequentially and use proportionally less RAM as you would free the memory after finishing an encryption). On a 12 core machine, you might wind up using 30 MB at at time, to support 240 logins per second. If you need to handle 240 logins per second (which presumably means many many more requests per second, as there are usually many requests per login), 30 MB of RAM is the least of your worries. Note that these numbers are simply extrapolations from the ones in the original scrypt paper, I haven't actually tried this on modern hardware. Regardless, there are parameters that allow you to trade off CPU time and RAM usage, so you can tweak it to provide the level of performance that you require (with the understanding that the faster it is and less RAM it uses, the faster cracking it would be).
- derefr 13y ago
  > If you need to handle 240 logins per second (which presumably means many many more requests per second, as there are usually many requests per login), 30 MB of RAM is the least of your worries. Well, if you have a large system of nodes, and until now you arranged things as an SOA where there's one node-cluster in particular that serves as an authentication service, doing all the hashing and table-lookup and comparison, and handing out session tokens for your other services to use--then with scrypt, that auth service will now be have the combined "memory hard"ness of every user's login requests on it for your entire system. With bcrypt, that level of CPU+memory load isn't so bad--but with scrypt, I think I'd think about pushing the hashing step into the client library part of that service's API, before the RPC call, so that the load gets distributed throughout the system back to where it's being "spent."

mbenjaminsmith 13y ago

Question: How can algorithms with an adjustable work factor be better or worse than each other? Answer: They can't be. They each provide an arbitrary amount of work (or entropy if you want to look at it that way) to a non-ideal key (e.g. a password). Moreover, any discussion of 'how much is enough' is a guess. How powerful the system used to brute force your keys will be is unknown. I've read things like 'adjust it until it takes 0.5 seconds on your computer'. That makes sense if and only if your key can only be attacked on that same machine, which is probably seldom the case. The rule of thumb is that it should be as expensive as you can make it (weighing user experience, operating costs, etc) and that more is better than less. There is no definite level of security provided by these algorithms (or families of) and their relative value can't be easily compared. Scrypt is an exception as it can use an arbitrary amount of memory, which adds a dimension to the cost added. Having said that, unless you're actually using these for what they were intended (deriving keys) and encrypting something then you're probably adding little actual security to your users' lives. I would consider this topic firmly in the realm of security theater. There's entirely too much handwringing about hashing passwords and entirely too little about encrypting user information or providing anonymity (where appropriate). I think we'd all be better off putting notices on signup pages that say "please don't reuse passwords" and spending more time on other more important security issues. Better, where we can we should move to zero-knowledge, bad-password tolerant protocols like SRP and bypass this issue entirely.

nikic 13y ago
> They can't be. That's not exactly right. What "better" or "worse" here refer to is how much the advantage the attacker with specialized hardware has over you running on a standard server. This advantage is largely dependent on how much memory the algorithm uses. The more memory, the better. In that regard the order is scrypt > bcrypt > PBKDF2. More memory is better because this makes running on a graphics card or ASIC harder or nigh impossible.

nullc 13y ago

> PKDF2 is worse than bcrypt (by roughly a factor of 5) Both Bcrytpt and PBKDF2 have security parameters. You can make them whatever ratio you want. (also scrypt)