3
$\begingroup$

I am reading up on Key Deriving Functions (KDF) and in a section of the Real-World Cryptographic book by David Wong, a comparison is being made with Pseudorandom number generator (PRNG). And one of the differences is said to be that KDF takes non-uniformly random arbitrary length input, while PRNG takes Uniformly random k-bit key. Even though both have Uniformly random arbitrary length output.

Basically it is said that The main differences are that a KDF does not expect a fully uniformly random secret as input (as long as it has enough entropy).

What exactly is meant by non-uniformly random and uniformly random in this context? Also what does entropy mean in this context?

It seems having a better understanding of these terms will help in better appreciating the difference between KDF and PRNGs

$\endgroup$
1
  • 1
    $\begingroup$ Could you add a citation and/or a link to have more context? $\endgroup$
    – Ievgeni
    Oct 22 at 11:10
5
$\begingroup$

Uniformly random means that all possible values are equally likely. Where "all possible values" would be those in some set which, when not otherwise defined, is the set of bitstrings the size of the variable considered.

An example on non-uniform input to a KDF is when the KDF is fed with the result of a Diffie–Hellman key exchange in $\mathbb Z_p^*$ with $g$ a generator of that whole group. The input of the KDF could be the value of $g^{a\,b}\bmod p$ expressed as a bytestring (e.g. big-endian) of fixed size (that of $p$, rounded up to a multiple of 8 bits), with $a$ and $b$ random ephemeral secrets. Some bytestrings that are valid at the input of the KDF can never occur in that actual use: the input bytestrings that do not represent an integer in $[1,p-1]$, including the all-0x00 and all-0xFF bytestrings. And among those that can be reached, quadratic residues (reached when either $a$ or $b$ are even) are three times more likely than non-quadratic residues (reached when $a$ and $b$ are odd).

Another example on non-uniform input is a passphrase, which is a common input for some KDFs (such as the modern Argon2 or the obsolete PBKDF2).


Shannon entropy (in bit) of a process generating a variable $X$ that can take $n$ values distinct values with probability $p_i$ with $0\le i<n$, thus with thus $1=\displaystyle\sum_{0\le i<n}p_i$ and $0\le p_i\le1$, is defined as the quantity $$H(X)=\sum_{0\le i<n\text{ and }p_i\ne0}p_i\log_2(1/p_i)$$

Another useful entropy is min-entropy, defined as $$H_\text{min}(X)=\log_2(1/\max_{0\le i<n}{p_i})$$

It always holds $H_\text{min}(X)\le H(X)$.

A process generating a $b$-bit bitstring $X$ has $b$-bit entropy (for either definition) if and only if it generates uniformly random bitstrings. When non-uniformly random, it's entropy is less than $b$-bit, down to $0$ when it always generates the same bitstring.

Informally, there is enough entropy at the input of a KDF if the output of that KDF is essentially uniformly random (for more or less stringent definition of that). That's possible when the input of the KDF is not uniformly random, but only if that input has (min-)entropy at least the KDF's output width of $b$ bit (or at least $b$ such that $2^b$ defies enumeration by adversaries). And then that's not strictly a sufficient condition.

$\endgroup$
4
  • $\begingroup$ basically if all possible values - are not equally likely - due to whatever restriction - then you have non-uniformly randomness? $\endgroup$
    – dade
    Oct 22 at 11:42
  • $\begingroup$ @dade: that's it. Except we say "non-uniformly random" or "non-uniform randomness". $\endgroup$
    – fgrieu
    Oct 22 at 11:43
  • 1
    $\begingroup$ A related question then...how can a "non-uniformly random" have "enough entropy"? $\endgroup$
    – dade
    Oct 22 at 11:57
  • $\begingroup$ @dade Don’t overthink this - it’s simple. Imagine that you want 128 of ‘stuff’, which is enough for cryptography. If it comes at a rate of 8 (uniform distribution within bytes), then you only need 16 goes. But you can get 128 of ‘it’ at a rate of 5.3 (weird distribution) if you take 25 goes. $\endgroup$
    – Paul Uszak
    Oct 23 at 12:48
4
$\begingroup$

What exactly is meant by non-uniformly random and uniformly random in this context? Also what does entropy mean in this context?

This is randomness with a non uniform distribution illustrated as a probability mass function (PMF):-

pmf

You can see that zeros are prevalent by far. If the randomness were uniform, all values would align with the blue line at p = 0.0039, which is $\frac{1}{256}$. Since in cryptography we are interested in min. entropy $\big(H_{\infty} = -\log_2 (p_{max}) \big)$, the above distribution (if I.I.D) has $H_{\infty} \approx 5.3$ bits/byte.

Had the PMF been uniformly random, we'd have $H_{\infty} = 8$ bits/byte. This is maximal entropy which is characteristic of uniform distributions.

So non uniform randomness goes into the KDF (perhaps a password like '123456'), and uniform randomness comes out.

$\endgroup$
2
  • 2
    $\begingroup$ "non uniform randomness goes into the KDF, and uniform randomness comes out" if there is enough entropy in the input. $\endgroup$
    – fgrieu
    Oct 22 at 19:05
  • $\begingroup$ @fgrieu Ah, ye olde chestnut - the differences between Kolmogorov complexity, cryptographic entropy and information entropy. We really really should resolve this one day... $\endgroup$
    – Paul Uszak
    Oct 23 at 12:48

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.