Encryption using password-derived keys

[John Kelsey]

>From: Jack Lloyd <lloyd at randombit.net>
>Sent: Nov 29, 2005 11:08 AM
>To: cryptography at metzdowd.com
>Subject: Encryption using password-derived keys

>The basic scenario I'm looking at is encrypting some data using a
>password-derived key (using PBKDF2 with sane salt sizes and iteration
>counts). I am not sure if what I'm doing is sound practice or just
>pointless overengineering and wanted to get a sanity check.

>My inclination is to use the PBKDF2 output as a key encryption key,
>rather than using it to directly key the cipher (with the key used
>for the cipher itself being created by a good PRNG). For some reason
>the idea of using it directly makes me nervous, but not in a way I
>can articulate, leading me to suspect I'm worried over nothing.

I think this is sensible for convenience reasons:

a.  You can now change passwords without decrypting and re-encrypting
all your data.  And similarly, if you ever had a reason to change
keys, you could do that without changing passwords.  

b.  You can now check the correctness of the entered password when you
decrypt the data encryption key (using authenticated encryption!),
rather than needing to process the whole data.  (You could also just
generate a few extra check bits from PBKDF2.)  

>So, assuming using it as a KEK makes sense: At first I thought to use
>XOR to combine the two keys, but realized that could lead to related
>key attacks (by just flipping bits in the field containing the
>encrypted key). That is probably not a problem with good algorithms,
>but, then again, why take the chance; so I was thinking instead using
>NIST's AES-wrap (or perhaps a less weirdly designed variant of it
>that uses HMAC for integrity checking and AES in CBC mode for
>confidentiality).

You almost certainly need to do encryption and authentication both on
your bulk data and your encrypted key.  So why not do some mode that
does both (CCM being the obvious choice) for both the key encryption
and the bulk data encryption?

Like:

salt = PRNG_output(128)
iteration_count = 1000000
nonce = current nonce
DEK = PRNG_output(128)
KEK = PBKDF2(password,salt,iteration_count,128)
KeyBlob = CCM(KEK,0,DEK)
BulkData = CCM(DEK,nonce,plaintext)

>Am I thinking about this far harder than I should?

I'll toss two other random ideas out there to see if they're useful to
you:

a.  You may be worried about having a properly seeded PRNG available
to do your data encryption key generation.  I think a sensible way
around this is to use both a PRNG output and some extra bits from
PBKDF2 to derive the first data encryption key.  Like you could do:

X = PBKDF2(password,salt,iteration_count,256)
KEK = left 128 bits of X
S = right 128 bits of X
DEK = S xor PRNG_output(128)  

b.  You can use a clever trick by Abadi, Lomas and Needham to save
yourself most of the work you do on iterating the password hash during
the creation of the KEK, but not when rederiving it.  Basically, what
you do is instead of setting an iteration count of 2^{21}, you
generate a big random salt, and omit 20 bits of it from the salt
that's stored with the encrypted file.  This forces anyone trying to
re-derive the KEK to do about 2^{20} work on average, but it makes
generating the original encrypted file almost free.  I'm always
surprised that this isn't used more often, because it's such a clever
trick.

>-Jack

--John Kelsey

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com