KHÁI QUÁT VỀ HÀM BĂM MẬT MÃ
Khái quát
Các hàm băm (Hash functions) là thuật toán dùng để tạo ra bản tóm tắt của thông điệp, giúp nhận diện và đảm bảo tính toàn vẹn của nó Hàm băm có ít nhất hai thuộc tính quan trọng.
Nén (Compression) là quá trình ánh xạ một chuỗi đầu vào x có chiều dài bất kỳ thành một chuỗi đầu ra h(x) có chiều dài cố định n bit Điều này có nghĩa là mặc dù chiều dài của thông điệp đầu vào có thể thay đổi, nhưng đầu ra sẽ luôn có chiều dài nhất định.
+ Dễ tính toán (Esae of computation): cho trước hàm h và đầu vào x, việc tính toán h(x) là dễ dàng.
Hình 1.1: Mô hình nén thông tin của hàm băm
Thông điệp đầu vào có chiều dài tùy ý sẽ trải qua nhiều vòng xử lý của hàm băm, từ đó tạo ra chuỗi rút gọn Digset với kích thước cố định ở đầu ra.
Phân loại
Hàm băm không khóa (unkeyed) là loại hàm băm mà đầu vào chỉ bao gồm thông điệp, được biểu diễn dưới dạng h(x) với h là hàm băm và x là thông điệp Một số ví dụ nổi bật của hàm băm không khóa bao gồm MDC, các hàm băm thuộc họ MD như MD2, MD4, MD5, MD6, cũng như các hàm băm thuộc họ SHA như SHA-0, SHA-1, SHA-2, SHA-3, bên cạnh đó là CRC và Checksums.
+ Hàm băm có khóa (keyed): đầu vào gồm thông điệp và khóa bí mật (dạng h(x, K) với hàm băm h, thông điệp x và khóa bí mật K) VD:MAC,…
Mã phát hiện sửa đổi MDC (Modification Detection Code) là một hàm băm không khóa, được sử dụng để tạo chuỗi đại diện cho thông điệp MDC kết hợp với các kỹ thuật khác như chữ ký số nhằm đảm bảo tính toàn vẹn của thông điệp MDC bao gồm hai loại nhỏ.
Hàm băm một chiều (OWHF – One-way hash function): dễ tính giá trị băm nhưng rất khó khôi phục thông điệp từ giá trị băm
Hàm băm chống đụng độ (CRHF – Collision resistant hash functions): rất khó để tìm được 2 thông điệp khác nhau nhưng có cùng giá trị băm
MDC thường được dùng trong quá trình tạo và kiểm tra chữ kí số
Mã xác thực thông điệp MAC (Message Authentication Code) là một phương pháp đảm bảo tính toàn vẹn của thông điệp mà không cần sử dụng kỹ thuật bổ sung nào khác, thông qua việc áp dụng hàm băm có khóa.
MAC được dùng trong các giao thức bảo mật SSL/TLS, IPSec,
Mô hình xử lí dữ liệu
Hình 1.2: Mô hình tổng quát xử lí dữ liệu của hàm băm
Sau khi tạo ra chuỗi rút gọn Digset với kích thước cố định, chuỗi này sẽ trải qua một bước chuyển đổi định dạng tùy chọn để tạo ra chuỗi băm kết quả.
Hình 1.3: Mô hình xử lí dữ liệu của hàm băm
Trong quy trình xử lý dữ liệu, bước 1 (tiền xử lý) bao gồm việc nối thêm bit và xác định kích thước khối, sau đó chia dữ liệu thành các khối có kích thước đồng nhất Bước 2 xử lý từng khối dữ liệu xi thông qua hàm nén f để tạo ra đầu ra Hi->Ht Cuối cùng, bước 3 chuyển đổi định dạng Ht thành giá trị băm kết quả h(x) thông qua hàm g.
Ứng dụng
Hàm băm mật mã thường tiêu tốn nhiều tài nguyên tính toán hơn so với các hàm hash thông thường Do đó, chúng thường được áp dụng trong các tình huống cần bảo vệ thông tin và chống lại sự giả mạo từ các đối tượng độc hại.
Sau đây là một số ứng dụng của hàm băm mật mã:
Để đảm bảo tính toàn vẹn của message và file, cần kiểm tra bằng cách so sánh giá trị băm của message trước và sau khi truyền Việc này giúp xác định liệu có bất kỳ thay đổi nào xảy ra trong quá trình truyền tải hay không.
Để tăng cường tính bảo mật, chúng ta có thể lưu trữ mật khẩu dưới dạng giá trị hàm băm Khi người dùng nhập mật khẩu, hệ thống sẽ thực hiện quá trình băm và so sánh với giá trị băm đã lưu trữ để xác thực.
Bằng chứng công việc (Proof of Work) là cơ chế được áp dụng trong blockchain nhằm ngăn chặn các cuộc tấn công DoS và spam, yêu cầu người truy cập thực hiện một công việc nhất định Đặc điểm nổi bật của cơ chế này là công việc phải có độ khó cao và tốn nhiều thời gian thực hiện từ phía người yêu cầu, trong khi đó, việc kiểm tra kết quả lại đơn giản cho nhà cung cấp.
CÁC GIẢI THUẬT HÀM BĂM SHA
Giới thiệu SHA
SHA là các thuật giải được FIPS chấp nhận, chuyển đổi dữ liệu thành đoạn có chiều dài cố định và xác suất khác biệt cao Chúng được coi là "an toàn" theo chuẩn FIPS 1802, phát hành ngày 1 tháng 8 năm 2002.
"for a given algorithm, it is computationally infeasible
1 To find a message that corresponds to a given message digest, or
2 To find two different messages that produce the same message digest Any change to a message will, with a very high probability,result in a different message digest".
1.Cho một giá trị băm nhất định được tạo nên bởi một trong những thuật giải SHA, việc tìm lại được đoạn dữ liệu gốc là không khả thi.
2 Việc tìm được hai đoạn dữ liệu khác nhau có cùng kết quả băm tạo ra bởi một trong những thuật giải SHA là không khả thi
Bất cứ thay đổi nào trên đoạn dữ liệu gốc, dù nhỏ, cũng sẽ tạo nên một giá trị băm hoàn toàn khác với xác suất rất cao."
Các thuật giải SHA bao gồm SHA-1, SHA-224, SHA-256 và SHA-384, với độ dài kết quả lần lượt là 160 bit, 224 bit, 256 bit và 384 bit.
SHA-2 bao gồm các thuật giải băm như SHA-256 (trả lại kết quả dài 256 bit), SHA-384 (384 bit) và SHA-512 (512 bit), được phát triển bởi Cục An ninh Quốc gia Mỹ (NSA) và công nhận bởi Viện Công nghệ và Chuẩn Quốc gia Mỹ (NIST) Phiên bản mới nhất, SHA-3, bao gồm 6 phiên bản: SHA3-224, SHA3-256, SHA3-384, SHA3-512, SHAKE128 và SHAKE256, được phát hành vào tháng 8 năm 2015.
SHA-1 được sử dụng phổ biến trong nhiều ứng dụng và giao thức an ninh như TLS, SSL, PGP, SSH, S/MIME và IPSec, và được xem là sự thay thế cho MD5 Tuy nhiên, từ năm 2005, SHA-1 đã bị coi là không còn an toàn khi các nhà mật mã học Trung Quốc thành công trong việc tìm ra hai đoạn dữ liệu có cùng kết quả băm Mặc dù chưa có ai khai thác được điểm yếu tương tự ở SHA-2, nhưng do sự tương đồng trong cấu trúc, nhiều nhà khoa học đang phát triển thuật giải băm an toàn hơn NIST cũng đã khởi động một cuộc thi nhằm phát triển thuật giải băm mới, tương tự như quy trình phát triển chuẩn mã hóa tiên tiến (AES).
Các giải thuật SHA
SHA-0 là phiên bản đầu tiên của thuật toán hàm băm an toàn, được công bố vào năm 1993 dưới tiêu đề Secure Hash Standard, FIPS PUB 180 bởi NIST Tuy nhiên, phiên bản này đã bị NSA thu hồi ngay sau khi phát hành và được thay thế bởi SHA-1, được công bố trong FIPS PUB 180-1 vào năm 1995.
SHA-0 là một hàm băm 160-bit, được thiết kế dựa trên nguyên lý của MD4 và sử dụng mô hình Merkle-Damgard cho chức năng nén Hàm này nhận đầu vào là các tin nhắn được đệm và chia thành các khối tin 512-bit Trong mỗi vòng lặp của hàm nén h, biến chuỗi 160-bit Ht được cập nhật với khối tin Mt+1.
Ht+1 = h (Ht, Mt+1) Giá trị ban đầu H0 (còn gọi là IV) được xác định trước và Hk là đầu ra của hàm băm.
Hàm nén SHA-0 được phát triển dựa trên cấu trúc Davis-Meyer, sử dụng hàm E như một mật mã khối với Ht là đầu vào tin nhắn và Mt+1 là đầu vào khóa Để đảm bảo tính bảo mật, cần thiết phải có một feed-forward nhằm phá vỡ tính không thể đảo ngược của quá trình.
Ht+1 = E(Ht , Mt+1 ) ⊕ Ht, trong đó ⨁ biểu thị phép cộng modulo 2^32 giữa các từ 32-bit Hàm này thực hiện 80 bước (4 vòng, mỗi vòng 20 bước), với mỗi bước xử lý một từ tin 32 bit Wi để cập nhật 5 thanh ghi nội bộ 32-bit (A, B, C, D, E) Các bước feed-forward bao gồm việc cộng modulo 2^32 giữa trạng thái ban đầu và trạng thái cuối cùng của mỗi thanh ghi Việc sử dụng nhiều bit tin hơn so với số liệu có sẵn dẫn đến việc mở rộng tin nhắn.
Mở rộng thông điệp: đầu tiên, khối thông điệp Mt được chia thành 16 từ 32-bit
W0, …,W15 Sau đó 16 từ này được mở rộng theo tuyến tính như sau:
Wi = Wi-16 ⨁ Wi-14 ⨁ Wi-8 ⨁ Wi-3 với 16 ≤ i ≤ 79
Cập nhật trạng thái: Đầu tiên, biến chuỗi Ht được chia thành 5 từ 32 bit để điền vào 5 thanh ghi (A0, B0, C0, D0, E0) Sau đó chuyển đổi tiếp theo được thực hiện 80 lần:
Trong đó Ki là các hằng số được xác định trước và f i là hàm luận lý được định nghĩa trong bảng 1.
Feed-forward: Các tổng modulo 2 32 : (A0+A80), (B0+B80), (C0+C80), (D0+D80), (E0+E80) được nối thành các biến chuỗi Ht+1.
Lưu ý rằng tất cả các thanh ghi đều được cập nhật, tuy nhiên thanh ghi Ai+1 chỉ là bản sao quay, vì vậy chúng ta chỉ cần tập trung vào thanh ghi A ở mỗi bước.
Vòng lặp Bước i fi(B,C,D) Ki
Bảng 2.1: Các hàm Boolean và hằng số trong SHA-0
Hàm băm SHA-1, được NIST giới thiệu vào năm 1995 như một Tiêu chuẩn xử lý Thông tin Liên bang, đã nhanh chóng trở thành tiêu chuẩn phổ biến cho nhiều chính phủ và ngành công nghiệp an ninh Đặc biệt, SHA-1 đóng vai trò quan trọng trong các tiêu chuẩn chữ ký số yêu cầu tính chống xung đột Ngoài ứng dụng trong chữ ký số, SHA-1 còn được sử dụng trong nhiều chương trình và giao thức mật mã khác nhau, bao gồm xác thực người dùng, hợp đồng khóa và tạo số ngẫu nhiên Nhờ vào những tính năng này, SHA-1 đã được triển khai rộng rãi trong hầu hết các hệ thống và sản phẩm bảo mật thương mại.
SHA-1 được cải tiến từ SHA-0 thông qua một vòng quay duy nhất trong lịch trình thông báo của hàm nén Theo NSA, sự thay đổi này nhằm khắc phục một lỗ hổng trong thuật toán ban đầu, giúp nâng cao độ an toàn mã hóa, nhưng không có thêm thông tin chi tiết nào được cung cấp.
Hàm băm SHA-1 nhận thông điệp có chiều dài nhỏ hơn 2^64 bit và tạo ra giá trị băm 160 bit Thông điệp đầu vào được đệm và xử lý theo các khối 512 bit trong cấu trúc Damgard / Merkle Trong mỗi vòng lặp, hàm nén sử dụng giá trị ràng buộc 160 bit cùng với khối tin 512 bit để xuất ra giá trị chuỗi 160 bit mới Giá trị chuỗi ban đầu (IV) được xác định bằng các hằng số cố định, và giá trị chuỗi cuối cùng chính là băm của thông điệp.
Trong phần này, chúng ta sẽ trình bày hàm nén của SHA-1 Đầu tiên, mỗi khối 512 bit của tin nhắn được chia thành 16 từ 32-bit (m0, m1, ,m15) Các từ này sau đó được mở rộng, với công thức cho i từ 16 đến 79: mi = (mi-3 ⨁ mi-8 ⨁ mi-14 ⨁ mi-16) ≪1 Các từ tin nhắn mở rộng sẽ được xử lý qua bốn vòng, mỗi vòng gồm 20 bước Hàm bước được định nghĩa cho i từ 1 đến 80, với a i = a i−1.
Giá trị chuỗi ban đầu IV = (a0, b0, c0, d0, e0) được định nghĩa như sau:
(0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476, 0xc3d2e1f0) Mỗi vòng sử dụng một hàm Boolean và hằng số ki khác nhau , được tóm tắt trong bảng 2.
Bảng 2.2: Các hàm Boolean và hằng số trong SHA-1
Hình 2.1 minh họa lưu đồ một vòng xử lý của SHA-1, trong đó các từ 32 bit A, B, C, D, E đại diện cho trạng thái, Wt là khối 32 bit của thông điệp đầu vào, và Kt là 32 bit hằng số khác nhau cho mỗi trong 16 vòng, kết hợp với hàm phi tuyến tính.
Hình 2.1: Lưu đồ một vòng xử lý của SHA-1
SHA-2
SHA-2 (Thuật toán băm bảo mật 2) là một bộ hàm băm mật mã do Cơ quan An ninh Quốc gia Hoa Kỳ (NSA) phát triển Nó được thiết kế dựa trên cấu trúc Merkle–Damgård và sử dụng một hàm nén một chiều được xây dựng theo cấu trúc Davies–Meyer từ một mã khối chuyên dụng.
SHA-2 là một sự cải tiến đáng kể so với SHA-1, bao gồm sáu hàm băm với các giá trị băm 224, 256, 384 hoặc 512 bit Các hàm băm này bao gồm SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224 và SHA-512/256.
SHA-256 và SHA-512 là các hàm băm mới, được tính bằng 8 từ 32-bit và 64-bit, với cấu trúc tương tự nhưng khác nhau về số vòng và hằng số Phiên bản rút gọn của chúng là SHA-224 và SHA-384, sử dụng các giá trị ban đầu khác nhau Ngoài ra, SHA-512/224 và SHA-512/256 cũng là các phiên bản rút ngắn của SHA-512, với giá trị ban đầu theo tiêu chuẩn FIPS PUB 180-4 SHA-2 đã được NIST công bố vào năm 2001 như một tiêu chuẩn liên bang của Hoa Kỳ và được cấp bằng sáng chế số 6829355, với giấy phép miễn phí bản quyền.
Đến năm 2011, các cuộc tấn công công khai đã làm suy yếu khả năng kháng nghịch ảnh của 52 trong 64 vòng lặp của SHA-256 và 57 trong 80 vòng lặp của SHA-512, đồng thời giảm khả năng chống va chạm của 46 trong 64 vòng lặp của SHA-256.
Hình 2.2 minh họa lưu đồ một vòng lặp trong hàm nén của SHA-2, trong đó các thành phần màu xanh thực hiện các hoạt động quan trọng để đảm bảo tính toàn vẹn và bảo mật của dữ liệu.
Vòng quay theo chiều bit trong SHA-512 sử dụng các hằng số khác với SHA-256 Các số được cung cấp trong bài viết này là dành riêng cho SHA-256 Hình ⊞ biểu thị toán tử cộng modulo 2^32 cho SHA-256 và modulo 2^64 cho SHA-512.
SHA-256 là một thuật toán bảo mật 256 bit thuộc nhánh SHA-2, được sử dụng để tạo ra các hàm băm duy nhất và không thể đảo ngược Với số lượng hàm băm lớn, xác suất hai giá trị khác nhau tạo ra cùng một giá trị hàm băm sẽ giảm xuống rất thấp.
Thuật toán SHA-256 tạo ra mã băm 256 bit (32 byte) gần như duy nhất, không thể tính toán ngược lại, giúp xác thực mật khẩu, chống giả mạo và chữ ký số Ứng dụng nổi bật nhất của SHA-256 là trong hệ thống tiền tệ Bitcoin.
2.3.2.1.2 Các bước thực hiện của SHA-256
+ Tất cả các biến là số nguyên không dấu 32 bit và phép công được tính theo modulo 2 32
+ Đối với mỗi vòng, có một hằng số vòng k[i] và một mục nhập trong mảng Lịch trình thông báo w[i], 0 i 63.
+ Hàm nén sử dụng 8 biến làm việc, từ a đến h.
Quy ước big-endian được áp dụng để biểu thị các hằng số trong mã giả, đồng thời cũng được sử dụng trong quá trình phân tích cú pháp tin nhắn, nơi dữ liệu sẽ được chuyển đổi từ byte thành từ.
Để khởi tạo giá trị băm, ta sử dụng 32 bit đầu tiên của phần phân đoạn căn bậc hai của 8 số nguyên tố đầu tiên từ 2 đến 19, cụ thể như sau: h0 = 0x6a09e667, h1 = 0xbb67ae85, h2 = 0x3c6ef372, h3 = 0xa54ff53a, h4 = 0x510e527f, h5 = 0x9b05688c, h6 = 0x1f83d9ab, h7 = 0x5be0cd19.
- Bước 2: Khởi tạo mảng các hằng số vòng (32 bit đầu tiên của phần phân đoạn của các rễ hình khối của 64 số nguyên tố đầu tiên 2 311): k [0 63]: 0x428a2 f98
0xc67178f2Bảng 2.3: 64 số nguyên tố đầu tiên dưới dạng 32-bit
- Bước 3: Tiền xử lý (Padding):
+ Bắt đầu với thông điệp ban đầu có độ dài L bit.
+ Thêm một bit '1' duy nhất.
+ Thêm K bit '0', trong đó K là số nhỏ nhất > = 0 sao cho L + 1 + K + 64 là bội số của 512.
+ Thêm L dưới dạng số nguyên big-endian 64 bit, làm cho tổng độ dài sau xử lý là bội số của 512 bit sao cho các bit trong thông báo là L 1 00