Об алгоритмической реализации s-боксов 16х16 со структурами ARX и «Бабочка» | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/32

Об алгоритмической реализации s-боксов 16х16 со структурами ARX и «Бабочка»

Предложены способы алгоритмической реализации новых s-боксов размера 16x16 бит, вычислительная сложность и криптографические характеристики которых улучшены по сравнению со способами, исследованными ранее. Первый способ реализует s-боксы на основе ARX (Add-Rotate-Xor)-структуры; второй - на основе структуры «Бабочка» с использованием нелинейных подстановочных s-боксов размера 8x8 бит. Максимальная разностная характеристика (МРХ) предложенных s-боксов с ARX-структурой равна 18/216, со структурой «Бабочка» -10/216. Максимальная линейная характеристика (МЛХ) s-боксов с ARX-структурой равна 764/215, со структурой «Бабочка» - 512/215. Минимальная степень нелинейности среди всех нетривиальных линейных комбинаций координатных функций предложенных s-боксов равна 15. Установлено, что использование предложенных s-боксов размера 16x16 бит в раундовых подстановках алгоритмов AES и «Кузнечик» позволяет улучшить их некоторые криптографические свойства. Для усечённых алгоритмов AES и «Кузнечик», реализующих несколько раундов шифрования, существенно снижены верхние оценки МРХ и МЛХ по сравнению с версиями алгоритмов, использующих штатные s-боксы.

