DI Management Home > Cryptography > Key Derivation Functions

Key Derivation Functions: How many KDFs are there?


A key derivation function (KDF) is a deterministic algorithm to derive a key of a given size from some secret value. If two parties use the same shared secret value and the same KDF, they should always derive exactly the same key.

Introduction | Glossary | Notation and Conventions | KDF1 | KDF2 | KDF3 | KDF4 | Examples of KDF | Password-Based Key Derivation Functions (PBKDF) | PBKDF1 | PBKDF-Schneier | PBKDF2 | Examples of PBKDF | References | Contact us

Introduction

There are at least four versions of KDF plus at least three password-based key derivation functions (PBKDF). One of the KDF algorithms is used as a mask generation function (MGF) in some public key encoding schemes.

The difference between a KDF and a PBKDF is that a KDF uses a binary secret value to derive a key while a PBKDF uses a text password together with a salt and an iteration count. The secret value for a KDF is provided as a byte string. A KDF may also use an optional, publicly-revealed byte string, OtherInfo.

KDF:   (derived key of length kLen) <-- (secret value, [OtherInfo])
PBKDF: (derived key of length kLen) <-- (password, salt, iterationCount)
AlgorithmReference
KDF1ISO-18033-2
KDF2ISO-18033-2, ANSI-X9-42
KDF3ISO-18033-2, NIST SP800-56A
KDF4ISO-18033-2
MGF1P1363, PKCS1-v2
PBKDF-Schneier[SCHN96]
PBKDF1PKCS5-v1
PBKDF2PKCS5-v2

Glossary

KDF
key derivation function
PBKDF
password-based key derivation function
MGF
mask generation function
PRF
pseudo-random function
PRBG
pseudo-random byte generator
HMAC
keyed-hash message authentication code
Hash
a cryptographically-secure message digest hash function

Notation and Conventions

In this page, all byte encodings are represented in hex and all lengths are defined in bytes (octets). Note that some references define lengths in bits and use bit strings instead of byte strings. In practice, there is no difference except a larger unit of measure.

KDF1

KDF1 is defined in ISO-18033-2 [ISO18033] and is the same as the MGF1 function from IEEE P1363a [P1363] and PKCS#1 v2.1 [PKCS1].


Algorithm: KDF1/MGF1.
INPUT:
Z, shared secret, a byte string;
Hash, hash function with output hLen bytes;
kLen, intended length of keying material in bytes;
[OtherInfo], optional extra shared material.
OUTPUT: Derived key, K, of length kLen bytes.
  1. Set d = ceiling(kLen/hLen).
  2. Set T = "", the empty string.
  3. for Counter = 0 to d-1 do:
    • C = IntegerToString(Counter, 4)
    • T = T || Hash(Z || C || [OtherInfo])
  4. Output the first kLen bytes of T as K.

KDF2

KDF2 is the same as KDF1 except the counter runs from 1 to d.

KDF2 is defined in ISO-18033-2 [ISO18033]. It is the same as the KDF based on concatenation algorithm in Section 7.7.2 of ANSI X9.42 [AX942], although you won't be able to reproduce the test vectors because the ANSI 9.42 document is wrong!

KDF3

KDF3 is defined in ISO-18033-2 [ISO18033] and uses essentially the same algorithm as the KDF function in NIST SP800-56A [SP80056A]. In the ISO-18033-2 version, KDF3 has an additional parameter pAmt, an integer of value 4 or more. It is recommended that this value is either 4 or is the length of the input block to the Hash function (64 for SHA-1). The NIST version has pAmt equal to 4 and has stricter, non-optional rules for the OtherInfo parameter.


Algorithm: KDF3.
INPUT:
Z, shared secret, a byte string;
Hash, hash function with output hLen bytes;
kLen, intended length of keying material in bytes;
pAmt, an integer of value 4 or more;
[OtherInfo], optional extra shared material.
OUTPUT: Derived key, K, of length kLen bytes.
  1. Set d = ceiling(kLen/hLen).
  2. Set T = "", the empty string.
  3. for Counter = 0 to d-1 do:
    • C = IntegerToString(Counter, pAmt)
    • T = T || Hash(C || Z || [OtherInfo])
  4. Output the first kLen bytes of T as K.

Having the counter value as the first input to the Hash function removes a possible security issue compared to KDF1 and KDF2.

In the absence of a value for pAmt, we suggest you use 4.

