S-Boxes
In the first section, we mentioned the desirable property of confusion, this being the effect of each output bit depending on many input bits. The source of confusion in all SPNs and inherently in PRESENT comes from the S-Boxes, i.e. the substitution step. The PRESENT S-Box is as follows: $$ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline x & \textbf{0} & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4} & \textbf{5} & \textbf{6} & \textbf{7} & \textbf{8} & \textbf{9} & \textbf{A} & \textbf{B} & \textbf{C} & \textbf{D} & \textbf{E} & \textbf{F} \ \hline S[x] & \textbf{C} & \textbf{5} & \textbf{6} & \textbf{B} & \textbf{9} & \textbf{0} & \textbf{A} & \textbf{D} & \textbf{3} & \textbf{E} & \textbf{F} & \textbf{8} & \textbf{4} & \textbf{7} & \textbf{1} & \textbf{2} \ \hline \end{array} $$
The inverse follows appropriately. Algebraically, the S-Box can also be represented with the following Boolean functions:
$$ \begin{aligned} &y_0 = x_0 + x_2 + x_3 + x_1x_2 \ &y_1 = x_1 + x_3 + x_1x_3 + x_2x_3 + x_0 x_1 x_2 + x_0x_1x_3 + x_0x_2x_3 \ &y_2 = 1 + x_2 + x_3 + x_0x_1 + x_0 x_3 + x_1 x_3 + x_0x_1x_3 + x_0x_2x_3 \ &y_3 = 1 + x_0 + x_1 + x_3 + x_1x_2 + x_0x_1x_2 + x_0x_1x_3 + x_0x_2x_3 \end{aligned} $$ At a glance, there doesn't seem to be a demonstrable pattern, and the S-Box seems to accomplish its job of confusion. However, something can be found if we dig enough.
Differential properties
We mentioned previously that the idea behind differential attacks is exploiting correlations between differences in input and differences in output. Specifically, we concern ourselves with the differences in the context of a cipher's S-Box.
Let's assume the difference in our input is $7$ (which we denote $\Delta_{\text{in}} = 7$). So one pair of inputs could be $(0,7)$, i.e. $x = 0$ and $x = 7$. Their output difference is then: $$\Delta_{\text{out}} = S[0] \oplus S[7] = \text{C} \oplus \text{D} = 1$$In a similar fashion, testing another pair $(8, \text{F})$ also gives $\Delta_{\text{out}} = 1$ for the same $\Delta_{\text{in}}$. From here, it's also obvious that $(7, 0)$ and $(\text{F}, 8)$ are valid pairs (and, in fact, the only missing ones). Given we have a total of sixteen eligible pairs (and only sixteen possible output differences), we come to realise that there must exist some bias when observing these differences. That is to say that some outputs are more likely than others (while some may be entirely impossible). This differential property of the S-Box is what we will base our attacks on this section.
Difference Distribution Table (DDT)
While finding all these properties isn't difficult, we have an interest in presenting them in an orderly fashion. The simplest way is as a table of various input and respective output differences, coined the Difference Distribution Table (DDT). Below is PRESENT's DDT.
Δ 0 1 2 3 4 5 6 7 8 9 a b c d e f
------------------------------------
0 | 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 | 0 0 0 4 0 0 0 4 0 4 0 0 0 4 0 0
2 | 0 0 0 2 0 4 2 0 0 0 2 0 2 2 2 0
3 | 0 2 0 2 2 0 4 2 0 0 2 2 0 0 0 0
4 | 0 0 0 0 0 4 2 2 0 2 2 0 2 0 2 0
5 | 0 2 0 0 2 0 0 0 0 2 2 2 4 2 0 0
6 | 0 0 2 0 0 0 2 0 2 0 0 4 2 0 0 4
7 | 0 4 2 0 0 0 2 0 2 0 0 0 2 0 0 4
8 | 0 0 0 2 0 0 0 2 0 2 0 4 0 2 0 4
9 | 0 0 2 0 4 0 2 0 2 0 0 0 2 0 4 0
a | 0 0 2 2 0 4 0 0 2 0 2 0 0 2 2 0
b | 0 2 0 0 2 0 0 0 4 2 2 2 0 2 0 0
c | 0 0 2 0 0 4 0 2 2 2 2 0 0 0 2 0
d | 0 2 4 2 2 0 0 2 0 0 2 2 0 0 0 0
e | 0 0 2 2 0 0 2 2 2 2 0 0 2 2 0 0
f | 0 4 0 0 4 0 0 0 0 0 0 0 0 0 4 4
Task Generate a DDT for the S-Box of PRESENT, matching the above output.
In our table, a row matches a set input difference, while a column an output difference. We can spot out earlier example on the table, $\Delta_{\text{in}} = 7$ and $\Delta_{\text{out}} = 1$, to have a value of 4, as we calculated. Notice how every entry is even? This is due to the innate symmetry of differentials — if $(x, y)$ is a pair with some input difference and output difference, then $(y, x)$ must have the same differences.
Another interesting thing to note is the 16 when $\Delta_{\text{in}} = 0$ and $\Delta_{\text{out}} = 0$. This makes sense: for any pair of identical inputs, we expect an identical output. This differential is called the trivial differential.
Notation
Cryptography is a young field. Differential cryptanalysis even more so. As a result, notation differs between authors. Nonetheless, we will try to agree on a few common terms for the duration of the course.
For a $\Delta_{\text{in}} = x$ we can choose a corresponding $\Delta_{\text{out}} = y$. Such a pair is called a differential and is denoted $x \rightarrow y$ . A differential has a set amount of solutions (i.e. input pairs that satisfy the differential). The set of solutions is denoted $S(x, y)$, and the number of solutions $#S(x,y)$ and is what the DDT showcases.
As mentioned, the differential $0 \rightarrow 0$ is called the trivial differential. Any differential for which $#S(x,y) = 0$ is called an impossible differential, and a possible differential otherwise.
A possible differential holds with some probability $p$. This probability can be gauged from the DDT, and is dependent on the number of solutions for the differential relative to the total amount of input pairs. For PRESENT, it follows that: $$p = \frac{#S(x,y)}{16}$$ Another useful term is differential uniformity. For a given DDT, the largest non-trivial value is the differential uniformity of the S-Box. For example, PRESENT has a differential uniformity of 4. This is useful when making security claims as it provides an upper limit to how "probable" a differential could be, and is something we'll use later.