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
- 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.
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;
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 2160 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).
use a weak random number generator such as java.util.Random
to generate salt bytes!
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.