Gửi lúc: 17/12/2018 11:15:03
Bookmark and Share

Đánh giá độ an toàn của GOST 28147-89 trước những tấn công thám mã hiện tại

Năm 1989, chuẩn mã hóa dữ liệu GOST 28147-89 của Liên bang Nga được ban hành và sử dụng. Đây là một thuật toán mã khối có cấu trúc Feistel, hoạt động trong 32 vòng với kích thước khối bản rõ và bản mã đều là 64 bit và sử dụng khóa kích thước 256 bit. Trong GOST 28147-89, bộ S-hộp của nó được giữ bí mật như thành phần khóa dài hạn. Năm 2015, thuật toán mã hóa dữ liệu trong chuẩn này được lấy tên là Magma và kết hợp với thuật toán mã hóa dữ liệu Kuznyechik để trở thành chuẩn mã hóa dữ liệu mới của Liên bang Nga - chuẩn GOST R 34.12-2015. Để làm rõ về vị trí hiện tại của thuật toán Magma trên cơ sở những ý kiến đánh giá gần đây, trong bài báo này chúng tôi sẽ trình bày về độ an toàn hiện tại của GOST 28147-89 trước các tấn công thám mã gần nhất.

Trong những năm gần đây xuất hiện hàng loạt các công trình nghiên cứu thám mã lên GOST 28147-89. Đồng thời ở giai đoạn này, trong cộng đồng mật mã Liên bang Nga cũng xuất hiện nhiều ý kiến công nhận ý tưởng những tấn công thám mã này, cũng như tính chất cài đặt của thuật toán. Các ý kiến đều cho rằng thuật toán mã hóa GOST 28147-89 đã lỗi thời, chậm, có nhiều điểm yếu và hiệu quả không bằng các thuật toán của nước ngoài có cùng kích thước. Tuy nhiên, khi thực hiện các tấn công thám mã khác nhau lên GOST 28147-89 đều cho thấy rằng, nó vẫn đảm bảo được độ an toàn.

ĐỘ AN TOÀN CỦA GOST 28147-89

Trong phần này, độ an toàn của GOST 28147-89 sẽ được đánh giá thông qua các công trình nghiên cứu thám mã lên nó. Chúng tôi sẽ trình bày tóm tắt các kết quả thám mã mới nhất lên thuật toán này.

Tấn công của N. Courtois

Trong một vài năm trở lại đây, tác giả N. Courtois có một loạt các công trình nghiên cứu thám mã lên thuật toán Magma. Tuy nhiên, các kết quả của tác giả này không được đánh giá cao, bởi thiếu cơ sở toán học trong các lập luận tấn công.

Tháng 10/2010, Nga đã xem xét và dự định đưa chuẩn GOST 28147-89 thành chuẩn ISO/IEC 18033-3. Sau đó, vào năm 2011, trên trang thư viện mật mã điện tử ePrint công bố bài báo của nhà mật mã nổi tiếng N. Courtois về GOST 28147-89 [1]. Công bố này tạo ra làn sóng tranh luận rất gay gắt trong cộng đồng mật mã nhằm vào tác giả, khi ông sử dụng các khái niệm thiếu cơ sở và kết quả của bài báo không mở ra bất kỳ một tính chất mới nào của thuật toán được xem xét. Nhưng mặt khác, những kết quả này lại đủ tạo cảm giác đúng đắn đối với những người đọc không nắm rõ được về thuật toán và tính chân thực các tính chất đạt được trong bài báo.

