Hiệu quả cài đặt của thuật toán GOST 28147-89

10:15 | 08/10/2019

Sau những đánh giá độ về an toàn của GOST 28147-89 ở Tạp chí An toàn thông tin số 3 (047) 2018, trong số này chúng tôi tiếp tục giới thiệu đến bạn đọc một số đặc trưng cài đặt của thuật toán GOST 28147-89. Hiện nay thuật toán này có tên gọi là thuật toán MAGMA trong chuẩn GOST R 34.12-2015. Tuy nhiên, để độc giả có cái nhìn chính xác về một thuật toán mã khối kinh điển từ những năm 90 của thế kỷ XX, trong bài viết này vẫn sử dụng tên chuẩn cũ là GOST 28147-89. Cụ thể, chúng tôi sẽ thảo luận về một số hướng có tính thời sự khi tối ưu hóa tốc độ trong cài đặt phần mềm của GOST 28147-89, và chỉ ra rằng thuật toán GOST 28147-89 có rất nhiều tính chất mà có thể khai thác được một cách hiệu quả trong cài đặt.

Trong những năm gần đây, việc tập trung vào tối ưu hóa hiệu suất cài đặt phần mềm đã có xu hướng sử dụng các tính toán song song nhiều hơn. Điều này là do tốc độ xung nhịp CPU chậm hơn. Trước đây, tốc độ của chương trình tăng lên độc lập với người phát triển phần mềm, do công suất xử lý CPU và trao đổi dữ liệu với bộ nhớ và các thiết bị ngoại vi tăng liên tục. Còn bây giờ nhiệm vụ này thuộc về các lập trình viên, để đạt được hiệu suất ứng dụng tối đa, các lập trình viên phải xem xét các khả năng song song hóa có trong hệ thống tổng thể. Những khả năng này bao gồm:

• Song song hóa nhiệm vụ giữa các nhân của bộ vi xử lý;

• Sử dụng các mở rộng véc-tơ của CPU;

• Sử dụng GPU.

Thuật toán GOST 28147-89 sẽ giúp tăng hiệu quả thực thi theo tính năng được mô tả ở trên. Bên cạnh đó, chúng tôi sẽ chú ý đến những cách tăng hiệu quả thực thi nhưng chủ yếu dựa vào các thuộc tính của chính thuật toán mã hóa. Đồng thời, chúng tôi cũng sẽ xem xét vấn đề xây dựng các cài đặt nhẹ (không tốn nhiều tài nguyên và năng lượng).

GOST 28147-89 và mở rộng véc-tơ của CPU

Nói về các tính toán song song trên một máy tính, thông thường là nói đến việc tính toán cùng một lúc trên nhiều vi xử lý (hoặc trên nhiều nhân của một bộ vi xử lý). Nhưng bên cạnh đó cũng tồn tại khả năng tính toán song song bên trong một nhân của bộ vi xử lý – đó là việc sử dụng cơ chế véc-tơ.

Cơ chế véc-tơ cho phép thực hiện nhiều thao tác trong một chu kỳ của bộ vi xử lý, ví dụ khi thực hiện cộng đồng thời các số.

Khả năng thực hiện các phép toán có dạng véc-tơ trong các hệ thống máy tính hiện đại trên nền tảng x86/x64 được cung cấp bởi các phần mở rộng của bộ xử lý đặc biệt SSE và AVX. Những tiện ích mở rộng này bổ sung các thanh ghi mới có độ dài từ 128 bit trở lên, cũng như các cơ chế để làm việc với chúng.

Dưới đây, sẽ đưa ra phương pháp sử dụng các tiện ích mở rộng này để thực hiện các cài đặt thuật toán GOST 28147-89 một cách hiệu quả (phần mô tả ý tưởng để sử dụng các tiện ích mở rộng này cũng có thể được tìm thấy trong [5]).

