PRF and KDF algorithms
Links
Description
A PseudoRandom Function family, or PRF, expands a key and a seed to a pseudorandom
output, which is usually of variable length. Normally the key should be chosen
uniformly at random (or at least with high entropy), but the seed can be any byte
string.
A PRF is sometimes called a Key Derivation Function, or KDF, especially when it
is used to derive or "separate" keys.
(Note that the classification used in this version of SCAN is different from
that in previous versions: functions with variablelength output that are always
used with only one input, rather than separate seed and key inputs, are treated
as MessageDigests. The only example of this was MGF1.)
Key derivation algorithms intended for use with lowentropy inputs (e.g.
passwords or passphrases) are classified separately, in the
PassphraseHash section.
? HMACPRF(digest)  PRF Construction

 Designers:
 David Hopwood
(HMAC: Mihir Bellare,
Ran Canetti,
Hugo Krawczyk,
Adi Shamir)
 Published:
 2000 (HMAC: June 1996)
 Description:
 HMACPRF is defined as:
HMACPRF(digest)(key, seed) =
HMAC(digest)(key, I2OSP_{4}(0)  seed) 
HMAC(digest)(key, I2OSP_{4}(1)  seed) 
HMAC(digest)(key, I2OSP_{4}(2)  seed)  ...
The maximum output length of the PRF is
2^{32} × (output length of digest).
 References:
 [Def, Impl (for HMAC)] M. Bellare, R. Canetti, H. Krawczyk,
"HMAC: KeyedHashing for Message Authentication,"
RFC 2104, February 1997.
 [Def, An (for HMAC)] M. Bellare, R. Canetti, H. Krawczyk,
"Keying hash functions for message authentication,"
Extended abstract in Advances in Cryptology  CRYPTO '96 Proceedings,
Volume 1109 of Lecture Notes in Computer Science (N. Koblitz, ed.).
SpringerVerlag, 1996.
Full paper:
http://wwwcse.ucsd.edu/users/mihir/papers/hmac.html#kmd5paper
 [Inf (for HMAC)] M. Bellare, R. Canetti, H. Krawczyk,
"Message authentication using hash functions: The HMAC construction,"
RSA Laboratories' CryptoBytes vol. 2, no. 1, Spring 1996.
http://wwwcse.ucsd.edu/users/mihir/papers/hmac.html#hmaccryptobytes
 Parameters:

String digest
[creation/read, no default]  the name
of the Block MessageDigest on which this PRF is to be based.
 Key length:
 Any multiple of 8 bits that does not cause the maximum input length for the
MessageDigest to be exceeded.
 Missing information:
 Test vectors.
? KDF2(digest)  PRF Construction

 Designers:
 P1363 Working Group
 Published:
 2001
 Description:
 KDF2 is defined as:
KDF2(digest)(key, seed) =
digest(key  I2OSP_{4}(1)  seed) 
digest(key  I2OSP_{4}(2)  seed) 
digest(key  I2OSP_{4}(3)  seed)  ...
The maximum output length of the PRF is
(2^{32}  1) × (output length of digest).
See the comments below concerning compatibility with IEEE P1363a.
 References:
 Parameters:

String digest
[creation/read, no default]  the name
of the message digest on which this PRF is to be based.
 Key length:
 Any multiple of 8 bits that does not cause the maximum input length for the
MessageDigest to be exceeeded.
 Missing information:
 Test vectors.
 Comments:
 This algorithm has changed incompatibly (twice) from SCAN 1.0.12. It
now aligns more closely with P1363a, if seed is considered to
be the "key derivation parameters".
 If the current P1363a definition of KDF2 were used with a littlebitendian
