5
$\begingroup$

From Serious Cryptography: "Entropy is maximized when the distribution is uniform because a uniform distribution maximizes uncertainty: no outcome is more likely than the others. Therefore, n-bit values can’t have more than n bits of entropy."

The MT strives to have as uniform a distribution as possible, so one would think the entropy is maximized and equal to the bit length of the seed.

But the MT becomes entirely predictable after 624 iterations, at which point its entropy should be considered to be zero, but the subsequent distribution is still uniform.

These two ideas seem to contradict each other.

$\endgroup$
  • 1
    $\begingroup$ "but the subsequent distribution is still uniform" it's not uniform at all. $\endgroup$ – Maeher Jan 20 at 11:45
4
$\begingroup$

But the MT becomes entirely predictable after 624 iterations, at which point its entropy should be considered to be zero, but the subsequent distribution is still uniform.

The subsequent distribution is not, in fact, independently uniform.

Given 624 32-bit outputs $$V = V_1 \mathbin\| V_2 \mathbin\| \cdots \mathbin\| V_{624},$$ I can deterministically recover the Mersenne twister state by $$S(V) = \tau^{-1}(V_1) \mathbin\| \tau^{-1}(V_2) \mathbin\| \cdots \mathbin\| \tau^{-1}(V_{624}),$$ where $\tau$ is the tempering transform, and then compute the next output by deterministically running the generator $G$ on the recovered state $S(V)$. If the $V_i$ were independently uniformly distributed, we would have $$\Pr[V_{625} = G(S(V))] = 1/2^{32},$$ but if the $V_i$ are instead generated by the Mersenne twister with uniform random initial state, we have $$\Pr[V_{625} = G(S(V))] = 1.$$

This test—evaluate whether $V_{625} = G(S(V))$—will distinguish the Mersenne twister under a uniform random initial state from a uniform random string with high success rate.

Does this nonuniformity matter for the Monte Carlo physics simulation you're doing? Perhaps not: your physics model is unlikely to, by happenstance, interact with the Mersenne twister output generation function $G$ in a way that would be a problem, because physics itself is usually not adversarially trying to screw you up personally, no matter how much the years of pain in grad school might make it seem.

On the other hand, if there is an intelligent adversary, as we assume in cryptography, that intelligent adversary will exploit this relation to decipher your messages, steal your money by forging signatures, etc.

In other words, the Mersenne twister is designed to appear uniform to stupid algorithms that don't even know it's the Mersenne twister they're trying to distinguish, but falls flat on its face when it trips on an adversary who knows it's the Mersenne twister but just doesn't know the initial state.

$\endgroup$
1
$\begingroup$

But the MT becomes entirely predictable after 624 iterations, at which point its entropy should be considered to be zero, but the subsequent distribution is still uniform.

You are mixing up two different concepts of "entropy" here.

  • The first is the "true" (information-theoretic) entropy of a random variable $X\colon\;\Omega\to A$, defined as $$ H(X) = -\sum_{a\in A}\;p_a\cdot\log_2 p_a \text, $$ where $p_a=\Pr[X=a]$ and $\log_2 p_a$ is considered to be $0$ in case $p_a=0$.

    In this case, you would e.g. consider $A$ to be the set of all (infinite) sequences of numbers in the output range $[0,\dots,2^{32}-1]$ of the Mersenne Twister, and $X$ should be the random variable that outputs all MT values starting from some randomized internal state (i.e. $624$ uniformly random $32$-bit words). Then, indeed, there are exactly $2^{32\cdot 624}$ distinct outcomes of $X$, and they are all equally likely, hence the entropy of $X$ is $32\cdot624=19968$ bits.

  • On the other hand, there is something one may call "statistical entropy" or "empirical entropy": This essentially consists of "guessing" a random variable $X$ that may have been used to generate a concrete observed outcome and then computing the entropy of that variable.

    Concretely, given just a MT output sequence of length $n$, one may (wrongly!) guess that it is the output of $n$ independent identically distributed random variables $X_1,\dots,X_n$, each giving $32$-bit words $i$ distributed according to the observed relative frequencies $p_i$, and then the entropy of the random variable $(X_1,\dots,X_n)$ would be $$n\cdot\sum_{i=0}^{2^{32}-1}-p_i\log_2 p_i$$ bits. This is clearly different from the information-theoretic entropy (above), but there is no contradiction — this is simply a guess for the true entropy based on incomplete information. There are other sets of assumptions (e.g. different word sizes; uniform distribution instead of estimating based on frequencies; bases different from powers of two; dependencies between the words in the sequence; ...) that typically lead to different estimates for the entropy.

    In summary, the information-theoretic entropy of any MT instance (without reseeding) is upper bounded by $19968$ bits, but without knowing that it comes from a MT the generated sequence may look like a uniformly random sequence to statistical tests.

    Note that this is essentially the same problem as determining the "entropy" of a password: Unless you are generating a password yourself using a known randomized process, there simply is no way to tell whether a password is "random enough" or not. Just by looking at the characters, e.g. an encoded version of $\mathrm{SHA256}(w)$ for a random dictionary word $w$ may look very "random", but once you know the process used to generate it, the entropy is clearly upper bounded by the $\log_2$ of the number of words in the dictionary.

