Diffusion (Khuếc tán) là thuộc tính mật mã làm lan tỏa thông tin thống kê của plaintext ra ciphertext: thay đổi 1 bit plaintext → thay đổi ~nửa bit ciphertext (và ngược lại). Mục tiêu: che giấu mối quan hệ thống kê plaintext-ciphertext, chống statistical attack.
Định nghĩa chính thức (Shannon, 1949)
Một cipher có diffusion tốt nếu:
- Mỗi bit ciphertext phụ thuộc vào nhiều bit plaintext.
- Mỗi bit plaintext ảnh hưởng đến nhiều bit ciphertext.
- Thay đổi 1 bit input → output thay đổi theo phân bố nhị phân cân bằng (avalanche effect).
Cơ chế đạt được Diffusion
| Kỹ thuật | Mô tả | Ví dụ |
|---|---|---|
| Permutation (P-box / D-box) | Hoán vị bit/word theo thứ tự cố định | DES initial/final permutation, AES ShiftRows |
| Linear Mixing (Matrix multiplication) | Nhân ma trận MDS trên trường hữu hạn | AES MixColumns (MDS 4×4 trên GF(2⁸)), Twofish MDS |
| Feistel Network | Nửa khối qua F-function, rồi swap | DES, Camellia, SM4 |
| ARX (Add-Rotate-XOR) | Cộng modulo 2ⁿ, xoay bit, XOR | ChaCha20, BLAKE2, Speck |
Diffusion trong AES (Ví dụ tiêu chuẩn)
- ShiftRows: Dịch hàng 2,3,4 lần lượt 1,2,3 byte — lan tỏa byte cột sang hàng khác.
- MixColumns: Nhân mỗi cột 4-byte với ma trận MDS cố định trên GF(2⁸). Branch number = 5: 1 byte input thay đổi → 4 byte output thay đổi (tối thiểu 5 byte tổng input+output).
- Kết quả: Sau 2 vòng: 1 byte plaintext ảnh hưởng đến tất cả 16 byte state (full diffusion).
Đo lường Diffusion
- Avalanche Effect: Flip 1 bit input → trung bình 50% bit output flip. Test: NIST SP 800-22, dieharder.
- Branch Number (B): B = min(wt(Δin) + wt(Δout)) cho mọi Δin ≠ 0. B lớn = diffusion mạnh. AES MixColumns: B=5 (tối đa cho 4-byte).
- Strict Avalanche Criterion (SAC): Flip 1 bit input → mỗi bit output flip với xác suất ½.
- Bit Independence Criterion (BIC): Các bit output thay đổi độc lập nhau.
Diffusion vs Confusion (Shannon)
| Diffusion | Confusion |
|---|---|
| Lan tỏa thống kê plaintext → ciphertext | Làm phức tạp quan hệ key ↔ ciphertext |
| Dịch chuyển/hoán vị/phép tuyến tính (MDS) | Thay thế phi tuyến (S-box) |
| Che giấu pattern plaintext | Che giấu pattern khóa |
| Ví dụ: ShiftRows, MixColumns, P-box | Ví dụ: AES S-box, DES S-box |
Cần cả hai mới an toàn. Chỉ diffusion (Permutation cipher) hoặc chỉ confusion (Substitution cipher) đều yếu.
Ứng dụng ngoài Block Cipher
- Hash function: Compression function cần diffusion mạnh (AES-NI trong SHA-256, Keccak-f permutation).
- Stream cipher: Keystream generator cần diffusion state (ChaCha20 quarter round).
- KDF / PRF: HKDF, PBKDF2 dùng diffusion của hash bên dưới.