# Why do "nothing up my sleeve numbers" have low entropy?

As a preface, forgive me for some of the links being from Wikipedia. I realize that academia frowns upon this.

In cryptography, nothing up my sleeve numbers are any numbers which, by their construction, are above suspicion of hidden properties. [...] Such numbers can be viewed as the opposite extreme of Chaitin–Kolmogorov random numbers in that they appear random but have very low information entropy.

In looking for an example of one of these numbers, I came across this Crypto Beta Q&A, where the answerer says:

[M]athematical constants like binary expansions of irrational numbers like 2√ (or roots of other numbers), e, π can be used, to show that one didn't select the numbers to create a back door.

This is what Wikipedia has to say about information entropy:

Entropy is typically measured in bits, nats, or bans. Shannon entropy is the average unpredictability in a random variable, which is equivalent to its information content. Shannon entropy provides an absolute limit on the best possible lossless encoding or compression of any communication, assuming that the communication may be represented as a sequence of independent and identically distributed random variables.

Based on this, I don't see why these numbers (or any possible number) can have low entropy. It seems like all numbers have equal likelihood of being generated as a "random variable" as long as that number is within the generated range (e.g., if the number is 1564631 [assumed to be one of these kinds of numbers], and I'm looking for number between 1 and 2000000, it has an equal likelihood of being generated, regardless).

Can anyone explain this concept? I looked at the definition of entropy, but I admit that the math is a little over my head. I'm not sure how someone would use a number without these properties to "create a backdoor."

• If I ask you to guess the next number in the "random" sequence 31415..., you can probably guess 9, and you'd be right. In (probably oversimplified) layman's terms, entropy = unpredictability. May 17 '14 at 1:20
• @TimS. Well, my guess would have been 1, followed by 6 :-). (I can recognize the first five digits of π, but the five numbers are also the integers 345 with a 1 after the first two).
May 17 '14 at 12:39
• @FreeRadical - your are correct; but two "most likely" guesses is less than "10 equally likely guesses", so it still has low entropy.
– Floris
May 17 '14 at 22:14
• @asteri The number wouldn't be 1564631, that's the entire point. Feb 29 '16 at 20:35

You're absolutely correct: numbers (or a given binary string) don't have entropy. However, a number can be sampled from a distribution that has entropy. In other words, the entropy is a property of the process used to generate a number, not of the number itself.

So if I just give you the number 4, and assure you that I picked this number uniformly at random from between 1 and 6, you have no way of knowing if I'm telling the truth. Depending on the scenario, maybe I had an ulterior motive for picking 4, rather than choosing a number at random.

The issue comes up in cryptography because when it comes time to choose the constants for an algorithm (such as SHA1, or any of the other examples in the Wikipedia article you linked), there might be mathematical arguments suggesting, "If the constants are chosen at random, then with high probability, no attacker will be able to break it." But cryptographers, being a paranoid lot, are skeptical when someone says, "Let's use this set of constants. I picked them at random, I swear." So as a compromise, they'll use constants like, say, the binary expansion of π. While we no longer have the mathematical benefit of having chosen them at random from some large pool of numbers, we can at least be more confident there was no sabotage.

These nothing-up-my-sleeve constants have low entropy because the process of choosing them didn't involve very many random choices --- compare the number of "reasonable" nothing-up-my-sleeve numbers to the number of, say, 128-bit strings they are used to produce. This is by design. If there were a large number of nothing-up-my-sleeve numbers to choose from, then it would be easier for a malicious algorithm designer to find some that suited his agenda.

A very recent and very alarming case of someone not using nothing-up-my-sleeve numbers to create a backdoor is the Dual EC DRBG standard, which is used to generate random numbers. This algorithm included two constants, P and Q, and would be secure if no one could compute f(P, Q), for a specific function f. Given randomly chosen P and Q, this would be hard. However, if you get to choose P and Q, then you could choose P, decide what you wanted f(P, Q) to be, and then solve for Q rather easily. Now you have a backdoor.

• And after choosing the number, it's fixed, so the entropy is 0. Jan 20 at 12:45

First let's say that entropy is a property of a generation process. A number, by itself, does not have any entropy. What has entropy is the algorithm or process which has produced that number, and the entropy measures what the number could have been. In that sense, the formulation in the Wikipedia page lacks rigour.

For a "nothing up my sleeve" number, we want a number such that there is no or as little as possible choice for whoever chose the number. An "evil number" would be a number where the generator could choose some characteristics of the integer. The intuitive idea behind using, say, π, is that while the digits of π are "seemingly random" (they can be computed but they are not all-zeros or regular), they are fixed and cannot be chosen at will by the attacker. The generation process should not include "randomness" because such randomness could be chosen by the attacker; but "natural randomness" like the digits of π is fair game because the attacker does not get to choose the digits of π.

It is important to realize that part of the problem is psychological. If I were a bad guy defining a new algorithm, and in the position to chose a constant value which can potentially be backdoored, then my goal will be to find a definition for that constant which will embody that backdoor, but accompanied with a story that will convince other people that I did not choose that exact value with evil intent.

There is still room for attacks in some cases. Suppose that I, as an attacker, have determined that one every billion values allows for a backdoor. Then, I may define my constant to be H(x) for some deterministic PRNG H and a seed value x. Then I proceed to enumerate "plausible" seed values x until I find one which implies a backdoorable constant. I can begin by trying out all Bible verses, excerpts of Shakespeare works, historical dates, names of people and places... because for all of them I can build a story which will make the seed value look innocuous (e.g. "the seed value is 'Phuntsholing' because that is where my grandmother was born"(*)). I can have casing variants (all-uppercase, all-lowercase...) and non-latin script add a wealth of possibilities.