KDF4

KDF4 is defined in ISO-18033-2 [ISO18033]. It uses a Hash function and requires a deterministic pseudo-random byte generator (PRBG) function which takes an input seed of length equal to hLen and outputs a random-looking, but pre-determined, byte string of length kLen. To our knowledge, KDF4 is not in common use, if it is at all.

K = PRBG(Hash(Z), kLen)

Examples of KDF

We use each of KDF1, KDF2 and KDF3 to generate a 256-bit key (kLen=32 bytes) using the shared secret value

Z=(0x)de ad be ef fe eb da ed

The hash function is SHA-1 (which has hLen=20) and there is no OtherInfo.

In all cases, d = ceiling(kLen/hLen) = ceiling(32/20) = 2.

KDF1

Counter=0, Hash(DEADBEEFFEEBDAED00000000)=B0AD565B14B478CAD4763856FF3016B1A93D840F
Counter=1, Hash(DEADBEEFFEEBDAED00000001)=87261BEDE7DDF0F9305A6E44A74E6A0846DEDE27
K=B0AD565B14B478CAD4763856FF3016B1A93D840F87261BEDE7DDF0F9305A6E44

KDF2

Counter=1, Hash(DEADBEEFFEEBDAED00000001)=87261BEDE7DDF0F9305A6E44A74E6A0846DEDE27
Counter=2, Hash(DEADBEEFFEEBDAED00000002)=F48205C6B141888742B0CE2C025C1023466A749C
K=87261BEDE7DDF0F9305A6E44A74E6A0846DEDE27F48205C6B141888742B0CE2C

KDF3

With pAmt=4.

Counter=0, Hash(00000000DEADBEEFFEEBDAED)=60CEF67059AF33F6AEBCE1E10188F434F80306AC
Counter=1, Hash(00000001DEADBEEFFEEBDAED)=0360470AEB41F81BAFB357908D6C142B5086E79B
K=60CEF67059AF33F6AEBCE1E10188F434F80306AC0360470AEB41F81BAFB35790

Comments

