Linear Cryptanalysis là kỹ thuật known-plaintext attack tìm xấp xỉ tuyến tính (linear approximation) cho các phép biến đổi phi tuyến trong block cipher. Được Mitsuru Matsui phát minh (1993), áp dụng đầu tiên cho FEAL, sau đó phá vỡ DES (2⁴³ known plaintexts).
Nguyên lý cốt lõi
Tìm phương trình tuyến tính trên GF(2) liên kết bit plaintext P, ciphertext C, khóa K:
P[α₁] ⊕ P[α₂] ⊕ ... ⊕ C[β₁] ⊕ C[β₂] ⊕ ... = K[γ₁] ⊕ K[γ₂] ⊕ ...
Phương trình đúng với xác suất p ≠ ½. Độ lệch (bias) ε = |p - ½|. Càng |ε| lớn càng tốt.
Hai giai đoạn tấn công
- Tìm xấp xỉ tuyến tính tốt (Offline): Phân tích S-box, round function, xây dựng linear trail qua nhiều vòng. Tính bias bằng Piling-up Lemma (Matsui). Mục tiêu: bias lớn nhất cho (n-1) hoặc (n-2) vòng.
- Khôi phục khóa (Online): Thu thập N known plaintext-ciphertext pairs. Với mỗi candidate subkey cho vòng cuối, giải mã phần tử ciphertext, kiểm tra linear approximation. Subkey đúng sẽ có thống kê lệch p rõ rệt (|count - N/2| > threshold).
Công cụ phân tích
- Linear Approximation Table (LAT): Bảng 256×256 cho S-box 8-bit: LAT[a][b] = #{x : a·x = b·S(x)} - 128. Bias = LAT[a][b]/256.
- Branch number / Wide-trail: Thiết kế AES giới hạn số S-box hoạt động → bias giảm cấp số nhân qua vòng.
Kết quả nổi bật
| Cipher | Vòng đầy đủ | Vòng bị phá (Linear) | Độ phức tạp |
|---|---|---|---|
| DES | 16 | 16 (full) | 2⁴³ known PT, 2⁴³ time |
| FEAL-4/8 | 4/8 | Full | Rất thấp |
| AES-128 | 10 | 7 | 2⁹⁹ data/time (giảm vòng) |
| Serpent | 32 | 10-12 | Giảm vòng |
| PRESENT | 31 | 25-26 | Giảm vòng |
Mở rộng: Multiple / Multidimensional Linear Cryptanalysis
- Dùng nhiều xấp xỉ tuyến tính cùng lúc (multiple approximations) → tăng bias hiệu quả, giảm data complexity.
- Multidimensional: dùng phân bố xác suất đa chiều (χ² test / LLR test) thay vì single bit parity.
Phòng thủ
- S-box: Non-linearity cao (max bias thấp), balanced (mỗi output xuất hiện đều).
- Diffusion layer: Branch number lớn (MDS matrix) → khuếc tán nhanh, giảm số linear trail hữu hiệu.
- Số vòng: Margin an toàn (AES: 10 vs best attack 7).
- Key schedule: Tránh linear relation giữa round keys.
Kết luận: Linear cryptanalysis là công cụ phân tích chuẩn, buộc thiết kế mật mã hiện đại phải chứng minh an toàn trước nó (provable security against linear/differential). AES, ChaCha20, Simon/Speck đều được thiết kế với wide-trail strategy để chống linear/differential.