Thuật toán mã hóa – Xác thực thông tin phát triển từ mật mã OTP

Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2020 87 THUẬT TOÁN MÃ HÓA – XÁC THỰC THÔNG TIN PHÁT TRIỂN TỪ MẬT MÃ OTP Lưu Hồng Dũng1*, Nguyễn Ánh Việt2, Đoàn Thị Bích Ngọc3 Tóm tắt: Bài báo đề xuất thuật toán mã hóa – xác thực thông tin từ việc phát triển mật mã sử dụng khóa một lần - OTP (One - Time Pad). Ưu điểm của thuật toán mới đề xuất là có tính an toàn và hiệu quả thực hiện cao tương tự OTP, đồng thời việc thiết lập, quản lý - phân phối và sử dụng khóa hoàn toàn giống như các hệ mã khóa đối xứng đang được ứng dụng trong thực tế (DES, AES). Từ khóa: Symmetric-Key Cryptography; Symmetric-Key Cryptographic Algorithm; Symmetric-Key Cryptosystems; One - Time Pad Algorithm; OTP Cipher. 1. ĐẶT VẤN ĐỀ Mật mã sử dụng khóa một lần OTP được Gilbert Vernam đề xuất vào năm 1917 và Joseph Mauborgne tiếp tục hoàn thiện sau đó. Nguyên tắc căn bản của mật mã OTP là sử dụng một khóa mật chia sẻ trước có độ dài bằng với độ dài của bản tin cần mã hóa (bản rõ), các bit của bản mã nhận được từ việc cộng loại trừ (XOR) trực tiếp các bit của bản rõ với các bit tương ứng của khóa mật. Lý thuyết của Claude E. Shannon [6] đã chỉ ra OTP là một loại mã có độ mật hoàn thiện (Perfect Secrecy). Hiện tại, mật mã OTP vẫn được xem là loại mã an toàn tuyệt đối, không thể phá vỡ. Điều đặc biệt là ngay cả tấn công theo kiểu “vét cạn” (Brute force attack) bằng máy tính lượng tử đối với loại mã này cũng trở nên vô nghĩa, nếu có thể đáp ứng được các điều kiện về khóa sau: - Khóa có tính chất ngẫu nhiên; - Mỗi khóa chỉ dùng để mã hóa duy nhất một bản tin; - Kích thước của khóa phải bằng hoặc lớn hơn kích thước của bản rõ; - Khóa phải được giữ bí mật hoàn toàn. Tuy có độ an toàn và tốc độ mã hóa cao cũng như khả năng cài đặt dễ dàng trên các thiết bị có năng lực tính toán và tài nguyên hạn chế, nhưng với các yêu cầu về khóa đã chỉ ra, thì loại mã này có rất ít khả năng ứng dụng trong thực tế. Nguyên nhân đầu tiên là việc tạo khóa phải có tính thực sự ngẫu nhiên, nhằm loại trừ các nguy cơ mất an toàn: a) từ một khóa đã biết, kẻ tấn công có thể tìm (suy ra) được các khóa đã được sử dụng trước đó hay các khóa sẽ được sử dụng trong tương lai; b) chuỗi bit khóa tồn tại chu kỳ lặp lại, từ đó tạo ra mối liên quan giữa bản rõ và bản mã, kẻ tấn công có thể tận dụng mối liên quan này để phá mã tương tự như với mã hóa đa bảng Vigenère [7]. Tuy nhiên, đây là một yêu cầu không dễ thực hiện về mặt kỹ thuật trong các ứng dụng. Nhưng lý do chủ yếu làm cho mã OTP ít có ý nghĩa thực tế là vì mỗi khóa chỉ được dùng một lần duy nhất và phải có kích thước không nhỏ hơn kích thước bản tin cần mã hóa, song lại phải được giữ bí mật tuyệt đối như bản tin cần mã hóa. Đã có một số nghiên cứu nhằm giải quyết các hạn chế của mật mã OTP được công bố [1-5], song từ các kết quả được công bố cho thấy những nghiên cứu này chủ yếu tập trung giải quyết vấn đề tạo chuỗi bit khóa OTP từ các chuỗi bit giả ngẫu nhiên có kích thước hạn chế, còn việc có thể sử dụng khóa nhiều lần tương tự như các hệ mã khóa đối xứng khác vẫn là hạn chế căn bản của các nghiên cứu này. Từ đó, bài báo đề xuất một biến thể của mật mã OTP với việc thiết lập, quản lý – phân phối và sử dụng khóa được thực hiện hoàn toàn như các hệ mã khóa đối xứng đang Công nghệ thông tin 88 L. H. Dũng, N. A. Việt, Đ. T. B. Ngọc, “Thuật toán mã hóa – xác thực từ mật mã OTP.” sử dụng trong thực tế (DES, AES,). Ngoài ra, xác thực nguồn gốc và tính toàn vẹn của bản tin được mã hóa cũng là một tính năng bổ sung quan trọng cho thuật toán này. 2. THUẬT TOÁN MÃ HÓA – XÁC THỰC THÔNG TIN 2.1. Mô tả thuật toán Bản rõ P được mã hóa dưới dạng n khối dữ liệu Pi có kích thước 128-bit: P = {P1,P2,,Pi,,Pn}, |Pi| = 128 bit, i = 1..n Khóa sử dụng một lần KOT cũng bao gồm n khóa con Ki có kích thước tương ứng với kích thước của khối dữ liệu: KOT = {K1,K2,,Ki,,Kn}, |Ki| = 128 bit, i = 1..n Do đó, bản mã C cũng bao gồm n khối dữ liệu Ci có kích thước 128-bit: C = {C1,C2,,Ci,,Cn}, |Ci| = 128 bit, i = 1..n Thuật toán mã hóa là phép XOR các bit của khối bản rõ Pi với các bit tương ứng của khóa con Ki : Ci = Pi  Ki , i = 1..n Tương tự, thuật toán giải mã cũng là phép XOR các bit của khối bản mã Ci với các bit tương ứng của khóa con Ki: Pi = Ci  Ki , i = 1..n Chú ý: Trường hợp chia bản tin P thành n khối không chẵn thì bù thêm một số bit để khối cuối cùng đủ 128-bit, việc bù thêm này được thực hiện tương tự như ở các hệ mã khối khác (DES, AES,) [8]. Khóa bí mật K để mã hóa và giải mã cho một bản tin P bao gồm khóa sử dụng một lần KOT và khóa bí mật chia sẻ trước giữa 2 đối tượng gửi/mã hóa – nhận/giải mã là KS. Trong đó, khóa sử dụng một lần KOT bao gồm các khóa con Ki: KOT = {K1,K2,,Ki,,Kn} được dùng để mã hóa các khối dữ liệu của bản rõ ở bên gửi và giải mã các khối bản mã ở phía bên nhận. Khóa bí mật chia sẻ KS được bên gửi sử dụng để tạo ra ”mầm khóa” - C0 tương ứng với mỗi bản tin cần mã hóa, nhờ hàm băm (Hash Function) MD5: C0 = MD5(P,KS). Thành phần C0 này được gửi như một khối của bản mã sang cho bên nhận. Dễ thấy rằng, giá trị C0 là khác nhau với các bản tin cần mã hóa khác nhau và có tính chất ngẫu nhiên – hệ quả của việc tạo ra từ hàm băm MD5 [9]. Tiếp đến, cả 2 bên gửi và nhận đều tạo khóa con đầu tiên K1 từ KS và C0 nhờ hàm MD5 như sau: K1 = MD5(C0,KS) Phía gửi tin, các khóa Ki được sinh bởi cùng một thuật toán từ khóa con đứng trước Ki-1 và khối dữ liệu tương ứng Pi-1: Ki = MD5(Pi-1,Ki-1), i = 2..n Phía nhận tin, sau khi tạo khóa con K1: K1 = MD5(C0,KS) sẽ giải mã khối đầu tiên: P1 = C1  K1. Từ đây, các khóa con tiếp theo sẽ được tạo ra theo cùng một qui tắc với phía bên gửi: Ki = MD5(Pi-1,Ki-1), i = 2..n và các khối mã tiếp theo sẽ được giải mã: Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2020 89 Pi = Ci  Ki , i = 2..n Chú ý rằng, việc tạo các khóa con của KOT ở phía bên gửi có thể thực hiện trước hay đồng thời với mã hóa các khối dữ liệu của bản tin, còn phía nhận tin thì việc tạo các khóa con của KOT và giải mã các khối bản mã cần phải được thực hiện một cách đồng thời với nhau. Như vậy, ở thuật toán mới đề xuất khóa bí mật K sẽ bao gồm 2 thành phần có chức năng phân biệt: K = {KS, KOT} Trong đó: KS là khóa bí mật chia sẻ giữa các đối tượng tham gia trao đổi thông tin mật, khóa này được sử dụng để tạo ra khóa KOT tương ứng với mỗi bản tin; KOT là khóa sử dụng một lần cho việc mã hóa và giải mã các khối dữ liệu. Từ đây, thuật toán sinh khóa và mã hóa được mô tả như sau: Input: P = {P1,P2,,Pi,,Pn}, KS. Output: C = { C0,C1,C2,,Ci,,Cn}. 1. C0 = MD5(P||KS) 2. K1 = MD5(C0||KS) 3. C1 = P1  K1 4. C[0] = C0, C[1] = C1 5. for i = 2 to n do begin Ki = MD5(Pi-1|| Ki-1|| Pi-1|| Ki-1) Ci = Pi  Ki C[i] = Ci end 6. return C Ghi chú: - Phép toán  là phép cộng modulo 2 (XOR) hai chuỗi bit. - Phép toán “||” là phép ghép nối tiếp 2 xâu bit. Thuật toán sinh khóa, giải mã và xác thực bao gồm các bước thực hiện như sau: Input: C = {C0,C1,C2,,Ci,,Cn}, KS. Output: M = {M1,M2,,Mi,,Mn}, true/false. 1. K1 = MD5(C0||KS) 2. M1 = C1  K1 3. M[1] = M1 4. for i = 2 to n do: begin Ki = MD5(Pi-1|| Ki-1|| Pi-1|| Ki-1) Mi = Ci  Ki M[i] = Mi end 5. M0 = MD5(M||KS) 6. if (M0 = C0) then return {M,true} else return {M,false} Công nghệ thông tin 90 L. H. Dũng, N. A. Việt, Đ. T. B. Ngọc, “Thuật toán mã hóa – xác thực từ mật mã OTP.” Ghi chú: - Nếu kết quả trả về là {M,true} thì bản tin được xác thực về nguồn gốc và tính toàn vẹn. Ngược lại, kết quả trả về là {M,false} thì hoặc M là bản tin giả mạo hoặc C đã bị thay đổi trong quá trình truyền tin. - Nếu bản mã được truyền chính xác từ bên gửi sang bên nhận thì khối dữ liệu C0 của bên nhận cũng chính là C0 của bên gửi. Mặt khác, do bên nhận và bên gửi có cùng thuật toán sinh khóa với dữ liệu vào C0 và khóa bí mật chia sẻ KS như nhau nên khóa mã hóa và khóa giải mã sử dụng một lần (KOT) sẽ hoàn toàn giống nhau. Vì thế, bản tin sau giải mã cũng chính là bản rõ trước khi mã hóa. Nên điều kiện M0 = C0 được thỏa mãn hoàn toàn. 2.2. Một số đánh giá về độ an toàn và hiệu quả thực hiện của thuật toán mới đề xuất 2.2.1. Mức độ an toàn Tương tự như mật mã OTP, khóa KOT ở đây chỉ sử dụng một lần, do vậy các dạng tấn công như thám mã vi sai, thám mã tuyến tính,.. và nói chung là tất cả các dạng tấn công đã được biết đến với các mã khối điển hình như DES, AES,... là không có tác dụng với thuật toán mới đề xuất. Ở đây, mức độ an toàn của thuật toán mới đề xuất có thể đánh giá qua khả năng kháng lại một số dạng tấn công như sau: - Tấn công khóa bí mật chia sẻ: Tấn công khóa bí mật chia sẻ có thể thực hiện dựa vào cách tạo giá trị C0: C0 = MD5(P||KS) hoặc tính giá trị của khóa con K1: K1 = MD5(C0||KS) Với việc tạo C0 và K1 như trên thì kích thước LK của khóa bí mật chia sẻ hoàn toàn có thể chọn tùy biến trong khoảng: Lmin≤LK≤2L-LP. Trong đó: Lmin là kích thước tối thiểu đủ để bảo đảm ngưỡng an toàn (≥ 80 bit); LP là kích thước bản rõ và L là kích thước lớn nhất của dữ liệu đầu vào hàm băm MD5. Khi đó, dữ liệu đầu vào hàm MD5 là sự ghép nối tiếp xâu bit của KS với P trong trường hợp tạo giá trị C0 hoặc là sự ghép nối tiếp xâu bit của KS với C0 trong trường hợp cần tạo khóa con K1. Từ đây có thể thấy rằng, khóa bí mật chia sẻ trước giữa các bên gửi – nhận ở đây hoàn toàn có thể được giữ bí mật không chỉ về giá trị mà còn bí mật cả về kích thước khóa. Dễ thấy rằng với đặc tính 1 chiều của hàm băm, hơn nữa với kích thước của KS cũng là một tham số bí mật thì việc tìm được KS từ C0, P và K1 (K1 có thể biết khi P đã được công khai) là hoàn toàn bất khả thi. - Tấn công “vét cạn” khi chỉ có bản mã: Nếu KOT là một chuỗi bit thực sự ngẫu nhiên thì giữa bản rõ và bản mã được tạo ra sẽ không có bất kỳ mối quan hệ nào. Khi đó, tấn công theo kiểu “vét cạn” có thể giải một bản mã thành bất kỳ bản tin có nghĩa nào có cùng độ dài (với bản mã) và đối với kẻ tấn công thì tất cả các bản tin có nghĩa sau giải mã đều có khả năng là bản tin được mã hóa (bản rõ). Nghĩa là, sẽ không có bất kỳ thông tin nào trong bản mã cho phép kẻ tấn công lựa chọn đúng bản rõ từ các bản tin có nghĩa sau giải mã bằng phương pháp “vét cạn”. Ngoài ra, nếu KOT thực sự ngẫu nhiên thì từ một khóa đã biết kẻ tấn công không thể tìm (suy) ra các khóa khác đã được tạo ra trước hay sau đó. Với thuật toán đề xuất, khóa sử dụng một lần KOT là một tập các khóa con Ki được tạo bởi hàm băm MD5 theo nguyên tắc: a) mỗi khóa con Ki được sinh ra từ khóa con đứng trước Ki-1 và khối dữ liệu tương ứng Pi-1; b) riêng khóa con đầu tiên K1 được tạo ra bởi “mầm khóa” C0 và khóa bí mật chia sẻ KS. Như vậy, KOT thực chất là một chuỗi bit được tạo ra bởi việc ghép nối tiếp n chuỗi (bit) con Ki, mà các chuỗi con Ki này chính là đoạn Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2020 91 128-bit đầu tiên của n chuỗi bit cơ sở được tạo bởi MD5 – đóng vai trò của hàm sinh số ngẫu nhiên với các giá trị khởi tạo hay các “mầm” (seed) khác nhau. Nói cách khác, chuỗi bit KOT được tạo ra từ n chuỗi bit cơ sở khác nhau, bằng cách lấy ra từ mỗi chuỗi bit cơ sở một chuỗi con (m bit đầu tiên) rồi ghép nối tiếp n chuỗi con này với nhau. Với việc sử dụng MD5 để tạo các chuỗi bit cơ sở, thì trong các chuỗi con có kích thước hạn chế Ki sẽ không tồn tại chu kỳ lặp lại và do đó các chuỗi con này thực sự có tính ngẫu nhiên là điều hoàn toàn có thể khẳng định. Mặt khác, các chuỗi bit cơ sở được tạo bởi các giá trị khởi tạo khác nhau nên chúng độc lập với nhau, dẫn đến các chuỗi con Ki (128-bit đầu tiên của chuỗi bit cơ sở) cũng độc lập với nhau. Như vậy, KOT là sự ghép nối tiếp các chuỗi con 128-bit có tính ngẫu nhiên và độc lập nhau, nên trong KOT sẽ không tồn tại chu kỳ lặp lại và do đó có tính ngẫu nhiên cũng là điều hoàn toàn có thể khẳng định được. Tóm lại, KOT được tạo ra theo giải pháp đề xuất đã đáp ứng được yêu cầu về tính ngẫu nhiên của khóa theo nghĩa: a) từ một khóa đã biết, kẻ tấn công không thể tìm được các khóa đã được tạo ra trước hoặc sau đó; b) chuỗi bit khóa không tồn tại chu kỳ lặp lại, nên sẽ không tạo ra mối liên quan giữa bản rõ và bản mã. Do đó, tấn công theo dạng “vét cạn” là hoàn toàn có thể kháng được đối với thuật toán mới đề xuất. - Tấn công giả mạo: Mật mã OTP không cung cấp tính năng xác thực cho bản tin được mã hóa, vì vậy kẻ tấn công có thể chặn bản mã được gửi đi và gửi cho bên nhận một bản tin giả mạo có cùng kích thước với bản tin thật. Trường hợp giải mã ra một bản tin vô nghĩa, người nhận có thể suy đoán về một sự giả mạo đã được thực hiện hoặc do lỗi truyền tin gây ra. Tuy nhiên, nếu giải mã ra một bản tin có nghĩa thì chính người nhận cũng không có cách nào xác định được bản tin này là thật hay giả mạo. Ở thuật toán mới đề xuất, bằng việc tạo “mầm khóa” C0 từ khóa bí mật chia sẻ KS và bản tin được mã hóa nhờ hàm băm MD5 ở phía bên gửi: C0 = MD5(P||KS), bên nhận hoàn toàn có khả năng nhận thực chính xác nguồn gốc cũng như tính toàn vẹn của bản tin sau giải mã qua việc tính: M0 = MD5(M||KS) và kiểm tra: M0 = C0. Đặc biệt là, chỉ có duy nhất bên nhận thực hiện được việc xác thực này, chính điều đó là một yếu tố quan trọng tạo nên khả năng kháng lại tấn công dạng “vét cạn” của thuật toán mới đề xuất. 2.2.2. Hiệu quả thực hiện Có thể nâng cao hiệu quả thuật toán đề xuất nếu khóa KOT được tạo ra trước các khi các thủ tục mã hóa và giải mã được thực hiện. Khi đó, các thuật toán sinh khóa, mã hóa và giải mã được mô tả như sau: + Thuật toán sinh khóa: Input: P = {P1,P2,,Pi,,Pn}, KS. Output: KOT = {K1,K2,,Ki,,Kn},C0. 1. C0 = MD5(P||KS) 2. KOT[1] = MD5(C0||KS) 3. for i = 2 to n do begin KOT[i] = MD5(KOT[i-1]) end 4. return {KOT,C0} + Thuật toán mã hóa: Công nghệ thông tin 92 L. H. Dũng, N. A. Việt, Đ. T. B. Ngọc, “Thuật toán mã hóa – xác thực từ mật mã OTP.” Input: P = {P1,P2,,Pi,,Pn}, KOT = {K1,K2,,Ki,,Kn},C0. Output: C = {C0,C1,C2,,Ci,,Cn}. 1. C[0] = C0 2. for i = 1 to n do begin C[i] = P[i]  KOT[i] end 3. return C + Thuật toán giải mã và xác thực: Input: C = {C0,C1,C2,,Ci,,Cn}, KOT = {K1,K2,,Ki,,Kn},KS. Output: M = {M1,M2,,Mi,,Mn}, true/false. 1. for i = 1 to n do begin M[i] = C[i]  KOT[i] end 2. M0 = MD5(M||KS) 3. if (M0 = C0) then return {M,true} else return {M,false} Có thể thấy rằng, hiệu quả thực hiện của thuật toán được đề xuất có thể đạt xấp xỉ hiệu quả thực hiện của mật mã OTP nếu cả hai sử dụng cùng thuật toán sinh số ngẫu nhiên như nhau. Trên thực tế, có thể nâng cao tốc độ thực hiện của thuật toán sinh khóa bằng cách sử dụng thuật toán sinh số ngẫu nhiên dạng thanh ghi dịch hồi tiếp tuyến tính – LFSR (Linear Feedback Shift Registers) [9] kiểu Shrinking Generator [11]. 3. KẾT LUẬN Bài báo đề xuất thuật toán mã hóa – xác thực thông tin từ việc phát triển mật mã sử dụng khóa một lần OTP. Với giải pháp thiết kế khóa mật từ 2 phân khóa tách biệt, thuật toán được đề xuất ở đây có khả năng loại trừ tất cả các dạng tấn công đối với các hệ mã khối/khóa đối xứng đã được biết đến, đây là một ưu điểm rất quan trọng được kế thừa từ mật mã OTP. Ngoài ra, do có cơ chế xác thực nguồn gốc và tính toàn vẹn của bản tin được mã hóa, thuật toán này còn có khả năng chống lại các dạng tấn công giả mạo rất hiệu quả. Những ưu điểm khác của thuật toán này là có tốc độ và hiệu quả thực hiện có thể so sánh với mật mã OTP, song khóa mật chia sẻ có thể sử dụng nhiều lần như các hệ mật khóa đối xứng khác. Đây là những đặc tính rất quan trọng mang lại khả năng ứng dụng cao cho thuật toán trong việc thiết kế - chế tạo các thiết bị bảo mật thông tin. TÀI LIỆU THAM KHẢO [1]. SharadPatil , Ajay Kumar (2010). "Effective Secure Encryption Scheme(One Time Pad) using Complement Approach". International Journal of Computer Science & Communication, Vol.1,No.1,January-June 2010, pp.229-233. [2]. Raman Kumar,Roma Jindal, Abhinav Gupta , SagarBhalla, HarshitArora (2011). "A Secure Authentication System-Using Enhanced One Time Pad Technique". IJCSNS International Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2020 93 Journal of Computer Science and Network Security,VOL.11 No.2,February 2011. [3]. SharadPatil ,ManojDevare , Ajay Kumar (2007). "Modified One Time Pad Data Security Scheme: Random Key Generation Approach". International Journal of Computer Science and Security (IJCSS) ,Volume (3): Issue(2). [4]. N.J.Croft and M.S.Olivier (2005). “Using an approximated One-Time Pad to Secure ShortMessaging service(SMS)”. SATNAC 2005 Proceedings. [5]. Jeff Connelly (1978). "A Practical Implementation of a One-time Pad Cryptosystem". CPE 456 , June 11, 2008. [6]. Shannon C.E. (1949). "Communication Theory of Secrecy Systems". Bell System Technical Journal, Vol.28-4, pp 656-715. [7]. William Stallings (2005). "Cryptography and Network Security Principles and Practices". Prentice Hall. [8]. FIPS PUB 197: "Federal information processing standards publication 197". Category: computer security standard, cryptography. November 2001. [9]. Menezes A., Van Oorschot P. and Vanstone S. (1996). "Handbook of Applied Cryptography". Boca Raton, Florida: CRC Press. [10]. D. Coppersmith, H. Krawczyk, and Y. Mansour, “The shrinking generator,” in CRYPTO ’93: Proceedings of the 13th annual international cryptology conference on Advances in cryptology, (New York, NY, USA), pp. 22–39, Springer-Verlag New York, Inc., 1994. ABSTRACT AN ENCRYPTION AND AUTHENTICATION ALGORITHM DEVELOPED BASED ON THE ONE – TIME PAD CIPHER An encryption and authentication algorithm developed based on the One – Time Pad (OTP) cipher are proposed. Advantages of the new algorithm is to have high safety and efficient implementation as OTP cipher, but the establishment, management - distribution and usage of keys are exactly the same as the Symmetric-key cryptosystems in practice (DES,AES, etc.) Keywords: Symmetric-key cryptography; Symmetric-key cryptographic algorithm; Symmetric-key cryptosystems; One - time pad algorithm; OTP cipher. Nhận bài ngày 17 tháng 10 năm 2020 Hoàn thiện ngày 10 tháng 12 năm 2020 Chấp nhận đăng ngày 15 tháng 12 năm 2020 Địa chỉ: 1Học viện KTQS; 2Bộ Tư lệnh Tác chiến không gian mạng; 3Trường Đại học CNTT & TT, Đại học Thái Nguyên. *Email: luuhongdung@gmail.com.