From Wikipedia:

In cryptography, a key derivation function (or KDF) derives one or more secret keys from a secret value such as a master key or other known information such as a password or passphrase using a pseudo-random function.

Is there a more formal security definition for what they are and what properties they are trying to guarantee, like ind-cpa security for encryption schemes, or collision resistance for hash functions?

  • 4
    $\begingroup$ Hugo Krawczyk has defined HKDF, which is intended to be a practical KDF based on HMAC. He wrote paper on subject: Cryptographic Extraction and Key Derivation: The HKDF Scheme. Because goals of KDF are not often well pronounced, this paper formalizes model for Key Derivation Functions (page 6). The formalized model from this paper could be suitable definition sufficient for your purposes. $\endgroup$ – user4982 Apr 16 '15 at 18:40
  • $\begingroup$ @user4982 If you could post an abstract of that text together with your link than it would make an excellent answer. $\endgroup$ – Maarten Bodewes Apr 16 '15 at 22:15

This is a summary of the indicated section of Cryptographic Extraction and Key Derivation: The HKDF Scheme from user4982's comment.

Because this is in the context of an academic paper describing a HMAC based KDF, the terminology can be a bit excessive. I have tried to trim it down in this summary.

Definition of a KDF:

A KDF takes four inputs: a key source value, an output length, a salt, and a context variable. The last two are optional. The security and quality of the KDF depends on the properties of the key source value.

Definition of a key source:

A source comprises two values, the key source material and auxiliary knowledge about it, created using an algorithm with sufficient statistical entropy to be considered random. (The auxiliary knowledge can be the distribution from a statistical entropy source, or the non-secret values of a DH key exchange, or any other related, but not secret data about the key source material)

Definition of the security of a KDF:

A KDF is secure if an attacker knowing the auxiliary data and salt value has little chance of deriving the key source material and context variable from repeated attempts at using the KDF with the auxiliary data, salt, and random key source materials and context variables (a.k.a brute forcing the KDF).


Probably the only thing they need to achieve is Pseudo-Randomness, defined in [GGM1986, §3.1].

KDF does not create more entropy than you gave it, but it avoid weaknesses in your cryptosystem due to patterns if the same key is used repeatedly in several rounds.

  • 3
    $\begingroup$ This is probably not a "more formal security definition" of a KDF. $\endgroup$ – Maarten Bodewes Apr 16 '15 at 22:19

A KDF takes as input a good short random looking password which it maybe easily human saved but actually is not uniformly distributed. An attacker may have some partial knowledge of the password. The output of the KDF is a cryptographically secure key, meaning that it is indistinguishable from a random looking bit-string. Following the Real-Or-Random game that is an attacker cannot distinguish whether it receives output from a real random function or it receives the output of the KDF on input of her choice. The goal of KDF is to transform inputs to closely uniform ones.

For the construction of KDF an HMAC can be used which is a PRF. Apart from the password the KDF takes as input the number a rounds that will control the amount of time it will take for somebody to run this KDF and a salt which will drastically increase the computation overhead of an attacker who tries to brute force a bunch of KDF evaluations on multiple passwords.

  • 2
    $\begingroup$ The missing key expansion, the focus on passwords and the fact that it certainly is not formal as requested made me vote down this answer. $\endgroup$ – Maarten Bodewes Apr 16 '15 at 22:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.