4.10 Deriving Symmetric Keys from a Password

4.10.1 Problem

You do not want passwords to be stored on disk. Instead, you would like to convert a password into a cryptographic key.

4.10.2 Solution

Use PBKDF2, the password-based key derivation function 2, specified in PKCS #5.^[3]

^[3] This standard is available from RSA Security at http://www.rsasecurity.com/rsalabs/pkcs/pkcs-5/.

You can also use this recipe to derive keys from other keys. See Recipe 4.1 for considerations; that recipe also discusses considerations for choosing good salt values.

4.10.3 Discussion

Passwords can generally vary in length, whereas symmetric keys are almost always a fixed size. Passwords may be vulnerable to guessing attacks, but ultimately we'd prefer symmetric keys not to be as easily guessable.

The function spc_pbkdf2( ) in the following code is an implementation of PKCS #5, Version 2.0. PKCS #5 stands for "Public Key Cryptography Standard #5," although there is nothing public-key-specific about this standard. The standard defines a way to turn a password into a symmetric key. The name of the function stands for "password-based key derivation function 2," where the 2 indicates that the function implements Version 2.0 of PKCS #5.

#include <stdio.h> #include <string.h> #include <openssl/evp.h> #include <openssl/hmac.h> #include <sys/types.h> #include <netinet/in.h> #include <arpa/inet.h> /* for htonl */     #ifdef WIN32 typedef unsigned _ _int64 spc_uint64_t; #else typedef unsigned long long spc_uint64_t; #endif     /* This value needs to be the output size of your pseudo-random function (PRF)! */ #define PRF_OUT_LEN 20     /* This is an implementation of the PKCS#5 PBKDF2 PRF using HMAC-SHA1.  It  * always gives 20-byte outputs.  */     /* The first three functions are internal helper functions. */ static void pkcs5_initial_prf(unsigned char *p, size_t plen, unsigned char *salt,                                 size_t saltlen, size_t i, unsigned char *out,                                 size_t *outlen) {   size_t        swapped_i;   HMAC_CTX      ctx;       HMAC_CTX_init(&ctx);   HMAC_Init(&ctx, p, plen, EVP_sha1(  ));   HMAC_Update(&ctx, salt, saltlen);   swapped_i = htonl(i);   HMAC_Update(&ctx, (unsigned char *)&swapped_i, 4);   HMAC_Final(&ctx, out, (unsigned int *)outlen); }     /* The PRF doesn't *really* change in subsequent calls, but above we handled the  * concatenation of the salt and i within the function, instead of external to it,   * because the implementation is easier that way.  */ static void pkcs5_subsequent_prf(unsigned char *p, size_t plen, unsigned char *v,                                    size_t vlen, unsigned char *o, size_t *olen) {   HMAC_CTX ctx;       HMAC_CTX_init(&ctx);   HMAC_Init(&ctx, p, plen, EVP_sha1(  ));   HMAC_Update(&ctx, v, vlen);   HMAC_Final(&ctx, o, (unsigned int *)olen); }     static void pkcs5_F(unsigned char *p, size_t plen, unsigned char *salt,                      size_t saltlen, size_t ic, size_t bix, unsigned char *out) {   size_t        i = 1, j, outlen;   unsigned char ulast[PRF_OUT_LEN];       memset(out,0,  PRF_OUT_LEN);   pkcs5_initial_prf(p, plen, salt, saltlen, bix, ulast, &outlen);   while (i++ <= ic) {     for (j = 0;  j < PRF_OUT_LEN;  j++) out[j] ^= ulast[j];     pkcs5_subsequent_prf(p, plen, ulast, PRF_OUT_LEN, ulast, &outlen);   }   for (j = 0;  j < PRF_OUT_LEN;  j++) out[j] ^= ulast[j]; }     void spc_pbkdf2(unsigned char *pw, unsigned int pwlen, char *salt,                   spc_uint64_t saltlen, unsigned int ic, unsigned char *dk,                  spc_uint64_t dklen) {    unsigned long i, l, r;   unsigned char final[PRF_OUT_LEN] = {0,};       if (dklen > ((((spc_uint64_t)1) << 32) - 1) * PRF_OUT_LEN) {     /* Call an error handler. */     abort(  );   }   l = dklen / PRF_OUT_LEN;   r = dklen % PRF_OUT_LEN;   for (i = 1;  i <= l;  i++)     pkcs5_F(pw, pwlen, salt, saltlen, ic, i, dk + (i - 1) * PRF_OUT_LEN);   if (r) {     pkcs5_F(pw, pwlen, salt, saltlen, ic, i, final);     for (l = 0;  l < r;  l++) *(dk + (i - 1) * PRF_OUT_LEN + l) = final[l];   } }

