Hàm băm (hash function) là gì?

Hàm băm (hash function) là gì?

Rate this post

Ở các phần trước ta đã xem xét việc xác thực thông điệp có sử dụng hàm băm. Vậy hàm băm là gì? Chúng có những đặc tính hay yêu cầu gì trong sử dụng? Trên thực tế chúng được sử dụng ra sao? Sau đây, chúng ta sẽ xem xét chi tiết hơn về các hàm băm.

Các bài viết liên quan:

Như đã nói ở trên, hàm băm là một hàm biến đổi thông điệp cho trước từ độ dài tuỳ ý thành độ dài cố định và dùng để xác thực thông điệp.

Hàm băm H cần nó có được các tính chất sau:

  1. Đầu vào hàm băm có thể có độ dài tùy ý còn đầu ra có độ dài cố định
  2. Hàm băm H cần được tính trong toàn thể khối thông điệp
  3. Tính H(x) tương đối dễ
  4. Hàm băm H là hàm 1 chiều (one-way): tính H-1(x) rất khó
  5. Hàm băm H là không xung đột (collision-free), gọi là:
    • không xung đột yếu nếu với thông điệp x cho trước rất khó tìm được thông điệp y ≠ x sao cho: H(y) = H(x)
    • không xung đột mạnh nếu rất khó tìm được cặp hai thông điệp nào đó x ≠ y sao cho: H(x) = H(y)

Các yêu cầu 1-4 là các yêu cầu tối thiểu cho một hàm băm, yêu cầu 5 là để đánh giá một hàm băm là mạnh hay yếu. Trên thực tế, không gian của các giá trị băm là hữu hạn (ví dụ hàm băm cho độ dài 128 bit thì không gian các giá trị băm khác nhau có độ lớn là: 2128), còn số lượng các thông điệp khác nhau là vô hạn, do đó luôn tìm được hai thông điệp khác nhau có cùng giá trị băm. 

Vấn đề ở đây là việc tìm ra những thông điệp có cùng giá trị băm có dễ dàng hay không. Khi độ dài của giá trị băm tăng lên thì cơ hội tìm được thông điệp có cùng giá trị băm với thông điệp cho trước càng nhỏ. 

Tuy nhiên, việc tăng độ dài giá trị băm cũng làm tăng thời gian tính toán và hơn nữa nếu chỉ tăng độ dài giá trị băm một cách cơ học thì cũng không  tăng được độ an toàn lên bao nhiêu (do việc này có thể không ảnh hưởng nhiều tới quy trình để tìm ra các giá trị xung đột). Sau đây là ví dụ một hàm băm đơn giản:

Hàm băm (hash function) là gì?

Thông điệp đầu vào được chia thành các khối n-bit để tạo ra giá trị băm n-bit: M = block1 || block 2 || … || block m. Các bit trong từng khối sẽ được XOR với nhau để có n bit của giá trị băm:

Ci = bi1 ⊕ bi2 ⊕ … ⊕ bim

Trong đó:

Ci : bit thứ i của giá trị băm, 1 ≤ i ≤ n m : số các khối n-bit của đầu vào

bij : bit thứ i của khối thứ j

Rõ ràng là hàm băm này thoả các yêu cầu tối thiểu 1-4 cho một hàm băm: 

  1. Hàm băm này biến đổi thông điệp có độ dài tuỳ ý thành chuỗi bit có độ dài cố định là n;
  2. Khi thay đổi một bit bất kỳ của hàm băm thì sẽ ảnh hưởng ngay đến giá trị băm; 
  3. Quy trình tính H là dễ và rõ ràng; 
  4. Từ giá trị băm khó có thể khôi phục được chính xác thông điệp ban đầu.

Tuy nhiên, hàm băm đơn giản này không thoả tính chất 5: không xung đột. Ta rất dễ dàng tìm được hai thông điệp khác nhau có cùng giá trị băm. Ví dụ, trong thông điệp ban đầu ta chỉ cần hoán vị đi hai block khác nhau của nó là nhận được một thông điệp mới mà giá trị băm của nó vẫn không thay đổi.

Cấu trúc phổ biến của một hàm băm có dạng:

Hàm băm (hash function) là gì?

Ở đây:

IV – Initial Value là giá trị khởi tạo, f – function là hàm biến đổi, CVi – Chaining Variable là các biến trung gian, L là số khối đầu vào, Yi là các khối đầu vào, b là độ dài khối đầu vào, và n là độ dài của giá trị băm.

Trong quá trình băm cần phải xử lý thông điệp: khối cuối cùng sẽ được bổ sung giá trị độ dài thông điệp và được bổ sung các bit 0 cho thành bội của b. Để tránh xung đột, cần chọn giá trị b > n. Quá trình biến đổi như sau:

Thông điệp M = Y0 || Y1 || … || YL-1 CV0 = IV = giá trị khởi tạo n-bit CVi = f(CVi-1, Yi-1) với 1 ≤ i ≤ L H(M) = CVL

Hàm băm trong thực tế

Những năm trước đây, hàm băm MD5 – Message-Digest Algorithm (Ronald Rivest, 1992), được sử dụng khá rộng rãi. Hàm băm này cho độ dài 128 bit. Đến năm 1996, người ta đã phát hiện ra những lỗi nhỏ của thuật toán. Từ sau năm 2004, các lỗi về xung đột ngày càng lộ ra nhiều và sau đó, năm 2008, US-CERT đã khuyến cáo không nên sử dụng MD5 nữa.