Những nghiên cứu tiếp theo của Courtois về GOST 28147-89 có cấu trúc rất giống nhau. Trong phần tóm tắt và giới thiệu của các nghiên cứu đều đưa ra các ngữ cảnh về tính chất rất yếu của chuẩn mã khối này của Nga. Theo đó, chuẩn này rất dễ bị tấn công và không rõ lý do tại sao tiểu ban chuẩn hóa ISO lại có thể xem xét tiếp nhận chuẩn này như một chuẩn mã hóa quốc tế. Tiếp theo trong những nghiên cứu này, Courtois trình bày về đánh giá độ phức tạp trong tấn công của ông. Theo đó, độ phức tạp này giảm một cách “tự nhiên” mà không có sự đảm bảo của cơ sở toán học. Courtois cũng phản bác lại tranh luận của cộng đồng mật mã quốc tế bằng cách, thay vì tường thuật và diễn giải các tấn công, Courtois đã xây dựng dựa trên nguyên tắc “khẳng định - bình luận”. Ông đưa ra các Fact (khẳng định) và bình luận về các Fact này. Thoạt nhìn có thể thấy rằng, các Fact là những lập luận “có vẻ hợp lý”, tuy nhiên, lại không có những chứng minh nghiêm ngặt. Trong phần kết luận, Courtois còn ngộ nhận và cho rằng, đây là lần đầu tiên trong lịch sử một mã khối đã được chuẩn hóa sử dụng trong lĩnh vực an ninh quốc phòng nhằm bảo vệ, cũng như phân loại các tài liệu bí mật cho chính phủ, các ngân hàng lớn và các tổ chức khác bị phá vỡ bởi một tấn công toán học.

Nhìn chung, những lập luận trong tấn công của Courtois được xây dựng trên cơ sở hai lớp phương pháp thám mã: Phương pháp thám mã đại sốphương pháp thám mã vi sai. Tuy nhiên, những nghiên cứu về thám mã đại số và thám mã vi sai của Courtois đã được một số tác giả của Liên bang Nga trình bày trong [6]. Trong đó, nhóm tác giả này chỉ ra rằng, đa số các Fact của Courtois là không có chứng minh và việc kiểm tra bằng thực nghiệm tính đúng đắn của chúng là phức tạp và không thể thực hiện được với năng lực tính toán hiện tại. Qua đó khẳng định, phương pháp này hoàn toàn không có tính thực tiễn. Ngoài ra, những vấn đề lớn nhất của Courtois về việc thiếu cơ sở toán học khi đưa ra các đánh giá của mình cũng đã được nhắc đến trong nghiên cứu [6]. Do đó, các công trình nghiên cứu của Courtois không được đăng trên các ấn phẩm của FSE, bởi thiếu tính xác thực.

Tấn công của Isobe và Dinur-Dunkelman-Shamir

Ý tưởng chung trong tấn công của Isobe [2] và tấn công của Dinur-Dunkelman-Shamir (tấn công DDS) [3] là xây dựng tập “hẹp” xác định các bản rõ (phụ thuộc khóa). Tập này tương đương với tập các biến đổi đơn giản hơn so với các biến đổi mã hóa. Trong trường hợp của tấn công của Isobe thì tập các khối là 64 bit x sao cho F8-1(Swap(F8(z)))= z, ở đây z= F16(x). Ký hiệu F8 (x) và F16(x) là biến đổi cho 8 và 16 vòng tương ứng trong GOST 28147-89, còn Swap là phép thay đổi vị trí hai nửa của khối 64 bit. Đối với những bản rõ trong tập này, kết quả biến đổi nó cho kết quả là 32 vòng mã hóa đầy đủ của GOST 28147-89, đây cũng chính là kết quả biến đổi của 16 vòng. Còn trong trường hợp của tấn công DDS, tập này sẽ bao gồm những điểm x thỏa mãn F8 (x) (là những điểm bất động của biến đổi F8). Khi đó, đối với mỗi điểm thuộc tập này biến đổi mã hóa trong GOST 28147-89 sẽ thực hiện giống như những biến đổi ở 8 vòng cuối, điều này sẽ làm giảm độ phức tạp khi tấn công.

