Suppose the entropy of seed key is $H(n)$ which is $n$-bit long and random and the output bit length of the PRNG is $2^n$, which will be used as a long running key. Though it is obvious in that case, as output key sequence of PRNG is derived from input seed key, so entropy of output key sequence of PRNG never exceeds the entropy of the seed key. $H(2^n) \le H(n)$ in this scenario but how to prove it?
$\begingroup$
$\endgroup$
4
-
$\begingroup$ What do you mean "prove it"? Do you mean prove that no deterministic algorithm can add entropy to a bitstring no matter how long it is? $\endgroup$– mikeazoMar 3, 2016 at 1:00
-
$\begingroup$ Actually yes @mikeazo $\endgroup$– Mitun TalukderMar 3, 2016 at 1:10
-
$\begingroup$ I don't know but doubt the feasibility of proof of the kind indicated in mikeazo's comment. On the other hand it's remarkable in my view that e.g. AES in counter mode could with 128 or 256 random bits generate an extremely long bit sequence that is commonly considered to be highly secure in practice. $\endgroup$– Mok-Kong ShenMar 3, 2016 at 10:12
-
1$\begingroup$ TL;DR: Your thought process was wrong. There's no such thing as $H(n)$ and $H(2^n)$, entropy is only defined on random variables. $\endgroup$– SEJPMMar 3, 2016 at 12:54
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
TL;DR: The applied thought process was wrong. Entropy is a function of random variables and not of arbitrary integers. The fact that the PRNG doesn't increase entropy follows from the fact that the input space is limited and there's no other input to the algorithm and thereby entropy can't be increased.
First, let's recall the formal definition of "entropy" (as can be found in the Handbook of Applied Cryptography, chapter 2.2, PDF):
Definition The entropy or uncertainity of $X$ is defined to be $H(X)=-\sum_{i=1}^np_i\lg p_i=\sum_{i=1}^np_i\lg (\frac{1}{p_i})$ where, by convention, $p_i\cdot \lg p_i=p_i\cdot \lg (\frac{1}{p_i})=0$ if $p_i=0$.
Notation: $\lg a$ is the binary logarithm of $a$. $X$ is a random variable that takes each value $x_i$ (from a finite set if size $n$) with the correspdoning probability $p_i$.
Now let's model the $m$-bit string as the random variable $X$. The $m$-bit string can take $n_X=2^m$ values, each of which has the probability $p_i=\frac{1}{n_X}=2^{-m}$. Thereby the entropy $H(X)$ is $$H(X)=\sum_{i=1}^np_i\lg (\frac{1}{p_i})=\sum_{i=1}^{2^m}2^{-m}\lg (2^m)=2^m\cdot(2^{-m}m)=m$$ as expected.
The next step is to properly model the "PRNG". I will model it as a pseudo random generator (PRG), because I assume that's how you meant it.
In short: A pseudo random generator (PRG) is a deterministic algorithm that takes a fixed length input and returns a longer output.
(not a full formal definition and the usual definition would restrict to polynomially sized outputs, but we don't need one here)
By this we can model our PRG $\mathcal G: \{0,1\}^m\rightarrow \{0,1\}^{2^m}$. As $\{0,1\}^m$ can only take $2^m$ states and this is the only input to the function, we know that there can be at most $2^m$ different outputs of the PRG.
If we model the PRG output as a random variable $Y$, we know that (in "best case") $p_i=2^{-m}$ for $2^m$ different $y_i$ and $n_Y=2^{2^m}$. We further know that for the remaining $2^{2^{m}}-2^m$ possible values $y_i$, $p_i=0$ holds. With this information, we can compute the upper bound of the entropy of the PRG:
$$H(Y)=\sum_{i=1}^np_i\lg (\frac{1}{p_i})=\sum_{i=1}^{2^m}2^{-m}\lg (2^m)+\sum^{2^{2^m}-2^m}_{i=1}0\cdot\lg(\frac{1}{0})=2^m\cdot(2^{-m}m)+(2^{2^m}-2^m)\cdot 0=m$$
Note that $0\cdot \lg(\frac{1}{0})$ is, by convention, $0$.
As we have modeled $Y$ using as an optimal "PRG", it may be very well the case that there aren't $2^m$ different outputs. So we can conclude with $$H(X)\geq H(Y)$$ as expected and thereby that the PR(N)G doesn't increase entropy by itself.
$\begingroup$
$\endgroup$
There is no simple $H(n)$ function - i.e. there is no generic function that measures entropy of a bit-stream. That is because bit-streams do not inherently possess entropy. To measure entropy in the data, you need to have a probabilistic model of the output which it is an example of.
You can construct an equivalent to $H(n)$ if $H$ includes a model of the generator.
If your version of $H(n)$ is based on arbitrary compression algorithm, then in general $H(n) < H(2^n)$ (using your notation of $n$ as seed and $2^n$ as output), because any good PRNG will generate hard-to-compress output. That is the opposite result from the proof you were expecting.
If your version of $H(n)$ is based on brute-forcing the seed value from the PRNG, then $H(n) = H(2^n)$ because all solutions resolve to finding the correct seed. So the main issue you face is that a PRNG does not generate entropy - in the strict cryptographic sense of increasing the number of bits of knowledge required to predict the system. Instead if you assume attacker knows how the PRNG functions, they only ever have to guess seed value to make an attack.
You could maybe turn this into a proof, but as you see it all hinges on the definition of $H$, and with the that based on guessing the seed, the "proof" is a trivial by definition statement.
If you want to assess a PRNG's qualities, you do not measure entropy. Measurements close to the concept of entropy involve taking statistical tests of the PRNG output - there are several test suites for this including FIPs, Dieharder. Instead of checking entropy, these tests check for predictable bias in a PRNGs output. For cryptographic use, you also want to be sure that output of the PRNG does not leak state information, and might also be concerned about attacks that try to extract or manipulate state.
