SPN Networks

• Round Function
• Diffusion Layer (permutation)
• Confusion Layer (substitution)
• Attacks
  • Linear Cryptanalysis
  • Differential Cryptanalysis
• Exercises

flowchart LR

A[PLAINTEXT]
B[ADD ROUND KEY]
C[ADD CONFUSION]
D[ADD DIFFUSION]
E[ADD CONFUSION]
F[ADD ROUND KEY]
G[CIPHERTEXT]

A --> B --> C --> D --> E --> F --> G
D --> B

consider the example SPN cipher that takes 16 bit input block and has 4 rounds

Round Function

• to incorporate secret key
• key mixing

simple XOR between round key bits and data block input

let us assume round keys are independently generated and unrelated

Confusion

• relation between key and ciphertext is obscured
• eg. substitution

break into 4 bit s-boxes

input	output
0	E
1	4
2	D
3	1
4	2
5	F
6	B
7	8
8	3
9	A
A	6
B	C
C	5
D	9
E	0
F	7

The attacks of linear and differntial cryptanalysis apply equally whether one s-box or multiple

Diffusion

• is an encryption operation where the influence of one plaintext symbol is spread over many ciphertext symbols with the goal of hiding statistical properties of the plaintext.
• eg. bit permutation, mix column

input	output
1	1
2	5
3	9
4	13
5	2
6	6
7	10
8	14
9	3
10	7
11	11
12	15
13	4
14	8
15	12
16	16

Attacks

attacks on symmetric key block ciphers¹

Linear Cryptanalysis

known-plaintext-attack

1. Create LATs for all S-boxes
2. Create LAT for overall cipher by concatenating
3. Extract Final subkey bits

Overview

• seeks to approximate bits of the cipher through linear equations²
• linearity refers to XOR opeations

$$X_{i_1}\oplus X_{i_2}\oplus \dots Y_{j_1}\oplus Y_{j_2}\oplus \dots Y_{j_v}=0$$

• the probability of the approximation should be bounded away from $\frac{1}{2}$ to be called a “good” approximation³
• to get these good approximations we inspect the only non-linear component: the S-Box

Piling-Up Principle

notice

• (linear relation) $X_1\oplus X_2=0\equiv X_1=X_2$
• (affine relation) $X_1\oplus X_2=1\equiv X_1\ne X_2$

let

• $\mathrm{Pr}[X_1=0]=p_1=1/2+{\epsilon }_1$
• $\mathrm{Pr}[X_2=0]=p_2=1/2+{\epsilon }_2$

gives

• $\mathrm{Pr}[X_1\oplus X_2=0]=1/2+2{\epsilon }_1{\epsilon }_2$
• $\therefore {\epsilon }_{1,2}=2{\epsilon }_1{\epsilon }_2$

can be extended to give

$${\epsilon }_{1,2,\dots ,n}=2^{n-1}\prod _{i=1}^n{\epsilon }_i$$

CAUTION

the random variables must be independent

Cipher Components

linear vulnerabilities of the s-box

consider $X_2\oplus X_3\oplus Y_1\oplus Y_3\oplus Y_4=0$

analysing our s-box above we can see that over all 16 possible inputs for X for exactly 12/16 cases the expression above holds true i.e. $\text{Bias}=12/16-1/2=1/4$

we may use this to create a Linear Approximation Table

where each number represents a linear combination of input/output variables

Linear Approximation Table

we created the LAT for one S-box above, to continue with the entire cipher we concatenate appropriate linear approximations of S-boxes

Consider the concatenation along this path

we will be using the following approximations of the S-box

1. $S_{12}:X_1\oplus X_3\oplus X_4=Y_2$ ⇒ $\epsilon =4/16$
2. $S_{22}:X_2=Y_2\oplus Y_4$ ⇒ $\epsilon =-4/16$
3. $S_{32}:X_2=Y_2\oplus Y_4$ ⇒ $\epsilon =-4/16$
4. $S_{34}:X_2=Y_2\oplus Y_4$ ⇒ $\epsilon =-4/16$

we cannot simply concatenate shit without acknowledging the key xors between rounds

consider input to s-box as $U$ and output as $V$ with the subkey as $K$

1. $U_{1,5}\oplus U_{1,7}\oplus U_{1,8}=V_{1,6}$ with bias $1/4$
2. $U_{2,6}=V_{2,6}\oplus V_{2,8}$ with bias $-1/4$
3. $U_{3,6}=V_{3,6}\oplus V_{3,8}$ with bias $-1/4$
4. $U_{3,14}=V_{3,14}\oplus V_{3,16}$ with bias $-1/4$

we can now concatenate all of these as $\text{Bias}[A_1=A_2=A_3=A_4]=2^3\cdot 1/4\cdot -1/4\cdot -1/4\cdot -1/4=-1/32$

CAUTION

we are proceeding under the impression that all s-box substitutions are independent (may not be true but close enough)

we can rephrase our concatenation as $U_{1,5}=P_5\oplus K_{1,5}$ and so on to expand into

$$P_5\oplus P_7\oplus P_8\oplus V_{3,16}\oplus V_{3,14}\oplus V_{3,8}\oplus V_{3,6}\oplus K_{1,5}\oplus K_{1,7}\oplus K_{1,8}\oplus K_{2,6}\oplus K_{3,6}\oplus K_{3,14}=0$$

