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

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 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, public byte string, OtherInfo.

KDF:   (derived key of length kLen) <-- (secret value, [OtherInfo])
PBKDF: (derived key of length kLen) <-- (password, salt, iterationCount)

Algorithm	Reference
KDF1	ISO-18033-2
KDF2	ISO-18033-2, ANSI-X9-42
KDF3	ISO-18033-2, NIST SP800-56A
KDF4	ISO-18033-2
MGF1	P1363, PKCS1-v2
PBKDF-Schneier	[SCHN96]
PBKDF1	PKCS5-v1
PBKDF2	PKCS5-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.

A || B denotes concatenation of byte strings A and B.
IntegerToString(i, n) is an n-byte encoding of the integer i with the most significant byte first (i.e. in "big-endian" order). So, for example,
```
IntegerToString(1, 4)=00000001,
IntegerToString(7658, 3)=001DEA
```
ceiling(x) is the smallest integer, n, such that n ≥ x. Hint: To find ceiling(n/d) using integer arithmetic, compute
```
(n + d - 1) / d
```

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.

Set d = ceiling(kLen/hLen).
Set T = "", the empty string.
for Counter = 0 to d-1 do:
- C = IntegerToString(Counter, 4)
- T = T || Hash(Z || C || [OtherInfo])
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.

Set d = ceiling(kLen/hLen).
Set T = "", the empty string.
for Counter = 0 to d-1 do:
- C = IntegerToString(Counter, pAmt)
- T = T || Hash(C || Z || [OtherInfo])
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.

If kLen > hLen then stop with error "kLen is too long"
T₁ = Hash(P || S)
for i = 2 to C
- T_i = Hash(T_i-1)
Output the first kLen bytes of T_C 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

T₁ = Hash(P || S)
for i = 2 to C
- T_i = Hash(T_i-1 || P || S)

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.

Set d = ceiling(kLen/hLen).
Let T = "", the empty string.
for i = 1 to d do
- F = U₁ = PRF(P, S || IntegerToString(i, 4))
- for j = 2 to C do
  - U_j = PRF(P, U_j-1)
  - F = F XOR U_j
- T = T || F
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

[AX942] ANSI X9.42-2003 Agreement of Symmetric Keys Using Discrete Logarithm Cryptography, American National Standards Institute, 19 November 2003.
[ISO18033] ISO/IEC 18033-2:2006, Information technology - Security techniques - Encryption algorithms - Part 2: Asymmetric ciphers, Ed. Victor Shoup, 2006. The final committee draft version FCD 18033-2, dated December 2004, is available at <www.shoup.net/iso/std6.pdf>.
[P1363] IEEE P1363 Standard Specifications for Public Key Cryptography, IEEE, November 1993.
[PKCS1] RSA Laboratories. PKCS #1 v2.1: RSA Encryption Standard. June 2002, <download>.
[PKCS5] RSA Laboratories. PKCS #5 v2.1: Password-Based Cryptography Standard, 5 October 2006, <download>.
[SCHN96] Bruce Schneier, Applied Cryptography - Protocols, Algorithms and Source Code in C, second edition, John Wiley, 1996.
[SP80056A] NIST Special Publication 800-56A Recommendation for Pair-Wise Key Establishment Schemes Using Discrete Logarithm Cryptography, National Institute of Standards and Technology, March 2007, <download>.

Contact us

Any comments, feedback, questions to our email or use our Contact Page.

This page first published 14 June 2008. Last updated: 9 July 2008.