Bài trước giới thiệu ba công cụ của mật mã học. Bài này đi vào công cụ đầu tiên và được dùng nhiều nhất: hàm băm. Git đặt tên mỗi commit bằng nó. Trình duyệt kiểm tra chứng chỉ bằng nó. Trang này dùng nó để đặt ?v=... sau tên file CSS, để biết bài viết tiếng Việt đã đổi so với bản dịch chưa (source_hash), và để ký phiên đăng nhập (HMAC).
Lộ trình: hàm băm là gì và ba tính chất của nó, hiệu ứng thác lũ (đo), lịch sử MD5, SHA-1 và các hàm hiện nay, tốc độ (đo), va chạm và nghịch lý ngày sinh (đo), tấn công nối dài và HMAC (làm thật), so sánh an toàn trước tấn công đo thời gian (đo), rồi những chỗ băm xuất hiện trong thực tế. Đo bằng Python 3.12 trên máy thật.
Hàm băm là gì
Hàm băm mật mã nhận dữ liệu dài bao nhiêu cũng được và trả về một chuỗi độ dài cố định. SHA-256 trả về 256 bit (32 byte, 64 ký tự hex):
sha256("viet.sarl") = b1bd86a146ce47b7af5cf5d595a29d2a8b35182c9da0d1350522a523ff40c80b
sha256("viet.sarm") = 0c0dee002f3a4b9679b41a4fd0284aa3b21c102a6ded28728d9433cc2f904387
Đổi một chữ cái cuối, kết quả khác hoàn toàn. Một hàm băm mật mã (khác hàm băm của dict trong Python) phải có ba tính chất:
| Tính chất | Nghĩa là | Nếu mất thì |
|---|---|---|
| Một chiều (preimage resistance) | Cho kết quả băm, không tìm được đầu vào | Lộ mật khẩu từ bản băm |
| Khó tìm đầu vào thứ hai (second preimage) | Cho một file, không tạo được file khác cùng kết quả | Thay file tải về bằng file độc mà kết quả kiểm tra vẫn khớp |
| Khó tìm va chạm (collision resistance) | Không tìm được bất kỳ hai đầu vào nào cùng kết quả | Giả chứng chỉ, giả chữ ký |
Lưu ý chữ "khó": va chạm luôn tồn tại (vô số đầu vào dồn vào 2²⁵⁶ kết quả), chỉ là không ai tìm ra được trong thời gian hợp lý.
Hiệu ứng thác lũ
Một hàm băm tốt phải khiến mỗi bit đầu vào ảnh hưởng tới mọi bit đầu ra, như thể đầu ra là ngẫu nhiên. Đo: lấy 2.000 thông điệp ngẫu nhiên 32 byte, lật 1 bit bất kỳ, đếm số bit khác nhau giữa hai bản băm SHA-256:
avalanche mean bits changed /256: 127.919 min 99 max 153
Trung bình 127,9 trên 256 bit, đúng một nửa, như tung đồng xu cho từng bit. Không có cách nào nhìn bản băm mà đoán "đầu vào gần giống cái kia". Đó là lý do bản băm dùng được làm dấu vân tay: hai file khác nhau dù chỉ một bit sẽ có dấu vân tay khác nhau hoàn toàn.
MD5, SHA-1 và những hàm còn dùng được
| Hàm | Năm | Đầu ra | Tình trạng |
|---|---|---|---|
| MD5 | 1992 | 128 bit | Hỏng. Từ năm 2006, tạo một va chạm trên laptop chỉ mất chưa tới một phút |
| SHA-1 | 1995 | 160 bit | Hỏng. Va chạm thật đầu tiên năm 2017 (SHAttered: hai file PDF khác nhau cùng bản băm) |
| SHA-256, SHA-512 (họ SHA-2) | 2001 | 256 / 512 bit | An toàn, dùng nhiều nhất |
| SHA-3 | 2015 | 224–512 bit | An toàn, cấu trúc khác hẳn SHA-2 (phòng khi SHA-2 có vấn đề) |
| BLAKE2, BLAKE3 | 2012 / 2020 | tùy chọn | An toàn, nhanh trong phần mềm |
Va chạm MD5 đã được dùng ngoài đời: năm 2008, các nhà nghiên cứu tạo được một chứng chỉ CA giả nhờ va chạm MD5, và mã độc Flame (2012) giả chữ ký cập nhật của Windows cũng bằng cách đó. Git ban đầu dùng SHA-1, và sau SHAttered thì chuyển sang bản SHA-1 có phát hiện va chạm, đồng thời làm định dạng repo dùng SHA-256.
MD5 vẫn ổn cho việc không có kẻ tấn công, ví dụ kiểm tra file tải về có bị hỏng do đường truyền hay không. Nhưng không có lý do gì chọn nó cho dự án mới, nhất là khi nó còn chậm hơn SHA-256.
Tốc độ
Băm 64 MB dữ liệu ngẫu nhiên, lấy lần nhanh nhất trong ba lần:
| Hàm | MB/giây |
|---|---|
| MD5 | 957 |
| SHA-1 | 3.348 |
| SHA-256 | 3.350 |
| SHA-512 | 1.912 |
| SHA3-256 | 1.109 |
| BLAKE2b | 1.653 |
SHA-256 nhanh nhất ở đây, nhanh gấp 3,5 lần MD5. Lý do không nằm ở thuật toán: nhiều CPU hiện nay có lệnh riêng cho SHA-256, giống như có lệnh riêng cho AES. Trên CPU không có lệnh đó, thứ tự sẽ khác: BLAKE2b và SHA-512 thường vượt SHA-256. Bài học từ bài CPU vẫn đúng: đo trên máy mình chạy, đừng đoán.
Ba GB mỗi giây là quá nhanh cho một việc: lưu mật khẩu. Kẻ tấn công cũng băm nhanh như vậy. Đó là chủ đề của bài 3.
Va chạm và nghịch lý ngày sinh
Trong một lớp 23 người, xác suất có hai người trùng ngày sinh là hơn 50%, dù năm có 365 ngày. Lý do: ta không cần ai trùng với một ngày cho trước, chỉ cần hai người bất kỳ trùng nhau, và số cặp tăng theo bình phương số người.
Với hàm băm cũng vậy: hàm băm có đầu ra n bit cần khoảng 2^(n/2) lần thử để gặp va chạm, không phải 2^n. Đo bằng cách cắt SHA-256 còn 32 bit, rồi băm dữ liệu ngẫu nhiên cho tới khi gặp hai kết quả trùng:
32-bit collision after 32539 tries
32-bit collision after 102205 tries
32-bit collision after 132589 tries
Lý thuyết dự đoán khoảng √(π/2 · 2³²) ≈ 82.000 lần thử. Ba lần đo nằm quanh con số đó, chứ không gần 4,3 tỷ (2³²). Cả thí nghiệm mất chưa tới một giây.
Áp vào hàm thật: MD5 128 bit chỉ có "sức chống va chạm" 64 bit ngay cả khi không bị phá, đã yếu từ đầu. SHA-256 cho 128 bit, tức 2¹²⁸ lần thử, ngoài tầm mọi máy tính. Đây cũng là lý do một mã băm rút gọn (ví dụ 12 ký tự hex = 48 bit như source_hash của trang này) chỉ dùng để phát hiện thay đổi, không dùng để chống kẻ cố ý tạo va chạm: 2²⁴ ≈ 16 triệu lần thử là ra.
Tấn công nối dài, và HMAC
Giả sử một máy chủ muốn "ký" một đường link để người dùng không sửa được tham số. Cách nghĩ tự nhiên: giữ một khóa bí mật, tính sha256(khóa + dữ liệu), gắn vào link. Kẻ tấn công không biết khóa thì không tính được bản băm đúng... phải không?
Không. SHA-256 (và MD5, SHA-1, SHA-512) xử lý dữ liệu theo từng khối 64 byte, và bản băm cuối cùng chính là trạng thái bên trong sau khối cuối. Có bản băm trong tay nghĩa là có trạng thái, và kẻ tấn công có thể băm tiếp từ đó, thêm dữ liệu vào cuối mà không cần biết khóa. Chỉ cần biết độ dài của khóa, mà thường đoán được bằng vài lần thử.
Thí nghiệm: viết lại SHA-256 bằng Python thuần (~30 dòng) để có thể bắt đầu từ một trạng thái cho trước. Máy chủ có khóa ngẫu nhiên 16 byte và ký user=an&amount=100:
mac = hashlib.sha256(key + b"user=an&amount=100").hexdigest() # máy chủ công bố
state = unpack(">8I", bytes.fromhex(mac)) # kẻ tấn công: bản băm = trạng thái
glue = padding(len(key) + len(msg)) # phần đệm máy chủ đã tự thêm vào
forged_msg = msg + glue + b"&amount=1000000"
forged = sha256_continue(state, b"&amount=1000000", ...)
forged message: b'user=an&amount=100\x80\x00\x00...\x00\x01\x10&amount=1000000'
server accepts: True
HMAC of forged == attacker guess: False
Máy chủ chấp nhận. Thông điệp giả có một đoạn byte rác ở giữa (phần đệm), nhưng nhiều trình phân tích tham số bỏ qua nó, và tham số amount cuối cùng thắng. Lỗ hổng kiểu này từng có thật trong API của Flickr năm 2009.
Cách sửa đúng là HMAC (hash-based message authentication code): một cấu trúc băm hai lần, H((K ⊕ opad) ‖ H((K ⊕ ipad) ‖ m)), được chứng minh là an toàn ngay cả khi hàm băm bên dưới có tính chất nối dài. Dòng cuối của thí nghiệm cho thấy cùng mánh đó áp vào HMAC thì thất bại. Trong Python:
import hmac, hashlib
tag = hmac.new(key, message, hashlib.sha256).digest()
SHA-3 và BLAKE2/3 không bị tấn công nối dài nhờ thiết kế khác, nhưng quy tắc thực tế vẫn đơn giản: cần "chữ ký" bằng khóa chung thì dùng HMAC, đừng tự ghép khóa với dữ liệu. Token đăng nhập HS256 của trang này chính là HMAC-SHA256.
So sánh chữ ký: đừng dùng ==
Khi máy chủ nhận một HMAC từ người dùng và so với HMAC tự tính, phép so sánh cũng là một chỗ rò rỉ. Toán tử == trên bytes dừng ngay ở byte khác đầu tiên. Đo trên hai chuỗi 1 MB, một chuỗi khác ở byte đầu và một chuỗi khác ở byte cuối:
== first-byte diff 0.02 us, last-byte diff 18.55 us | compare_digest 276.08 / 276.24 us
== mất 0,02 µs khi sai ở byte đầu và 18,55 µs khi sai ở byte cuối, chênh gần 1.000 lần. Kẻ tấn công đo thời gian phản hồi có thể dò từng byte một: thử 256 giá trị cho byte đầu, cái nào chậm hơn một chút là đúng, rồi sang byte tiếp. Với chuỗi ngắn như một HMAC 32 byte, chênh lệch chỉ vài nano giây và bị nhiễu mạng che lấp phần lớn, nhưng các nghiên cứu đã đo được chênh lệch cỡ đó qua mạng LAN khi lặp đủ nhiều lần.
hmac.compare_digest luôn đi hết chuỗi, sai ở đâu cũng mất cùng thời gian (276 µs cả hai, chậm hơn vì nó cố ý không tối ưu, nhưng với 32 byte thì không đáng kể). Trang này dùng nó khi so state của OAuth:
if not (code and state and saved and secrets.compare_digest(state, saved.state)):
Băm ở đâu trong thực tế
| Nơi | Băm gì | Vì sao |
|---|---|---|
| Git | Nội dung mỗi file, cây thư mục, commit | Định danh theo nội dung; sửa một byte lịch sử là đổi mọi mã commit sau đó |
| File tĩnh của trang này | ?v= + mã băm nội dung CSS/JS |
Đổi file là đổi URL, nên cache được lâu mà không sợ cũ |
source_hash của blog |
Bản tiếng Việt | Biết bản dịch đã cũ chưa |
| Tải phần mềm | SHA-256 của file cài đặt | Phát hiện file bị hỏng hoặc bị thay (khi mã băm lấy từ kênh tin cậy) |
| Chứng chỉ TLS, chữ ký số | Băm dữ liệu rồi ký bản băm | Ký 32 byte thay vì ký cả file |
| Mật khẩu | Băm chậm có salt | Bài 3 |
| JWT HS256, cookie có ký, webhook | HMAC | Chống sửa nội dung |
| Blockchain | Băm khối trước, cây Merkle, proof of work | Mỗi khối "khóa" toàn bộ lịch sử trước nó |
Một giới hạn hay bị quên ở dòng "tải phần mềm": nếu kẻ tấn công thay được file trên trang tải về, họ cũng thay được mã băm in ngay bên cạnh. Mã băm chỉ chứng minh "file này khớp với mã băm kia". Muốn chứng minh "file này do đúng nhà phát hành tạo ra" thì cần chữ ký số (bài 4).
Tóm lại
- Hàm băm mật mã: đầu ra cố định, một chiều, khó tìm va chạm, và đổi 1 bit đầu vào làm đổi trung bình 127,9/256 bit đầu ra.
- MD5 và SHA-1 đã bị phá về va chạm. Dùng SHA-256, SHA-3 hoặc BLAKE2/3.
- Đo được: SHA-256 3.350 MB/s (nhờ lệnh riêng trong CPU), nhanh hơn MD5. Nhanh là tốt cho kiểm tra file, là xấu cho mật khẩu.
- Nghịch lý ngày sinh: n bit chỉ chống va chạm được 2^(n/2). Bản băm 32 bit va chạm sau 33–133 nghìn lần thử.
sha256(khóa + dữ liệu)giả được bằng tấn công nối dài (làm thật trong bài). Dùng HMAC.- So sánh chữ ký bằng
hmac.compare_digest, không bằng==(chênh gần 1.000 lần giữa sai byte đầu và sai byte cuối).
Bài tiếp theo dùng hàm băm cho việc nhạy cảm nhất: lưu mật khẩu. Vì sao SHA-256 nhanh lại là thảm họa ở đó, salt chặn được gì, Argon2id mà trang này dùng chậm cố ý tới mức nào, và một kẻ có bản sao database mất bao lâu để dò mật khẩu 8 ký tự.