1 of 19

p l a i n t e x t

S2 #1 - Linear Cryptanalysis

01 / 28 / 2025

2 of 19

Introductions!

Join the SIGNAL! -->

Introduce yourself:

  • Name + Where are you from
  • Major + class year
  • Favorite pizza toppings
  • Interest/experience in crypto

3 of 19

Outline

  • Symmetric Key Crypto review
  • SPN Ciphers
  • Linear Cryptanalysis main idea
  • Linear Approximation Table
  • Actual attack
  • Live demonstration

4 of 19

Why do we need cryptography?

2 main types of encryption: Symmetric and Asymmetric

5 of 19

Today: Symmetric-Key Encryption

Examples: AES and ChaCha20

6 of 19

Good Ciphers & SPN Ciphers

Good ciphers must have sufficient:

  • diffusion (spread things out)
  • confusion

(Shannon)

​

Key construction:

Substitution-Permutation Networks

​

Simple round repeated multiple times

​

Each round:

  • XOR with round key
  • Do substitution with Sbox (confusion)
  • Do a permutation (diffusion)

7 of 19

Example SPN cipher

Uses a 16*3 = 48 bit key with 3

parts: K0, K1, K2.

​

Layout:

  • Key 0 XOR
  • Sboxes
  • Permute
  • Key 1 XOR
  • Sboxes
  • Key 2 XOR
  • Output

​

Takes in a 16 bit block P

and encrypts it to a 16

bit block C.

​

​

8 of 19

Substitution step through an S-Box

S-Box is just a nonlinear bijective mapping.

​

Adds confusion because the data gets messed up throughout the cipher.

​

The main focus of linear cryptanalysis and cipher design

9 of 19

Permutation step

Shuffling the bits according to some set pattern

​

For simple, few round ciphers, the exact permutation is not super important for linear cryptanalysis

​

But permutations are very important in real cipher design and exploitation.

10 of 19

Linear Cryptanalysis Main Idea

We have lots (>>10000x) of plaintext ciphertext pairs like:

Plaintext: “My bank account number is 1234”

Ciphertext: da4dec98b6fb00510960f9d7ec72c1eb6457449c4a7892876520e8427aa32262

​

Using this data, we want to recover the key

This would let us decrypt any ciphertext we hear in the future

Linear Cryptanalysis main idea: exploit linear approximations of the cipher to do this

11 of 19

Linearities

Linear equations are the easiest types of equations

For example, “x + 10 = 0” is easy to solve

Compare this with “x^3 + 10x^2 = 0”... quite a lot harder

​

A cipher that has any linear part has no confusion, so that would be a terrible cipher and why we have S-Box.

But even okay seeming ciphers might have approximate linearities if the S-Box isn’t well designed.

12 of 19

Approximate linearities

Instead of relationships like x + y = 0 inside the cipher,

we have relationships like

x + y = 0, 60% of the time

Or any other percentage.

​

Ideally a cipher should have no linearities, so all linear relationships should hold with a 50% chance. Even a slight deviation from this 50% may allow us to use linear cryptanalysis

13 of 19

Linearities in the cipher

Only part of the cipher that isn’t linear is the Sbox.

​

Linearities in the Sbox:

​

Slightly complicated so done on board

​

Key concepts:

  • Input mask
  • Output mask
  • XOR and parity

​

Masks determine a linear equation like a + b = c

​

14 of 19

What linearities do we want?

Let's say some linearities are found with probability p.

We want p to be as far away from 1/2 as possible.

I.e. we want the bias to be as high as possible

​

bias = |p - 1/2| where |x| is the absolute value of x

Usually, we put all the linearities and their biases in a table called the Linear Approximation Table (LAT)

15 of 19

Linear Approximation Table (LAT)

​

​

(Explained on board)

16 of 19

Actual Attack

With good linearity with high bias, to recover the key(s):

  • Guess a subkey
  • Check whether linearity holds for given subkey, plaintext and ciphertext
  • Keep count of the percentage

The subkey with the largest bias is most likely correct (Why? on board)

17 of 19

Live demonstration

Recap of the attack:

  • Compute the LAT to find high bias linearity
  • Make guesses for K2
  • Check if correct with linearity
  • (Do the same thing for K1)
  • (Getting K0 is trivial after you have K1 & K2)

18 of 19

Summary

  • Symmetric Key Crypto review
  • SPN Ciphers
  • Linear Cryptanalysis main idea
  • Linear Approximation Table
  • Actual attack
  • Live demonstration

19 of 19

References and Resources

Thanks for coming :)