DES (Data Encryption Standard) — block cipher Feistel 64-bit block, 56-bit key, 16 vòng — đã bị phá vỡ hoàn toàn về mặt thực tế. Các tấn công chính:
1. Brute Force Attack (Tấn công vét cạn khóa)
- Key space: 2⁵⁶ ≈ 7.2×10¹⁶ keys.
- Lịch sử: 1997 EFF Deep Crack (56 giờ, $250k hardware). 1998 distributed.net (22h). 2017: ~$100 cloud (GPU/FPGA). 2024: phút/giây trên phần cứng chuyên dụng.
- Meet-in-the-middle trên 2DES: 2DES (Double DES) chỉ 2⁵⁷ operations (không phải 2¹¹²) → không an toàn.
- 3DES (3-key): 2¹¹² security (meet-in-the-middle) — vẫn an toàn lý thuyết nhưng block 64-bit yếu (birthday bound 2³² blocks), chậm, deprecated.
2. Differential Cryptanalysis (Biham & Shamir, 1990)
- Phân tích lan truyền độ chênh lệch (Δ) qua S-box và P-box.
- DES S-box: max differential probability = 4/64 = 1/16.
- Characteristic 15-round: prob ~2⁻⁵⁵ → cần 2⁴⁷ chosen plaintexts.
- Full 16-round: 2⁴⁷ chosen plaintexts, 2³⁷ DES operations — thực tế trên phần cứng hiện đại (nhưng cần chosen plaintext, khó thực hiện thực tế).
- NSA/IBM thiết kế DES đã biết differential cryptanalysis (giữ bí mật đến 1990) → S-box được tối ưu chống differential.
3. Linear Cryptanalysis (Matsui, 1993)
- Tìm linear approximation P·α ⊕ C·β = K·γ với bias ε = |p - ½|.
- DES: Best linear trail bias ~2⁻²¹ (14-round) → 2⁴² known plaintexts cho 14-round; full 16-round: 2⁴³ known plaintexts, 2⁴³ time.
- First attack phá full DES thực tế (known-plaintext, không chosen).
- Yêu cầu 2⁴³ known plaintext-ciphertext pairs (~8 TB dữ liệu) — khó thu thập thực tế nhưng lý thuyết phá vỡ.
4. Related-Key Cryptanalysis
- Kẻ biết/có thể chọn mối quan hệ giữa khóa (K, K⊕Δ).
- DES key schedule tuyến tính (rotation + PC-2) → related-key attack hiệu quả.
- Không thực tế cho mô hình single-key, nhưng nguy hiểm cho protocol dùng key derivation yếu (K, K+1, K+2...).
5. Weak Keys & Complement Property
- 4 Weak keys: C₀/D₀ all 0 hoặc all 1 → mọi round key giống nhau → E(K, E(K, P)) = P (self-inverse).
- 6 Semi-weak key pairs: K₁, K₂: E(K₁, E(K₂, P)) = P.
- Complement property: E(K, P) = C ⇒ E(K̅, P̅) = C̅. Giảm brute-force 1 bit (2⁵⁵).
- Triển khai phải check và reject weak/semi-weak keys.
6. Small Block Size Attack (Birthday Bound)
- Block 64-bit → sau ~2³² blocks (32 GB) encrypt dưới cùng khóa (CBC/CTR), collision ciphertext xảy ra với prob ~0.5.
- Leak thông tin plaintext (Sweet32 attack trên TLS/OpenVPN 3DES/Blowfish 64-bit block).
- AES 128-bit block → birthday bound 2⁶⁴ blocks (256 EB) — an toàn.
7. Side-Channel Attacks (Triển khai)
- Timing attack: S-box table lookup cache timing.
- Power/EM analysis (DPA/CPA): Trên smartcard, HSM không hardening.
- Fault injection: Laser/glitch gây lỗi round → suy ra key.
Bảng tóm tắt độ phức tạp tấn công DES
| Tấn công | Loại | Data Complexity | Time Complexity | Thực tế? |
|---|---|---|---|---|
| Brute Force | Known/CT | 1 PT-CT | 2⁵⁶ (2⁵⁵ avg) | CÓ (phút/giây 2024) |
| Differential Cryptanalysis | Chosen PT | 2⁴⁷ CP | 2³⁷ DES ops | Lý thuyết (cần CP) |
| Linear Cryptanalysis | Known PT | 2⁴³ KP | 2⁴³ DES ops | Lý thuyết (cần 8TB KP) |
| Meet-in-the-Middle (2DES) | Known PT | 1 KP | 2⁵⁷ time, 2⁵⁶ mem | CÓ (2DES broken) |
| Sweet32 (Birthday, 64-bit block) | Passive | 2³² blocks | 2³² blocks | CÓ (TLS 3DES/Blowfish) |
Kết luận: DES không an toàn cho mọi mục đích mới. Brute-force key 56-bit dễ dàng. Block 64-bit gây Sweet32. 3DES 3-key (112-bit) vẫn an toàn key-recovery nhưng block size yếu, chậm, deprecated NIST 2023. Bắt buộc chuyển sang AES-256-GCM / ChaCha20-Poly1305 / XChaCha20-Poly1305.