Như đã biết, một vòng của thuật toán GOST 28147-89 bao gồm phép cộng theo modulo 232, 8 S-hộp (hộp thế) 4 bit và phép dịch vòng sang trái 11 bit. Điều này cho thấy, hiệu suất tốt nhất chỉ có thể đạt được khi sử dụng các cơ chế véc tơ để xử lý vài khối tại một thời điểm. Hơn nữa, càng nhiều khối được tính toán cùng một lúc, tốc độ thực thi tăng sẽ càng lớn. Kích thước khối trong thuật toán GOST 28147-89 là 64 bit, nhưng do thiết kế theo mạng Feistel, tất cả các phép biến đổi sử dụng nhiều tài nguyên chỉ được thực hiện trên một nửa khối, tức là trên 32 bit dữ liệu. Tính năng này của thuật toán cho phép chúng ta có thể cộng các khóa vòng hoặc phép dịch vòng đồng thời một vài khối khi sử dụng thanh ghi AVX.

Thực tế là trong phần mở rộng AVX, lệnh VPSHUFB đã được thêm vào, sao chép các byte từ thanh ghi nguồn sang thanh ghi đích theo thứ tự được mô tả trong thanh ghi chỉ mục. Do đó cần đặc biệt chú ý đến các nút thay thế sử dụng S-hộp 4 bit.

Hình 1. Minh họa sử dụng cơ chế véc tơ cho tính toàn qua tầng S-hộp

Nếu bảng S-hộp được ghi vào thanh ghi nguồn và dữ liệu cần xử lý được lưu vào thanh ghi chỉ mục, thì bằng cách sử dụng những cơ chế này, chúng ta có thể thực hiện thay thế 16 nửa byte cho mỗi chu kỳ xung nhịp của bộ vi xử lý. Và kết quả là cho phép tăng tốc đáng kể so với cài đặt tuần tự các phép thế.

Cần lưu ý rằng việc sử dụng hiệu quả cơ chế véc tơ này là do thuật toán GOST 28147-89 sử dụng các S-hộp 4 bit. Thật vậy, vì lệnh VPSHUFB chỉ sử dụng 4 bit thấp hơn của mỗi byte trong thanh ghi chỉ mục, nên chúng ta chỉ có thể thay thế các bit tương ứng. Ngoài ra, một bảng thay thế cho 4 bit có kích thước 24 × 4 = 64 bit, cho phép hai bảng được đặt trong một thanh ghi 128 bit cùng một lúc.

Bây giờ chúng ta sẽ xem xét trong trường hợp mã pháp tổng thể. Hình 2 dưới đây là đồ thị tốc độ thực thi của thuật toán GOST 28147-89 ở chế độ Gamma (một chế độ thường được sử dụng trong các giao thức mật mã) theo luồng dữ liệu trên máy chủ (№1), đây cũng là ví dụ trên các máy tính thông thường.

Hình 2. Trên máy chủ sử dụng chip Intel Xeon E5-2680

Khi cài đặt các giao thức TLS và IPsec để kiểm tra tính toàn vẹn của dữ liệu sử dụng chế độ tạo MAC theo chuẩn GOST 28147-89, thì yêu cầu đặt ra là đồng thời cần mã hóa và tính MAC. Dưới đây là đồ thị minh họa sự phụ thuộc tốc độ mã hóa cùng với việc tính MAC vào số lượng luồng dữ liệu. Trên đồ thị, chế độ MultiPacket thể hiện việc đồng thời xử lý một vài gói dữ liệu.

Hình 3. Tốc độ của GOST 28147-89 khi thực hiện đồng thời mã hóa và tính MAC

GOST VÀ GPU

Khi xem xét tính hiệu quả cài đặt của thuật toán mật mã không thể không nhắc đến hướng cài đặt trên GPGPU (General-purpose graphics processing units).

GPGPU là kỹ thuật sử dụng bộ vi xử lý đồ họa trong tính toán, có nghĩa là không giải quyết các bài toán liên quan đến xử lý đồ họa, ví dụ như trong mật mã.

Bây giờ chúng ta hãy xem xét lợi thế khi sử dụng GPU để giải quyết các bài toán tính toán so với các bộ vi xử lý trung tâm.

• Đầu tiên là số lượng nhân. Nếu như bộ vi xử lý trung tâm có trung bình từ 2 đến 16 nhân, thì bộ vi xử lý đồ họa có từ vài trăm đến vài nghìn nhân (ví dụ bộ vi xử lý đồ họa GeForce GTX 970 có 1664 nhân, còn Radeon R9 295X2 là 5632 nhân).

• Thứ 2 là chức năng của các transitor. Ở bộ vi xử lý trung tâm phần lớn các transitor được sử dụng cho Cache và để điều khiển các luồng thực thi, thì ở thời điểm này trong bộ vi xử lý đồ họa phần lớn các transitor được sử dụng cho mục đích tính toán.

