Score:3

Difference between Non-uniformly random and Uniformly random

bt flag

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

Ievgeni avatar
cn flag
Could you add a citation and/or a link to have more context?
Score:5
ng flag

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.

dade avatar
bt flag
basically if all possible values - are not equally likely - due to whatever restriction - then you have non-uniformly randomness?
fgrieu avatar
ng flag
@dade: that's it. Except we say "non-uniformly random" or "non-uniform randomness".
dade avatar
bt flag
A related question then...how can a "non-uniformly random" have "enough entropy"?
Paul Uszak avatar
cn flag
@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.
Score:4
cn flag

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.

fgrieu avatar
ng flag
"non uniform randomness goes into the KDF, and uniform randomness comes out" _if_ there is enough entropy in the input.
Paul Uszak avatar
cn flag
@fgrieu Ah, ye olde chestnut - the differences between Kolmogorov complexity, cryptographic entropy and information entropy. We really really should resolve this one day...
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.