$\endgroup$
  • $\begingroup$ So once you go through 624 iterations of MT, the information-theoretic entropy remains the same. However, the "statistical entropy" goes down to zero because there is no longer any guessing involved. That is, there is no need to guess which random variable produced the 624-element sequence. It's known. Do I have the right idea? Also, can the MT still be considered to be uniformly distributed at that point? $\endgroup$ – Bastien Jan 20 at 19:14
  • $\begingroup$ @Bastien No, the "perceived" (statistical) entropy for someone who does not make use of the knowledge that it's a MT just keeps increasing, since the sequence looks uniform. I also recommend that you think of entropy as a property of the whole random process, not as something that "changes over time": for example, a better way to phrase your first observation is "the (information-theoretic) entropy of an infinite MT sequence $X$ is the same as that of $X$ cut off after $624$ steps." $\endgroup$ – yyyyyyy Jan 21 at 16:06
  • $\begingroup$ So it's like a Heisenbergian situation? If I don't make use of (or don't know) that it's predictable, then the entropy remains high. But if I detect or know that it's predictable, then it's zero. $\endgroup$ – Bastien Jan 21 at 17:26
  • 1
    $\begingroup$ @Bastien Well, "the entropy" is independent of the observer; it either is a certain value or it is not. But if the observer uses some simplified (i.e. wrong) model of the random process to estimate the entropy, they may think it's high even though it isn't. Once the observer learns the procedure that generates the sequence, their estimated entropy based on the new model of the random process would also drop, but in reality it was already lower than their first estimate from the start! $\endgroup$ – yyyyyyy Jan 21 at 18:04
-3
$\begingroup$

Your question encompasses both the cryptographic and information theory definitions of entropy. In cryptography, one is generally concerned with unknown entropy.

Entropy is maximized when the distribution is uniform...

This is true and holds whether the sequence is known or unknown. In the standard $ H(X)=-\sum_{x \in X} P(x) \log_2{P(x)} $ formula, the summation is maximised when all $ P(x) $ are equal. It drops as the distribution moves away from uniform to other types (Poisson, Gaussian, etc.) You can envisage it as related to the area of the sequence's histogram, as long as the bins remain the same.

But the MT becomes entirely predictable after 624 iterations, at which point its entropy should be considered to be zero, but the subsequent distribution is still uniform.

Mostly correct. Assume that the input to the MT is unknown (unknown entropy). MT therefore will start generating unknown entropy. The ratio $ \frac{H_{unknown}}{H_{known}} $ will then linearly decrease from high to 0 as the output lengthens to 624 words. After 624 words, all future MT output will be entirely predictable and thus known. Yet according to information theory the known entropy will remain at 8 bits/byte as the distribution is uniform. Storage of said entropy would still require 8 bits/byte. Unknown entropy useful for cryptography will of course then be zero.

Nobody at all does, but if you did use MT for cryptographic randomness, I suggest that one should reseed after 616 outputs, guaranteeing a 256 bit security level. There are other MT warm up nusances that make this a sub-optimal idea, but it illustrates the principle of entropy transforming from unknown to known.

$\endgroup$
  • $\begingroup$ Thanks, Paul. So if I understand correctly, there is entropy as it pertains purely to measuring how uniform a distribution, and then there's cryptographic entropy which is concerned with practical unpredictability. In the former case, the information theoretic entropy remains high, but since everything is now predictable, the cryptographic entropy goes down to zero. Is that the correct idea? I don't see this distinction made often (or maybe I miss it). $\endgroup$ – Bastien Jan 20 at 17:35
  • 5
    $\begingroup$ @Bastien I believe the reason you don't see this distinction made often is that it appears to be the opinion of Paul Uszak, rather than any kind of common terminology or theory used by the cryptographic community at large. (Citations to papers could help to prove this otherwise, but I have yet to see citations appear on answers such as this, and the terms "unknown entropy" and "known entropy" have never appeared in any paper I have ever seen) $\endgroup$ – Ella Rose Jan 20 at 17:43
  • $\begingroup$ @EllaRose Once the MT becomes predictable, can the distribution of the MT still be considered uniform? If not, what is the distribution at that point? $\endgroup$ – Bastien Jan 20 at 17:49
  • 1
    $\begingroup$ @Bastien Replace "Once a random variable is determined to not really be random" for "Once MT becomes predictable". You can substitute "Is it uniform? If not, what is it?" with "What distribution does this random variable have". Put that together and you get "Once a random variable is determined to not really be random, what distribution does that random variable have?" Look at it in either one of two ways. If it was bad to model a deterministic algorithm as a random variable then the question is invalid. If it's an okay model for pragmatic reasons, then the answer is that it's still uniform. $\endgroup$ – Future Security Jan 21 at 3:22
  • $\begingroup$ @FutureSecurity What I really want to know is the entropy of a Mersenne Twister at all times. The consensus, expressed in various ways, is that the entropy is high for the first 624 steps. At the 625th step, then it depends! If you know that it's predictable at that point, then it's zero. But if you don't know or pretend it's not, then it remains high. I am having a hard time wrapping my head around it because it's more philosophical than anything. $\endgroup$ – Bastien Jan 21 at 17:28

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.