1
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$
    – Paul Uszak
    Sep 27 at 2:35
  • $\begingroup$ @PaulUszak I have replaced my final note with my own guesses, as example of the level of detail I expect. $\endgroup$
    – sanscrit
    Sep 27 at 12:25
  • $\begingroup$ @PaulUszak We can say my question is mostly theoretical. $\endgroup$
    – sanscrit
    Sep 27 at 12:48
  • 1
    $\begingroup$ 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$. $\endgroup$
    – fgrieu
    Sep 27 at 16:39
  • $\begingroup$ @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. $\endgroup$
    – sanscrit
    Sep 27 at 20:35
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – sanscrit
    Sep 27 at 20:50
  • 1
    $\begingroup$ @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). $\endgroup$
    – fgrieu
    Sep 27 at 20:58

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.