Hash function là gì ? | Ứng dụng của hash function

    Hash function hay còn gọi là “hàm băm” là hàm nhận một input đầu vào, từ input đó tạo ra một giá trị output (hay còn gọi là “hash value” – “giá trị băm”) tương ứng. Giá trị đầu vào có thể có độ dài tuỳ ý nhưng giá trị băm thì luôn có độ dài cố định. Hash function là hàm mã hoá một chiều.

Một hash function tốt phải thỏa mãn các điều kiện sau

  • Tính toán nhanh
  • Ít xảy ra đụng độ, tức là khả năng để các gía trị input khác nhau cho ra cùng một giá trị băm là rất thấp
  • Không thể đảo ngược: Đảm bảo không có phương pháp khả thi để tính toán được dữ liệu vào nào đó để cho ra giá trị băm mong muốn

Hash function được ứng dụng chính vào một số công việc sau

  • Xây dựng cấu trúc dữ liệu để tối ưu việc tìm kiếm: Hashtable
  • Lưu và kiểm tra password
  • Kiểm tra tính toán vẹn của dữ liệu
  • Sinh mã OTP

Một số hash function phổ biến

  • MD5 (MD là viết tắt của Message Digest)
    Là hash function 128-bit (dùng 128 bit để lưu giá trị băm), giá trị băm được biểu diễn bằng chuỗi 32 ký tự mã 16 (32 hexadecimal characters). MD5 được sử dụng rộng rãi để kiểm tra tính toán vẹn khi truyền file. Ví dụ, file server cung cấp giá trị băm tính toán trước bằng MD5 cho mỗi file (gọi là mã checksum), người dùng sau khi download file xuống có thể dùng tool tính lại mã checksum của file đó và so sánh với mã checksum mà server cung cấp. Nếu 2 mã là giống nhau thì có nghĩa là file download xuống giống với file gốc, không bị chỉnh sửa, giả mạo hay attach virus. Tuy nhiên vào năm 2004, “đụng độ” trong thuật toán MD5 đã được phát hiện ra. Một nghiên cứu cho thấy chỉ mất vài tiếng đồng hồ sử dụng một mạng lưới gồm nhiều máy tính có thể cho ra được giá trị input để cho ra được gía trị băm mong muốn. Chính vì vậy MD5 bây giờ không còn được khuyến khích sử dụng đối với những hệ thống hoặc chức năng yêu cầu security cao.
  • Secure Hash Function (SHA): Họ SHA bao gồm 4 thuật toán hash khác nhau là SHA-0, SHA-1, SHA-2, and SHA-3.
    • SHA-0: Hash function 160-bit, được công bố bởi NIST (National Institute of Standards and Technology) vào năm 1993. Do có một vài nhược điểm nên nó không được dùng phổ biến
    • SHA-1: Hash function 160-bit, ra đời năm 1995, khắc phục một số nhược điểm của SHA-0. SHA-1 được sử dụng để xây dựng giao thức SSL (Secure Socket Layer). Vào năm 2005, một phương pháp đã được tìm thấy để phát hiện ra các va chạm của SHA-1 trong khoảng thời gian khả thi khiến khả năng sử dụng lâu dài của SHA-1 bị nghi ngờ.
    • SHA-2: Công bố lần đầu năm 2001, bao gồm một số biến thể là SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224 và SHA-512/256. Cho đến nay thì chưa thấy có báo cáo nào về phương pháp tạo ra đụng độ trong SHA-2. Mặc dù SHA-2 là họ hash function mạnh nhưng thiết kế của nó vẫn dựa trên SHA-1 nên NIST vẫn muốn có thiết kế của hash function mới cạnh tranh với SHA-2
    • SHA-3: Năm 2012, NIST chọn thuật toán Keccak là để xây dựng SHA-3. Thuật toán Keccak có performance (hiệu năng) và khả năng chống “đụng độ” rất tốt.
  • Một số hash function khác: CRC232, RIPEMD, Whirlpool

Có thể sử dụng online tool ở link sau để tính Hash value

Ví dụ một số giá trị băm của MD5 và SHA-256

  • MD5(“hello”) = 5D41402ABC4B2A76B9719D911017C592
  • MD5(“goodbye”) = 69FAAB6268350295550DE7D587BC323D
  • SHA-256(“hello”) = 2CF24DBA5FB0A30E26E83B2AC5B9E29E1B161E5C1FA7425E73043362938B9824
  • SHA-256(“goodbye”) = 82E35A63CEBA37E9646434C5DD412EA577147F1E4A41CCDE1614253187E3DBF9

Tham khảo

— Phạm Minh Tuấn (Shun) —