4 ms·

Incidentally, a presentation at the NIST crypto reading group recently pointed out some of the weaknesses of current password KDFs: Argon2i has a viable attack,

Incidentally, a presentation at the NIST crypto reading group recently pointed out some of the weaknesses of current password KDFs: Argon2i has a viable attack, bcrypt truncates input, PBKDF2 needs an utterly insane number of rounds, and scrypt and argon2d/argon2id have data-dependent computation time and seem to be vulnerable to side-channel attacks. It turns out this is a really hard problem.

soatok 2y ago
I wasn't present for the NIST crypto reading group, but I documented a lot of these in 2022, if you'd like a deeper dive into that problem space: https://soatok.blog/2022/12/29/what-we-do-in-the-etc-shadow-cryptography-with-passwords/ https://soatok.blog/2022/12/29/what-we-do-in-the-etc-shadow-...
tptacek 2y ago
None of which are material compared to someone using a salted hash.
- lelanthran 2y ago
  I'm still in the dark about the problem with storing a salted hash, assuming a decent hash function and a decently long random salt. Simply replying "everyone knows what the problem is and has know since the 70s" is not as helpful as "here is the problem in three sentences". You can assume a base level of knowledge in your answer, as I have worked in encryption for a little bit, having written the 3DES implementation for some firmware, and done EMV development.
  - eadmund 2y ago
    The very short version is that decent hash functions are very, very fast, take almost no storage to compute and can thus easily be run in parallel. If you store `(,salt ,(HMAC-SHA2-256 salt password)) in your database and it leaks, an attacker can check hundreds of millions of possible passwords every second. The password ‘open sesame’ will get found pretty early, but so will ‘0p3n#s3s4m3$’. Pretty much anything which is not of the form ‘62Jm1QyJKGIZUpb5zARRLM’ will get found pretty quickly. You want something that is slow and takes a lot of resources to run. PBKDF2 was an early attempt which uses lots and lots of CPU, but it doesn’t use a lot of space. scrypt, bcrypt and Argon2 use lots of CPU and also lots of space in an attempt to make it more expensive to run (which is the point: you want the expected cost of finding a password to be more than the expected value of knowing that password). That’s one level of issue. The next level of issue is that when you run a simple system like that the user shares his password with you for you to check that it’s valid. This sounds find: you trust yourself, right? But you really shouldn’t: you make mistakes, after all. An you may have employees who make mistakes or who are malicious. They might log the password the user sent. They might steal the user’s password. Better systems use a challenge-response protocol in which you issue a one-time challenge to the user, the user performs some operation on the challenge and then responds with a proof that he knows his secret. But those have their own issues! And then there are issues with online systems and timing attacks and more. It’s a very difficult problem, and it all matters what you are protecting and what your threat model is.
    - lelanthran 2y ago
      > But those have their own issues! It’s a very difficult problem, and it all matters what you are protecting and what your threat model is. it's all a trade-off - those challenge/response systems are better, but they also have more moving parts. There's more bits in the system to go wrong. When there's only two pieces of the system (compare salted hash of user-provided password against stored salted hash) there's very little room for errors to creep in. Your auditing will all be focused on ensuring that the user-provided password is not leaked/stored/etc after a HTTP sign-in request is rxed. When using challenge/response, there is some pre-shared information that must synchronised between the systems (algorithm in use, key length, etc depending on the specific challenge/response system chosen). That's a great deal more points of attacks for malicious actors. And then, of course, you need to add versioning to the system (algorithms may be upgraded over time, key lengths may be expanded, etc) that all present even more points of attack. Compare to the simple "compare salted hash of password to stored salted hash": even with upgrading the algorithms and the key lengths there still remain only one point of attack - downloading the salted hashes! It doesn't matter how much more secure a competing system is if it introduces, in practice anyway, more points of failure. My takeaway after doing some cryptography for some parts of my career is that by choosing a hash function to be expensive in computational power and expensive is space and keeping the "user enters a password and we verify it" is still going to have fewer points of attack than "Synchronising pre-shared information between user and authenticator as the security is upgraded over the years". Basically, the trade-off is between "we chose a quick hash function, but can at least upgrade everything without the client software noticing" and the digital equivalent of "It's an older code, sir, but it checks out" problems.
      - eadmund 2y ago
        You keep returning to salted hashes. Please read the first two paragraphs of what I wrote for why that is a mistake. If you are going to use a shared secret system, do not use salted hashes. There is almost never a good reason to use salted hashes in 2025. > you need to add versioning to the system You need this with salted hashes, too! And of course with any password-based system.
- pclmulqdq 2y ago
  In all seriousness, can you please stop recommending bcrypt for new systems? The input length is hard limited to a frighteningly short string and it is not a KDF since it has a fixed output length. Its internal state is small enough that it can be efficiently cracked with FPGAs (although the structure is unsuitable for GPU-based crackers). The distinction between a KDF and a hash function is that a KDF has an output length that is configurable so you can directly use its output to generate a cryptographic key with 100% of the entropy of the input. A KDF theoretically needs to have arbitrary input length and arbitrary output length. Bcrypt has neither. Argon2d is great, scrypt is great, PBKDF2 with 1000000+ rounds works fine if you want FIPS, but bcrypt is somehow still on many people's list as though it doesn't have these flaws. It's not at the point where it needs to be imminently replaced in a legacy system, but if you're building something new, you should use something better.

soatok 2y ago

I wasn't present for the NIST crypto reading group, but I documented a lot of these in 2022, if you'd like a deeper dive into that problem space: https://soatok.blog/2022/12/29/what-we-do-in-the-etc-shadow-cryptography-with-passwords/ https://soatok.blog/2022/12/29/what-we-do-in-the-etc-shadow-...

tptacek 2y ago

None of which are material compared to someone using a salted hash.

lelanthran 2y ago
I'm still in the dark about the problem with storing a salted hash, assuming a decent hash function and a decently long random salt. Simply replying "everyone knows what the problem is and has know since the 70s" is not as helpful as "here is the problem in three sentences". You can assume a base level of knowledge in your answer, as I have worked in encryption for a little bit, having written the 3DES implementation for some firmware, and done EMV development.
- eadmund 2y ago
  The very short version is that decent hash functions are very, very fast, take almost no storage to compute and can thus easily be run in parallel. If you store `(,salt ,(HMAC-SHA2-256 salt password)) in your database and it leaks, an attacker can check hundreds of millions of possible passwords every second. The password ‘open sesame’ will get found pretty early, but so will ‘0p3n#s3s4m3$’. Pretty much anything which is not of the form ‘62Jm1QyJKGIZUpb5zARRLM’ will get found pretty quickly. You want something that is slow and takes a lot of resources to run. PBKDF2 was an early attempt which uses lots and lots of CPU, but it doesn’t use a lot of space. scrypt, bcrypt and Argon2 use lots of CPU and also lots of space in an attempt to make it more expensive to run (which is the point: you want the expected cost of finding a password to be more than the expected value of knowing that password). That’s one level of issue. The next level of issue is that when you run a simple system like that the user shares his password with you for you to check that it’s valid. This sounds find: you trust yourself, right? But you really shouldn’t: you make mistakes, after all. An you may have employees who make mistakes or who are malicious. They might log the password the user sent. They might steal the user’s password. Better systems use a challenge-response protocol in which you issue a one-time challenge to the user, the user performs some operation on the challenge and then responds with a proof that he knows his secret. But those have their own issues! And then there are issues with online systems and timing attacks and more. It’s a very difficult problem, and it all matters what you are protecting and what your threat model is.
  - lelanthran 2y ago
    > But those have their own issues! It’s a very difficult problem, and it all matters what you are protecting and what your threat model is. it's all a trade-off - those challenge/response systems are better, but they also have more moving parts. There's more bits in the system to go wrong. When there's only two pieces of the system (compare salted hash of user-provided password against stored salted hash) there's very little room for errors to creep in. Your auditing will all be focused on ensuring that the user-provided password is not leaked/stored/etc after a HTTP sign-in request is rxed. When using challenge/response, there is some pre-shared information that must synchronised between the systems (algorithm in use, key length, etc depending on the specific challenge/response system chosen). That's a great deal more points of attacks for malicious actors. And then, of course, you need to add versioning to the system (algorithms may be upgraded over time, key lengths may be expanded, etc) that all present even more points of attack. Compare to the simple "compare salted hash of password to stored salted hash": even with upgrading the algorithms and the key lengths there still remain only one point of attack - downloading the salted hashes! It doesn't matter how much more secure a competing system is if it introduces, in practice anyway, more points of failure. My takeaway after doing some cryptography for some parts of my career is that by choosing a hash function to be expensive in computational power and expensive is space and keeping the "user enters a password and we verify it" is still going to have fewer points of attack than "Synchronising pre-shared information between user and authenticator as the security is upgraded over the years". Basically, the trade-off is between "we chose a quick hash function, but can at least upgrade everything without the client software noticing" and the digital equivalent of "It's an older code, sir, but it checks out" problems.
    - eadmund 2y ago
      You keep returning to salted hashes. Please read the first two paragraphs of what I wrote for why that is a mistake. If you are going to use a shared secret system, do not use salted hashes. There is almost never a good reason to use salted hashes in 2025. > you need to add versioning to the system You need this with salted hashes, too! And of course with any password-based system.
pclmulqdq 2y ago
In all seriousness, can you please stop recommending bcrypt for new systems? The input length is hard limited to a frighteningly short string and it is not a KDF since it has a fixed output length. Its internal state is small enough that it can be efficiently cracked with FPGAs (although the structure is unsuitable for GPU-based crackers). The distinction between a KDF and a hash function is that a KDF has an output length that is configurable so you can directly use its output to generate a cryptographic key with 100% of the entropy of the input. A KDF theoretically needs to have arbitrary input length and arbitrary output length. Bcrypt has neither. Argon2d is great, scrypt is great, PBKDF2 with 1000000+ rounds works fine if you want FIPS, but bcrypt is somehow still on many people's list as though it doesn't have these flaws. It's not at the point where it needs to be imminently replaced in a legacy system, but if you're building something new, you should use something better.