linear cryptanalysis (w3)

Question 1

what is linear cryptanalysis?

Answer 1

a category of attack launched against block ciphers

powerful attack, aims to approximate block ciphers by means of linear expressions

these expressions are true or false with some bias

we can use this bias to discover key bits

Question 2

how can bias in S-boxes be used to “guess” keys?

Answer 2

1. Determine biases of S-boxes,
   construct LAT
2. Approximate each S-box with
   (biased) linear expression.
3. Link expressions from initial
   plaintext to intermediate
   ciphertext.
4. Determine bias for linked
   expressions via Matsui’s
   Lemma.
5. For the final subkeys, determine
   how often expressions holds - if
   it matches bias, you have
   discovered the key!
6. Repeat for each subkey.

Question 3

key points from linear relations table for S-boxes:

Answer 3

• The expressions in columns involve either inputs or outputs (but not both).
• The number of agreements between some input expression and some output expression is calculated for the S-box.
• If the number of agreements and disagreements is not equal, then if we know the value of the output expression, we have information on the likely value of the input expression (without doing extra work).
• Thus we would expect the indicated expression
  X₃ XOR X₄ = Y₁ XOR Y₄
  to be true 2/16 of the time, i.e., X₃ XOR X₄ != Y₁ XOR Y₄ with probability
  14/16.
  So if you know Y₁ XOR Y₄ you can take a very good guess at the value
  of X₃ XOR X₄

Question 4

what is Matsui’s Piling Up Lemma?

Answer 4

• Matsui’s formula to estimate the bias that the derived expression will hold generally.
• There is a formula that will enable us to apply the ideas we have encountered to more complex systems with many substitution boxes.
• For n binary independent (potentially biased) random variables Z₁,…, Zn:
  Pr(Z₁ XOR Z₂ XOR … Z_n = 0) = 0.5 + 2^{n - 1} Π⁽ⁿ⁾_(i=1)ε_i
  *biases represented by ε₁…ε_n
• Logically if even one Z_i is unbiased (ε_i = 0), then
  Pr(Z₁ XOR Z₂ XOR … Z_n = 0) = 0.5
• Can prove this formula via induction

Question 5

what happens with Matsui’s Piling Up Lemma if one of the variables is genuinely unbiased?

Answer 5

• If just one of the variables in the sum is genuinely unbiased
  then so is the XOR sum of the two variables.
• Effectively randomizes Z₁ XOR Z₂

Question 6

what type of attack is linear cryptanalysis?

Answer 6

known plaintext attack (KPA)