Educated Guesswork

PKCS #5, described in RFC 2898, has a widely used method for turning pass phrases into keys that includes an iteration count (section 5.1 and 5.2 of the RFC). It amounts to repeatedly iterating a hash or MAC function, feeding the output of one pass into the input of the next.

This approach is widely used, but typically there is no control by the end user over the number of iterations used. Some users wouldn't mind waiting 1 second or even longer; others would demand that it be perceptually instantaneous, say a tenth of a second. It will depend on how often you have to enter your pass phrase vs how much security you want.

GPG uses a slightly different system with a fixed count of 65536, but that is characters, not iterations. It alternately hashes the pass phrase and a salt until it has hashed this many characters. While this does slow things down relative to a straight hash, it is still fast and will be well under a millisecond, so you're not getting nearly as much protection as you might want.

Unfortunately this kind of option is complicated and hard to explain to an end user so there is not much motivation to include it as an adjustable parameter. GPG users are stuck with that value unless they patch their source.

Yes, I should have mentioned PKCS#5. Thanks for the reminder.

Another option is to have a random, secret, salt. This is generated when the key is first used and then discarded. Each time the user enters their password, the program then has to exhaustively search that salt until it gets the right key. (This is usually done by having some check that lets you instantly know if you've hit the right key.)

One problem with the salt is that you might get unlucky and choose a low one. 1% of people will have salts in the low 1% of the range. These people get less protection if they are unlucky enough to be targeted. This situation is different from keys, where you might think the same thing applies, because the range of these salts is intentionally small enough to allow brute forcing.

I don't think this is correct. Recall that the attacker doesn't know the salt and so has to try every candidate salt for each candidate password. So, if you imagine that the passwords are ranked in order from 1 to P and the salts are chosen from 1 to S, if you have password i and you happen to chose 1 as your salt, the attacker still has to do (i-1)S + 1 operations... as opposed to iS if you choose S as your salt. Assuming that i is even modestly large, these (i-1)S + 1 ~= iS.

Now, obviously, an attacker could try every candidate password with salt 1, then every candidate password with salt 2, etc. In this case you clearly would suffer from having a weak salt. On the other hand, this doesn't seem like a very good attack strategy, since it nullifies any benefit you might have from predicting which candidate passwords are more frequent, while optimizing for breaking passwords with small salts, even though salts are likely to be uniformly distributed, whereas passwords are not.

Ah, yes, that makes sense. So that would be another way to do it.

Now though it would mean that people would hope to be one of the "lucky" ones who gets a low salt! They get the benefit of fast access to their keys while protected by the attacker's forced assumption that the salt might be anything in a large range. I wonder if this would make people do something to improve their odds of getting lucky... which would then suggest that attackers might in fact bias their searches towards low salts, to some degree.

Interesting point. I think the Nash Equilibrium is probably random selection slightly biased towards small salts, but I can't prove it....