Hai kỹ thuật cryptanalysis khối mạnh nhất đối với block cipher. Cùng mục tiêu: khôi phục khóa bí mật từ quan hệ thống kê giữa plaintext, ciphertext, khóa.
Linear Cryptanalysis (Matsui, 1993)
Ý tưởng: Tìm xấp xỉ tuyến tính (linear approximation) cho hàm phi tuyến (S-box, round function):
P[α₁..αₐ] ⊕ C[β₁..β_b] = K[γ₁..γ_c] với xác suất p ≠ ½.
Bias ε = |p - ½|. Cần ~1/ε² known plaintext-ciphertext pairs.
- Mô hình tấn công: Known-plaintext attack (KPA).
- Đặc điểm: Xử lý từng bit/parity bit; dùng hệ phương trình tuyến tính trên GF(2).
- Ứng dụng nổi bật: Phá DES (2⁴³ known plaintexts), FEAL, réduit-round AES/Serpent/Twofish.
Differential Cryptanalysis (Biham & Shamir, 1990)
Ý tưởng: Theo dõi sự lan truyền của độ chênh lệch (difference) ΔP = P₁ ⊕ P₂ qua các vòng mã hóa, tìm differential characteristic ΔP → ΔC với xác suất cao.
- Mô hình tấn công: Chosen-plaintext attack (CPA) — kẻ chọn P₁, P₂ với ΔP cố định.
- Đặc điểm: Xử lý cặp (pairs); xác suất đặc tính = tích xác suất từng S-box hoạt động.
- Ứng dụng nổi bật: Phá DES (2⁴⁷ chosen plaintexts), FEAL, Khufu, Khafre, réduit-round AES.
Bảng so sánh chi tiết
| Tiêu chí | Linear Cryptanalysis | Differential Cryptanalysis |
|---|---|---|
| Loại tấn công | Known-Plaintext (KPA) | Chosen-Plaintext (CPA) |
| Đối tượng phân tích | Parity bits / Linear approximation | Bitwise difference (XOR diff) / Differential characteristic |
| Độ phức tạp dữ liệu | ~ 1/ε² (ε = bias) | ~ 1/p (p = xác suất characteristic) |
| Cách tìm khóa | Thống kê parity bits → hệ phương trình tuyến tính → giải khóa | Lọc subkey candidates bằng xác suất differential → exhaustive search phần còn lại |
| Yêu cầu S-box | Bias tuyến tính lớn (linear approximation table - LAT) | Xác suất differential lớn (difference distribution table - DDT) |
| Kết hợp | Differential-Linear Cryptanalysis (Langford & Hellman, 1994): Kết hợp differential characteristic (trên) + linear approximation (dưới). Mạnh hơn từng cái riêng lẻ. | |
Áp dụng lên AES
- S-box AES (x⁻¹ trên GF(2⁸)): Max linear bias = 2⁻³, Max differential prob = 2⁻⁶.
- Wide-trail strategy: Số S-box hoạt động tăng tối thiểu mỗi vòng (branch number = 5).
- Kết quả: Cả hai chỉ phá ≤ 7 vòng AES-128 (giảm vòng). 10 vòng đầy đủ an toàn.
Thiết kế chống lại
- S-box: Non-linearity cao, low differential uniformity (APN/near-APN), low linear bias.
- Diffusion layer: Branch number lớn (MDS matrix), khuếc tán nhanh.
- Số vòng: Đủ margin (AES: 10/12/14 vs best attack 7).
- Key schedule: Tránh related-key weakness.