Does a key derivation function always generate an even distribution of bits in the resulting key?

Question

I am a student of crypto. During our study course, we went into the AES-128 algorithm. All the examples given used an initial key k, 128 bits and we only briefly touched on the key derivation of PBKDF2. We looked at the key as a series of bits of fixed length and discussed the security and so forth.

If the 128-bit key is generated from a function that takes a password as an input, will the distribution of 0 and 1s across the resulting key k always be random?

Let's say I have a dictionary of 'real' passwords from say a leaked website (a good sample size of say 1M), and put these passwords through a PBKDF2 function and recorded the keys k1, k2, through kn (where n=1,000,0000).

If I were to draw a histogram of frequency of bits 0 through 127 being set or not, if the keys were indistinguishable from random I would expect an even number of bits being set across the board. Picture if you will, balls falling through a matrix and landing in 1 of 128 slots.

My questions are, is that the case? Is it possible to see a skew (i.e. do the resulting keys bunch in one area of the spectrum of bits, maybe a curve of sorts?

My rationale behind asking is that is the resulting keys were to bunch to a particular resulting key type, it would narrow the key space to attack the AES-128 encryption.

Therefore, is it true to say that the AES-128 is only as good as the password derivation function having been used to form the key to begin with? If the resulting keys are poor, the key space would narrow?

Answer 1

It will be uniformly random for such a simple statistical test. The problem is that you are treating the probability of bits having a particular state as independent of each other. You would need to look at the conditional probability distributions of certain bits being set given other bits.

The entire joint distribution of output and input bits for a function that maps $\{0,1\}^a \to \{0,1\}^b$ requires on the order of $2^{a+b}$ memory to store. Clearly it becomes prohibitive to store and sample it for even a small function that maps 32-bits onto another 32-bits through a fixed transformation (i.e., without including any key bits that define a particular permutation).

The full conditional distribution of a function completely determines it's output. It can be seen as a transition probability matrix in a Markov model. Because of this, the distribution will encode any bias of the function, such as a preference to produce certain bit patterns (with probability).

Answer 2

Yes and no. Your general mindset is not wrong. Since the key (for a fixed number of iterations) depends only on the password, it is subject to the limitations of passwords. In particular, they have low entropy, some of them are more likely than others, they are prone to be found in a dictionary, and so on.

However, the target of PBKDF2 is to deal with the weak seed of a password and create a key that can be fed to a cryptographic primitive. To prevent precalculation, a salt value can be added to the password. Given the nature of the function, you will get two results: brute force is inefficient (assuming that the salt is public) and the entropy of the key is high (meaning that you can't claim that some keys are more likely than others).