Giới thiệu về thuật toán RC6
Giới thiệu chung
Thuật toán RC6 do Rivest thiết kế năm 1998 [2] là phiên bản cải tiến của thuật toán RC5 [1] được đưa ra trước đó, trong đó có sửa một số điểm để tăng độ an toàn, tăng hiệu suất làm việc và đáp ứng được các yêu cầu cho cuộc thi tuyển chọn thuật toán AES. RC6 dựa trên phép dịch vòng mà số lượng dịch vòng phụ thuộc vào dữ liệu. Thuật toán sử dụng 4 thanh ghi và phép nhân số nguyên nhằm làm tăng tính khuếch tán sau mỗi vòng, tăng tính bảo mật, giảm số vòng và tăng hiệu suất chung của thuật toán.
RC6 được thiết kế đơn giản, do đó các tấn công lên nó chủ yếu tập trung vào độ an toàn của phép dịch vòng phụ thuộc dữ liệu. Ngay từ khi được đề xuất, đã có rất nhiều nghiên cứu về cấu trúc và các phép tính toán ảnh hưởng tới độ an toàn của nó. Mặc dù cho tới nay chưa có tấn công thực hành nào có thể áp dụng cho RC6, song các kết quả nghiên cứu đã thu được một số phân tích/tấn công lý thuyết đáng kể. Trong đó chủ yếu tập trung vào việc sử dụng thám mã vi sai và thám mã tuyến tính trong tấn công RC6, ngoài ra vẫn có một số kiểu tấn công khác.
Mô tả thuật toán RC6
Thủ tục mã hóa/giải mã của RC6
RC6 là một họ các thuật toán mã hóa được tham số hóa thường được biết đến với ký hiệu RC6-w/r/b, trong đó:
• w: là kích thước của từ (khối con, sử dụng trong tính toán mã), tính theo bit.
• r: là số vòng mã (khuyến cáo từ 20-24 vòng).
• b: ký hiệu là độ dài của khóa mã tính theo đơn vị byte.
Quá trình mã hóa của RC6 được tiến hành như sau: một nửa khối dữ liệu sẽ được cập nhật theo nửa dữ liệu còn lại và hai nửa khối sẽ được tráo đổi cho nhau. Với phiên bản đệ trình cho cuộc thi AES, mặc định ta định nghĩa w = 32, r = 20 và có 3 phiên bản khóa (tham số b) khác nhau là 16, 24 và 32 byte khóa. Khi có giá trị w hoặc r trong tên thuật toán, các giá trị tham số sẽ được xác định là RC6-w/r. Với mọi biến thể, RC6-w/r/b thực hiện trên 4 từ w-bit sử dụng sáu phép tính cơ bản sau. Phép logarithm cơ số 2 của w được ký hiệu là lgw.
Người dùng cung cấp một khóa có độ dài k byte và khối bản rõ 128-bit được nạp vào các từ A, B, C và D. Bốn từ w-bit này sẽ chứa bản mã đầu ra của thuật toán mã hóa.
RC6 làm việc với bốn thanh ghi w-bit A, B, C và D mà chứa bản rõ đầu vào đầu tiên cũng như bản mã đầu ra ở cuối thủ tục mã. Byte đầu tiên của bản rõ hoặc bản mã được đặt trong byte có trọng số nhỏ nhất của A; byte cuối cùng của bản rõ hoặc bản mã được đặt trong byte có trọng số cao nhất (msb) của D. Ta sử dụng (A, B, C, D) = (B, C, D, A) theo nghĩa là gán song song các giá trị ở bên phải cho các thanh ghi ở bên trái. Thuật toán mã hóa và giải mã được mô tả như sau:
Thủ tục mã hóa của RC6-w/r/b:
B = B + S [0]
D = D + S [1]
for i = 1 to r do
{
t = (B × (2B + 1)) << lg w
u = (D × (2D + 1)) << lg w
A = ((A ⨁ t) <<< u) + S [2i]
C = ((C ⨁ u) <<< t) + S [2i + 1]
(A, B, C, D) = (B, C, D, A)
}
A = A + S [2r + 2]
C = C + S [2r + 3]
Thủ tục giải mã của RC6-w/r/b:
C = C – S [2r + 3]
A = A – S [2r + 2]
for i = r downto 1 do
{
(A, B, C, D) = (D, A, B, C)
u = (D × (2D + 1)) <<<lg w
t = (B × (2B + 1)) <<< lg w
C = ((C - S[2i + 1]) >>> t) ⨁ u
A = ((A - S[2i]) >>> u) ⨁ t
}
D = D – S [1]
B = B – S [0]
Lược đồ tạo khóa của RC6
Người dùng sẽ cung cấp một khóa có độ dài b byte. Các byte 0 sẽ được thêm vào nếu cần để độ dài của khóa phải là bội số khác không của bốn byte. Sau đó, khóa được lưu vào c từ w-bit L[0], ..., L[c-1], với byte đầu tiên của khóa được lưu byte thấp nhất của L[0],..., và L[c-1] được đệm thêm với các byte 0 nếu cần. (Chú ý rằng nếu b = 0 thì c = 1 và L[0] = 0). Các khóa vòng thêm vào được lưu trữ trong mảng S[0, ..., 2r + 3]. Khi đó, lược đồ tính khóa của RC6-w/r/b được mô tả như sau (với Pw và Qw là các hằng số xác định trước):
S[0] = Pw
for i = 1 to 2r + 3 do
S[i] = S[i - 1] + Qw
A = B = i = j = 0
v = 3 × max{c, 2r + 4}
for s = 1 to v do
{
A = S[i] = (S[i] + A + B) <<< 3
B = L[j] = (L[j] + A + B) <<< (A + B)
i = (i + 1) mod (2r + 4)
j = (j + 1) mod c
}
Chú ý rằng lược đồ tính khóa cũng sử dụng phép dịch vòng với số vòng phụ thuộc dữ liệu.
Tổng quan về độ an toàn của RC6
Đánh giá tổng thể
Cho tới nay, chưa có tấn công nào có thể áp dụng được cho RC6, mà chỉ tồn tại các tấn công lên số vòng rút gọn. Tuy vậy, đây cũng là một cơ sở để đánh giá “hành lang an toàn” của các thuật toán mật mã. Một số đặc trưng khác để đánh giá độ an toàn của thuật toán là thông qua phân tích lược đồ thiết kế cũng như độ khó trong phân tích tổ hợp các phép tính toán bằng các kỹ thuật hiện có. Các đánh giá này bao gồm các kiểm tra thống kê, tính đơn giản và các quan sát, nhận xét khác. Tổng hợp một số tấn công lên RC6 được cho trong Bảng 1.
Bảng 1. Một số tấn công lên dạng rút gọn vòng của RC6
Các kết quả tấn công lên các dạng RC6 đều dựa vào độ lệch thống kê nhỏ, nhưng lặp đi lặp lại của hàm vòng. Các quan hệ thống kê giữa các đầu vào có dạng cụ thể với các đầu ra của chúng được dùng để phân biệt một số vòng của RC6 với một hoán vị ngẫu nhiên (xem [5]). Tấn công này dựa vào các kết quả thực nghiệm và có thể áp dụng cho RC6 lên tới 15 vòng. Với các lớp khóa yếu, nó ước lượng có thể tấn công lên tới 17 vòng của RC6. Đây là kết quả quan trọng và đáng chú ý nhất với thuật toán mã khối RC6. Do vậy, NIST (tr. 24 [6]) cho rằng RC6 có một hành lang an toàn phù hợp.
Đánh giá về các tiêu chí thiết kế RC6, NIST có một số đánh giá như sau:
• Cấu trúc vòng của RC6 là một dạng của Feistel. Độ an toàn của RC6 dựa trên phép dịch vòng đi với số lượng khác nhau và tạo độ phi tuyến chính, mà không có các S-hộp.
• Việc sử dụng phép toán nhân modulo được xem là phép toán phức tạp hơn nhiều so với các phép tính trong các mã pháp thông thường khác. Việc sử dụng phép cộng khóa modulo và phép dịch vòng phụ thuộc dữ liệu làm cho việc đánh giá khả năng kháng lại các thám mã vi sai và tuyến tính khó khăn hơn nhiều. Hơn nữa, các phép tính phụ thuộc dữ liệu này dẫn tới rất khó khăn trong ngăn chặn các tấn công cài đặt như các tấn công thời gian và tấn công năng lượng (xem [6], trang 66).
• Vì không có khả năng tính toán khóa on-the-fly, nên khi cài đặt trên các thiết bị hạn chế tài nguyên là không phù hợp. (Lược đồ khóa on-the-fly là lược đồ khóa mà có thể tính khóa con ở vòng i từ khóa con ở vòng i-1 hoặc ngược lại. Lược đồ khóa dạng này có thể sử dụng với các thiết bị hạn chế về bộ nhớ, không cần lưu trữ toàn bộ khóa con trong quá trình mã hóa/giải mã ở trong RAM).
• Các phép nhân 32 bit và phép dịch vòng 32 bit không được hỗ trợ ở một số bộ vi xử lý 32 bit. Do vậy, với cùng một mã nguồn cài đặt RC6, nhưng khi biên dịch và chạy trên những máy tính có nền tảng (platform) khác nhau thì có kết quả khác biệt. Các kết quả đánh giá về hiệu suất cho thấy RC6 có tốc độ mã tốt nhất trên các vi xử lý 32 bit. Tuy nhiên, RC6 lại có thể cài đặt khá hiệu quả bằng phần cứng riêng.
Trong một kết quả đánh giá về cài đặt gần đây, Moharir và cộng sự [11] đã chỉ ra rằng Rijndael là thuật toán có hiệu suất tốt nhất trong 5 ứng viên cuối cùng của cuộc thi AES. Theo đó, nếu chỉ xét về tốc độ mã hóa, thì RC6 xếp 2/5 (sau Rijndael); nếu xét về dữ liệu lưu trong RAM thì RC6 đứng thứ 3/5 (sau Twofish, Rijndael); xét về hiệu suất tổng (tính cả lược đồ khóa) thì RC6 xếp thứ 4/5 (thứ tự Rijndael, Twofish, MARS, RC6 và Serpent).
Các tấn công với RC6
Cho đến nay, các tấn công lên RC6 đều chỉ dừng ở việc phân tích mang tính lý thuyết mà chưa có tính thực hành, vì các tấn công đều yêu cầu cả độ phức tạp tính toán và độ phức tạp lưu trữ lớn. Hai tấn công mạnh nhất là thám mã vi sai và thám mã tuyến tính với RC6 được trình bày trong [4]. Một tấn công ở dạng mở rộng của tấn công tuyến tính là thám mã tuyến tính bội (multiple linear cryptanalysis) [8].
Một hướng khai thác khác với RC6 là các tấn công thống kê hoặc còn gọi là các tấn công tương quan. Tấn công tương quan sử dụng các tương quan giữa đầu vào và đầu ra, mà có thể được xác định bởi test χ2; vì với một phép dịch vòng xác định trong RC6 thì tạo ra các tương quan giữa 2 giá trị số nguyên tương ứng. Tấn công tương quan bao gồm 2 phần, một thuật toán phân biệt (distinguishing attack) và một thuật toán khôi phục khóa. Thuật toán phân biệt chỉ được dùng để điều khiển các bản rõ sao cho giá trị χ2 của một phần bản mã thu được là cao hơn đáng kể. Mặt khác, thuật toán khôi phục khóa chỉ ra tất cả các khóa sai, và lựa chọn chính xác một khóa đúng từ các giá trị χ2. Trong [3] và [7], các tác giả đã tập trung vào nghiên cứu thuật toán phân biệt. Nghĩa là các tác giả tập trung vào tìm một giá trị χ2 cao, mà được tính toán từ thực nghiệm trên trung bình của các khóa.
Trong [7], các tấn công tương quan được áp dụng để khôi phục khóa con cho khóa vòng cuối từ khóa vòng đầu tiên cùng bằng cách điều chỉnh một bản rõ (A0, B0, C0, D0) theo cách để giá trị χ2 sau một vòng trở lên cao đáng kể. Tuy nhiên, thuật toán khôi phục khóa ở đây chưa có tính thực tế vì nó yêu cầu độ phức tạp tính toán cỡ 262.2 và với độ phức tạp dữ liệu là 242 cho 5 vòng RC6.
Cùng ý tưởng này, Miyaji và Nonaka [9] đã đề xuất phương pháp khôi phục khóa RC6 với số vòng nhỏ mà không có bước làm trắng (cộng khóa trước vòng 1 và sau vòng cuối cùng). Gần đây nhất, vào năm 2018, nhóm tác giả người Trung Quốc [10] đã chỉ ra một tấn công tích phân lên RC6 với 4 vòng có độ phức tạp (w+1)2w bản rõ chọn trước và tấn công vi sai không thể (impossible differential) lên RC6 với 5 vòng mã có độ phức tạp w × 2w+2 bản mã chọn trước.
Kết luận
Thuật toán mã hóa RC6 có ưu điểm nổi bật là tốc độ thực thi nhanh trên các bộ vi xử lý 32 bit và do đó thường được ứng dụng trong một số công cụ mã hóa ảnh số. Tuy nhiên, có thể vì không được công nhận là một tiêu chuẩn mật mã nào nên không có nhiều kết quả nghiên cứu thám mã tập trung vào nó trong những năm gần đây. Bên cạnh đó, RC6 cũng được đánh giá còn một số hạn chế nhất định. Ở bài báo này, chúng tôi mô tả chi tiết về thuật toán mã khối RC6, nguyên lý thiết kế và tổng hợp một số đánh giá tổng quan về RC6. Bài báo giúp người đọc có hình dung cơ bản về thuật toán RC6 và là cơ sở cho những nghiên cứu sâu hơn. Ưu điểm nổi bật của RC6 là sự đơn giản trong mô tả và có hiệu suất mã dịch vượt trội trong môi trường xử lý 32 bit. Độ an toàn của RC6 dựa chính vào phép dịch vòng phụ thuộc dữ liệu, mà không sử dụng các S-hộp. Việc sử dụng các phép nhân modulo, phép dịch vòng có thể thay đổi (phụ thuộc dữ liệu) và phép cộng modulo làm cho việc phân tích/đánh giá khả năng kháng lại tấn công vi sai và tuyến tính phần nào khó khăn hơn.
|
Tài liệu tham khảo [1]. Ronald L. Rivets, “The RC5 Encryption Algorithm”, Fast Software Encryption 1994, pp.86-96. [2]. Ronald L. Rivets, M.J.B. Robshaw, R. Sidney, Y.L. Yin, “The RC6 Block Cipher”, hội thảo Chuẩn mã dữ liệu tiên tiến lần thứ nhất (AES 1), 1998. [3]. J. Shimoyama, T. Takeuchi, K. Hayakawa (2000), “Correlation Attack to the Block Cipher RC5 and the Simplified Variants of RC6”, hội thảo Chuẩn mã dữ liệu tiên tiến lần 3 (AES3), 2000. [4]. Scott Contini, Ronald L. Rivest, M.J.B. Robshaw, Y.L. Yin, “The Security of the RC6 Block Cipher”, báo cáo tự đánh giá của RSA laboratories, có thể tải tại ftp://ftp.rsasecurity.com/pub/rsalabs/rc6/security.pdf, 1998. [5]. H. Gilbert, H. Handschuh, A. Joux, S. Vaudenay “A Statistical Attack on RC6”, FSE 2000 (Vol. 1978), pp. 64-74, [6]. “Report on the development of the Advanced Encryption Standard (AES)”, báo cáo của NIST về kết quả cuộc tuyển chọn AES, tháng 10, năm 2000. Có thể tải tại: csrc.nist.gov/archive/aes/round2/r2report.pdf. [7]. L. Knudsen, W. Meier, “Correlations in RC6 with a reduced numbers of rounds”, Proceeding Fast Software Encryption, Lectures Notes in Computer Science, vol.1978, pp. 94-108, Springer-Verlag, 2001. [8]. Takeshi Shimoyama, Masahiko Takenaka, Takeshi Koshiba, “Multiple Linear Cryptanalysis of a reduced round RC6”, Fast Software Encryption, 9th International Workshop, FSE 2002, vol. 2365., Springer-Verlag (2002) p. 76–88. [9]. A. Miyaji, M. Nonaka, “Cryptanalysis of Reduced-Round RC6 without Whitening”, IEICE trans. fundamentals, vol. E86-A, No.1, January 2003, pp. 19-30. [10]. Zhu, Hongguo, Xin Hai, and Jiuchuan Lin. “Integral and Impossible Differential Cryptanalysis of RC6.” International Conference on Cloud Computing and Security. Springer, Cham, 2018. [11]. Moharir, Minal, and A. V. Suresh. “Analysis of Advanced Encryption Standards.” GSTF Journal on Computing (JoC) 1.1 (2018). |
Trần Hồng Thái