• Thứ 3 là tốc độ đọc ghi từ bộ nhớ thì bộ vi xử lý đồ họa lớn hơn nhiều lần. Ví dụ khi sử dụng bộ vi xử lý Intel Xeon E5-2670 và 4 module RAM DDR3, thì tốc độ của bộ nhớ là khoảng 80 Gb/s, trong khi tốc độ của bộ vi xử lý đồ họa GeForce GTX 979 và Radeon R9 295X2 tương ứng là 224 và 680 Gb/s.

Bây giờ chúng ta chứng minh rằng GOST 28147-89 là thích hợp để cài đặt trên GPU. Trước tiên chúng ta cần trình bày về nguyên lý tính toán trên GPU, bất kỳ chương trình nào trên GPU đều chứa một số bước cơ bản, được hiển thị trong Hình 4.

Hình 4. Bước tính toán cơ bản trên GPU

Dữ liệu ở bước tính toán trên GPU được thực hiện trong vài nghìn luồng. Các luồng không được thực hiện đồng thời, mà được thực hiện theo nhóm. Trong thời gian làm việc của một nhóm, tất cả tài nguyên của bộ vi xử lý đồ họa (các véc-tơ, thanh ghi, bộ nhớ,...) được chia thành các luồng của nhóm này, nên số lượng luồng trong nhóm phụ thuộc vào lượng tài nguyên sử dụng để tính toán một luồng. Rõ ràng càng ít tài nguyên để xử lý một luồng thì càng có nhiều luồng được xử lý đồng thời trên GPU và do đó tốc độ xử lý của chương trình sẽ càng cao. Cho nên để đạt được tốc độ xử lý cao trên GPU cần tối thiểu hóa lượng tài nguyên được sử dụng để thực hiện tính toán.

Theo quan điểm này, thuật toán GOST 28147-89 có hàng loạt lợi thế. Đầu tiên là lợi thế trong lược đồ khóa với những tính toán đơn giản mà không yêu cầu nhiều tài nguyên. Thứ 2 có thể đơn giản hóa hàm vòng sử dụng các bảng tính trước. Cụ thể từ 8 S-hộp 4 bit và phép dịch vòng ta có thể biến đổi về phép cộng theo modulo 2 của 4 luồng 8 bit. Tất cả những điều này làm giảm số lượng tài nguyên cài đặt và nó là lợi thế của GOST 28147-89 cho làm việc trên GPU.

Hình 5. Cải tiến cài đặt cho GOST 28147-89

Cách tối ưu hóa biến đổi cơ sở của thuật toán GOST 28147-89 để cài đặt trên GPU có thể tham khảo trong [4]. Để giảm số lượng phép truy cập bộ nhớ, tác giả đề xuất phương án cài đặt các S-hộp sử dụng hàm bool và cách này cho phép tăng đáng kể tốc độ của thuật toán.

Hình 6. Tốc độ cài đặt trên GPU của một số thuật toán mật mã

Trên Hình 6 là một số kết quả cài đặt trên GPU của một số thuật toán mã khối. Tất cả các cài đặt được thực hiện trên máy tính thông thường như đã giới thiệu bên trên. Trong quá trình đánh giá sử dụng chế độ ECB với khối dữ liệu 256 Mb (Megabyte). Tốc độ được cho theo đánh giá lý thuyết và thực tế. Kết quả về tốc độ lý thuyết là kết quả mã hóa trực tiếp trên GPU, còn kết quả thực tế là bao gồm cả tốc độ mã hóa và tốc độ copy vào bộ nhớ GPU và từ bộ nhớ GPU vào RAM.

Như thấy trong đồ thị, tốc độ mã hóa thực tế trên GPU nhỏ hơn nhiều so với tốc độ lý thuyết. Điều này là do tốc độ đọc ghi bộ nhớ của GPU và RAM. Đây là lý do tạo ra những khó khăn sử dụng GPU trong thực tế.

GOST và mật mã hạng nhẹ

