Hashing là hàm xác định (deterministic) ánh xạ đầu vào tùy ý độ dài thành đầu ra độ dài cố định (hash value / digest / fingerprint). Một chiều (one-way): Dễ tính H(M), khó tìm M từ H(M).
Quy trình chung (Merkle-Damgård construction — SHA-256, MD5, SHA-1, BLAKE2)
- Padding: Đệm thông điệp để độ dài ≡ block_size - length_field_size (mod block_size). Thêm bit 1, các bit 0, rồi ghi độ dài bản gốc (big-endian).
- Khởi tạo trạng thái (IV): Giá trị cố định chuẩn (SHA-256: 8 word 32-bit từ căn bậc 2 số nguyên tố đầu tiên).
- Xử lý từng khối (Compression function): Với mỗi block 512-bit (SHA-256):
- Mở rộng message schedule: 16 word → 64 word (SHA-256).
- 64 vòng: cập nhật 8 thanh ghi trạng thái (a..h) bằng các phép logic (Ch, Maj, Σ₀, Σ₁) + hằng số K[t] + message word W[t].
- Finalization: Cộng dồn trạng thái cuối vào IV → hash value.
Sponge Construction (SHA-3 / Keccak / BLAKE3)
- Absorb: XOR từng block rate (r-bit) vào state (r+c = 1600-bit cho Keccak), áp dụng permutation f (Keccak-f[1600] 24 vòng).
- Squeeze: Trích xuất output block r-bit, áp dụng f nếu cần thêm output.
- Ưu điểm: XOF (output tùy ý), chống length extension tự nhiên, domain separation dễ dàng.
Đặc tính bảo mật cốt lõi
| Tính chất | Định nghĩa | Độ an toàn lý thuyết (n-bit output) |
|---|---|---|
| Preimage Resistance | Cho h, khó tìm M: H(M)=h | 2ⁿ |
| Second Preimage Resistance | Cho M, khó tìm M'≠M: H(M')=H(M) | 2ⁿ |
| Collision Resistance | Khó tìm M₁≠M₂: H(M₁)=H(M₂) | 2ⁿ/² (Birthday bound) |
Ứng dụng bảo mật chính
- Lưu trữ mật khẩu: Hash = H(salt || password) — nhưng phải dùng KDF chậm (Argon2id, bcrypt), không dùng SHA/MD5 trực tiếp.
- Chữ ký số: Ký hash(H(M)) thay vì ký M (hiệu quả, an toàn).
- Xác thực toàn vẹn tệp: So sánh hash tải về với hash gốc (checksum).
- MAC (HMAC): HMAC(K, M) = H((K⊕opad) || H((K⊕ipad) || M)).
- KDF (HKDF): HKDF-Extract(salt, IKM) → PRK; HKDF-Expand(PRK, info, L) → OKM.
- Blockchain / Merkle Tree: Hash liên kết block, Merkle root.
- Commitment Scheme: Commit = H(r || m), reveal = (r, m).
Collision Attack & Birthday Paradox
Với n-bit output, cần ~2ⁿ/² thử ngẫu nhiên để tìm collision (birthday paradox). Do đó:
- MD5 (128-bit): 2⁶⁴ → đã phá thực tế (2004).
- SHA-1 (160-bit): 2⁸⁰ → đã phá thực tế (2017, 2⁶³.¹).
- SHA-256 (256-bit): 2¹²⁸ → an toàn cho thấy thấy.
- SHA-512 (512-bit): 2²⁵⁶ → an toàn lâu dài.
Lưu ý triển khai
- Dùng thư viện chuẩn (OpenSSL, libsodium, BLAKE3, Go crypto, Rust ring).
- Không tự implement hash cho production.
- Domain separation: H("context" || data) hoặc SHAKE256(context, data).
- Kiểm tra độ dài output phù hợp yêu cầu (128-bit minimum cho collision resistance).