New proofs for pseudorandomness of HMAC-based key derivation functions (RFC 5869)

The key derivation function (KDF) is crucial in cryptographic systems, aiming to derive an initial key source, which may lack even randomness or be partially known to attackers, and generate secure secret keys. The HMAC-based key derivation function (HKDF), built on HMAC, is claimed to have Pseudo-Random Bit Generator (PRBG) properties, though no formal proof exists in current literature. This paper conducts a comprehensive analysis and evaluation of the pseudo-randomness within the HKDF key derivation scheme, as specified in RFC 5869. We demonstrate that the HKDF scheme attains PRBG properties under the assumption that either the input salt or the Initial Keying Material (IKM) is random, and we further assume the underlying HMAC function is a Pseudo-Random Function (PRF). Additionally, we present results showcasing the pseudo-randomness in an extended scenario where HKDF is required to generate a large number of keys. Specifically, we perform various experimental evaluations of the randomness of the HKDF scheme based on statistical standards outlined in NIST SP 800-22. Finally, a sensitivity evaluation of HKDF is conducted, revealing that a change of 1 bit in the IKM input results in an approximate 50% change in the number of bits in the derived key (OKM). This outcome signifies the robust randomness and high sensitivity of the HKDF. Our findings not only offer novel proof confirming the pseudo-randomness of HKDF but also enhance the overall security of the algorithm.