On algorithmic implementation of 16-bit s-bo-xes with arx and butterfly structures.pdf Цель работы - оценить важнейшие характеристики некоторых способов реализации s-боксов (узлов замены) размера 16 x 16 бит и перспективы их использования в итеративных алгоритмах блочного шифрования. Нелинейные отображения векторного пространства Vn (s-боксы размера n x n бит) в симметричных алгоритмах блочного шифрования обычно реализуются в виде таблиц, содержащих множество всех образов. Для хранения одного такого массива требуется n2 бит памяти. Это вынуждает в алгоритмах блочного шифрования использовать s-боксы малых размеров (8x8 бит в алгоритме «Кузнечик», 4x4 в алгоритме «Магма», 6x4 в DES, 8x8 в AES). В данной работе предложены способы алгоритмической реализации новых s-боксов большого размера (16x16 бит). При алгоритмическом вычислении значений s-боксов больших затрат памяти не требуется. Обозначим b : Z2n ^ Vn - биективное отображение числа X G Z2 n в его двоичное представление, b(X) = X = (ж0,... , жп-1); (X1 ,X2) - конкатенация двух векторов; X1,X2 G Z2n -полублоки входного блока X s-бокса, X = (X1,X2) G Z2i6; b(X1) = X1 = (жо,...,жт), b(X2) = X2 = (Ж8,...,Ж15), b(X) = (жо,...,Ж15); Y ^ t (Y ^^ t) -циклический сдвиг координат вектора Y на t бит вправо (влево); ® - умножение в поле F(28) = F2[x]/(ж8 + ж4 + ж3 + ж + 1); а254 = а-1 -обратный к ненулевому элементу а поля F(28); S : Vm ^ Vm - функция s-бокса размера m x m бит. Для ж G Vm и ж' = ж ф a G Vm (пар текстов с фиксированной разностью a G Vm) и s-бокса S : Vm ^ Vm определим разностную характеристику (РХ) DPS(a,b) = |{ж G Vm : S(ж) ф S(ж') = b}|/2m - вероятность появления случайной величины- разности b G Vm выходных текстов S^) и S(ж'). Максимальная разностная характеристика (МРХ) s-бокса определена как = max DPS(a, b). Для вектора a = (a0,..., am-1) G Vm определим линейную булеву функцию la(x0,... , xm-1) = m_ 1 = ф ajXj. Для некоторых a, b G Vm и s-бокса S : Vm ^ Vm с компонентными функци-i=0 ями (S0,... , Sm-1) определим линейную характеристику (ЛХ) LPS(a,b) = 21-m|{x G G Vm : la(x) = lb(S(x))}| - 1. Максимальную линейную характеристику (МЛХ) s-бокса S определим как = max LPS(a,b). Пусть deg f - степень нелинейности функции f. Минимальная степень нелинейности среди всевозможных линейных комбинаций координатных функций определена в [1] как AS = min {deg(la(S(x)))}. Производительность s-боксов измеряется в Мбайт/с, ёмкость памяти - в байтах. Алгоритмы AES и «Кузнечик» при использовании в них s-боксов размера 16x16 бит вместо стандартных обозначим AES16 и К16. 1. Описание метода алгоритмической реализации s-бокса 16x16 с ARX-структурой s-Боксы на основе ARX-структуры используют операции сложения, циклического сдвига и побитового XOR-сложения векторов. Эти операции не требуют существенных затрат памяти на хранение предварительно вычисленных таблиц [2, 3], характеризуются низкой ресурсоёмкостью в программных и аппаратных реализациях и выполняются менее чем за половину такта процессора. Раундовые подстановки g : V16 ^ V16, i = 1, 2, s-боксов 16x16 с ARX-структурой, предлагаемые в данной работе, в общем виде представимы в виде композиции двух преобразований fi1, fi2 : V16 ^ V16: gi(X) = fi2 ◦ fi1(X). (1) Построены перспективные схемы с ARX-структурой с точки зрения сочетания положительных криптографических характеристик с высокой производительностью программной реализации. Первый вариант раундового преобразования (1) s-бокса обозначим g1, для него fn(X) = (b(((X1 ^ 2)+X2) mod 28),^2), MX) = (Xbb(((X «< 1)+C) mod 28)®^1). Второй вариант раундового преобразования (1) s-бокса обозначим g2, для него f21(X) = (b(((X1 ^ 1)+X2) mod 28),X2), f22(X) = (Xbb(((X ^ 2)+C) mod 28)®X1). Здесь C G Z28 -константа, C = 185 для g1 и C = 100 для g2. Обозначим = g^, = g2 - предложенные s-боксы с ARX-структурой. Экспериментально установлено, что для предложенных s-боксов = = 18/216, ^i = 762/215, ^ = 764/215, A^i = A^ = 15. В табл. 1 приведены частоты значений DP в таблицах разностей и Видно, что частота встречаемости МРХ невелика, поэтому при реализации разностной атаки сложно подобрать несколько s-боксов с МРХ более чем в одном рауде шифрования. Таблица 1 Частота встречаемости значений DP в таблицах разностей ^>1 и ^>2 216 ■ DP 0 2 4 6 8 10 12 14 16 18 2,6 ■ 109 1,3 ■ 109 3,3 ■ 108 5,4 ■ 107 6,8 ■ 106 678529 56603 4062 280 14 ¥>2 2,6 ■ 109 1,3 ■ 109 3,3 ■ 108 5,4 ■ 107 6,8 ■ 106 677386 56885 4058 256 7 2. Об алгоритмической реализации s-бокса 16x16 со структурой «Бабочка» В [4, 5] предложены способы построения s-боксов 8x8 со структурой «Бабочка» с использованием умножения в GF(24) и подстановок меньших размеров (4x4 бит), реализующих мономы в GF(24). В данной работе предложены два типа s-боксов 16x 16 со структурой «Бабочка» с использованием умножения в GF(28) и подстановок меньших размеров (8x8 бит), реализующих мономы в GF(28). Обозначим ф^ : V16 ^ V16, i =1, 2: ^(X) = ^(XbX2) = (b(Fi1(X1,X2)),b(Fi2(X2,Fi1(X1,X2)))) = (X ,X2). За основу первого типа s-боксов 16x16 взята структура из [4]. Обозначим его ф^ для него h1(X1), X2 = 0, (X1 0 X2)254, X2 = 0, MX2), X1 = 0, X1 0 (X2)254, X1 = 0, F11 (Xb X2) = X1 F12 (X2, X1) = X2 где F11(X1,X2), F12(X2,X1) : F(216) ^ F(28) -биективные функции по X1 и X2 соответственно; h1,h2 : F(28) ^ F(28) -нелинейные подстановки, реализующие могде ж номы в F2[ж]/(ж8 + ж4 + ж3 + ж + 1). При h2(ж) G {ж254,ж253} и ^1(ж) k G {28, 37, 56, 73, 74,131,146,148,164,191,193, 239, 247, 251, 253, 254}, отображение ф1 биективно, p^ = 10/216, Л^ = 15 и = 512/215. За основу второго типа s-боксов 16x16 взята структура из [5]. Обозначим его ф2, для него (X1)254, X2 = 0, X1 0 h1 ¥>2 Ф x 1, таблица [6] Размер 8 x 8 8 x 8 8 x 8 16 x 16 16 x 16 16 x 16 16 x 16 Ps 4/28 12/28 8/28 18/216 18/216 10/216 4/216 Ss 12/27 28/27 28/27 762/215 764/215 512/215 256/215 As 7 6 7 15 15 15 15 3. Верхние оценки разностной и линейной характеристик для алгоритмов AES16 и K16 При реализации разностной атаки s-бокс называется активным для раунда итеративного алгоритма блочного шифрования, если разность поступающих на этом раунде ему на вход текстов не равна нулю. Пусть L : Vm ^ Vm - линейное преобразование алгоритма блочного шифрования на основе SP-сети с размером блока m-n бит. Обозначим вг, i = 1,... , 4, число активных s-боксов на i-м раунде. Степень ветвления (branch number) линейного преобразования L (обозначим в2" или вг в случае, когда L является композицией всех используемых в алгоритме линейных преобразований) есть e^ = min {w(x) + w(L(x))}, где w(x) = w(xi, x2,..., xn) = |{x = 0 : x G Vm, i = 1,..., n}|. Степень ветвления алгоритма блочного шифрования на основе SP-сети можно определить как минимальное возможное число активных s-боксов, участвующих в первых двух раундах шифрования. Известно [7], что для AES в2 = 5, в4 = (в2)2 = 25, для алгоритма «Кузнечик» в2 = 17 [8]. Для AES16 в2 = 5, в4 = 15; для К16 в2 = 9. Обозначим ak, bk G V^ разности пар входных и выходных текстов размера mn бит к-го раунда алгоритма блочного шифрования на основе SP-сети с s-боксами Si : Vm ^ Vm, i = 1,... ,n; DP2(a1,b2) (DP4(a1,b4)) - РХ двух (четырёх) раундов алгоритма шифрования на основе SP-сети; LP2(a1, b2) (LP4(a1, b4)) -ЛХ двух (четырёх) раундов алгоритма шифрования на основе SP-сети. Теорема 1 [9]. Для любой ненулевой разности a1 G V^.ra пары входных текстов РХ двух раундов алгоритма шифрования на основе SP-сети верно неравенство {2m-1 2m-1 ] max max V {DP(u, j)}в2, max max V {DPSi(j,u)}e2 > KKn 1

Ключевые слова

s-бокс 16x16, алгоритмическая реализация, ARX, «Бабочка», максимальная разностная характеристика, максимальная линейная характеристика, степень нелинейности, 16-bit s-box, algorithmic implementation of s-boxes, ARX, Butterfly, maximum differential probability, maximum linear probability, nonlinear order

Авторы

ФИООрганизацияДополнительноE-mail
Комиссаров Семён МихайловичНИЯУ МИФИстудентsemenkomissarov@gmail.com
Всего: 1

Ссылки

Menyachikhin A. Spectral-linear and spectral-difference methods for generating cryptographically strong S-boxes // CTCrypt Preproc. Yaroslavl, 2016. P. 232-252. https://mjos.fi/doc/rus/CTCrypt2016Preproceedings.pdf
Фомичев В. М., Лолич Д. М., Юзбашев А. В. Алгоритмическая реализация s-боксов на основе модифицированных аддитивных генераторов // Прикладная дискретная математика. Приложение. 2017. №10. С. 102-104.
Бобров В. М, Комиссаров С. М. О свойствах двух классов s-боксов размера 16x16 // Прикладная дискретная математика. Приложение. 2018. №11. С. 57-61.
Jimenez R. A. Generation of 8-bit s-boxes Having Almost Optimal Cryptographic Properties Using Smaller 4-bit s-boxes and Finite Field Multiplication. Havana: Havana University, Institute of Cryptography, 2017. http://www.cs.haifa.ac.il/~orrd/LC17/paper60.pdf
Fomin D. B. New Classes of 8-bit Permutations Based on a Butterfly Structure. CTCrypt. Suzdal, 2018. https://ctcrypt.ru/files/files/2018/09_Fomin.pdf
Wood C. A. Large Substitution Boxes with Efficient Combinational Implementations. Thesis. Rochester Institute of Technology, 2013.
Daemen J. and Rijmen V. The Design of Rijndael, AES - the Advanced Encryption Standard. Springer Verlag, 2002.
AlTawy R. and Youssef A. M. A meet in the middle attack on reduced round Kuznyechik // IEICE Trans. 2015. V. 98-A. P. 2194-2198.
Park S., Sung S.H., Lee S., and Lim J. Improving the upper bound on the maximum differential and the maximum linear hull probability for SPN structures and AES // LNCS. 2003. V. 2887. P. 247-260.
 Об алгоритмической реализации s-боксов 16х16 со структурами ARX и «Бабочка» | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/32

Об алгоритмической реализации s-боксов 16х16 со структурами ARX и «Бабочка» | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/32