4.11 Algorithmically Generating Symmetric Keys from One Base Secret

4.11.1 Problem

You want to generate a key to use for a short time from a long-term secret (generally a key, but perhaps a password). If a short-term key is compromised, it should be impossible to recover the base secret. Multiple entities in the system should be able to compute the same derived key if they have the right base secret.

For example, you might want to have a single long-term key and use it to create daily encryption keys or session-specific keys.

4.11.2 Solution

Mix a base secret and any unique information you have available, passing them through a pseudo-random function (PRF), as discussed in the following section.

4.11.3 Discussion

The basic idea behind secure key derivation is to take a base secret and a unique identifier that distinguishes the key to be derived (called a distinguisher) and pass those two items through a pseudo-random function. The PRF acts very much like a cryptographic one-way hash from a theoretical security point of view, and indeed, such a one-way hash is often good as a PRF.

There are many different ad hoc solutions for doing key derivation, ranging from the simple to the complex. On the simple side of the spectrum, you can concatenate a base key with unique data and pass the string through SHA1. On the complex side is the PBKDF2 function from PKCS #5 (described in Recipe 4.10).

The simple SHA1 approach is perhaps too simple for general-purpose requirements. In particular, there are cases where you one might need a key that is larger than the SHA1 output length (i.e., if you're using AES with 192-bit keys but are willing to have only 160 bits of strength). A general-purpose hash function maps n bits to a fixed number of bits, whereas we would like a function capable of mapping n bits to m bits.

PBKDF2 can be overkill. Its interface includes functionality to thwart password-guessing attacks, which is unnecessary when deriving keys from secrets that were themselves randomly generated.

Fortunately, it is easy to build an n-bit to m-bit PRF that is secure for key derivation. The big difficulty is often in selecting good distinguishers (i.e., information that differentiates parties). Generally, it is okay to send differentiating information that one side does not already have and cannot compute in the clear, because if an attacker tampers with the information in traffic, the two sides will not be able to agree on a working key. (Of course, you do need to be prepared to handle such attacks.) Similarly, it is okay to send a salt. See the sidebar, Distinguisher Selection for a discussion.

Distinguisher Selection The basic idea behind a distinguisher is that it must be unique. If you want to create a particular derived key, we recommend that you string together in a predetermined order any interesting information about that key, separating data items with a unique separation character (i.e., not a character that would be valid in one of the data items). You can use alternate formats, as long as your data representation is unambiguous, in that each possible distinguisher is generated by a single, unique set of information. As an example, let's say you want to have a different session key that you change once a day. You could then use the date as a unique distinguisher. If you want to change keys every time there's a connection, the date is no longer unique. However, you could use the date concatenated with the number of times a connection has been established on that date. The two together constitute a unique value. There are many potential data items you might want to include in a distinguisher, and they do not have to be unique to be useful, as long as there is a guarantee that the distinguisher itself is unique. Here is a list of some common data items you could use: The encryption algorithm and any parameters for which the derived key will be used The number of times the base key has been used, either overall or in the context of other interesting data items A unique identifier corresponding to an entity in the system, such as a username or email address The IP addresses of communicating parties A timestamp, or at least the current date The MAC address associated with the network interface being used Any other session-specific information In addition, to prevent against any possible offline precomputation attacks, we recommend you add to your differentiator a random salt of at least 64 bits, which you then communicate to any other party that needs to derive the same key.

The easiest way to get a solid solution that will resist potentially practical attacks is to use HMAC in counter mode. (Other MACs are not as well suited for this task, because they tend not to handle variable-length keys.) You can also use this solution if you want an all-block cipher solution, because you can use a construction to convert a block cipher into a hash function (see Recipe 6.15 and Recipe 6.16).

More specifically, key HMAC with the base secret. Then, for every block of output you need (where the block size is the size of the HMAC output), MAC the distinguishers concatenated with a fixed-size counter at the end. The counter should indicate the number of blocks of output previously processed. The basic idea is to make sure that each MAC input is unique.

If the desired output length is not a multiple of the MAC output length, simply generate blocks until you have sufficient bytes, then truncate.

The security level of this solution is limited by the minimum of the number of bits of entropy in the base secret and the output size of the MAC. For example, if you use a key with 256 bits of entropy, and you use HMAC-SHA1 to produce a 256-bit derived key, never assume that you have more than 160 bits of effective security (that is the output size of HMAC-SHA1).

Here is an example implementation of a PRF based on HMAC-SHA1, using the OpenSSL API for HMAC (discussed in Recipe 6.10):

#include <sys/types.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <openssl/evp.h>
#include <openssl/hmac.h>
#define HMAC_OUT_LEN  20 /* SHA1 specific */
   
void spc_make_derived_key(unsigned char *base, size_t bl, unsigned char *dist, 
                           size_t dl, unsigned char *out, size_t ol) {
  HMAC_CTX       c;
  unsigned  long ctr = 0, nbo_ctr;
  size_t         tl, i;
  unsigned char  last[HMAC_OUT_LEN];
   
  while (ol >= HMAC_OUT_LEN) {
    HMAC_Init(&c,  base, bl, EVP_sha1(  ));
    HMAC_Update(&c, dist, dl);
    nbo_ctr = htonl(ctr++);
    HMAC_Update(&c, (unsigned char *)&nbo_ctr, sizeof(nbo_ctr));
    HMAC_Final(&c,  out, &tl);
    out += HMAC_OUT_LEN;
    ol  -= HMAC_OUT_LEN;
  }
  if (!ol) return;
  HMAC_Init(&c, base, bl, EVP_sha1(  ));
  HMAC_Update(&c, dist, dl);
  nbo_ctr = htonl(ctr);
  HMAC_Update(&c, (unsigned char *)&nbo_ctr, sizeof(nbo_ctr));
  HMAC_Final(&c, last, &tl);
  for (i = 0;  i < ol;  i++)
    out[i] = last[i];
}

Here is an example implementation of a PRF based on HMAC-SHA1, using the Windows CryptoAPI for HMAC (discussed in Recipe 6.10). The code presented here also requires SpcGetExportableContext( ) and SpcImportKeyData( ) from Recipe 5.26.

#include <windows.h>
#include <wincrypt.h>
   
#define HMAC_OUT_LEN 20 /* SHA1 specific */
   
static DWORD SwapInt32(DWORD dwInt32) {
  _ _asm mov   eax, dwInt32
  _ _asm bswap eax
}
   
BOOL SpcMakeDerivedKey(BYTE *pbBase, DWORD cbBase, BYTE *pbDist, DWORD cbDist,
                       BYTE *pbOut, DWORD cbOut) {
  BYTE       pbLast[HMAC_OUT_LEN];
  DWORD      cbData, dwCounter = 0, dwBigCounter;
  HCRYPTKEY  hKey;
  HMAC_INFO  HMACInfo;
  HCRYPTHASH hHash;
  HCRYPTPROV hProvider;
   
  if (!(hProvider = SpcGetExportableContext(  ))) return FALSE;
  if (!(hKey = SpcImportKeyData(hProvider, CALG_RC4, pbBase, cbBase))) {
    CryptReleaseContext(hProvider, 0);
    return FALSE;
  }
  HMACInfo.HashAlgid     = CALG_SHA1;
  HMACInfo.pbInnerString = HMACInfo.pbOuterString = 0;
  HMACInfo.cbInnerString = HMACInfo.cbOuterString = 0;
   
  while (cbOut >= HMAC_OUT_LEN) {
    if (!CryptCreateHash(hProvider, CALG_HMAC, hKey, 0, &hHash)) {
      CryptDestroyKey(hKey);
      CryptReleaseContext(hProvider, 0);
      return FALSE;
    }
    CryptSetHashParam(hHash, HP_HMAC_INFO, (BYTE *)&HMACInfo, 0);
    CryptHashData(hHash, pbDist, cbDist, 0);
    dwBigCounter = SwapInt32(dwCounter++);
    CryptHashData(hHash, (BYTE *)&dwBigCounter, sizeof(dwBigCounter), 0);
    cbData = HMAC_OUT_LEN;
    CryptGetHashParam(hHash, HP_HASHVAL, pbOut, &cbData, 0);
    CryptDestroyHash(hHash);
    pbOut += HMAC_OUT_LEN;
    cbOut -= HMAC_OUT_LEN;
  }
  if (cbOut) {
    if (!CryptCreateHash(hProvider, CALG_HMAC, hKey, 0, &hHash)) {
      CryptDestroyKey(hKey);
      CryptReleaseContext(hProvider, 0);
      return FALSE;
    }
    CryptSetHashParam(hHash, HP_HMAC_INFO, (BYTE *)&HMACInfo, 0);
    CryptHashData(hHash, pbDist, cbDist, 0);
    dwBigCounter = SwapInt32(dwCounter);
    CryptHashData(hHash, (BYTE *)&dwBigCounter, sizeof(dwBigCounter), 0);
    cbData = HMAC_OUT_LEN;
    CryptGetHashParam(hHash, HP_HASHVAL, pbLast, &cbData, 0);
    CryptDestroyHash(hHash);
    CopyMemory(pbOut, pbLast, cbOut);
  }
   
  CryptDestroyKey(hKey);
  CryptReleaseContext(hProvider, 0);
  return TRUE;
}

Ultimately, if you have a well-specified constant set of distinguishers and a constant base secret length, it is sufficient to replace HMAC by SHA1-hashing the concatenation of the key, distinguisher, and counter.

4.11.4 See Also

Recipe 4.10, Recipe 5.26, Recipe 6.10, Recipe 6.15, Recipe 6.16