SPN Networks

2026-11-18

notes / Cryptography / Block Ciphers

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

Round Function

simple XOR between round key bits and data block input

let us assume round keys are independently generated and unrelated

Confusion

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

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 ciphers1

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

Xi1⊕Xi2⊕…Yj1⊕Yj2⊕…Yjv=0

Piling-Up Principle

notice

let

gives

can be extended to give

ε1,2,…,n=2n−1∏i=1nεi

Caution

the random variables must be independent

Cipher Components

linear vulnerabilities of the s-box

consider X2⊕X3⊕Y1⊕Y3⊕Y4=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. 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. S12:X1⊕X3⊕X4=Y2 => ε=4/16
  2. S22:X2=Y2⊕Y4 => ε=−4/16
  3. S32:X2=Y2⊕Y4 => ε=−4/16
  4. S34:X2=Y2⊕Y4 => ε=−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. U1,5⊕U1,7⊕U1,8=V1,6 with bias 1/4
  2. U2,6=V2,6⊕V2,8 with bias −1/4
  3. U3,6=V3,6⊕V3,8 with bias −1/4
  4. U3,14=V3,14⊕V3,16 with bias −1/4

we can now concatenate all of these as Bias[A1=A2=A3=A4]=23⋅1/4⋅−1/4⋅−1/4⋅−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 U1,5=P5⊕K1,5 and so on to expand into

P5⊕P7⊕P8⊕V3,16⊕V3,14⊕V3,8⊕V3,6⊕K1,5⊕K1,7⊕K1,8⊕K2,6⊕K3,6⊕K3,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 U4,16=V3,16⊕K4,16 and so on to get

P5⊕P7⊕P8⊕U4,16⊕U4,14⊕U4,8⊕U4,6⊕ΣK=0

Where Σ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 (K5) 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

Differential Cryptanalysis

Overview

Cipher Components

Sample difference pairs of S-box: for ΔX=1011

X X′ Δ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 ΔY=0010 has probability 8/16

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 2n=16
  2. All element values are even (commutativity of Δ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 ΔX=1011, ΔY=0010 has the high probability. Let us construct our path

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

Using

  1. S12:ΔX=B→ΔY=2 with Pr=8/16
  2. S23:ΔX=4→ΔY=6 with Pr=6/16
  3. S32:ΔX=2→ΔY=5 with Pr=6/16
  4. S33:ΔX=2→ΔY=5 with 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

∴ we get the probability of getting the input to the last round as 8/16*(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 ND≈c/pD where pD is the differential characteristic probability for the R−1 rounds and c is a small constant.

Exercises

linked from


  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/↩︎