Hàm Băm Mật Mã

Một hàm băm nhận đầu vào là một xâu ký tự dài (hay thông điệp) có độ dài tùy ý và tạo ra kết quả là một xâu ký tự có độ dài cố định, đôi khi được gọi là tóm tắt thông điệp (message digest) hoặc chữ ký số (digital fingerprint).

Trong nhiều chuẩn và ứng dụng, hai hàm băm thông dụng nhất là MD5 và SHA-1. Năm 2005, người ta đã tìm ra lỗi bảo mật của cả hai thuật toán trên.

Nói rộng, một hàm băm mật mã học phải hoạt động càng giống với một hàm ngẫu nhiên càng tốt, trong khi vẫn có tính chất đơn định và tính toán có hiệu quả.

Một hàm băm mật mã học được coi là không an toàn nếu một trong các việc sau là khả thi về mặt tính toán:

• cho một tóm tắt (digest), tìm một thông điệp (chưa biết) khớp với tóm tắt đó
• tìm các "xung đột băm" (hash collision), trong đó hai thông điệp khác nhau có tóm tắt trùng nhau.

Nếu có thể thực hiện một trong hai việc trên, một người có thể tấn công bằng cách dùng các cách trên để thay một thông điệp không được xác nhận (unauthorized message) vào chỗ của một thông điệp được xác nhận.

Về lý tưởng, việc tìm hai thông điệp có tóm tắt rất giống nhau cũng nên không khả thi; người ta không muốn một kẻ tấn công có thể tìm hiểu được điều gì đó hữu ích về một thông điệp nếu biết tóm tắt.

Các giá trị tổng kiểm và mã kiểm soát lỗi (cyclic redundancy check - CRC) rất khác với các hàm băm mật mã học, và được dùng cho các ứng dụng khác. Nếu dùng cho bảo mật, các loại kiểm tra đó rất dễ bị tấn công.

Một mã xác thực thông điệp (message authentication code - MAC) lấy một thông điệp và một khóa bí mật, và tạo ra một "thẻ MAC" (MAC tag), sao cho kẻ tấn công khó có thể tạo một cặp (thông điệp, thẻ) hiệu lực khớp với thẻ được biết; ngoài các ứng dụng khác, loại mã hóa này dùng để ngăn chặn những kẻ tấn công tạo các thông điệp giả. Tuy đôi khi được gọi là "hàm băm có khóa" (keyed hash function), MAC phục vụ một mục đích rất khác và có các tính chất rất khác với một hàm băm mật mã học; ví dụ, nếu một người biết khóa MAC có thể dễ dàng tạo 2 thông điệp có cùng MAC, thì đây không phải một lỗi. Có thể dùng các hàm băm để tạo các hàm MAC; ví dụ, xem HMAC.

Không có một định nghĩa hình thức bao trùm tất cả các tính chất mong muốn của một hàm băm mật mã học. Các tính chất dưới đây được coi là yêu cầu tiên quyết:

• Preimage resistant (Về một tính chất có liên quan nhưng hơi khác, xem bài hàm một chiều): cho trước h việc tìm m sao cho h = hash(m) là rất khó.
• Second preimage resistant: cho thông điệp m₁, việc tìm một thông điệp m₂ (khác m₁) sao cho hash(m₁) = hash(m₂) là rất khó.
• Collision-resistant: việc tìm 2 thông điệp khác nhau m₁ và m₂ sao cho hash(m₁) = hash(m₂) là rất khó. Do khả năng tấn công ngày sinh nhật (birthday attack), điều đó có nghĩa là kết quả của hàm băm phải dài ít nhất là gấp đôi so với yêu cầu của preimage-resistance.

Một hàm băm thỏa mãn các tiêu chí trên có thể vẫn có các tính chất không mong muốn. Ví dụ, các hàm băm phổ biến nhất dễ bị tổn thương bởi các tấn công length-extension: Cho trước h(m) và len(m) nhưng không cho trước m, bằng cách chọn m' thích hợp, một kẻ tấn công có thể tính h (m || m'), trong đó || ký hiệu phép nối xâu (concatenation). Tính chất này có thể được dùng để phá các phương pháp xác thực đơn giản dựa vào các hàm băm. Việc xây dựng HMAC đã tránh được các vấn đề này.

Nhiều người có một khái niệm sai rằng "tính chất một chiều" của một hàm băm mật mã hóa có nghĩa rằng việc xử lý trạng thái băm là không thể lần ngược được, và rằng nó mâu thuẫn với các nguyên tắc dùng để xây dựng các mã hóa khối (block cipher). Thực ra, "tính chất không thể đảo ngược" đó có nghĩa rằng có các xung đột địa phương tạo điều kiện cho các tấn công. Để có tính chất an toàn mật mã học, hàm băm phải là một quá trình xử lý hoán vị trạng thái của nó theo kiểu song ánh (bijective) Tính chất không thể đảo ngược đó thực ra có nghĩa rằng: không thể tìm khóa dùng cho việc mã hóa một khối A thành một khối B bằng một phương pháp nào nhanh hơn là vét cạn.