The examples above are meant to illustrate the technique. Note that the entropy in the shared secret in this case is less than the size of the derived key (because it's shorter). The security level cannot be greater than the entropy in the shared secret. Also, you should not use the same shared secret to derive different keys.

Password-Based Key Derivation Functions (PBKDF)

PBKDFs are designed to be used with a password. Because the keyspace for passwords is much smaller than that of a randomly-generated byte string of the same length, the security is improved by "salting" - adding a random salt to prevent a dictionary attack - and "stretching", repeating the process several times to hinder brute force attacks. The user has to provide a random salt and an interation count, typically of 1000 or more.

PBKDF1

PBKDF1 is defined in PKCS#5 v1 [PKCS5]. The length of the derived key is limited to the output length of the hash function (16 bytes for MD5 and 20 bytes for SHA-1).


Algorithm: PKDF1.
INPUT:
P, password, a byte string;
S, salt, an 8-byte string;
C, a positive integer;
kLen, intended length of keying material in bytes;
Hash, hash function with output hLen bytes;
OUTPUT: Derived key, K, of length kLen bytes.
  1. If kLen > hLen then stop with error "kLen is too long"
  2. T1 = Hash(P || S)
    for i = 2 to C
    • Ti = Hash(Ti-1)
  3. Output the first kLen bytes of TC as K.

PBKDF-Schneier

Bruce Schneier describes a password-based key derivation function in [SCHN96]. It is the same as PBKDF1 except step 2 is

This is slightly more awkward to implement in practice than PBKDF1 for no increase in security.

PBKDF2

PBKDF2 is defined in PKCS#5 v2 [PKCS5]. The length of the derived key is essentially unlimited. It requires a pseudorandom function (PRF) to be defined as well. The HMAC function with SHA-1 is recommended as the default PRF.


Algorithm: PKDF2.
INPUT:
P, password, a byte string;
S, salt, a byte string of arbitrary length;
C, a positive integer;
kLen, intended length of keying material in bytes;
PRF, pseudorandom function with output hLen bytes;
OUTPUT: Derived key, K, of length kLen bytes.
  1. Set d = ceiling(kLen/hLen).
  2. Let T = "", the empty string.
  3. for i = 1 to d do
    • F = U1 = PRF(P, S || IntegerToString(i, 4))
    • for j = 2 to C do
      • Uj = PRF(P, Uj-1)
      • F = F XOR Uj
    • T = T || F
  4. Output the first kLen bytes of T as K.

For the PRF function above, use an HMAC function (e.g. HMAC-SHA-1) with the first parameter the "key" and the second parameter the "text". So

PRF(x, y) = HMAC(key:=x, text:=y)

Examples of PBKDF

PBKDF1

To derive a key of 16 bytes (128 bits) using the SHA-1 algorithm:

Password = "password" 
         = (0x)70617373776F7264
Salt     = (0x)78578E5A5D63CB06
Count    = 1000
kLen     = 16
Key      = PBKDF1(Password, Salt, Count, kLen)
         = (0x)DC19847E05C64D2FAF10EBFB4A3D2A20

P || S = 70617373776F726478578E5A5D63CB06
T_1=     D1F94C4D447039B034494400F2E7DF9DCB67C308
T_2=     2BB479C1D369EA74BB976BBA2629744E8259C6F5
...
T_999=   6663F4611D61571068B5DA168974C6FF2C9775AC
T_1000=  DC19847E05C64D2FAF10EBFB4A3D2A20B4E35EFE
Key=     DC19847E05C64D2FAF10EBFB4A3D2A20

PBKDF2

To derive a key of 24 bytes (192 bits) suitable for the des-ede3-cbc encryption scheme, using HMAC-SHA-1 as the PRF:

Password = "password" 
         = (0x)70617373776F7264
Salt     = (0x)78578E5A5D63CB06
Count    = 2048
kLen     = 24
Key      = PBKDF2(Password, Salt, Count, kLen)
         = (0x)BFDE6BE94DF7E11DD409BCE20A0255EC327CB936FFE93643

In more detail:

d=ceiling(24,20)=2
Loop i=1
S||Int(i)=78578E5A5D63CB0600000001
F=U_1=PRF(P,S||Int(i))=cd677888fb7232e994a20ca3c5ae1620a153d9ea
U_2 = PRF(P,U_1) =     1bc6c5c9c4376852aca98ad403a38b979a57f7bd
F = F XOR U_2 =        D6A1BD413F455ABB380B8677C60D9DB73B042E57
U_3 = PRF(P,U_2) =     852f357144fd1c5296a6afd500378277fc8efb3e
F = F XOR U_3 =        538E88307BB846E9AEAD29A2C63A1FC0C78AD569
...
j=2047
U_2047=PRF(P,U_2046)=  18600a44fbcbe967bb3c681d22fa9a84f3ae06f6
F = F XOR U_2047=      2923C52DF41E2DFD40ED324CA2D8AA219CE6F7BF
U_2048=PRF(P,U_2047)=  96fdaec4b9e9cce094e48eaea8daffcdae9a4e89
F = F XOR U_2048=      BFDE6BE94DF7E11DD409BCE20A0255EC327CB936
T=BFDE6BE94DF7E11DD409BCE20A0255EC327CB936
Loop i=2
S||Int(i)=78578E5A5D63CB0600000002
F=U_1=PRF(P,S||Int(i))=c38d8f403a5a1c691719cec521735a8d0bbcef46
U_2 = PRF(P,U_1) =     0636ec10d724eaaf2797c70d8ecf27995e8da83f
F = F XOR U_2 =        C5BB6350ED7EF6C6308E09C8AFBC7D1455314779
U_3 = PRF(P,U_2) =     8cda5e588c93f230c46f57def627456dbd1f5da5
F = F XOR U_3 =        49613D0861ED04F6F4E15E16599B3879E82E1ADC
...
U_2047=PRF(P,U_2046)=  a5fea061297970c50434ea571590736f8867882e
F = F XOR U_2047=      DECB298C5D697A9D2067381FC4CD8CF0360DD890
U_2048=PRF(P,U_2047)=  21221fcf99d82a43d712293d80b415b551ff3124
F = F XOR U_2048=      FFE93643C4B150DEF77511224479994567F2E9B4
T=BFDE6BE94DF7E11DD409BCE20A0255EC327CB936FFE93643C4B150DEF77511224479994567F2E9B4
K=MSB(T,24)=BFDE6BE94DF7E11DD409BCE20A0255EC327CB936FFE93643

References

Contact

To comment on this page or ask a question, please send us a message.

This page first published 14 June 2008. Last updated: 28 January 2013.