Password-based encryption in Java: salt and key derivation

In our introduction to password-based encryption, we mentioned two fundamental problems: (a) user-memorable passwords typically don't contain as much randomness as we need for a secure key; (b) in a typical application, an attacker gets as many tries as they like at the password. An additional problem is that if, say, the password abc123 always generated the same key in our application, then an attacker could calculate the key from this password once and then quickly decrypt any data protected with this password.

Two common techniques are used in password-based encryption to try to alleviate these problems:

• a deliberately slow method is used to derive the encryption key from the password, reducing the number of guesses that an attacker can make in a given time frame;
• some random bytes, called a salt, are appended to the password before it is used to calculate the key.

We'll look firstly at salt, and then on the next page at typical PBE key derivation techniques.

Salt

The idea of salt is that when the user enters the password, we don't actually use their raw password to generate the key. We first append some random bytes to the password. A new, random salt is used for every file/piece of data being encrypted. The salt bytes are not secret: they are stored unencrypted along side the encrypted data. This means that the salt bytes would add no extra security if there was only once piece of data in the world encrypted with a given password. But they prevent dictionary attacks, whereby an attacker pre-computes the keys from some common passwords and then tries those keys on the encrypted data. Without salt bytes, the dictionary attack would be worthwhile attack because we use a deliberately slow function to derive a key from a password. With the salt bytes, the attacker is forced to run the slow key derivation function for each password they want to try on each piece of data.

To generate salt bytes in Java, we just need to make sure that we use a secure random number generator. Construct an instance of SecureRandom, create (say) a 20-byte array, and call nextBytes() on that array:

Random r = new SecureRandom();
byte[] salt = new byte[20];
r.nextBytes(salt);

How many salt bytes should you use? Well, not too few (probably not less than 16 bytes; Ferguson & Schneier perhaps overcautiously recommend 32). But there's also no point in using more salt bytes than the period of the random number generator. For example, SecureRandom, which is based internally on the 160-bit SHA-1 hash function, can only generate 2¹⁶⁰ possible sequences of any length. So there is absolutely no point in using more than 160 bits of salt (=20 bytes) with this generator. There is also no point in having a salt that is longer than the key length (given equal bit lengths, it's generally quicker to brute-force the symmetric key than the salt).

PBE key derivation

Now, given a (salt, password) pair, the aim is to use these to generate, say, an AES or DES encryption key. On the next page, we look at typical password-based key derivation functions.