Một ứng dụng điển hình của một hàm băm mật mã học như sau: Alice đưa cho Bob một câu đố khó và tuyên bố rằng cô ấy đã giải được rồi. Bob muốn tự giải, nhưng cũng muốn chắc chắn là Alice đúng là đã giải được. Do đó, Alice viết đáp án, gắn thêm một nonce ngẫu nhiên, tính giá trị băm của nó, và đưa kết quả băm cho Bob (trong khi vẫn giữ bí mật đáp án và nonce). Bằng cách này, khi Bob tự giải xong, Alice có thể chứng minh rằng cô đã có đáp án từ trước bằng cách đưa nonce cho Bob.

Trong thực tiễn, Alice và Bob thường là các chương trình máy tính, và bí mật thường là cái gì đó không dễ lừa bằng một lời giải cho câu đó. Ứng dụng trên được gọi là một hệ thống tin cậy (commitment scheme). Một ứng dụng quan trọng khác của các hàm băm bảo mật là sự kiểm tra tính toàn vẹn của thông điệp. Ví dụ, việc xác định xem một file hay một thông điệp có bị sửa đổi hay không có thể thực hiện bằng cách so sánh tóm tắt được tính trước và sau khi gửi (hoặc một sự kiện bất kỳ nào đó). Còn có thể dùng tóm tắt thông điệp làm một phương tiện đáng tin cậy cho việc nhận dạng file. Một ứng dụng có liên quan là kiểm tra mật khẩu. Mật khẩu thường không được lưu dưới dạng văn bản rõ (clear text), mà ở dạng tóm tắt. Để xác thực một người dùng, mật khẩu do người đó nhập vào được băm và so sánh với kết quả băm được lưu trữ.

Do các lý do cả về bảo mật và hiệu năng chương trình, đa số các thuật toán chữ ký số nói rằng chỉ có tóm lược của thông điệp, chứ không phải toàn văn thông điệp, được "ký". Các hàm băm còn có thể được dùng để tạo các bit giả ngẫu nhiên (pseudorandom).

SHA-1, MD5, và RIPEMD-160 nằm trong số các thuật toán tóm tắt thông điệp được dùng rộng rãi nhất của năm 2005. Tháng 8 năm 2004, các nhà nghiên cứu đã tìm được các điểm yếu của một loạt hàm băm, trong đó có MD5, SHA-0 và RIPEMD. Tháng 2 năm 2005, người ta ghi nhận một tấn công đối với SHA-1. Tháng 8 năm 2005, người ta lại ghi nhận một tấn công khác đối với SHA-1.

Các hàm băm được dùng để nhận dạng các file trong các mạng chia sẻ tệp đồng đẳng. Ví dụ, trong một ed2k link, một biến thể của MD4 được kết hợp với kích thước file để cung cấp thông tin cho việc xác định nguồn file, tải xuống và kiểm tra nội dung.

Một số thuật toán trong danh sách dưới đây được biết là không an toàn; xem các bài cho từng thuật toán cụ thể để biết thêm thông tin về tình trạng thuật toán. Xem thêm các hàm băm khác ở cuối trang.

Các hàm băm SHA là một loạt các hàm do NSA phát triển: SHA, còn được biết với tên SHA-0, SHA-1 và 4 biến thể của một hàm có tên SHA-2.

Lưu ý: Ở đây, trạng thái trong (internal state) có nghĩa là "tổng băm trong" (internal hash sum) sau mỗi lần nén một khối dữ liệu. Hầu hết các hàm băm còn dùng một số biến bổ sung khác, chẳng hạn như độ dài của dữ liệu đã được nén cho đến thời điểm hiện tại, do điều này cần cho việc chèn độ dài (length padding) ở cuối. Xem chi tiết tại Hàm băm Merkle-Damgård.

Các phương pháp tính băm cho các mã hóa khối (block cipher)

Xem chi tiết tại hàm băm dựa vào mã hóa khối.

• Matyas-Meyer-Oseas
• Davies-Meyer
• Miyaguchi-Preneel
• MDC-2
• MDC-4

• Hiệu ứng thác (Avalanche effect)
• MD5CRK
• Message authentication code
• Keyed-hash message authentication code
• CRHF Collision Resistant Hash Functions.
• UOWHF Universal One Way Hash Functions - Hàm băm một chiều tổng quát.
• CRYPTREC và NESSIE (các dự án đánh giá các hàm băm)
• danh sách băm (Hash list)
• cây băm (Hash tree)
• PGP word list

Tiếng Anh:

• The Hash function lounge Lưu trữ 2005-03-02 tại Wayback Machine — danh sách các hàm băm và các tấn công đã được biết
• Danh sách hàm băm của Helger Lipmaa Lưu trữ 2007-03-21 tại Wayback Machine
• Các sơ đồ giải thích các hàm băm mật mã học
• An Illustrated Guide to Cryptographic Hashes của Steve Friedl
• Cryptanalysis of MD5 and SHA: Time for a New Standard của Bruce Schneier
• Hash collision Q&A
• Attacking hash functions by poisoned messages (construction of multiple sensible Postscript messages with the same hash function) Lưu trữ 2006-08-08 tại Wayback Machine
• What is a hash function? Lưu trữ 2006-12-06 tại Wayback Machine phòng thí nghiệm RSA
• Password Hashing in PHPLưu trữ 2012-11-29 tại Wayback Machine của James McGlinn tại PHP Security Consortium