# Estimation of the entropy of keys derived from truly random numbers

NOTE: This question is based on my assumption that $$X$$ is a "truly random number" if and only if it's length measured in bits is equal to its entropy measured in bits. In other words, when every bit of $$X$$ has been generated by a random coin toss.

Suppose I have a truly random number $$R$$ of size 256 bits (256 bits of entropy), and a truly random number $$S$$ of length $$n * 256$$, where $$n$$ is some natural number, so it has $$n * 256$$ bits of entropy.

I now derive four keys $$T_1$$ to $$T_4$$ from $$R$$

• $$T_1 = \text{concat}(R, \text{... n times ...}, R)$$
• Calculate $$t_1 = \text{sha256}(R)$$, $$t_2 = \text{sha256}(t_1)$$, ..., $$t_n = \text{sha256}(t_{n-1})$$, and do $$T_2=\text{concat}(t_1, ..., t_n)$$.
• $$T_3$$ is calculated same as above, but using HMAC instead of sha256.
• $$T_4 = \text{hkdf_expand}(R, \text{null}, n * 256 / 8)$$.

Finally, I calculate $$K_i = T_i\text{ xor }S$$.

How many bits of entropy does $$K_1$$, $$K_2$$, $$K_3$$ and $$K_4$$ have?

My happy guesses:

• $$T1$$ will have as most as many entropy as $$R$$, since concatenation by repetition doesn't increase the entropy of the output, but I suspect it won't decrease it either.
• $$\text{sha256}$$ and $$\text{HMAC}$$ are believed to preserve the bits of entropy of the input, but since the process to construct $$T_2$$ and $$T_3$$ is deterministically calculated from $$R$$, the entropy of $$T_2$$ and $$T_3$$ will be roughly equivalent to $$T1$$.
• No idea about $$T_4$$. I guess the benefits of $$\text{hkdf_expand}$$ kick in when its input is not a truly random number.

About every $$K_i$$, I'm not sure. I recently learned that XORting two truly random numbers gives a truly random number, so the bits of entropy of the output is still its length, but since the $$T_i$$s aren't truly random numbers anymore, I don't know what will happen here.

My intuition tells me that the entropy of $$S$$ will be preserved ($$n * 128$$ bits), because $$K_i$$ is equivalent to encrypt $$T_i$$ using $$S$$ as a one-time pad key, making $$T_i$$ or $$S$$ theoretically unbreakable, so $$K_i$$ is still a truly random number.

• Hiya! Err, I'm confused. Can you simplify the question given that you have access to truly random numbers? What are you trying to do? Sep 27 at 2:35
• @PaulUszak I have replaced my final note with my own guesses, as example of the level of detail I expect. Sep 27 at 12:25
• @PaulUszak We can say my question is mostly theoretical. Sep 27 at 12:48
• Issues A) [snip, question fixed]. B) HMAC needs a key. C) Strictly speaking, "How many bits of entropy does $K_1$, $K_2$, $K_3$ and $K_4$ have?" asks something moot, since bitstrings don't have entropy (or have none); the process that builds them has a well-defined entropy. D) The entropy of the processes that build $K_1$, $K_2$, $K_3$ and $K_4$ depends on if $R$ and $S$ are independent. In the affirmative, it's [excessive hint snipped] thanks to "I calculate $K_i=T_i\text{ xor }S$" and $T_i$ being a function of $R$.
– fgrieu
Sep 27 at 16:39
• @fgrieu I meant each $T_i$ depends entirely on $R$; and yes I know the entropy depends on the process, not the number. I can get the number 5 by a random pick, or by 2 + 3 where 2 and 3 are random numbers, or by 2 + 3 where 2 and 3 are known numbers. The first process will have 3 bits of entropy, the 2nd process probably too (a guess of mine, because adding random numbers changes the statistical distribution, but it's still a random process), and the third process 0 bits of entropy. Sep 27 at 20:35

XORing two truly random numbers gives a truly random number

No. Counterexample: $$S$$ uniformly random, $$S\oplus S$$ is the all-zero bitstring of the same size as $$S$$, and is not uniformly random (unless $$S$$ is empty).

What holds is: XORing two independent values of the same size, at least one of which is a truly random number, yields a truly random number.

In the exercise, $$S$$ is uniformly random, and $$T_i$$ depends only on $$R$$ (and an unstated key for HMAC in the case of $$T_3$$, but let's ignore that), and everything points at $$R$$ being independent of $$S$$. Thus $$T_i$$ being independent of $$S$$.

The above, size of things, and $$K_i$$ being built as $$K_i=T_i\oplus S$$, are enough to conclude about

how many bits of entropy does $$K_1$$, $$K_2$$, $$K_3$$ and $$K_4$$ have

and this is left as an exercise to the reader.

• Thank you. Can I conclude that since I have already truly random numbers as input, in order to expand $R$ to construct $T_i$, more complex and computationally expensive operations like sha256 or hkdf_expand gives me nothing (considering that I will XORted it with $S$ later) and just repeating $R$ (to build $T_1$) is enough? Sep 27 at 20:50
• @sanscrit. The point is that regardless of the process that builds a $T_i$ of the same size as $S$, and independently of uniformly random $S$ (including, builds $T_i$ as a function of $R$ independent of $S$), one can conclude about the entropy in $K_i=T_i\oplus S$. That' not exactly what you state above. In particular, you don't care that $R$ is uniformly random, only that it's independent of $S$ (and that $S$ is uniformly random).
– fgrieu
Sep 27 at 20:58