success
fail
**Nov**
DEC
**Feb**
29
**2009**
2010
**2012**
66 captures 19 Jul 2008 - 19 Feb 2018
About this capture
COLLECTED BY
Organization: Internet Archive
The Internet Archive discovers and captures web pages through many different web crawls. At any given time several distinct crawls are running, some for months, and some every day or longer. View the web archive through the Wayback Machine.
Collection: Wide Crawl started October 2010
Web wide crawl with initial seedlist and crawler configuration from October 2010
TIMESTAMPS
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 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
_{1}= Hash(P || S)

for i = 2 to C- T
_{i}= Hash(T_{i-1})

- T
- 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
_{1}= Hash(P || S)

for i = 2 to C- T
_{i}= Hash(T_{i-1}|| P || S)

- T

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
_{1}= PRF(P, S || IntegerToString(i, 4)) - for j = 2 to C do
- U
_{j}= PRF(P, U_{j-1}) - F = F XOR U
_{j}

- U
- T = T || F

- F = U
- 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

*This page first published 14 June 2008. Last updated: 3 January 2010.*

## Comments

Post a comment on this page.**0** comments so far

Copyright © 2008-10 DI Management Services Pty Limited ABN 78 083 210 584 Sydney, Australia.

**www.di-mgt.com.au**. All rights reserved.

Home | Services | About Us | Projects | Links | Cryptography | CryptoSys API | CryptoSys PKI | DBXanalyzer | BigDigits | Wclock | Su Doku | About This Site | Contact | Email Us