# What are the relations between cryptanalysis of block ciphers such as AES and Kendall's tau coefficient?

Studying AES on Wikipedia, I noticed a statement regarding some ongoing studies on the use of Kendall's Tau coefficient in cryptanalysis:

According to the Snowden documents, the NSA is doing research on whether a cryptographic attack based on tau statistic may help to break AES

This paper on Kendall's tau refers to the Pearson correlation coefficient, and in the related Wikipedia article we can read:

Pearson correlation coefficient is a measure of the linear correlation between two variables X and Y

It's somehow straightforward to think at the variables in this statement like the variables in linear cryptanalysis... is this correct?
Is the application of Kendall's tau a sort of power-up of Linear Cryptanalysis? How?

• I believe this is used in Differential Power Analysis – David 天宇 Wong Nov 18 '17 at 18:28
• @David天宇Wong Do you have more information about that? – forest Aug 15 '19 at 1:41
• @forest You can check en.wikipedia.org/wiki/Power_analysis for a start. – hola Dec 11 '19 at 18:21
• @xxx--- I know what power analysis and differential power analysis are. I'm curious how the Kendall tau correlation coefficient is related to differential power analysis. – forest Dec 12 '19 at 9:06

Here is a wild guess as to what this reference may actually mean.

TL;DR; The Kendall $$\tau$$ can be used to measure how close different rankings of key guesses resulting from stages of the attack are, to track if the attack is getting close to the real key ranking, in some sense.

Aside: The paper On Probability of Success in Linear and Differential Cryptanalysis by A A Selcuk, available here is an excellent reference on probability of success in linear and differential cryptanalysis, where ranking of keys is also mentioned.

Please note that the idea of Pearson correlation coefficient is quite general, however it does measure correlation between random variables, including the type of binary random variables encountered in linear cryptanalysis, for example, if we focus on a single Sbox $$S(\cdot)$$, $$\textrm{corr}_{a,b}(S)=\sum_{X \in \{0,1\}^n} (-1)^{a\cdot X\oplus b\cdot S(X)}$$ is exactly a Pearson type of coefficient for the pair of binary random variables $$(-1)^{a\cdot X},(-1)^{b\cdot S(X)}.$$ However, I don't think this is where the interesting direction of this argument lies.

For sure, we choose $$a,b$$ in order to maximize the correlation, and eventually do this for $$r-1$$ rounds in order to attack some input key bits into the $$r^{th}$$ round by partial decryption of the ciphertext, conditional on those guessed keys. Specifically the key guess which maximizes the overall correlation dependent on whatever $$a_i,b_i$$ choices in a collection of Sboxes away from zero as we compute biases over a large set of plaintext/ciphertext pairs are hypothesized to be more likely to be the correct key guess.

However, how does this actually work in practice?

We obtain a ranking of key guesses from most likely to less likely, based on the correlation samples obtained. We keep a count of how many times each key guess satisfies the hypothesized linear expression, and rank guesses according to how biased they are. I will refer to the most likely key as the highest ranked. There is an actual correct ranking which puts the correct key on top and all the rest below it. In fact the collection of rankings which put the correct key on top, and the rest arbitrarily are all admissible.

Let's recall the wikipedia reference to Kendall's $$\tau.$$

The Kendall tau rank distance is a metric that counts the number of pairwise disagreements between two ranking lists. The larger the distance, the more dissimilar the two lists are. Kendall tau distance is also called bubble-sort distance since it is equivalent to the number of swaps that the bubble sort algorithm would take to place one list in the same order as the other list.

The evidence is that AES is very strong against differential cryptanalysis. This means that it will require a huge number of plaintext/ciphertext pairs to break it this way.

To make things simple, consider attacking AES in a sequence of attacks using $$K_i=2^{(i+N)},$$ for $$i\geq 0,$$ plaintext/ciphertext pairs, where $$N$$ is some large integer. This is conceptual of course, since $$N$$ has to be impractically large.

Say we look at the ranking of the key guesses that result from each of these attacks (by doubling the number of P/C pairs used at each step as $$i$$ increases). If we want to gauge how we are progressing as $$i$$ increases, we would like to find out if some kind of convergence in the key ranking is occuring towards the correct ranking. Let $$\pi_i$$ be the ranking corresponding to the $$i^{th}$$ attack.

One way of doing this would be to compute the Kendall $$\tau$$ coefficient between the different rankings $$\pi_i.$$

A similar argument could be made for differential cryptanalysis as well, since both attacks rely on collecting enough plaintext/ciphertext samples so that the correct key guess has the highest rank, rank 1, with high probability.