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

Ở 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:

• Xác thực thông điệp(message authentication) là gì?
• Mã hóa công khai( public key)
• Khoa học mật mã(cryptographic science)
• Thuật toán mã hóa khối(block cipher) – DES
• Các Hash funtion đang được sử dụng
• Kiểm tra lỗ hổng bảo mật Weak Encryption

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à: 2¹²⁸), 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:

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:

C_i = b_i1 ⊕ b_i2 ⊕ … ⊕ b_im

Trong đó:

C_i : 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

b_ij : 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:

Ở đâ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, Y_i 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 = Y₀ || Y₁ || … || Y_L-1 CV₀ = IV = giá trị khởi tạo n-bit CV_i = f(CV_i-1, Y_i-1) với 1 ≤ i ≤ L H(M) = CV_L

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

Những câu hỏi phổ biến về Hàm băm (hash function)

1. Hàm băm là gì?

• Hàm băm là một hàm toán học chuyển đổi một chuỗi dữ liệu đầu vào bất kỳ thành một giá trị đầu ra cố định có độ dài cố định.
• Hàm băm được sử dụng rộng rãi trong các ứng dụng mã hóa, bảo mật và tìm kiếm.

2. Tại sao lại sử dụng hàm băm?

• Hàm băm được sử dụng để bảo mật dữ liệu và tìm kiếm nhanh chóng trong cơ sở dữ liệu.
• Hàm băm giúp giảm độ phức tạp tính toán và giúp tăng tốc độ tìm kiếm và truy xuất dữ liệu.
• Hàm băm cũng được sử dụng để mã hóa mật khẩu và tạo chữ ký số.

3. Các tính chất của hàm băm là gì?

• Hàm băm có tính chất bảo mật, một chuỗi đầu vào cụ thể luôn tạo ra một giá trị đầu ra cụ thể và không thể tạo ra hai giá trị đầu ra khác nhau cho cùng một chuỗi đầu vào.
• Hàm băm có tính chất định hướng, hai chuỗi đầu vào khác nhau sẽ tạo ra hai giá trị đầu ra khác nhau.
• Hàm băm có tính chất đơn chiều, nghĩa là không thể dễ dàng suy luận ngược lại từ giá trị đầu ra để tìm ra giá trị đầu vào ban đầu.

4. Các ứng dụng của hàm băm là gì?

• Hàm băm được sử dụng trong các thuật toán tìm kiếm và xác minh tính toàn vẹn của dữ liệu trong các ứng dụng mã hóa.
• Hàm băm cũng được sử dụng trong các ứng dụng xác thực, đăng nhập và chữ ký số.
• Hàm băm được sử dụng trong các hệ thống cơ sở dữ liệu để tìm kiếm và truy xuất dữ liệu nhanh chóng.

5. Các thuật toán hàm băm phổ biến là gì?

• Các thuật toán hàm băm phổ biến bao gồm MD5, SHA-1, SHA-2 và SHA-3.
• MD5 và SHA-1 đã bị phá vỡ và không còn được sử dụng trong các ứng dụng bảo mật quan trọng.
• SHA-2 và SHA-3 hiện đang được sử dụng trong các ứng dụng bảo mật và có độ bảo mật cao hơn.

6. Các loại tấn công vào hàm băm là gì?

• Tấn công theo từ điển (dictionary attack): tấn công này sử dụng một từ điển các giá trị đầu vào phổ biến để tìm ra giá trị đầu ra tương ứng. Tấn công này chỉ hiệu quả đối với các thuật toán hàm băm yếu.
• Tấn công dựa trên va chạm (collision attack): tấn công này cố gắng tìm hai giá trị đầu vào khác nhau tạo ra cùng một giá trị đầu ra, từ đó giả lập được dữ liệu. Tấn công này khó thực hiện với các thuật toán hàm băm có độ dài giá trị đầu ra lớn và tỉ lệ va chạm thấp.
• Tấn công preimage attack: tấn công này nhằm tìm một giá trị đầu vào thỏa mãn cho giá trị đầu ra đã cho trước. Tấn công này khó thực hiện với các thuật toán hàm băm có độ dài giá trị đầu ra lớn và được sử dụng trong các ứng dụng bảo mật.

7. Các phương pháp tăng cường độ bảo mật của hàm băm là gì?

• Sử dụng các thuật toán hàm băm mới nhất với độ dài giá trị đầu ra lớn.
• Sử dụng phương pháp đệ quy (hash chaining) để giảm tỉ lệ va chạm và tăng độ bảo mật.
• Sử dụng kỹ thuật salt (muối) để ngăn chặn tấn công theo từ điển.
• Sử dụng kỹ thuật HMAC (Hash-based Message Authentication Code) để đảm bảo tính toàn vẹn của dữ liệu.