The spc_pbkdf2( ) function takes seven arguments:

pw

Password, represented as an arbitrary string of bytes.

pwlen

Number of bytes in the password.

salt

String that need not be private but should be unique to the user. The notion of salt is discussed in Recipe 4.9.

saltlen

Number of bytes in the salt.

ic

"Iteration count," described in more detail later in this section. A good value is 10,000.

dk

Buffer into which the derived key will be placed.

dklen

Length of the desired derived key in bytes.

The Windows version of spc_pbkdf2( ) is called SpcPBKDF2( ). It has essentially the same signature, though the names are slightly different because of Windows naming conventions. The implementation uses CryptoAPI for HMAC-SHA1 and requires SpcGetExportableContext( ) and SpcImportKeyData( ) from Recipe 5.26.

#include <windows.h> #include <wincrypt.h>     /* This value needs to be the output size of your pseudo-random function (PRF)! */ #define PRF_OUT_LEN 20     /* This is an implementation of the PKCS#5 PBKDF2 PRF using HMAC-SHA1.  It  * always gives 20-byte outputs.  */     static HCRYPTHASH InitHMAC(HCRYPTPROV hProvider, HCRYPTKEY hKey, ALG_ID Algid) {   HMAC_INFO  HMACInfo;   HCRYPTHASH hHash;       HMACInfo.HashAlgid     = Algid;   HMACInfo.pbInnerString = HMACInfo.pbOuterString = 0;   HMACInfo.cbInnerString = HMACInfo.cbOuterString = 0;       if (!CryptCreateHash(hProvider, CALG_HMAC, hKey, 0, &hHash)) return 0;   CryptSetHashParam(hHash, HP_HMAC_INFO, (BYTE *)&HMACInfo, 0);   return hHash; }     static void FinalHMAC(HCRYPTHASH hHash, BYTE *pbOut, DWORD *cbOut) {   *cbOut = PRF_OUT_LEN;   CryptGetHashParam(hHash, HP_HASHVAL, pbOut, cbOut, 0);   CryptDestroyHash(hHash); }     static DWORD SwapInt32(DWORD dwInt32) {   _ _asm mov   eax, dwInt32   _ _asm bswap eax }     static BOOL PKCS5InitialPRF(HCRYPTPROV hProvider, HCRYPTKEY hKey,                             BYTE *pbSalt, DWORD cbSalt, DWORD dwCounter,                             BYTE *pbOut, DWORD *cbOut) {   HCRYPTHASH hHash;       if (!(hHash = InitHMAC(hProvider, hKey, CALG_SHA1))) return FALSE;   CryptHashData(hHash, pbSalt, cbSalt, 0);   dwCounter = SwapInt32(dwCounter);   CryptHashData(hHash, (BYTE *)&dwCounter, sizeof(dwCounter), 0);   FinalHMAC(hHash, pbOut, cbOut);   return TRUE; }     static BOOL PKCS5UpdatePRF(HCRYPTPROV hProvider, HCRYPTKEY hKey,                            BYTE *pbSalt, DWORD cbSalt,                            BYTE *pbOut, DWORD *cbOut) {   HCRYPTHASH hHash;       if (!(hHash = InitHMAC(hProvider, hKey, CALG_SHA1))) return FALSE;   CryptHashData(hHash, pbSalt, cbSalt, 0);   FinalHMAC(hHash, pbOut, cbOut);   return TRUE; }     static BOOL PKCS5FinalPRF(HCRYPTPROV hProvider, HCRYPTKEY hKey,                           BYTE *pbSalt, DWORD cbSalt, DWORD dwIterations,                           DWORD dwBlock, BYTE *pbOut) {   BYTE  pbBuffer[PRF_OUT_LEN];   DWORD cbBuffer, dwIndex, dwIteration = 1;       SecureZeroMemory(pbOut, PRF_OUT_LEN);   if (!(PKCS5InitialPRF(hProvider, hKey, pbSalt, cbSalt, dwBlock, pbBuffer,                         &cbBuffer))) return FALSE;   while (dwIteration < dwIterations) {     for (dwIndex = 0;  dwIndex < PRF_OUT_LEN;  dwIndex++)       pbOut[dwIndex] ^= pbBuffer[dwIndex];     if (!(PKCS5UpdatePRF(hProvider, hKey, pbBuffer, PRF_OUT_LEN, pbBuffer,                          &cbBuffer))) return FALSE;   }   for (dwIndex = 0;  dwIndex < PRF_OUT_LEN;  dwIndex++)     pbOut[dwIndex] ^= pbBuffer[dwIndex];   return TRUE; }     BOOL SpcPBKDF2(BYTE *pbPassword, DWORD cbPassword, BYTE *pbSalt, DWORD cbSalt,                DWORD dwIterations, BYTE *pbOut, DWORD cbOut) {   BOOL       bResult = FALSE;   BYTE       pbFinal[PRF_OUT_LEN];   DWORD      dwBlock, dwBlockCount, dwLeftOver;   HCRYPTKEY  hKey;   HCRYPTPROV hProvider;       if (cbOut > ((((_ _int64)1) << 32) - 1) * PRF_OUT_LEN) return FALSE;   if (!(hProvider = SpcGetExportableContext(  ))) return FALSE;   if (!(hKey = SpcImportKeyData(hProvider, CALG_RC4, pbPassword, cbPassword))) {     CryptReleaseContext(hProvider, 0);     return FALSE;   }       dwBlockCount = cbOut / PRF_OUT_LEN;   dwLeftOver   = cbOut % PRF_OUT_LEN;   for (dwBlock = 1;  dwBlock <= dwBlockCount;  dwBlock++) {     if (!PKCS5FinalPRF(hProvider, hKey, pbSalt, cbSalt, dwIterations, dwBlock,                        pbOut + (dwBlock - 1) * PRF_OUT_LEN)) goto done;   }   if (dwLeftOver) {     SecureZeroMemory(pbFinal, PRF_OUT_LEN);     if (!PKCS5FinalPRF(hProvider, hKey, pbSalt, cbSalt, dwIterations, dwBlock,                        pbFinal)) goto done;     CopyMemory(pbOut + (dwBlock - 1) * PRF_OUT_LEN, pbFinal, dwLeftOver);   }   bResult = TRUE;     done:   CryptDestroyKey(hKey);   CryptReleaseContext(hProvider, hKey);   return bResult;     }