Độ phức tạp trong tấn công của Isobe là 2224 phép mã hóa, còn tấn công DDS là 2192. Tuy nhiên, hai tấn công này lại có những hạn chế và điều kiện khác nhau khi áp dụng lên GOST 28147-89. Cụ thể tấn công của Isobe yêu cầu 232 cặp bản rõ/mã, còn tấn công DDS là 264. Việc xử lý một khối dữ liệu khổng lồ như vậy mà không có sự thay đổi khóa là không khả thi đối với những mã pháp thực tế có độ dài khối là 64 bit. Trong điều kiện lý tưởng, yêu cầu 232 cặp bản rõ/mã là tương đương với bài toán nghịch lý ngày sinh, khi đó là gần với xác suất ½ của việc xuất hiện các khối lặp lại, điều này sẽ giúp cho kẻ tấn công có lợi thế khi đưa ra được một số kết luận về bản rõ thông qua bản mã mà không cần xác định khóa. Còn nếu kẻ tấn công có khả năng tạo ra 264 cặp bản rõ/mã mà chỉ sử dụng một khóa, khi đó kẻ tấn công có thể thực hiện phép mã và giải mã mà không cần biết giá trị khóa này. Nói cách khác là, trong trường hợp này kẻ tấn công có một bảng tra toàn bộ các biến đổi mã hóa. Tuy nhiên, trong thực tế tình huống này không thể xảy ra do không thể đáp ứng những yêu cầu trong thiết kế mã pháp.

Ví dụ, trong bộ thư viện CryptoPro CSP có đưa ra giới hạn về dung lượng dữ liệu được phép thực hiện mã hóa mà không cần thay đổi khóa là 4MB. Các tấn công trên khó có thể khai thác thông tin khóa dựa trên lượng dữ liệu như vậy, do đó, tấn công của Isobe và DDS là không thể áp dụng trong trường hợp này. Như vậy, thuật toán GOST 28147-89 giữ nguyên được độ an toàn có thể là 2256.

Bên cạnh đó, cần phải lưu ý rằng các nhà nghiên cứu khi nghiên cứu hai thuật toán trên đã chỉ ra một số tính chất của GOST 28147-89, cho phép xây dựng phương pháp thám mã mà họ chưa nghiên cứu. Những kết quả nghiên cứu này chỉ mang tính lý thuyết, nhưng được cộng đồng mật mã đánh giá rất cao. Từ đó cho thấy rằng, có thể tồn tại bài toán đơn giản thực hiện tấn công hiệu quả cho một số trường hợp đặc biệt của các khóa và các bản rõ.

Các tấn công dựa trên cơ sở biết một số thông tin giả định về khóa

Những năm gần đây, nhiều công trình nghiên cứu liên quan đến các tấn công lên GOST 28147-89 được phát triển dựa trên mô hình tấn công khóa quan hệ. Theo đó, mô hình này đưa ra giả thiết là, kẻ tấn công không chỉ có quyền truy cập vào các cặp bản rõ/mã với khóa cần tìm, mà còn có quyền truy cập vào tập các cặp bản rõ/mã được tạo thành từ các khóa có quan hệ nào đó (ví dụ hai khóa sai khác nhau ở một số vị trí cố định). Khi thực hiện tấn công theo mô hình này mang lại những kết quả rất đáng lưu tâm lên GOST 28147-89, nhưng đồng thời cũng đưa đến nhiều kết quả tương tự khi áp dụng lên một thuật toán rất phổ biến trong nhiều hệ thống mạng (thuật toán AES). Tuy nhiên, cần phải nhấn mạnh rằng, kết quả dạng tấn công này chỉ là các kết quả lý thuyết có tính hàn lâm cao theo quan điểm nghiên cứu tính chất của các biến đổi mật mã, nhưng trên thực tế thì nó rất khó có thể áp dụng. Ví dụ, tất cả các sản phẩm bảo vệ thông tin bằng mật mã được cấp phép bởi cơ quan FSB đều thực hiện các yêu cầu nghiêm ngặt theo lược đồ mở rộng khóa. Kết quả được đưa ra trong nghiên cứu [4] chỉ ra rằng, khi tìm được 18 khóa quan hệ và 210 cặp bản rõ/mã, thì độ phức tạp để tìm ra khóa bí mật là cỡ 226 với xác suất thành công là 1 - 10-4. Nhưng khi thực hiện theo các yêu cầu nghiêm ngặt trong lược đồ mở rộng khóa, thì xác suất để tìm ra số lượng khóa quan hệ trên là 2-4352, nghĩa là nhỏ hơn 24096 lần so với việc phỏng đoán các khóa bí mật.

