3 ms·

> You mention yescrypt as an example of a good KDF, but its main design goal is to be a password hashing function! I mentioned I'd heard it was a good KDF (not

> You mention yescrypt as an example of a good KDF, but its main design goal is to be a password hashing function! I mentioned I'd heard it was a good KDF (not a good password storage function). I didn't know that was its main purpose. Thanks, will need to read more about it. Still, there's marginal returns on how much w can be increased while keeping the KDF useful, right? There's only so much magic they can do for a weak password. The article on scrypt being a poor candidate for password storage stuck out in my memory. I haven't seen or heard of the practice of strong hash function + random salt for password storage falling out of favor, so I didn't look into using other KDFs for that purpose. EDIT: it does seem like a trade off. This article seems to have a good explanation of it: https://crackstation.net/hashing-security.htm https://crackstation.net/hashing-security.htm If you use a key stretching hash in a web application, be aware that you will need extra computational resources to process large volumes of authentication requests, and that key stretching may make it easier to run a Denial of Service (DoS) attack on your website. I still recommend using key stretching, but with a lower iteration count. You should calculate the iteration count based on your computational resources and the expected maximum authentication request rate. The denial of service threat can be eliminated by making the user solve a CAPTCHA every time they log in. Always design your system so that the iteration count can be increased or decreased in the future. I do stand corrected about KDFs not being OK for password storage. Seems like they can be overkill in some situations, but in general do a good job of protecting passwords.

pbsd 12y ago
Yes, realistically you can only add at most ~30 bits of security to a password. This does not save very poor passwords, but can save decent ones. 'Strong' means different things in different contexts. SHA-256, for example, is a strong hash function: it has good preimage and collision resistance. However, a function is evaluated by its weakest point: when given a low-entropy secret (which is not the assumption in a strong hash function) and a strong hash function, the easiest attack is to bruteforce it by sampling its distribution (e.g., the most common password patterns). Since SHA-256 is fast, bruteforce is naturally also fast: the average time-to-break for a string of entropy s is 2^(s-1) times the cost of a SHA-256 evaluation. You can build on this by, say, iterating on SHA-256: def pwdhash(input, salt, w): h = sha256(salt + input).digest() for i in range(2**w): h = sha256(h).digest() return h But once you get into these ad hoc schemes to make the password hash less amenable to bruteforce, you're basically reinventing PBKDF2. scrypt (and bcrypt, to some extent) is like the above, but also uses random memory accesses on a large buffer to make things harder for specialized hardware (think GPUs, FPGAs, etc).
- chacham15 12y ago
  > Yes, realistically you can only add at most ~30 bits of security to a password. This sentence makes no sense to me. tptacek, correct me if I'm wrong, but Im pretty sure you can increase w to be as large as you want (i.e. the keyspace is large enough that youll be waiting years for a singular hash to finish before you wrap the whole keyspace). The only problem is that you force legitimate users to wait as well. Let make up an extreme example to illustrate, you set w so that a hash takes 1 years - 1 day to compute on the clients machine. Also, they change passwords every year. (Yes, this is absurd because it means that the client can only work one day a year). Now, lets assume that he uses one of five-hundred passwords. If the attacker has 100x the compute power of the client, he will only have a 20% chance of getting the correct password. And that is with only roughly 9 bits of entropy.
  - tptacek 12y ago
    Take anything 'pbsd writes to the bank. The problem here is that adding enough cost to add significantly more difficulty than that to a password quickly takes you to places where the real-world cost is infeasible. (He's not arguing against using KDF-like constructions to store password authenticators).
    - chacham15 12y ago
      I've actually wanted to ask you about: https://news.ycombinator.com/item?id=8088253 https://news.ycombinator.com/item?id=8088253 but I cant reply yet. If that ever actually became an issue, could it be solved by instead having the client send (2 ^ w) - 1 rounds of the hash and having the server do the last round? My reasoning is that the client would have to brute force the full hash space if they wanted to reverse only the last round instead of trying to brute force the password.
      - nialo 12y ago
        one possible reason this doesn't work: A limit on the number of iterations for a password hash is the amount of latency the user is willing to accept, which is (approximately) constant regardless of whether those iterations are computed on the client or the server

pbsd 12y ago

Yes, realistically you can only add at most ~30 bits of security to a password. This does not save very poor passwords, but can save decent ones. 'Strong' means different things in different contexts. SHA-256, for example, is a strong hash function: it has good preimage and collision resistance. However, a function is evaluated by its weakest point: when given a low-entropy secret (which is not the assumption in a strong hash function) and a strong hash function, the easiest attack is to bruteforce it by sampling its distribution (e.g., the most common password patterns). Since SHA-256 is fast, bruteforce is naturally also fast: the average time-to-break for a string of entropy s is 2^(s-1) times the cost of a SHA-256 evaluation. You can build on this by, say, iterating on SHA-256: def pwdhash(input, salt, w): h = sha256(salt + input).digest() for i in range(2**w): h = sha256(h).digest() return h But once you get into these ad hoc schemes to make the password hash less amenable to bruteforce, you're basically reinventing PBKDF2. scrypt (and bcrypt, to some extent) is like the above, but also uses random memory accesses on a large buffer to make things harder for specialized hardware (think GPUs, FPGAs, etc).

chacham15 12y ago
> Yes, realistically you can only add at most ~30 bits of security to a password. This sentence makes no sense to me. tptacek, correct me if I'm wrong, but Im pretty sure you can increase w to be as large as you want (i.e. the keyspace is large enough that youll be waiting years for a singular hash to finish before you wrap the whole keyspace). The only problem is that you force legitimate users to wait as well. Let make up an extreme example to illustrate, you set w so that a hash takes 1 years - 1 day to compute on the clients machine. Also, they change passwords every year. (Yes, this is absurd because it means that the client can only work one day a year). Now, lets assume that he uses one of five-hundred passwords. If the attacker has 100x the compute power of the client, he will only have a 20% chance of getting the correct password. And that is with only roughly 9 bits of entropy.
- tptacek 12y ago
  Take anything 'pbsd writes to the bank. The problem here is that adding enough cost to add significantly more difficulty than that to a password quickly takes you to places where the real-world cost is infeasible. (He's not arguing against using KDF-like constructions to store password authenticators).
  - chacham15 12y ago
    I've actually wanted to ask you about: https://news.ycombinator.com/item?id=8088253 https://news.ycombinator.com/item?id=8088253 but I cant reply yet. If that ever actually became an issue, could it be solved by instead having the client send (2 ^ w) - 1 rounds of the hash and having the server do the last round? My reasoning is that the client would have to brute force the full hash space if they wanted to reverse only the last round instead of trying to brute force the password.
    - nialo 12y ago
      one possible reason this doesn't work: A limit on the number of iterations for a password hash is the amount of latency the user is willing to accept, which is (approximately) constant regardless of whether those iterations are computed on the client or the server