Giải thích hàm băm
Khi bạn tải phần mềm về và so sánh tổng kiểm tra, đăng nhập bằng mật khẩu, ký một tài liệu hay thêm một khối vào Bitcoin, có một hàm băm đang làm việc. Nó biến một lượng dữ liệu bất kỳ thành một dấu vân tay ngắn có kích thước cố định, gọi là giá trị băm (digest), theo cách không thể đảo ngược hay làm giả. Ý tưởng thì đơn giản, nhưng yêu cầu đối với một hàm băm tốt rất khắt khe, và hai trong số những hàm được dùng rộng rãi nhất, MD5 và SHA-1, đã không vượt qua được.
Dấu vân tay cho dữ liệu
Hàm băm nhận một đầu vào có độ dài bất kỳ và trả về một giá trị băm có độ dài cố định: 256 bit với SHA-256, được viết thành 64 chữ số thập lục phân. Cùng một đầu vào luôn cho cùng một giá trị băm, nên giá trị băm có thể đại diện cho dữ liệu. Nếu hai tệp có cùng giá trị băm SHA-256, bạn có thể chắc rằng chúng giống hệt nhau, và nếu một bit của tệp tải về bị hỏng, giá trị băm của nó sẽ không còn khớp với giá trị mà nhà phát hành công bố. Vì số đầu vào khả dĩ nhiều hơn rất nhiều so với số giá trị băm, nhiều đầu vào buộc phải có chung mỗi giá trị băm; một hàm băm tốt chỉ đơn giản là khiến việc tìm ra bất kỳ đầu vào nào trong số đó trở nên bất khả thi.
Ba lời hứa
Một hàm băm mật mã đưa ra ba lời hứa. Kháng tiền ảnh: cho một giá trị băm, bạn không thể tìm được đầu vào tạo ra nó. Kháng tiền ảnh thứ hai: cho một đầu vào, bạn không thể tìm được đầu vào khác có cùng giá trị băm. Kháng va chạm: bạn không thể tìm được bất kỳ hai đầu vào nào có cùng giá trị băm. Với một hàm băm lý tưởng n bit, cách tấn công tốt nhất là đoán: khoảng 2ⁿ lần thử để tìm tiền ảnh và khoảng 2ⁿᐟ² để tìm va chạm. Một hàm băm được gọi là đã bị phá khi ai đó tìm ra cách nhanh hơn thế rất nhiều.
Hiệu ứng tuyết lở
Đổi một bit đầu vào thì mỗi bit của giá trị băm phải bị lật với xác suất một nửa, độc lập với các bit khác. Khi đó một thay đổi nhỏ trong thông điệp cho ra giá trị băm trông hoàn toàn không liên quan, và giá trị băm không để lộ gì về phần nào của đầu vào đã thay đổi. SHA-256 đạt được điều này bằng cách chạy 64 vòng xoay, cộng và kết hợp tám từ 32 bit của nó, để chỉ sau vài vòng mọi bit đầu vào đã ảnh hưởng đến mọi từ. Ngược lại, một phép cộng đơn giản các byte chỉ thay đổi đúng bằng lượng mà đầu vào thay đổi, nên nó để lộ tất cả.
Bên trong SHA-256
Trước tiên, SHA-256 đệm thông điệp: nó thêm một bit 1, các bit 0 và độ dài của thông điệp, cho đến khi tổng độ dài là bội của 512 bit. Sau đó nó xử lý thông điệp theo từng khối 512 bit. Mỗi khối được kéo dãn thành 64 từ, rồi được trộn vào một trạng thái gồm tám từ 32 bit, xuất phát từ các giá trị cố định lấy từ căn bậc hai của tám số nguyên tố đầu tiên. Trạng thái sau khối cuối cùng chính là giá trị băm. Thiết kế dạng chuỗi này, mang tên Ralph Merkle và Ivan Damgård, cũng được MD5, SHA-1 và SHA-512 sử dụng; SHA-3 mới hơn, được chuẩn hóa năm 2015, dùng một cấu trúc khác gọi là cấu trúc bọt biển (sponge).
Tấn công ngày sinh
Trong một nhóm 23 người, xác suất có hai người trùng ngày sinh là hơn một nửa một chút, dù một năm có 365 ngày, vì điều quan trọng là số cặp, vốn tăng theo bình phương quy mô nhóm. Va chạm trong hàm băm tuân theo cùng quy luật đó. Trong số 2ᵏ giá trị băm khả dĩ, một va chạm được dự kiến xuất hiện sau khoảng √(π/2 · 2ᵏ) đầu vào ngẫu nhiên. Với 32 bit, con số đó là khoảng 82.000 đầu vào, xong trong chớp mắt; với 128 bit là khoảng 2⁶⁴, nằm trong tầm với của những nỗ lực tính toán lớn. Đó là lý do 128 bit của MD5 chưa bao giờ là dư dả, và vì sao SHA-256 tăng gấp đôi độ dài để đạt mức an toàn 128 bit.
MD5 và SHA-1: đã bị phá
Ron Rivest thiết kế MD5 năm 1991, còn NSA thiết kế SHA-1, được công bố năm 1995. Năm 2004, Xiaoyun Wang và các đồng nghiệp đã chỉ ra cách tạo va chạm MD5 nhanh chóng, và năm 2008 các nhà nghiên cứu dùng chúng để giả mạo một chứng chỉ được các trình duyệt web tin cậy. Phần mềm gián điệp Flame năm 2012 dùng một va chạm MD5 để giả làm bản cập nhật của Microsoft. SHA-1 sụp đổ năm 2017, khi Google và CWI Amsterdam công bố hai tệp PDF khác nhau có cùng giá trị băm SHA-1, sau khoảng 2⁶³ phép tính. Cả hai vẫn ổn để phát hiện lỗi vô tình, nhưng không dùng được cho bất cứ thứ gì mà kẻ tấn công có thể nhắm tới.
Hàm băm được dùng ở đâu
Chữ ký số ký lên giá trị băm của tài liệu chứ không phải chính tài liệu. Git đặt tên cho mọi tệp và commit bằng giá trị băm của chúng, còn thợ đào Bitcoin tìm những tiêu đề khối có giá trị băm SHA-256 kép bắt đầu bằng một dãy dài các số 0. Các trang web không bao giờ nên lưu mật khẩu, chỉ lưu giá trị băm của chúng; nhưng vì người ta hay chọn mật khẩu ngắn, giá trị băm đó phải chậm và có thêm muối, bằng các phương pháp như bcrypt, scrypt hay Argon2, để việc đoán trở nên tốn kém. Các tổng kiểm tra như CRC-32, dùng trong tệp ZIP, ảnh PNG và Ethernet, cũng là hàm băm, được tạo ra để bắt nhiễu chứ không phải kẻ tấn công.
Tự khám phá
Mở sân chơi hàm băm để băm văn bản của riêng bạn bằng SHA-256, SHA-512, SHA-1, MD5, CRC-32 và một tổng byte đồ chơi. Đổi một ký tự và đếm số bit bị lật, chạy kiểm tra tuyết lở qua một nghìn lần đổi một bit để thấy đường cong hình chuông quanh một nửa giá trị băm, và tìm những va chạm thật trên 8 đến 32 bit đầu của giá trị băm để xem tấn công ngày sinh hoạt động.
Câu hỏi thường gặp
Băm có giống mã hóa không?
Không. Mã hóa được tạo ra để người giữ khóa có thể giải ngược lại; băm không có khóa và không ai có thể đảo ngược được. Mã hóa giữ bí mật một thông điệp, còn hàm băm chỉ cho một dấu vân tay giúp bạn kiểm tra một thông điệp bạn đã có.
Mất bao lâu để tìm một va chạm SHA-256?
Với tấn công ngày sinh, cần khoảng 2¹²⁸ phép băm, một con số có 39 chữ số. Ngay cả khi mọi máy tính trên Trái Đất không làm gì khác, việc đó vẫn mất thời gian lâu hơn tuổi của vũ trụ rất nhiều. Chưa có lối tắt nào được biết đến.
Vì sao hai lần băm cùng một văn bản không bao giờ khác nhau?
Hàm băm có tính tất định: nó không có yếu tố ngẫu nhiên và không có khóa, nên cùng các byte luôn cho cùng một giá trị băm. Những khác biệt nhỏ mà bạn không nhìn thấy, như một dấu cách ở cuối, kiểu xuống dòng khác hoặc một dạng Unicode khác của chữ có dấu, thì lại cho ra giá trị băm khác.
Muối (salt) là gì?
Một giá trị ngẫu nhiên được lưu cạnh giá trị băm của mật khẩu và được trộn vào đó. Nhờ vậy hai người dùng có cùng mật khẩu sẽ có giá trị băm khác nhau, và kẻ tấn công không thể dùng một bảng mật khẩu phổ biến tính sẵn cho mọi tài khoản.
Sẵn sàng thử chưa?
Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.
Mở sân chơi hàm băm