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