How to simply and efficiently generate different keys from one password?

Question

I saw here that using the same key to encrypt and mac (in that order) a message could eventually be unsafe.

What is the best way to generate two different keys from the same password (using a PBKDF with a password and a salt)?

• Generate a longer output and split it?
• Generate two keys using the same password/salt but with different number of iterations?
• Generate two keys using the same password, but different salts?
• Something else?

(I know that using a AEAD mode would be better, but let's assume that I have no other choice)

Answer 1

Technically, PBKDF2 can produce an arbitrary long output (it is a Key Derivation Function), but it has issues for that: PBKDF2 uses HMAC over some hash function, which has output length k bits (e.g. k = 160 for the usual SHA-1). If you ask for more output than that size, then the computational cost rises quickly: if you want 320 bits, it will cost twice as much as 160 bits.

Unfortunately, though PBKDF2 is "strengthened" to deter dictionary attacks, the attacker's cost will not rise as fast. Consider for instance that you use PBKDF2/SHA-1 to produce 256 bits worth of key material: 128 bits for symmetric encryption, then 128 bits for a MAC. As the defender (the normal user) you must get your whole 256 bits. The attacker, on the other hand, does not need as much; he can simply produce the first 128 bits, at half the cost, and see if decryption yields non-junk data.

This is a known issue with PBKDF2. Note that the same issue would appear if you used another password hashing function twice, with two different salts: you pay for the hashing twice, but the attacker can ignore one of the keys, and will thereby be twice faster than you.

If you prefer to use bcrypt, then you run into another issue, which is that bcrypt is not a KDF; its output size is 192 bits. No more. Its processing time does not depend upon its output size, because its output size is fixed.

The generic method is to run a password hashing function, and then expand the output with a Key Derivation Function. That's what @CodesInChaos suggests, with HKDF-Expand. There are several KDF out there; usually, for my own designs/proposals, I rely on HMAC_DRBG, from NIST SP800-90 and X9.62 (e.g. in this). Ideally, you want a KDF which is well-vetted, i.e. which has been investigated by cryptographers, and they found nothing bad to say about it (or, even better, they produced "security proofs").

If you are in a hurry and don't need a lot of key material, a relatively simpler method is to hash the password hashing function output with SHA-512. This will give you 512 bits worth of key material.

Answer 2

When using PBKDF2 you can specify the output length of the output key. If you want to generate two 256 bit keys you generate a 512 bit output and split it. It is recommended to use a long salt, so that the entropy of the both keys is indeed 512 bit.

Answer 3

Generate two keys using the same password, but different salts? This is the correct answer given sufficiently long and [cryptographically] random salts. CodesInChaos makes two good points - don't exceed the natural output size of your underlying hash (160 bits for PBKDF2-HMAC-SHA-1, 512 bits for PBKDF2-HMAC-SHA-512, etc.), and a 128 bit salt is probably fine, especially if you're using 128 bit encryption.

Per RFC2898, one of the PBKDF2/RFC2898/PKCS#5 specs, section 4.1: "A salt in password-based cryptography has traditionally served the purpose of producing a large set of keys corresponding to a given password, among which one is selected at random according to the salt." The rest of 4.1 goes into detail on other considerations for generating multiple salts, in particular on how other parties can easily tell which salt they should use for which operation.*

*I.e. one answer (not explicitly referenced in the RFC) is to generate salts such that the salt that starts with AA is for the first operation, the salt that starts with AB for the second, AC for the third, etc.; add a non-random first byte to the salt for a "placement indicator", as long as the rest of the salt is cryptographically random and long enough.