message digest, then it would be incompatible with this algorithm.
This is because, in the P1363a definition, byte string key and seed
inputs are converted to a bit string using the OS2BSP primitive (which
always uses bigbitendian order), and then processed by the digest
function using its native bit order. Therefore the bits in each byte
of the key and seed would need to be reversed, relative to the algorithm
defined here.
However, P1363a only defines KDF2 for a specific set
of message digest functions: SHA1, SHA{256,384,512}, and RIPEMD160.
All of these are bigbitendian, and so there is no incompatibility
in practice. It is likely that if some future amendment of IEEE Std 1363
allowed any littlebitendian digest functions, it would correct this
bit order problem.
 Security comments:
 Extension attacks are possible on the seed, due to the MerkleDamgård
structure of most message digest algorithms. The suggested way to prevent
these attacks is to ensure that the seed has a prefixfree encoding.
 In section 12.3 of the cited paper by Victor Shoup, use of KDF2
for applications that require entropy smoothing,
is criticised as being dependent on the security of "a quite unorthodox
construction that does not appear to be based on any wellworn or otherwise
sound principles."
 Designers:
 Netscape Communications Corp.
 Description:
 SSL3PRF is defined as:
SSL3PRF(key, seed) =
MD5(key  SHA1("A"  key  seed)) 
MD5(key  SHA1("BB"  key  seed)) 
MD5(key  SHA1("CCC"  key  seed))  ...
A maximum of 26 × 16 = 416 bytes may be generated.
When used as a KDF, set seed to the zerolength string.
 References:
 Key length:
 Any multiple of 8 bits that does not cause the maximum input length for
MD5 or SHA1 to be exceeeded.
 Missing information:
 Test vectors.
 Comment:
 When SSL3PRF is used to implement SSL version 3, the master_secret
described in the SSL specification corresponds to the PRF key, and
(ServerHello.random  ClientHello.random) corresponds to the PRF seed.
 Designers:
 IETF Transport Layer Security Working Group
 Published:
 January 1999
 Description:
 TLSPRF is defined as follows:
TLSPRF(key, seed) =
P_{MD5}(S1, seed) XOR P_{SHA1}(S2, seed)
L_{key} = length in bytes of key
L_{S1} = L_{S2} = ceiling(L_{key} / 2)
S1 = first L_{S1} bytes of key
S2 = last L_{S2} bytes of key
A_{H}(0) = seed
A_{H}(i) = HMAC(H)(key, A_{H}(i1)), for i > 0
P_{H}(S1, seed) =
HMAC(H)(key, A_{H}(1)  seed) 
HMAC(H)(key, A_{H}(2)  seed) 
HMAC(H)(key, A_{H}(3)  seed)  ...
 References:
 [Def] T. Dierks, C. Allen,
"The TLS Protocol Version 1.0,"
RFC 2246,
January 1999.
 [Test] To: "IETF Transport Layer Security WG" <ietftls@lists.consensus.com>
Subject: PRF Testvector for the standard
From: Rene Eberhard <rene.eberhard@entrust.com>
Date: Mon, 5 Oct 1998 03:33:57 0400
http://www.imc.org/ietftls/mailarchive/msg01589.html
 Key length:
 Any multiple of 8 bits that does not cause the maximum input length for
MD5 or SHA1 to be exceeeded.
 Comment:
 When TLSPRF is used to implement the TLS protocol, the "label" argument to
the PRF should be prepended to the seed. The key is referred to as the "secret"
by the TLS specification. I.e. where the TLS spec
says "PRF(secret, label, seed)",
this may be implemented as
"TLSPRF(secret, label  seed)".
 Security comment:
 The intention of using both MD5 and SHA1 in the design was to try
to ensure that weaknesses in only one of these hashes would not cause
any security problem. However, only the first half of the key is used
in P_{MD5}, and only the second half in P_{SHA1}. This
means that the security cannot be guaranteed to depend on the stronger
of MD5 and SHA1, unless there is sufficient entropy in both the first
and last halves of the input key. If the key contains nonrandom fields
(e.g. the version field in the master secret for TLS RSA ciphersuites),
these will only affect one of P_{MD5} or P_{SHA1}.
Arguably, this does not matter much in practice because either
P_{MD5} or P_{SHA1} would be secure PRFs on their own.
Alleged PRFs and KDFs