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) <-- derived="" iterationcount="" key="" klen="" length="" of="" password="" pbkdf:="" pre="" salt="" secret="" therinfo="" value="">
Note: This page was originally written several years ago. It was never meant to be an exhaustive list of all possible KDFs. It does not reflect more recent changes to defeat parallelization like bcrypt or
scrypt, or the 2015
Password Hashing Competition.
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.
- 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.
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
1 = Hash(P || S)
for i = 2 to C
- 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
T
1 = Hash(P || S)
for i = 2 to C
- Ti = Hash(Ti-1 || P || S)
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 = 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
- 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 (available as RFC3447).
- [PKCS5] RSA Laboratories. PKCS #5 v2.1: Password-Based Cryptography Standard, 5 October 2006 (v2.0 is available as RFC2898).
- [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.
Contact
This page first published 14 June 2008. Last updated: 20 February 2016.
