4.10. Deriving Symmetric Keys from a Password

Problem

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

Solution

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

Tip

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.

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.

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).



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

Get Secure Programming Cookbook for C and C++ now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.