Trong các nghiên cứu liên quan đến mô hình tấn công khóa quan hệ, có thể kể đến nghiên cứu [5]. Nghiên cứu này được công bố năm 2010 và tạo ra nhiều tiếng vang trong các ấn phẩm điện tử của Liên bang Nga, nhưng những kết quả trong nghiên cứu này không được giải thích bởi bất cứ một cơ sở nào, trong khi nội dung chính của nó trình bày về việc bẻ gãy chuẩn mật mã của Liên bang Nga trong những máy tính xách tay yếu chỉ trong vài giây. Do đó, tính khả thi của các phương pháp trong bài báo này là khó thực hiện. Để có căn cứ phủ nhận những điều này, các tác giả trong [4] đã đưa ra phân tích cụ thể, rõ ràng những thiếu sót nghiêm trọng và không có tính thực tiễn đã được trình bày trong [5]. Từ đó, đưa ra cơ sở phân tích rằng độ phức tạp trung bình trong phương pháp của [5] là không nhỏ hơn so với phương pháp thám mã vét cạn, tức là không thể thực hiện được trong thực tiễn.

Độ an toàn trên thực tế của GOST 28147-89

Trong phần này, tác giả đưa ra bảng tổng hợp các nghiên cứu nổi tiếng khi phân tích độ an toàn của GOST 28147-89. Chú ý rằng, độ phức tạp tính toán được xác định bởi phép mã hóa theo thuật toán GOST 28147-89, bộ nhớ trong bảng được đo bởi số lượng khối (64 bit = 8 byte).

Mặc dù có rất nhiều công trình thực hiện việc đánh giá độ an toàn lên GOST 28147-89, nhưng đến thời điểm này không một tấn công nào cho thấy có thể thực hành được lên GOST 28147-89 với kích thước khối là 64 bit. Trong các tấn công hiện nay, những giới hạn về dung lượng được xử lý chỉ bằng một khóa theo các tham số của thuật toán (độ dài khối và khóa ở dạng bit) về mặt căn bản là lớn hơn rất nhiều so với dung lượng tối thiểu sử dụng trong các ứng dụng thực tế. Như vậy, khi thực hiện theo các tham số an toàn trong điều kiện sử dụng thực tế của thuật toán, có thể khẳng định rằng, đến thời điểm hiện tại không có một tấn công nào có thể thực hiện lên GOST 28147-89 mà độ phức tạp của nó nhỏ hơn phương pháp thám mã vét cạn.

Do vậy, theo quan điểm về độ an toàn, thuật toán GOST 28147-89 vẫn đứng vững trước các tấn công thám mã. Cho đến nay, mặc dù có nhiều thuật toán mới được thiết kế, có nhiều đề xuất tấn công, nhưng chúng ta không thể bỏ qua thuật toán GOST 28147-89 - một thuật toán được thiết kế độ an toàn cao và được chứng minh bởi thời gian và sự phát triển của khoa học công nghệ.

Một trong những lợi thế lớn của GOST 28147-89 là khả năng cài đặt nhanh. Vấn đề này sẽ được chúng tôi nghiên cứu và trình bày trong những bài tiếp theo.

Tài liệu tham khảo

[1]. N. Courtois. Security Evaluation of GOST 28147-89 In View Of International Standardisation. Cryptology ePrint Archive 2011/211.

[2]. T. Isobe. A Single-Key Attack on the Full GOST Block Cipher. FSE 2011. LNCS, vol. 6733, Springer, 2011, pp. 290–305.

[3]. I. Dinur, O. Dunkelman, A. Shamir. Improved Attacks on Full GOST. FSE 2012, LNCS 7549, pp. 9-28, 2012.

[4]. V. Rudskoy. On zero practical significance of “Key recovery attack on full GOST block cipher with zero time and memory. Cryptology ePrint Archive 2010/111.

[5]. E. Fleischmann, M. Gorski, J.-H. Huhne, S. Lucks. Key Recovery Attack on full GOST Block Cipher with Zero Time and Memory, WEWoRC, 2009.

[6]. V. Rudskoy, A. Dmukh. Algebraic and Differential Cryptanalysis of GOST: Fact or Fiction. Proceedings of CTCrypt 2012.

TS. Nguyễn Văn Long, Viện Khoa học - Công nghệ mật mã, Ban Cơ yếu Chính phủ