# 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/