Cryptographic Hash Function là hàm toán học: H: {0,1}* → {0,1}ⁿ chuyển đầu vào tùy ý độ dài thành đầu ra độ dài cố định n-bit, thỏa mãn các tính chất bảo mật nghiêm ngặt. Là khối xây dựng cơ bản của mật mã học hiện đại.
Định nghĩa hình thức
Hàm băm H là hàm nén (compression function) lặp:
- Domain: D = {0,1}* (chuỗi nhị phân độ dài tùy ý).
- Range: R = {0,1}ⁿ (chuỗi nhị phân độ dài cố định n, n ≥ 128 cho bảo mật hiện đại).
- Tính toán: H(M) = h trong thời gian đa thức O(|M|).
- Deterministic: Cùng M → cùng h.
Ba tính chất bảo mật cốt lõi (Security Properties)
| Tính chất | Định nghĩa | Độ khó lý thuyết (n-bit output) |
|---|---|---|
| Preimage Resistance (Kháng nguyên ảnh) | Cho h, không thể tính được M nào sao cho H(M)=h | 2ⁿ |
| Second Preimage Resistance (Kháng nguyên ảnh thứ 2) | Cho M₁, không thể tìm M₂≠M₁ sao cho H(M₂)=H(M₁) | 2ⁿ |
| Collision Resistance (Kháng va chạm) | Không thể tìm M₁≠M₂ bất kỳ sao cho H(M₁)=H(M₂) | 2ⁿ/² (Birthday bound) |
Mối quan hệ: Collision resistance ⇒ Second preimage resistance ⇒ Preimage resistance. Nhưng ngược lại không đúng.
Các tính chất bổ sung
- Avalanche Effect: 1 bit input change → ~50% output bits change.
- Pseudorandomness: Output không phân biệt được với random (dùng cho PRF, KDF).
- Efficiency: Tính nhanh trên phần cứng/phần mềm.
- Fixed output length: Dễ lưu trữ, so sánh, truyền tải.
Cấu trúc phổ biến
| Construction | Đại diện | Đặc điểm |
|---|---|---|
| Merkle-Damgård | MD5, SHA-1, SHA-2, RIPEMD, BLAKE2 | Iterated compression function f(state, block). Padding + length encoding. Dễ length extension attack (trừ BLAKE2, truncated SHA-2). |
| Sponge (Keccak) | SHA-3, SHAKE, KangarooTwelve | State = rate (r) + capacity (c). Absorb (XOR r) → Permute f → Squeeze (output r). Chống length extension tự nhiên. XOF (variable output). |
| Tree / Parallel Hash | BLAKE3, ParallelHash | Chia block thành cây, song song hóa, SIMD. Cực nhanh trên multi-core. |
| ARX-based | BLAKE2/3, SipHash, Chaskey | Chỉ ADD/ROTATE/XOR. Constant-time tự nhiên, không table lookup. |
Thuật toán tiêu chuẩn 2024
- SHA-256 / SHA-512 (FIPS 180-4): Mặc định, hardware accel (Intel SHA, ARMv8), an toàn, phổ biến.
- SHA-3 / SHAKE (FIPS 202): Dự phòng, đa dạng hóa, XOF, domain separation dễ dàng.
- BLAKE3: Nhanh nhất (1-2 cpb), song song, XOF, keyed mode, derive key. Khuyên dùng cho high-performance.
- BLAKE2b/s: Nhanh, keyed (MAC), salt, personalization. Thay thế SHA-1/MD5 legacy.
Ứng dụng cốt lõi
- Chữ ký số: Sign(SK, H(M)). Cần collision resistance.
- MAC (HMAC, KMAC): Keyed hash cho integrity + authenticity.
- KDF (HKDF, PBKDF2, Argon2): Dẫn xuất khóa từ secret/password.
- Blockchain / Merkle Tree: Bitcoin SHA-256d, Ethereum Keccak-256.
- Certificate / PKI: Cert fingerprint, CRL, OCSP hash.
- Password Hashing: Argon2id(H(salt||pwd)) — KDF chậm, không phải hash nhanh.
- Commitment / VRF / ZKP: Hash là building block.
Cấm dùng / Legacy
- MD5: Collision practical (2004), chosen-prefix (2008). Chỉ checksum non-security.
- SHA-1: Collision SHAttered (2017, 2⁶³.¹). HMAC-SHA1 chấp nhận được nhưng deprecated.
- RIPEMD-160: Chỉ Bitcoin legacy (Hash160).
Best Practice: Dùng thư viện chuẩn (OpenSSL, libsodium, BLAKE3, Go crypto, Rust ring). Không tự implement. Domain separation: H("context"||data) hoặc SHAKE256(context, data). Output length ≥ 256-bit cho collision resistance lâu dài.