How to check whether the permutation is random or not

Question

Imagine that my friend gives me the permutation $\pi$. He pretends that the permutation was generated completely random.

I'm suspicious and worried, because the permutation (for instance) looks like: $\pi(x) = ax + b \pmod n$ for some $a$, $b$. My friend said to me that it happens by chance.

Of course it is not possible for me to actually prove that permutation is not random, because we always can generate this one by chance.

Is there any strategy using which I can rigorously state (as a mathematical statement) that this event is very unplausible?

I can try to say something like : well, there is a structure, and a chance that random permutation will have this structure is really small. But the structure can be more tricky (for example, k-round Feistel network over some group with some round functions or the like). And my friend is telling me: well you can always invent some tricky formula and get every my permutation. But this does not indicate that the permutation is not random.

So the question is: if I found some "hidden" structure in "random" object, does it indicate that the object is very unlikely to be random or I can always find structure in every object that friend gives to me? How this "suspiciousness" can be quantified in the rigorous mathematical sense?

Answer 1

There are at most $n \cdot (n - 1)$ permutations of $\mathbb Z/n\mathbb Z$ of the form $x \mapsto ax + b$: if $n$ is prime, there are $n - 1$ choices for $a$ and $n$ choices for $b$ under which this is a permutation. There are $n!$ permutations of $\mathbb Z/n\mathbb Z$ altogether. So the probability that a uniform random permutation has this form is negligible if $n$ is even modest in size—the probability is at most $n \cdot (n - 1)/n! = 1/(n - 2)!$, which gets very small very quickly as $n$ grows. For example, for $n = 64$, this probability is already less than $1/2^{256}$, which, in cryptographic terms, is not-gonna-happen squared.

• You can confidently verify whether it has this form given oracle access to the permutation simply by querying it on two different inputs and solving for $a$ and $b$, and then checking it on a third point, and a fourth point, etc., to see if they match.

  Exercise: Compute the false alarm rate of this test for a uniform random permutation as a function of the number of confirmation points. The statistical power of the test under the alternative hypothesis of the form $x \mapsto ax + b$, of course, is the maximum possible: 1.

