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

Question

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

I came across this article about "nothing up my sleeve numbers". In it, it says:

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."

Answer 1

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.

Answer 2

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.

Answer 3

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 = log₂ (# of possibilities). So if you want to calculate the entropy of a 50-digit decimal password it would be log₂10^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 log₂ 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.