Tại thời điểm hiện nay, các hàm băm sử dụng phổ biến là SHA (Secure Hash Algorithm). SHA được NIST phát triển và được coi là chuẩn từ năm 1993 (FIPS 180). Sau đó năm 1995, SHA được cải tiến thành SHA-1 (FIPS 180-1). SHA-1 cho giá trị băm có độ dài 160 bit. Vào năm 2002, NIST phát triển thành SHA-2 (FIPS 180-2) có thể cho các độ dài giá trị băm là 256, 384 hay 512 bit, có ký hiệu tương ứng là SHA-256, SHA-384 và SHA-512. Sau đó NIST cũng đã bổ sung thêm SHA-224 (FIPS 180-3).

Các hàm băm SHA-1 và SHA-2 có thể coi như chưa bị bẻ khoá (vì chưa có ai chỉ được quá trình tạo xung đột trong thời gian ít hơn thời gian vét cạn) nhưng các hàm băm này có cấu trúc và các phép tính toán học giống như MD5 – là hàm băm đã bị bẻ khoá. Do đó, có thể dự đoán việc các hàm băm SHA-1 và SHA-2 bị bẻ khoá sẽ xảy ra trong thời gian không xa.

NIST quyết định bắt đầu quá trình phát triển chuẩn cho các hàm băm mới. Năm 2007, NIST công bố cuộc thi tạo thế hệ hàm băm mới SHA-3 và dự kiến sẽ kết thúc vào cuối năm 2012. Các yêu cầu cho hàm băm mới như sau:

  • SHA-3 có thể thay thế SHA-2 một cách dễ dàng trong mọi ứng dụng hiện nay. Có nghĩa là SHA-3 phải hỗ trợ các tất cả các giá trị băm có độ dài 224, 256, 384 và 512 bit.
  • SHA-3 phải giữ nguyên được bản chất trực tuyến của SHA-2. Có nghĩa là SHA-3 phải được tính toán mỗi lần trên các khối nhỏ (512, 1024 bit), tránh việc phải nhập nguyên cả thông điệp dài vào bộ nhớ khi xử lý.

Ngoài các yêu cầu chính như trên, NIST còn đưa ra các tiêu chí đánh giá cho hàm băm mới SHA-3 liên quan đến các yêu cầu cho các ứng dụng mà hiện nay SHA-2 đang hỗ trợ như: các quy trình chữ ký số, mã xác thực thông điệp, tạo khoá, tạo các số ngẫu nhiên,…

Cảnh báo khi sử dụng hàm băm

Một trong những hàm băm hoặc hàm nén lâu đời nhất là MD4 hàm băm. Nó thuộc về họ thông báo thông báo (MD). Khác các thành viên của gia đình MD là MD5 và MD6, và có nhiều các biến thể của MD4 chẳng hạn như RIPEMD. Họ MD của thuật toán tạo ra thông báo thông báo 128 bit bằng cách sử dụng các khối 512 bit. 

Họ đã rộng rãi được sử dụng làm tổng kiểm tra để xác minh tính toàn vẹn của dữ liệu. Nhiều máy chủ tệp hoặc phần mềm kho lưu trữ được sử dụng để cung cấp tổng kiểm tra MD5 được tính toán trước, người dùng có thể kiểm tra tệp họ đã tải xuống. Tuy nhiên, đã có một rất nhiều lỗ hổng được tìm thấy trong dòng MD và nó đã không còn được dùng nữa.

Một họ hàm băm khác như vậy là Thuật toán băm an toàn (SHA) gia đình. Về cơ bản có bốn thuật toán trong họ này, chẳng hạn như SHA-0, SHA-1, SHA-2 và SHA- 3. Thuật toán đầu tiên được đề xuất trong họ được đặt tên là SHA, nhưng các phiên bản mới hơn sẽ đi kèm với tính năng bảo mật các bản sửa lỗi và cập nhật, vì vậy một từ viết tắt đã được áp dụng cho nó và nó được đặt thành SHA-0.

Nó được phát hiện có một lỗ hổng bảo mật nghiêm trọng nhưng chưa được tiết lộ và đã ngừng sản xuất. Sau đó, SHA-1 được đề xuất thay thế cho SHA-0. SHA-1 có một bước tính toán bổ sung giúp giải quyết vấn đề trong SHA-0. Cả SHA-0 và SHA-1 đều là hàm băm 160 bit tiêu thụ Kích thước khối 512-bit. SHA-1 được thiết kế bởi Cơ quan An ninh Quốc gia (NSA) để sử dụng nó trong thuật toán chữ ký số (DSA). 

Nó đã được sử dụng khá rất nhiều trong nhiều công cụ bảo mật và giao thức Internet như SSL, SSH, TSL,vv Nó cũng được sử dụng trong các hệ thống điều khiển phiên bản như Mercurial, Git, v.v. để kiểm tra tính nhất quán và không thực sự để bảo mật. Sau đó, khoảng năm 2005, Các điểm yếu về mật mã đã được tìm thấy trong đó và nó không được chấp nhận sau khi năm 2010. Chúng ta sẽ tìm hiểu chi tiết về SHA-2 và SHA-3 trong phần sau các phần

Leave a Reply