I can thus try billions of such "plausible seed values". This number is multiplied by the number of variants for the PRNG itself (there are several of them out there).

If we want to see this as "entropy", then the seed is the source of the entropy. But we see here the limitations of the entropy formalism: the crucial point is not the presence or absence of randomness in the process, but how many non-random deliberate choices I can smuggle under the disguise of a nice story. This is a matter of psychology, and the terminology of mathematics is ill-fitting.

(*)Phuntsholing is a town in Bhutan.

Edit: JP Aumasson wrote this script a few months ago as a proof-of-concept of the generation of millions of NUMS-looking constants, and noticed that it was an embodiment of the kind of attack I am talking about in the text above.

The mathematical section to the wikipedia article provides a poor introduction to informational entropy. To get an intuitive feel for it, replace entropy with the related concept of Kolmogorov complexity. (Things with low Kolmogorov complexity will have low informational entropy; things with high complexity will have a high amount of entropy).

Kolmogorov complexity of a number/string is simply the length of a minimal description of how to generate that in some formal language -- there is no concrete way to compute this complexity, but its still a useful concept. For example the strings aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa (32 as) or 11235813213455891442333776109871597258441816765... (concatenate together first hundred fibonacci numbers) have low complexity. While something like gwhobkghgylxuelc would have higher complexity as there's no obvious pattern and you'd have to specify all the letters to allow some to regenerate it (so it would have higher complexity).

Something like the first 512 binary digits of pi or would have low entropy/Kolmogorov complexity -- there's only handful of very important math constants (pi, e, phi, sqrt(2)) and taking the first 512 digits is a simple description. However, if I just gave you a arbitrary 512 binary digit string that would have very high complexity -- you'd have to specify every digit. By having that free choice, you could purposely choose a weak version where there's some particular property that let's you attack it. If you want to prove that you didn't choose a number to be purposefully weak, you base it on simple easy choices.

Informational entropy is not that complicated of a concept, though the wikipedia article muddles it up. It's best to think of entropy as just the logarithm (to avoid having to deal with very large numbers all the time, and in informational theory we usually use the base-2 log to measure the entropy in bits) of the number of equally likely possibilities. Simply S = log2 (# of possibilities). So if you want to calculate the entropy of a 50-digit decimal password it would be log210^50 = 166 bits. But if you had the first 50 decimal digits of a well-known mathematical constant (and chose from a list of 8 of these numbers), then you'd have an informational entropy of log2 8 = 3 bits.

The complicated equation S = - Σ P log P is equivalent to this other form when all events are equally likely. If there are N = # of possibilities and they are all equally likely then the probability of any one is P = 1/N. Then S = - Σ (1/N) log (1/N) = Σ (1/N) log N = log N.

• @PaulUszak - If I need to send someone a trillion 0s, you don't say the entropy is a trillion bits. You merely agree on an appropriate compression scheme for that type of data, say a digit and how many times to repeat that digit. Then it ends up being under 100 bits (~40 to store a trillion, plus the digit (maybe 8 bit) to repeat and some overhead to indicate the compression scheme, separators, end of transmission). Similarly, if you needed to send the first digits of pi efficiently, you could use a compression scheme that transmits a formula for pi and the number of digits to calculate. Jan 14 '16 at 5:31
• The formula for Shannon entropy is S = - Σ p_i log (p_i) where you iterate over all possibilities. E.g., if you have a 1 digit password where all 10 digits were chosen uniformly p_i = 1/10 for all i (from 0 to 9), then S = - 10 * (1/10 lg (1/10)) = lg 10 ~ 3.322. Similarly for 2-digit there are N=100 possibilities, each with prob p=1/100, so S = lg 100 = 2*lg 10 ~ 6.644. Thus, for 50 digit passwords, each password is chosen at p=10^-50 and there are 10^50 of them, so the Shannon entropy of generating a random 50 digit password is exactly S = 50*lg 10 (which is approximately 166.096). Jan 14 '16 at 6:05
• @PaulUszak - I never said Shannon entropy and Kolmogorov complexity are equivalent concepts, they aren't. I said they are related concepts (which they are see for example: en.wikipedia.org/wiki/Kolmogorov_complexity#Relation_to_entropy or homepages.cwi.nl/~paulv/papers/info.pdf or www-isl.stanford.edu/~cover/papers/transIT/0331leun.pdf ). Second, I have read Shannon's 1948 paper and see his theorem 2 defining entropy as H = -Σpᵢ log pᵢ . This isn't an approximation or upper bound and if it was a gross overestimate, prove it. Jan 25 '16 at 21:41
• @PaulUszak - Simply generate say N=100,000 random 50 digit passwords and write them to a text file. Try any method of encoding or compression (that doesn't have knowledge of some phenomenon underlying the randomness of how the 50-digit passwords were generated; e.g., no access to PRNG seeds). If you can encode 100k such passwords in less than 166*N = 16,609,640 bits (about 2.07 MB), then you've shown it's an overestimate. As quick check, applying standard compression (which adds things like checksums), I can compress such a file to about 2.15 MB (bzip2) which is 172 bits/pw. Jan 25 '16 at 21:59
• @PaulUszak H = -Σpᵢ log pᵢ is an exact formula the entropy of random strings generated with probabilities pᵢ. If you have many random strings generated with a total entropy of N bits, it will be impossible (in aggregate) to losslessly compress such data with less than N bits. This does mean that H is an estimate or upper bound on the entropy; it means this calculated entropy sets a lower-bound on the size of losslessly compressed data (in aggregate). Furthermore, 11.9 bits is not less than 7.3. See: en.wikipedia.org/wiki/… Feb 5 '16 at 4:43