Об интегральных различителях алгоритмов блочного шифрования, основанных на обобщениях схемы Фейстеля | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/27

Об интегральных различителях алгоритмов блочного шифрования, основанных на обобщениях схемы Фейстеля

Интегральный метод и его модификации широко применяются для анализа известных алгоритмов блочного шифрования, например KHAZAD, PRESENT, RECTANGLE, PRINCE, HIGHT. Основу метода составляет структура мультимножества текстов, сохраняемая функцией зашифрования на некотором числе раундов и применяемая для построения интегрального различителя. В работе рассматриваются интегральные различители некоторых обобщений схемы Фей-стеля. Так, описан 3-раундовый интегральный различитель алгоритма блочного шифрования PICARO. Для этого исследовано влияние небиективного s-бокса и расширяющей матрицы алгоритма PICARO на интегральные свойства мультимножества текстов в зависимости от числа раундов.

On integral distinguishers of block ciphers based on generalized feistel schemes.pdf В [1] для анализа XSL-алгоритмов блочного шифрования предложен интегральный метод криптоанализа. В настоящее время известны его различные модификации, например метод на основе разделяющего свойства [2], метод на основе мультимножеств [3]. Предложены атаки на такие известные алгоритмы блочного шифрования, как AES, PRESENT, DES, SIMON 32, CAMELLIA, KHAZAD, RECTANGLE, PRINCE, HIGHT и т. д. Идея интегрального метода состоит в нахождении структуры мультимножества текстов, сохраняемой на некотором числе раундов функцией зашифрования и используемой для построения интегрального различителя, с помощью которого восстанавливаются отдельные биты или целиком ключ шифрования. Пусть N - множество натуральных чисел; N0 = N U {0}; Vn, - n-мерное векторное пространство над полем GF(2); I(A) -индикатор выполнения условия A; 0n - нулевой n-мерный вектор. Естественным образом пронумеруем векторы Vn. Вектору n (ai,... , an) Е Vn поставим в соответствие число d = 2n-Jaj. Для удобства далее будем использовать обозначение j=i vdn) = (vdS,..., v2) = (ai,..., an). Пусть Q - мультимножество векторов с носителем Vn, первичная спецификация [4] (n)\C0 f (n) \°2n~1 имеет вид Q = (^^J ,... , (^"-J , где вектор v(n) встречается в Q ровно С раз, c0,..., c2n-1 е N0. Интегралом мультимножества Q [1] называется величина Q®, заданная условием 2"-1 f ^ \ /2П -1 2" - 1 \ Q® = 0 (vi(n) ■ сЛ = 0 (vS) ■ c),..., е (vg ■ c) , i=0 v 7 \ i=0 i=0 / где с = c mod 2 для i = 0,... , 2n - 1. Говорят [1], что мультимножество Q с носителем Vn имеет: 1) интегральное свойство S, если Q® = 0n; 2) интегральное свойство A, если c = 1 для каждого i Е {0,... , 2n - 1}; 3) интегральное свойство C, если существует такое единственное i G {0,..., 2n - 1}, что с* = 0; 4) интегральное свойство U, если мультимножество Q не имеет свойства S [3]. Очевидно, что интегральные свойства A и C подразумевают свойство S. Таким образом, для произвольного мультимножества Q однозначно определена функция : Q ^{U,S}. Пусть n = mr, r > 1. Вектор v* можно рассматривать как элемент r-мерного векторного пространства над полем GF(2m), т.е. v(n) = (ui,1, ...,u*,r), ui,j G GF(2m), j = 1,..., r, i = 0,..., 2n - 1. Пусть i G {1,...,r} и Q(i) -мультимножество с носителем GF(2m) и первичной спецификацией Q(i) = (v0m)) ,..., , где bj = j- I fut,j = v(m)) ct t=0 для j = 0,... , 2m - 1. Для мультимножества Q(i) аналогичным образом определяются интегральные свойства. Мультимножеству Q ставится в соответствие упорядоченный набор мультимножеств (Q(1),... , Q(r)), для каждого из которых, в свою очередь, определено интегральное свойство. Упорядоченный набор соответствующих интегральных свойств называется вектором интегральных свойств мультимножества Q, например (A, C, C, C), если r = 4. Пусть g : Vn х Vd ^ Vn - раундовая функция итерационного алгоритма блочного шифрования, у которого частичная /-раундовая функция зашифрования /J)1,...,fci) : Vn ^ Vn задана условием /J)1,...,fci) : a ^ gk . ..gki(a) где gki(a) = g(a,ki) для всех k1,..., kj G Vd, a G Vn. Пусть Q0 - мультимножество открытых текстов с носителем V^ и первичной спецификацией (v0n) ) ,... , (v2n)_1 ) . При t = 1,... , l мультимножество Qt таn) ково, что элемент gkt ... gk1 (v* I встречается в нём ровно с* раз для каждого i G G {0,..., 2n - 1}. Назовём l-раундовым интегральным различителем алгоритма блочного шифрования с раундовой функцией g такую последовательность мультимножеств Q0=eQ01),...,Q0r)T,..., Qi=eQ( 1),...,Q(r)T, что выполнены следующие свойства: 1) для каждого j G {0,...,l - 1} существует i G {1,... , r}, удовлетворяющее условию ^(Qj^) = U; 2) ^m(Q(t)) = U для каждого i G {1,... , r}. В данной работе исследуются интегральные свойства алгоритма блочного шифрования PICARO [5], основанного на схеме Фейстеля. Доказано существование 3-раун-дового различителя, при построении которого использованы свойства небиективного s-бокса и расширяющей матрицы, являющихся компонентами раундовой функции. В настоящее время активно исследуются обобщения схемы Фейстеля [6 - 8]. Для некоторых из них построены интегральные различители для длины регистра r ^ 4. В частности, пусть справедливы следующие условия: 1) длина регистра r = 4; 2) функция усложнения h такова, что переводит мультимножество с вектором интегральных свойств (A, C, C, C) в мультимножество с вектором (U, U, U, U); 3) мультимножество Q0 таково, что его вектор интегральных свойств равен (A C C C C C C C C C C C C C C C) Тогда вектор интегральных свойств мультимножества равен (U, U, U, U, U, U, U, U, U, U, U, U, U, U, U, U).

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

non-bijective s-boxes, generalized Feistel scheme, PICARO block cipher, integral cryptanalysis, небиективные s-боксы, обобщённая схема Фейстеля, алгоритм блочного шифрования PICARO, интегральный метод

Авторы

ФИООрганизацияДополнительноE-mail
Пудовкина Марина АлександровнаМосковский государственный технический университет им. Н. Э. Бауманадоктор физико-математических наук, профессор кафедры информационной безопасностиmaricap@rambler.ru
Сорокин Михаил АртёмовичНациональный исследовательский ядерный университет «МИФИ»студент кафедры криптологии и кибербезопасностиsorokin.michael.96@yandex.ru
Всего: 2

Ссылки

Nyberg K. Generalized Feistel networks // ASIACRYPT 1996. LNCS. 1996. V. 1163. P. 90-104.
Hoang V. T. and Rogaway P. On generalized Feistel networks // CRYPTO 2010. LNCS. 2010. V. 6223. P. 613-630.
Nachef V., Volte E., and Patarin J. Differential attacks on generalized Feistel schemes // CANS 2013. LNCS. 2013. V.8257. P. 1-19.
Piret G., Roche T., and Carlet C. PICARO - a block cipher allowing efficient higher-order side-channel resistance // ACNS 2012. LNCS. 2012. V. 7341. P. 311-328.
Сачков В. Н. Введение в комбинаторные методы дискретной математики. М.: Наука, 1982. 384 с.
Knudsen L. and Wagner D. Integral cryptanalysis // FSE 2002. LNCS. 2002. V.2365. P. 112-127.
Todo Y. Structural evaluation by generalized integral property // EUROCRYPT 2015. LNCS. 2015. V. 9056. P. 287-314.
Biryukov A. and Shamir A. Structural cryptanalysis of SASAS // EUROCRYPT 2001. LNCS. 2001. V. 2045. P. 394-405.
 Об интегральных различителях алгоритмов блочного шифрования, основанных на обобщениях схемы Фейстеля | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/27

Об интегральных различителях алгоритмов блочного шифрования, основанных на обобщениях схемы Фейстеля | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/27