The salt is used to prevent against a dictionary attack. Without salt, a malicious system administrator could easily figure out when a user has the same password as someone else, and he would be able to precompute a huge dictionary of common passwords and look to see if the user's password is in that list.

While salt is not expected to be private, it still must be chosen carefully. See Recipe 4.9 for more on salt.

How Many Iterations?

To what value should you set the iteration count? The answer depends on the environment in which you expect your software to be deployed. The basic idea is to increase computational costs so that a brute-force attack with lots of high-end hardware is as expensive as possible, but not to cause too noticeable a delay on the lowest-end box on which you would wish to run legitimately.

Often, password computations such as these occur on a server. However, there are still people out there who run servers on their 33 MHz machines. We personally believe that people running on that kind of hardware should be able to tolerate a one-second delay, at the very least when computing a password for a modern application. Usually, a human waiting on the other end will be willing to tolerate an even longer wait as long as they know why they are waiting. Two to three seconds isn't so bad.

With that guideline, we have timed our PKCS #5 implementation with some standard input. Based on those timings, we think that 10,000 is good for most applications, and 5,000 is the lowest iteration count you should consider in this day and age. On a 33 MHz machine, 10,000 iterations should take about 2.5 seconds to process. On a 1.67 GHz machine, they take a mere 0.045 seconds. Even if your computation occurs on an embedded processor, people will still be able to tolerate the delay.

The good thing is that it would take a single 1.67 GHz machine more than 6 years to guess 2³² passwords, when using PKCS #5 and 10,000 iterations. Therefore, if there really is at least 32 bits of entropy in your password (which is very rare), you probably won't have to worry about any attacker who has fewer than a hundred high-end machines at his disposal, at least for a few years.

Expect governments that want your password to put together a few thousand boxes complete with crypto acceleration, though!

Even with salt, password-guessing attacks are still possible. To prevent against this kind of attack, PKCS #5 allows the specification of an iteration count, which basically causes an expensive portion of the key derivation function to loop the specified number of times. The idea is to slow down the time it takes to compute a single key from a password. If you make key derivation take a tenth of a second, the user won't notice. However, if an attacker tries to carry out an exhaustive search of all possible passwords, she will have to spend a tenth of a second for each password she wants to try, which will make cracking even a weak password quite difficult. As we describe in the sidebar "How Many Iterations?", we recommend an iteration count of 10,000.

The actual specification of the key derivation function can be found in Version 2.0 of the PKCS #5 standards document. In brief, we use a pseudo-random function using the password and salt to get out as many bytes as we need, and we then take those outputs and feed them back into themselves for each iteration.

There's no need to use HMAC-SHA1 in PKCS #5. Instead, you could use the Advanced Encryption Standard (AES) as the underlying cryptographic primitive, substituting SHA1 for a hash function based on AES (see Recipe 6.15 and Recipe 6.16).

4.10.4 See Also

• RSA's PKCS #5 page: http://www.rsasecurity.com/rsalabs/pkcs/pkcs-5/

• Recipe 4.9, Recipe 4.11, Recipe 5.26, Recipe 6.15, Recipe 6.16