• You can confidently say your friend is not being entirely forthcoming about how they chose the permutation if it has this form (e.g., it's an 8-bit permutation and you can verify all 256 outputs) but they claim they chose it uniformly at random.

  For an 8-bit permutation, the probability of falsely accusing your friend in the event they actually did choose the permutation uniformly at random—the false alarm rate, or ‘statistical significance’—is below $1/2^{256}$, the equivalent of ‘$p < .0000…00001$’ (77 zeros).

However, that's only for this particular test, if you devised the test without knowledge of the permutation. If your friend gives you a permutation and based on the permutation you devise a test that it fails, that may not mean anything—for any particular choice of permutation, there are many tests with low false alarm rates that it will fail. And if you string many tests together, so that any one of them will raise an alarm, then the false alarm rate rises—a standard consequence of ‘$p$-value hacking’ or the ‘garden of forking paths’.

---

This question is similar to the issues surrounding the hash function Стрибог (Streebog), from the Russian federal government standard ГОСТ Р 34.11-2012 (also RFC 6986), and the block cipher Кузнечик (Kuznyechik), from ГОСТ Р 34.12-2015 (English; also RFC 7801).

In 2015, Alex Biryukov, Léo Perrin, and Aleksei Udovenko discovered a remarkable structure in the S-box—a permutation of 8-bit strings which the Streebog designers maintain was chosen at random by rejection sampling on uniform random S-boxes (archived).

When Perrin et al. identified the structure, they reasoned that the designers' story is implausible because there are $256! \approx \sqrt{2\pi\,256\,} (256/e)^{256} \approx 2^{1684}$ possible S-boxes, of which only about $2^{82}$ admit a neat concise description with the special structure.

‘But,’ you object, ‘knowing my permutation, you could invent any tiny class of permutations containing my permutation even if I really did choose it uniformly at random. Then you could use the low probability of your class to claim that I must have chosen my permutation from that class intentionally, rather than guessing it by luck! That doesn't mean anything!’ (This is essentially the argument made by the designers to claim that they are not lying spooks, according to Léo Perrin, as recently as a couple of weeks ago at an ISO standardization meeting.)

So Perrin put it to codegolf.SE, whose participants came up with various short descriptions of the permutation including a 78-byte, or 624-bit, AMD64 instruction sequence.

A code-golfing exercise is interesting not so much because a program can be invented that is shorter (for example, a 1-bit program for a machine that either computes the S-box if the program is 0, or returns zero if the program is 1), but because the AMD64 instruction set was presumably designed without knowledge of the chosen S-box—and if the Streebog designers really did sample from permutations uniformly at random to choose the S-box, the probability of getting one that admits a 78-byte/624-bit description in the AMD64 instruction set is at most $2^{624}\!/2^{1684} = 1/2^{1060}$. Of course, the Streebog designers had some criteria for rejection sampling, but even if they went through a quintillion candidates this way (short scale, about $2^{60}$), the probability would remain less than $1/2^{1000}$.

---

Another way to look at it is:

• Imagine writing down a sequence of all ${\approx}2^{1684}$ 8-bit permutations, labeling them $1,$ $2,$ $\dotsc,$ $2^{1684} - \mathit{whatever}$. It doesn't matter what order you put them in; you can put them in any order you want, as long as you do it without seeing into the future of what I'm about to do.

  If I then pick a permutation uniformly at random, there's a 1/2 chance it'll be in the first half of your sequence. There's a 1/4 chance it'll be in the first half of the first half—that is, the first quarter—of your sequence. More generally, there's a $1/2^n$ chance it'll be in the first half of the first half of the first half…of the first half ($n$ times)—same odds as flipping a coin $n$ times and having it come up heads every time. If I wanted to find a permutation in that region by trying them uniformly at random until one works, the expected number of permutations I'd have to try is about $2^n$.

• Now imagine writing out all byte strings: (empty), 0x00, 0x01, 0x02, …, 0xff, 0x00 0x00, 0x01 0x00, 0x02 0x00, …, 0x00 0x01, 0x01 0x01, 0x02 0x01, and so on. Some of these are valid AMD64 instruction sequences. Some of the valid AMD64 instruction sequences implement permutations (say, permuting the value of AL, ignoring all other architectural state).

  You certainly need at least 211 bytes to cover all of the permutations this way, because with only 210 bytes = 1680 bits, there are more 8-bit permutations than there are sequences of 210 bytes. You almost certainly need more than 211 bytes, too, because most AMD64 instructions sequences do not compute permutations—but you don't need much more than 256 bytes, because you could use a 256-byte table of all inputs and outputs in ROM and then a MOV instruction or two to use it.

  So, you have now laid out a sequence of all 8-bit permutations by enumerating AMD64 instruction sequences. Somehow, by allegedly doing rejection sampling on uniform random choices of 8-bit permutations, the designers found one that lies in the first half of the first half of the first half…of the first half of this sequence, iterated over a thousand times, an event with probability less than $1/2^{1000}$—even if they rejected a quintillion candidates first.

If you wrote out any sequence of a thousand coin toss outcomes—THTTHHHTHT…—and then watched a gambler flip a coin a thousand times coming up with exactly your sequence while looking at it, would you believe that they were doing fair coin tosses, or would you begin to suspect they might be pretty good at flipping coins to come up the way they want?

---

Of course, in principle, this could still be a fluke: By shopping around to different languages in the garden of forking paths, we could maybe find a language in which this permutation by chance happens to turn up early in the sequence…by shopping through about $2^{990}$ different programming languages to raise the probability of a false alarm from $2^{-1000}$ to a mere one-in-a-thousand $2^{-10}$. But (a) it is not plausible that codegolf.SE tried out $2^{990}$ different programming languages, and (b) besides AMD64 instructions, there are also now descriptions of the same S-box in many languages that all clock in at well under 200 bytes, including C, C#, JavaScript, Rust, and Python.

There's an alternative hypothesis: Like a gambler who can make a coin come up the way they want (it's actually quite easy!), the Streebog designers may have used a method of generating the S-box that enabled compact, efficient implementation which they just aren't telling anyone about. The outcome of such a method—even if randomized—would be much more likely to have many short descriptions in existing programming languages. In a Bayesian analysis, whatever prior odds ratio we assigned to the hypotheses $\text{structured}$ and $\text{uniform random}$ (i.e., the relative plausibility of the two hypotheses a priori), we can write the posterior odds ratio by Bayes' rule in terms of the prior odds ratio and the likelihood ratio as:

\begin{multline*} \frac{\Pr[\text{structured} \mid \text{78-byte code golf}]} {\Pr[\text{uniform random} \mid \text{78-byte code golf}]} \\ = \frac{\Pr[\text{structured}]}{\Pr[\text{uniform random}]} \cdot \frac{\Pr[\text{78-byte code golf} \mid \text{structured}]} {\Pr[\text{78-byte code golf} \mid \text{uniform random}]}. \end{multline*}

It is obviously hard to quantify what $\Pr[\text{78-byte code golf} \mid \text{structured}]$ is without a clearer idea of what structures the Streebog designers might have considered, but let's say that there's about a one-in-a-googol ($10^{100} \approx 2^{332}$) chance that there's a 78-byte code golf solution in a well-known widely-used programming language for the method the Streebog designers used. In that case, we might measure the magnitude of code golf as evidence for the structured hypothesis over the uniform random hypothesis—the likelihood ratio, which is the ratio of the posterior odds ratio to the prior odds ratio, measured in decibels—as

\begin{multline*} 10 \log_{10} \frac{\Pr[\text{78-byte code golf} \mid \text{structured}]} {\Pr[\text{78-byte code golf} \mid \text{uniform random}]} \\ \leq 10 \log_{10} \frac{2^{-332}}{2^{-1000}} = 10 \log_{10} 2^{790} \approx 2000\,\mathrm{dB}. \end{multline*}

To put this number in perspective, the magnitude of evidence we demand in cryptography before accepting a message in typical message authentication code rather than rejecting it as a forgery is over $300\,\mathrm{dB}$—and remember that decibels are a logarithmic scale. (For more on measuring weight of evidence between two hypotheses in decibels, see Jaynes's book, particularly chapter 4.)

Of course, this is a very heuristic quantification of the evidence—it should really be taken mainly as an illustration of the Bayesian shape of reasoning. There may also be other hypotheses which this analysis doesn't consider—for instance, perhaps the Streebog designers just used a particularly bad PRNG when allegedly performing a Fisher–Yates shuffle to generate the permutations, and didn't realize that they were exploring a subspace that has an interesting relation to the AMD64 instruction set.

Exercise: Hypothesize plausible PRNGs that the Streebog designers might have used, and extend this to a many-hypothesis Bayesian analysis.

---

For more on the background and references, see Léo Perrin's web site and the story so far at ASIACRYPT 2019.

Answer 2

This precise issue recently arose in light of suspicious patterns in the S-box of a Russian cipher Kuznyechik. See:

Xavier Bonnetain and Léo Perrin and Shizhu Tian: Anomalies and Vector Space Search: Tools for S-Box Analysis, Asiacrypt 2019

One way the authors chose to quantify how unlikely such a permutation could have occurred by chance is to find the smallest program that implements the permutation. In this case, the permutation is on 8 bits and so there are $256! \approx 2^{1684}$ possible permutations. But since there is a 624-bit machine code implementation of the permutation, there are only $2^{625}$ permutations that are as simple (or simpler), under the measure of code size. Put differently, the chance that a randomly sampled permutation has such a small implementation is less than $2^{-1000}$.