1. All the $U$‘s from the first layer appear
2. All the $V$‘s from the last layer appear
3. All the intermediary $K$‘s appear

in our final expression

we can do some expansion to get rid of the $V$‘s using $U_{4,16}=V_{3,16}\oplus K_{4,16}$ and so on to get

$$P_5\oplus P_7\oplus P_8\oplus U_{4,16}\oplus U_{4,14}\oplus U_{4,8}\oplus U_{4,6}\oplus {\Sigma }_K=0$$

Where ${\Sigma }_K$ is a deterministic constant depending on the master key and can be ignored

Extracting Key Bits

The idea is

1. You have $n$ known plaintext-ciphertext pairs
2. Your $2nd$ last round sends the output only to certain last round S-Boxes.
3. You can bruteforce the subkey bits after those boxes ($K_5$) and compare the final output with your known ciphertext
4. For every tried subkey you keep track of how many plaintext/ciphertext pairs it gave a correct result of (final output matched ciphertext bits)
5. ideally the subkey with the most matches is the correct guess

Complexity

• Number of known pairs required: $N_L\approx 1/{\epsilon }^2$

Differential Cryptanalysis

• Chosen Plaintext Attack (CPA)
• stems from the analysis of the XOR of two plaintexts as they travel through the cipher⁴
• XOR tells us where the two plaintexts differ

Overview

• seeks to exploit scenario where particular $\Delta Y$ occurs given a particular input difference $\Delta X$ with very high probability $p_D$
• $(\Delta X,\Delta Y)$ is called a differential
• $\Delta X=X_i^{\prime }\oplus X_i^{\prime \prime }$
• subkey bits end up disappearing since they appear in both inputs
• the initial goal is to find high probability differential pair

Cipher Components

• to analyse a $4\times 4$ S-box you need to check over all possible pairs $X_i^{\prime }$ and $X_i^{\prime \prime }$ that xor to give some $\Delta X$. (only ends up being 16 since $X_i^{\prime \prime }$ is determined based on $\Delta X$ which is constant)
• for each pair derive the value of $\Delta Y$
• You will notice many repeated values in the list of $\Delta Y$ found

Sample difference pairs of S-box: for $\Delta X=1011$

$X$	$X^{\prime }$	$\Delta Y$
0000	1011	0010
0001	1010	0010
0010	1001	0111
0011	1000	0010
0100	1111	0101
0101	1110	1111
0110	1101	0010
0111	1100	1101
1000	0011	0010
1001	0010	0111
1010	0001	0010
1011	0000	0010
1100	0111	1101
1101	0110	0010
1110	0101	1111
1111	0100	0101

notice how $\Delta Y=0010$ has probability $8/16$

• we tabularise this entire data in a difference distribution table, where the left column iterates over values of $\Delta X$ and the top row over $\Delta Y$

	0	1	2	3	4	5	6	7	8	9	a	b	c	d	e	f
0000	16
0001				2				2		2	4		4	2
0010				2		6	2	2		2					2
0011			2		2					4	2		2			4
0100				2			6			2		4	2
0101		4				2	2				4		2			2
0110				4		4							2	2	2	2
0111			2	2	2		2			2	2					4
1000							2	2				4		4	2	2
1001		2			2			4	2		2	2	2
1010		2	2						6			2			4
1011			8			2		2						2		2
1100		2			2	2	2					2		6
1101		4						4	2		2		2		2
1110			2	4	2				6						2
1111		2			6					4		2			2

1. Sum of all elements in a row/column is $2^n=16$
2. All element values are even (commutativity of $\Delta X$)
3. Due to these properties we can never have ideal S-box (all elements = 1)

REMEMBER

Key bits have no influence on a differential since they cancel out

Differential Characteristics

Notice for $\Delta X=1011$, $\Delta Y=0010$ has the high probability. Let us construct our path

$\Delta P=[0000101100000000]$ will have many such possible pairs. We call those right pairs

Using

1. $S_{12}:\Delta X=B\to \Delta Y=2$ with $\mathrm{Pr}=8/16$
2. $S_{23}:\Delta X=4\to \Delta Y=6$ with $\mathrm{Pr}=6/16$
3. $S_{32}:\Delta X=2\to \Delta Y=5$ with $\mathrm{Pr}=6/16$
4. $S_{33}:\Delta X=2\to \Delta Y=5$ with $\mathrm{Pr}=6/16$

ALERT

we assume the differentials of each round is independent of the previous and next rounds, thus the joint probability is just the product

$\therefore$ we get the probability of getting the input to the last round as $8/16\ast (6/16{)}^3=27/1024=0.026$

Extracting Key Bits

Once an $R-1$ round differential characteristic is discovered we can attack the cipher by recovering bits from the last subkey.

Now partially decrypt the ciphertexts by bruteforcing over the target partial subkey bits. The keys with the highest probability are your candidates

Complexity

Number of chosen plaintext pairs $N_D\approx c/p_D$ where $p_D$ is the differential characteristic probability for the $R-1$ rounds and $c$ is a small constant.

Exercises

Footnotes

1. https://cs.bc.edu/straubin/crypto2017/heys.pdf ↩

2. https://kevinliu.me/posts/linear-cryptanalysis/ ↩

3. https://cse.iitkgp.ac.in/~debdeep/courses_iitkgp/Crypto/slides/LC.pdf ↩

4. https://maticstric.github.io/differential-cryptanalysis-tutorial/ ↩