Disproving a Coincidence with Code Golf

π (as in the Greek letter) is a component used by the latest standard symmetric cryptographic algorithms in Russia, namely the block cipher Kuznyechik and the cryptographic hash function Streebog. It is what we cryptographers call an S-box, i.e. a small non-linear function with an input small enough that it is possible to specify said function simply by providing all of its outputs. That is what the C array above is: pi[x] is equal to π(x).

Both Streebog and Kuznyechik are standards in Russia and at the IETF (RFC 6986 and 7801 respectively). Streebog is also an ISO/IEC standard and Kuznyechik might become one. In a previous paper on this S-box [3], I found that it could be described by a very simple algorithms which I called TKlog. This work and its context are summarized on this page.

Since the publication of that structure, the designers of these algorithms have claimed that the presence of said structure was a mere coincidence during an ISO/IEC meeting [4]. They claim to have in fact generated it by picking random permutations and then keeping one with good enough cryptographic properties. More details about their claims can be seen in two internal ISO documents that were recently leaked:

• the first describes their generation process: memo-on-kuznyechik-s-box.pdf,
• the second is a summary of a discussion that took place after the publication of the final decomposition [3]: meeting-report-for-the-discussion-on-kuznyechik-and-streebog.pdf.

However, the set of TKlogs is beyond tiny (it contains \(2^{82.6}\) elements while there are \(256! \approx 2^{1684}\) permutations of \(\{ 0,1,...,255 \}\)), meaning that their claim is a priori very hard to believe. To put these unfathomable number into perspective: there are about \(2^{265}\) atoms in the universe and a random permutation is a TKlog with a probability of \(2^{82.6-1684} \approx 2^{-1601.4}\) which is just under \((2^{-265})^6\). Suppose that you are participating in a special lottery where you have to pick 1 atom in the whole universe, and that you win if you guessed the right one. The probability of obtaining a TKlog when choosing an 8-bit permutation uniformly at random is a bit below the probability of winning this atomic lottery 6 times in a row. What I am trying to say is that the probability of obtaining a TKlog by chance is small. Like, really, really really small.

Thus, to try to reconcile my work with their claims of randomness, the designers of π asserted that, for any permutation, it is possible to find a simple structure implementing it. Thus, while the probability of having a TKlog specifically is tiny, the probability of having some structure is very high. Had they picked the next randomly generated S-box, I would have found another equally unlikely structure.

It sounds plausible! Indeed, suppose that you have a coin and want to check if it is biased. To do this, you look at the number of tails you get when tossing it 10000 times and find 4970. The probability that you get exactly this number is quite small: $$ \textrm{Pr}\left[\# \textrm{tails} = 4970 \right] = {10000 \choose 4970} 2^{-10000} \approx 0.0067 ~. $$ But it is not that interesting. What would be much more meaningful in this case is the probability that you get 4970 tails or fewer, namely $$ \textrm{Pr}\left[\# \textrm{tails} \leq 4970 \right] = \sum_{i=0}^{4970}{10000 \choose i} 2^{-10000} \approx 0.28 ~, $$ which is actually quite high.

The situation would then be the same for the presence of a structure in an S-box. Sure, each specific structure has a tiny probability (like that of having exactly 4970 tails) but it is the case for the structure of all the S-boxes. It is similar to the case of the coin, having exactly 4971 or 4969 tails is also unlikely. But it doesn't mean anything: it is in the end not that weird to have at most 4970 tails, and we cannot deduce that the coin is biased from the fact that it yielded 4970 tails. For π, we similarly could not deduce that its structure is not a coincidence from the fact that said structure has a low probability.

Except this is completely wrong.

As plausible as it may sound, the argument about π detailed above is completely wrong because a random permutation does not have a structure and certainly not one as simple as a TKlog.

To see why, we need to find a way to sort the different S-box structures. If two structures can always be ranked (i.e. if we can find a partial ordering of the S-box structures), then we can look at probabilities that are far more meaningful: instead of the probability that π has a specific structure (here, the TKlog), we can instead look at the probability that π is at least as structured as a TKlog. As in the example above with the coin, this would give us a probability of having a structure like the one we found or better, which would be far more informative.

And that is why we will code golf!

The ordering we propose to use is very simple and takes inspiration from the Kolmogorov complexity. Intuitively, if a function is "simple" or "too structured" then it should be possible to implement it using a short program. Here, short means that the program takes literally little space, i.e. that it can be encoded with few bits. The length of the smallest program is then an integer, and those are very easy to order: 1 is smaller than 5 which is smaller than 47, etc. Identically, a function that can be implemented on 400 bits is simpler than one that needs at least 2000. Finding small implementations is precisely the goal of code golf, which is why we need to grab our metaphorical golf clubs. We must however be careful to choose a meaningful language: if we just define a language such that p() is a predefined function that implements π then we haven't said much.

One problem remains: we can now compare the simplicity of two functions by comparing the length of their smallest implementation. But in order to say something about the simplicity of a given function compared to all the others, we need some absolute quantification of said simplicity. This implies bounding the length of the program needed to implement a random permutation.

It is surprisingly simple to obtain a (very coarse) bound suited to our purpose. In fact, Claude Shannon used the same kind of argument to prove that almost all Boolean functions mapping n bits to 1 are as difficult to implement as the hardest ones [6]. Suppose that all strings of \(b\) bits are valid programs in the language of your choice. Then at most \(1+2+4+...+2^b = 2^{b+1}-1\) functions have an implementation at most \(b\) bits long. There are at most \(2^{b+1}-1\) such program so it is impossible that they correspond to \(2^{b+1}\) distinct functions or more.

Thus, in our case, if a permutation can be implemented by a program of length \(L\) then there are at most \(2^{L+1}\) permutations with an implementation as small as this, and the probability that a random permutation is that simple is at most equal to \(2^{L+1-1684}\). This bound is everything but tight! It assumes that all strings are valid programs corresponding to distinct permutations. It is not the case, so we have an upper bound—but that is all we need.