---
# System prepended metadata

title: Linear Cryptanalysis on Linear-SBox AES

---

# Linear Cryptanalysis on Linear-SBox AES

## 1. Linear Cryptanalysis là gì?
- Là 1 kĩ thuật known-plaintext attack, tức là chúng ta sẽ dùng những cặp plaintext-ciphertext được mã hóa dưới cùng 1 key để khôi phục lại cái key đó
- Kĩ thuật này tấn công vào những kiểu mật mã có thể biểu diễn dưới dạng **Linear Funtion** hoặc **Affine Transformation**:
$$f(x*y)=f(x)*f(y)$$
## 2. Method Attack on Linear-SBox AES
- Một SBox có tính chất "Linear" khi:
$$S[i \oplus j] \oplus S[i] \oplus S[j]=constant$$
- Điều này dẫn tới việc thuật toán mã hóa AES có thể được biểu diễn dưới một Binary Matrix như sau:
$$E_{K}(msg')\oplus E_{K_0}(msg')= A.E_{K'}(msg')$$
- Trong đó $K =$ secret key, $msg =$ secret msg, $K' =$ optional key,$K_0 =$ 16 bytes **0x00**, $msg' =$ optional msg, $A$ = constant binary matrix
- Cụ thể hơn:
$$
 \begin{pmatrix}
  a_{1,1} & a_{1,2} & \cdots & a_{1,128}
 \end{pmatrix}
 \oplus 
 \begin{pmatrix}
  b_{1,1} & b_{1,2} & \cdots & b_{1,128}
 \end{pmatrix}
 = 
 \begin{pmatrix}
  c_{1,1} & c_{1,2} & \cdots & c_{1,128}
 \end{pmatrix}
 .
 \begin{pmatrix}
  d_{1,1} & d_{1,2} & \cdots & d_{1,128} \\
  d_{2,1} & d_{2,2} & \cdots & d_{2,128} \\
  \vdots  & \vdots  & \ddots & \vdots  \\
  d_{128,1} & d_{128,2} & \cdots & d_{128,128} 
 \end{pmatrix}
$$
- Construct Binary 128x128 matrix:
    - $K'_0 = 1$
    - for each $i$ in (0,127):
        - $K'_i = K_0' << i$
        - add($E_{K'_i}(msg')$) to binary matrix
- $K = \begin{pmatrix}
  c_{1,128} & c_{1,127} & \cdots & c_{1,1}
 \end{pmatrix}$

- Chall luyện tập: 
    - https://cryptohack.org/challenges/aes/