Hàm băm (Bản
thô)
Tổng quan
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 thuật toán có liên quan
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.
Các tính chất mật mã học
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 m1,
việc tìm một thông điệp m2 (khác m1)
sao cho hash(m1) = hash(m2) là
rất khó.
·
Collision-resistant: việc tìm 2 thông điệp khác nhau m1 và m2 sao
cho hash(m1) = hash(m2) 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ướch(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.
Ứng dụng của các hàm băm mật mã học
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.
Danh sách các hàm băm mật mã học[
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.
Thuật toán
|
Kích thước đầu ra (output size)
|
Kích thước trạng thái trong (Internal state
size)
|
Kích thước khối (Block size)
|
Độ dài (Length size)
|
Kích thước word (Word size)
|
Xung đột (Collision)
|
256/224/192/160/128
|
256
|
1024
|
64
|
32
|
Có
|
|
128
|
384
|
128
|
Không
|
8
|
khả năng lớn
|
|
128
|
128
|
512
|
64
|
32
|
Có
|
|
128
|
128
|
512
|
64
|
32
|
Có
|
|
256
|
8736
|
256
|
No
|
32
|
Có lỗi
|
|
128
|
128
|
512
|
64
|
32
|
Có
|
|
128/256
|
128/256
|
512
|
64
|
32
|
Không
|
|
160/320
|
160/320
|
512
|
64
|
32
|
Không
|
|
160
|
160
|
512
|
64
|
32
|
Không
|
|
160
|
160
|
512
|
64
|
32
|
Có lỗi
|
|
256/224
|
256
|
512
|
64
|
32
|
Không
|
|
512/384
|
512
|
1024
|
128
|
64
|
Không
|
|
192/160/128
|
192
|
512
|
64
|
64
|
Không
|
|
160/256
|
256/384
|
8
|
80/128
|
1
|
||
320/512
|
512/768
|
8
|
160/256
|
1
|
Không
|
|
512
|
512
|
512
|
256
|
8
|
Không
|
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)
·
Matyas-Meyer-Oseas
·
Davies-Meyer
·
Miyaguchi-Preneel
·
MDC-2
·
MDC-4
Không có nhận xét nào:
Đăng nhận xét