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  PasswordBased Key Derivation Functions (PBKDF)  PBKDF1  PBKDFSchneier  PBKDF2  Examples of PBKDF  References  Contact us
Introduction
There are at least four versions of KDF plus at least three passwordbased 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, publiclyrevealed byte string, OtherInfo.
KDF: (derived key of length kLen) < (secret value, [OtherInfo]) PBKDF: (derived key of length kLen) < (password, salt, iterationCount)
Algorithm  Reference 

KDF1  ISO180332 
KDF2  ISO180332, ANSIX942 
KDF3  ISO180332, NIST SP80056A 
KDF4  ISO180332 
MGF1  P1363, PKCS1v2 
PBKDFSchneier  [SCHN96] 
PBKDF1  PKCS5v1 
PBKDF2  PKCS5v2 
Glossary
 KDF
 key derivation function
 PBKDF
 passwordbased key derivation function
 MGF
 mask generation function
 PRF
 pseudorandom function
 PRBG
 pseudorandom byte generator
 HMAC
 keyedhash message authentication code
 Hash
 a cryptographicallysecure 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 nbyte encoding of the integer i with the most significant
byte first (i.e. in "bigendian" 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 ISO180332 [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 d1 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 ISO180332 [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 ISO180332 [ISO18033] and uses essentially the same algorithm as the KDF function in NIST SP80056A [SP80056A]. In the ISO180332 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 SHA1). The NIST version has pAmt equal to 4 and has stricter, nonoptional 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 d1 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 ISO180332 [ISO18033]. It uses a Hash function and requires a deterministic pseudorandom byte generator (PRBG) function which takes an input seed of length equal to hLen and outputs a randomlooking, but predetermined, 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 256bit key (kLen=32 bytes) using the shared secret value
Z=(0x)de ad be ef fe eb da ed
The hash function is SHA1 (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.
PasswordBased 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 randomlygenerated 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 SHA1).
Algorithm: PKDF1.
INPUT:
P, password, a byte string;
S, salt, an 8byte 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_{1} = Hash(P  S)
for i = 2 to C T_{i} = Hash(T_{i1})
 Output the first kLen bytes of T_{C} as K.
PBKDFSchneier
Bruce Schneier describes a passwordbased key derivation function in [SCHN96]. It is the same as PBKDF1 except step 2 is

T_{1} = Hash(P  S)
for i = 2 to C T_{i} = Hash(T_{i1}  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 SHA1 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_{1} = PRF(P, S  IntegerToString(i, 4))
 for j = 2 to C do
 U_{j} = PRF(P, U_{j1})
 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. HMACSHA1) 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 SHA1 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 desede3cbc encryption scheme, using HMACSHA1 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 SInt(i)=78578E5A5D63CB0600000001 F=U_1=PRF(P,SInt(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 SInt(i)=78578E5A5D63CB0600000002 F=U_1=PRF(P,SInt(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.422003 Agreement of Symmetric Keys Using Discrete Logarithm Cryptography, American National Standards Institute, 19 November 2003.
 [ISO18033] ISO/IEC 180332:2006, Information technology  Security techniques  Encryption algorithms  Part 2: Asymmetric ciphers, Ed. Victor Shoup, 2006. The final committee draft version FCD 180332, 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: PasswordBased 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 80056A Recommendation for PairWise Key Establishment Schemes Using Discrete Logarithm Cryptography, National Institute of Standards and Technology, March 2007, <download>.
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.