Những năm gần đây mật mã được phát triển theo hướng thiết kế các thuật toán hạng nhẹ (lightweight). Mục tiêu chính là tạo ra những thuật toán để sử dụng trong các môi trường có tài nguyên hạn chế như smart-card, sensor, thẻ RFID,.... Việc cài đặt chúng thường là trên phần cứng sử dụng các mạch tích hợp (ASIC) và phần mềm là mã nguồn đối với các minicontroller lập trình được.

Mục đích của mật mã hạng nhẹ là tối thiểu hóa tài nguyên cài đặt cho thuật toán mà vẫn giữ được độ an toàn cần thiết. Tài nguyên ở đây được hiểu rằng là năng lượng tiêu thụ và giá thành của môi trường cài đặt. Theo hướng này thì các cài đặt phần cứng có lợi thế hơn phần mềm. Tham số cài đặt cài đặt phần cứng được hiểu là diện tích của mạch thực thi cần thiết trên môi trường phát triển. Diện tích này càng nhỏ càng tốt. Tuy nhiên điều này là phụ thuộc nhiều vào công nghệ mà người thiết kế sử dụng. Cho nên tham số cơ sở để đánh giá trong các cài đặt phần cứng đối với mật mã hạng nhẹ là sử dụng các cổng tương đương (GE – Gate Equivalents). Đại lượng này là chỉ số lượng các phần tử NAND có thể sử dụng trên một đơn vị diện tích. Như vậy thì càng ít cổng GE càng tốt. Hình 7 là về số cổng GE yêu cầu cho cài đặt một số thuật toán mật mã.

Với những thông số cài đặt như vậy, GOST 28147-89 thuộc nhóm các thuật toán hạng nhẹ và phù hợp để sử dụng cài đặt cho các môi trường có tài nguyên hạn chế như smart-card, sensor, thẻ RFID....

Hình 7. Thông số cài đặt phần cứng một số thuật toán mật mã

Kết luận

Theo quan điểm cài đặt, ta thấy rằng GOST 28147-89 là rất có hiệu quả vì nó có nhiều lợi thế. Thứ nhất là có lược đồ khóa đơn giản. Thứ hai là sử dụng S-hộp 4 bit sẽ phù hợp trong cài đặt phần mềm khi sử dụng các cơ chế véc tơ, còn cài đặt phần cứng yêu cầu ít tài nguyên. Và thứ 3 là có biến đổi vòng đơn giản sẽ tạo thuận tiện cho cài đặt phần mềm cũng như phần cứng. Như trong số trước, đến thời điểm hiện tại, GOST 28147-89 không chỉ an toàn về mặt mật mã mà còn cài đặt hiệu quả trên các môi trường khác nhau. Khi sử dụng lược đồ khóa cải tiến được trình bày trong [3, 6] còn có thể loại bỏ được các tấn công lý thuyết (phương pháp Isobe và Dinur-Dunkelman-Shamir).

Tài liệu tham khảo

[1]. Poschmann, A., Ling, S., Wang, H.: 256 bit standardized crypto for 650 GE – GOSTrevisited. In: Mangard, S., Standaert, F.-X. (eds.) CHES 2010. LNCS, vol. 6225,pp. 219–233. Springer, Heidelberg (2010)

[2]. Bogdanov, A., Leander, G., Knudsen, L., Paar, C., Poschmann, A., Robshaw, M.,Seurin, Y., Vikkelsoe, C.: PRESENT - An Ultra-Lightweight Block Cipher. In:Paillier, P., Verbauwhede, I. (eds.) CHES 2007. LNCS, vol. 4727, pp. 450–466.Springer, Heidelberg (2007)

[3]. Дмух А.А., Маршалко Г.Б. О возможности модификации алгоритма шифрования ГОСТ 28147-89 с сохранением приемлемых эксплуатационных характеристик. Материалы XV международной конференции “РусКрипто’2013”.

[4]. Кролевецкий А.В.: Эффективная реализация алгоритма ГОСТ 28147-89 с помощью технологии GPGPU. Материалы XVI международной конференции “РусКрипто’2014”.

[5]. Достигаем феноменальной скорости на примере шифрования ГОСТ 28147—89. Журнал “Хакер”. https://xakep.ru/2013/10/19/shifrovanie-gost-28147-89/

[6]. A. A. Dmukh, D. M. Dygin, G. B. Marshalko, “A lightweight-friendly modification of GOST block cipher”, Матем. вопр. криптогр., 5:2 (2014), 47–55