Исследование SPN-структуры блочного симметричного шифра. Анализ критериев оценки ее эффективности, возможность отличения такой структуры от случайной перестановки. Теорема про максимальную вероятность отличения SPN-структуры и случайной перестановки.
Восточно-Европейский журнал передовых технологий ISSN 1729-3774 6/9 (72 ) 2014Висунута та доведена теорема про максимальну віро-гідність розрізнення SPN-структури та випадкової перестановки. Исследована SPN-структура (substitution-permutation network) блочного симметричного шифра. Выдвинут критерий оценки ее эффективности, основой которого является возможность отличения такой структуры от случайной перестановки. Выдвинута и доказана теорема про максимальную вероятность отличения SPN-структуры и случайной перестановки.Эффективность высокоуровневой конструкции блочного шифра целесообразно оценивать через сложность различения перестановки, сформированной этой структурой (при использовании одного ключа шифрования), от случайной соответствующей степени, поскольку именно множество случайных перестановок степени является моделью идеального блочного шифра [1]. В качестве критерия эффективности высокоуровневой конструкции блочного симметричного шифра целесообразно использовать возможность различения случайной перестановки и подстановки, сформированной шифрующем преобразованием [2], а в качестве показателей эффективности - вероятность успешного различения и сложность работы соответствующего алгоритма-различителя [3]. Несмотря на это, авторы поставили перед собой цель оценить эффективность SPN-структуры путем сравнения ее со случайной перестановкой (как это было сделано в [4] и [5] для других конструкций), чтобы в конечном итоге получить сравнительную оценку всех трех структур. hi - i-й алгоритм-различитель высокоуровневой структуры блочного шифра и случайной перестановки; h* - лучший теоретический алгоритм-различитель (возможно, гипотетический) высокоуровневой структуры блочного шифра и случайной перестановки; используется для оценки верхней границы эффективности различения; Таким образом, различение является вероятностным и допускает появление ошибок первого рода (последовательности, сформированные блочным шифром, принимаются сформированными случайной перестановкой изза отсутствия характерных признаков) и второго рода (последовательности, сформированные случайной перестановкой, имеют специфические признаки, по которым принимается решение об использовании блочного шифра).В ходе исследований были получены количественные оценки эффективности SPN-структуры основанные на вероятности ее отличения от случайной перестановки. Данный подход уже был применен к цепи Фейстеля и схеме Лей-Месси, поэтому целесообразно было сделать аналогичное исследование для SPN-структуры. Для этого в первую очередь была найдена максимально возможная вероятность различения SPN-структуры и случайной перестановки.
Введение
Опыт проведения открытых криптографических конкурсов показал, что в настоящее время при проектировании симметричных блочных шифров основное внимание уделяется раундовому преобразованию, обоснованию его дифференциальных, линейных и алгебраических свойств, а также схеме формирования раундовых подключей. Выбор высокоуровневой конструкции шифра осуществляется на основе предпочтений разработчика и в подавляющем большинстве случаев не имеет теоретического обоснования.
Тем не менее, при разработке алгоритма целесообразно опираться на некоторую численную оценку эффективности. С точки зрения обеспечения требуемых криптографических свойств и стойкости здесь целесообразно использовать модель блочного шифра как случайной перестановки, а с точки зрения программной (или аппаратной) реализации - требуемое количество операций.
Эффективность высокоуровневой конструкции блочного шифра целесообразно оценивать через сложность различения перестановки, сформированной этой структурой (при использовании одного ключа шифрования), от случайной соответствующей степени, поскольку именно множество случайных перестановок степени является моделью идеального блочного шифра [1]. Сложность выполнения алгоритма-различителя и достигаемая вероятность успеха являются численными показателями эффективности высокоуровневой конструкции. Для исключения влияния свойств конкретной раундовой функции необходимо использовать идеализированное раундовое преобразование, такое как случайная функция или случайная перестановка.
В качестве критерия эффективности высокоуровневой конструкции блочного симметричного шифра целесообразно использовать возможность различения случайной перестановки и подстановки, сформированной шифрующем преобразованием [2], а в качестве показателей эффективности - вероятность успешного различения и сложность работы соответствующего алгоритма-различителя [3].
Наряду с цепью Фейстеля с схемой Лей-Месси, SPN-структура (substitution-permutation network) является одной из наиболее распространенных высокоуровневых конструкций блочных симметричных шифров. В частности, это преобразование использовано в наиболее широко распространенном во всем мире алгоритме AES/Rijndael, шифрах Anubis, GRANDCRU, Noekeon, «Калина» и др. Исследования эффективности различения цепи Фейстеля и схемы Лей-Месси были рассмотрены авторами в [4] и [5] соответственно. В данной статье проводится анализ SPN-структуры.
2. Обзор существующих публикаций и постановка проблемы
Одной из основополагающих работ по оценке эффективность некоторой конструкции путем сравнения ее со случайной перестановкой является работа М. Luby и С. Rackoff [2]. Авторы публикации исследовали цепь Фейстеля, которая является основой алгоритма DES.
4
? Д. С. Кайдалов, Р. В. Олейников, 2014
Информационно-управляющие системы
Данная работа дала толчок к появлению других публикаций на эту тему. К примеру, U. M. Maurer в своей работе [3] развивает и улучшает результаты исследований М. Luby и С. Rackoff. J. Patarin применил данный метод к алгоритму DES с различным количеством раундов [6]. В [7] он оценил возможность атаковать 5 раундов, а [8] оценивается 6 и более раундов алгоритма DES. Авторы текущей статьи также провели ряд исследований по цепи Фейстели и смогли получить еще более точные оценки для данной конструкции [4].
Основываясь на этих работах, S. Vaudenay в [9] провел анализ схемы Лей-Месси, показав, что метод, предложенный М. Luby и С. Rackoff, применим не только для цепи Фейстеля. В свою очередь, авторы текущей статьи также проводили исследования схемы Лей-Месси и разработали несколько новых алгоритмов-различителей, опубликованных в [5].
Однако совсем мало работ, в которых осуществляются попытки применить такой подход к SPN-структуре. Во многом это продиктовано большими различиями между цепью Фейстеля и схемой Лей-Месси с одной стороны и SPN-структурой с другой. Несмотря на это, авторы поставили перед собой цель оценить эффективность SPN-структуры путем сравнения ее со случайной перестановкой (как это было сделано в [4] и [5] для других конструкций), чтобы в конечном итоге получить сравнительную оценку всех трех структур.
3. Цель и задачи исследования
Целью проводимых исследований являлось по-лучение количественных оценок, по которым можно было бы оценить эффективность SPN-структуры и сравнить ее с другими высокоуровневыми конструкциями блочных шифров. Как уже было упомянуто выше, такими оценками являются вероятности различения SPN-структуры и случайной перестановки.
Для достижения поставленной цели решались следующие задачи: - определение максимально достижимой вероятности различения SPN-структуры и случайной перестановки. Требовалось вывести выражение, которое позволит рассчитать такую характеристику и доказать его математически.
- нахождение алгоритма-различителя для 2-х раундовой SPN-структуры. Расчет вероятности, с которой такой алгоритм позволяет отличать от случайной перестановки.
- нахождение алгоритма-различителя для 3-х и более раундов SPN-структуры. Обоснование неотличи-мости 3-х и более раундов от случайной перестановки. s - множество перестановок степени n;
s - множество перестановок степени 2n;
n
2n y - биективное отображение на основе цепи Фейстеля;
V - биективное отображение на основе схемы Лей-Месси;
J - биективное отображение на основе SPN-структуры;
hi - i-й алгоритм-различитель высокоуровневой структуры блочного шифра и случайной перестановки; h* - лучший теоретический алгоритм-различитель (возможно, гипотетический) высокоуровневой структуры блочного шифра и случайной перестановки; используется для оценки верхней границы эффективности различения;
P - вероятность, с которой алгоритм-различитель определяет высокоуровневую структуру блочного шифра;
1
P* -вероятность,скоторойалгоритм-различитель определяет случайную функцию (перестановку);
1 x·y - конкатенация двух векторов x и y.
Алгоритм-различитель (distinguisher) hi предназначен для определения преобразования, которое было использовано для формирования выходной последовательности по входной (блочный шифр или случайная перестановка) [3].
Метод различения основан на поиске специфических признаков, характерных для блочного шифра. Сложность различения может определяться как для конкретного алгоритма, так и как верхняя граница для произвольного (любого возможного) алгоритма.
Алгоритм (рис. 1) получает на входе множество открытых текстов x ,1? i? m и множество соответствующих шифрованных текстов yi ,1? i? m . После завершения работы на выходе алгоритма формируется значение «1» (использована высокоуровневая конструкция блочного шифра) либо «0» (выходные данные сформированы случайной перестановкой или функцией).
( )
{ } i
( )
{ }
4. Модель алгоритма-различителя
В этом, а также последующих разделах, будут использоваться следующие условные обозначения: In - множество битовых векторов длины n;
I - множество битовых векторов длины 2n; F - множество функций F:I ®I ;
2n n n n
F n - множество функций F:I2n ®I2n;
2
Рис. 1. Модель алгоритма-различителя
Поскольку в качестве раундового преобразования в модели блочного шифра используется случайная перестановка или случайная функция, то появление
5
Восточно-Европейский журнал передовых технологий ISSN 1729-3774 6/9 ( 72 ) 2014
специфических признаков тоже является случайным событием, имеющим некоторую вероятность (по которой определяется вероятность успешного различения и эффективность конкретного алгоритма). В то же время, при выборе случайной перестановки существует ненулевая вероятность того, что такая перестановка будет иметь признаки, характерные для блочного шифра, и алгоритм-различитель примет неверное решение. Модуль разности этих вероятностей и определяет эффективность конкретного алгоритма-различителя: Таким образом, рассматриваемая модель шифрующего преобразования SPN-структуры состоит из итеративного применения слоя случайных перестановок и обменаэлементовмеждуколонкамиматрицысостояния.
Один цикл шифрования алгоритмом на основе SPN-структуры при nc = nb представлен на рис. 2.
Advhi (n,s2n)= P?P* , (1)
1 1 где NI{y,V,J} - некоторая высокоуровневая структура блочного шифра.
Таким образом, различение является вероятностным и допускает появление ошибок первого рода (последовательности, сформированные блочным шифром, принимаются сформированными случайной перестановкой изза отсутствия характерных признаков) и второго рода (последовательности, сформированные случайной перестановкой, имеют специфические признаки, по которым принимается решение об использовании блочного шифра).
Отметим, что алгоритм-различитель hi может быть представлен как некоторая машина Тьюринга, так и как отображение hi :({0,1 2n )k ®{0,1 , не требующее дополнительной памяти.
} }
5. Модель SPN-структуры
В соответствии с принципами Шеннона [10], SPN-структура чередует операции перемешивания (diffusion) и рассеивания (confusion), реализуемые с помощью линейных и нелинейных преобразований соответственно.
В отличие от цепи Фейстеля и схемы Лей-Месси, для реализации корректного расшифрования в раундовом преобразовании SPN-структур требуется применение исключительно биективных отображений (перестановок), т. е. SPN-структура не может быть по-строена на основе случайных функций.
По аналогии с представлением внутреннего состояния алгоритмов Square и AES/Rijndael, обрабатываемый шифром блок целесообразно представить в виде прямоугольной матрицы размером nc ?nb элементов, каждый из которых имеет размер n битов, причем размер блока равен 2n = nc ?nb ?ne битов. Для обеспечения требуемых криптографических свойств и эффективности программной реализации целесообразно выбирать nc = nb ?2l,LI 1,2,... . Кроме того, все современные шифры являются байт-ориентированными, поэтому для AES/Rijndael, «Калина» и других алгоритмов ne = 8. e
{ }
Как и в случае с предыдущими высокоуровневыми конструкциями, для исключения влияния конкретных компонентов принимается, что в раундовом преобразовании SPN-структуры используются случайные перестановки. Проводя аналогию с AES/Rijndael, такую случайную перестановку можно назвать Super-S-box (см., например, [11]).
Рис. 2. Цикл шифрования алгоритмом на основе SPN-структуры
В общем случае, модель s-циклового шифра на основе SPN-структуры может быть представлен в виде формулы
Теорема 1 (верхняя граница различения 2-цикловой SPN-структуры и случайной перестановки на ограниченном числе запросов).
Максимальная вероятность различения случайной перестановки s2n и 2-цикловой SPN-структуры с
6
Информационно-управляющие системы b b размером блока 2n битов и внутренним состоянием, n -1 k-1 n -1 k-2 представляемым в виде матрицы размером n ?n b b c e c e
1 1
? ? ? ?
? ? ? ?
? ? ? ?
? ? ? ?
= - - -
? ? ? ?
? ? ? ?
? ? ? ? c b элементов, каждый из которых имеет размер n би- ph 1 1 n ?n 1 n ?n ... e
* тов (2n = n ?n ?n ), при соответствии соотношений ?? 2 nb ? ? ?? 2 nb -1? ? c b e
{ } размеров матрицы условию n = n ?2l,LI 1,2,... , при- c b k-(k-1) менении случайных перестановок s 2n в раундовом ?? ?nb -1?
? ?
? ? nc?ne nc?ne ...??1- nc?ne 1 ? ? = преобразовании, для k запросов ?2? k ? 2 nb ? на ?? 2 nb - k -2 ? ?
? ?
(
)
? ?
? ?
? ?
? ? входе алгоритма-различителя не превышает значения k-2 ? ?(nb -1)(k-i-1) =1- 1- n ?n . c e
1
? ?
? ?
O
Adv (J,s2n)= i=0 ? 2 nb -i? h*
= P (h*(f(x1),...,f(xk ))=1:f R J(2))-P* (h*(f(x1),...,f(xk ))=1:f R s2n ) ? При малом размере выборки
1 1
I I
( ) b n n n
?
? ?
?
? ?
? ?
? ?
? ?
2 -i
{ }
? ?
? ? i k-2 nc?ne (nb -1)(k-i-1) k(k-1)-1 ??2nc?ne -1 nb -i?
? 1- 1-2 nb - » i=0 ? ? i=0 c e
2 i
-
? ?
? ?
O O
nc?ne
# x << 2 nb вероятность появления ? ? коллизии на входе случайной перестановки второго цикла изменяется незначительно, откуда можно воспользоваться аппроксимацией k(k-1)(n -1) n k(k-1) nc?ne 2 nc?ne?k? k-1) nc?ne 2
» 1-?1-2 nb ? -2 2 ??2 nb -1 .
(
? ?
?
? ?
-
? ?
-
? ?
(3) k(k-1)(n -1) ? ? 2 b
? ?
1 ph* »1-?1- nc?ne ? . (5) b
? ? n
2
Доказательство. Вероятность появления повторяющихся значений Вероятность различения SPN-структуры оценива- на выходе блоков, соответствующих границе Super-ется следующим образом. S-box, для случайной перестановки s2n можно оце- Для запроса из одной пары элементов нить следующим образом.
( ) xi,xj , 1? i< j? k , при отличающемся входе только Число комбинаций для одной пары, при которых для одной случайной перестановки (активный Super- выходные значения не повторяются ни в одном из бло-S-box), на следующем цикле на каждую перестановку nc?ne nb
? ?
? ? ков, равно p = 2-nc?ne ? 2 nb -1 . Для запроса, состо-поступит c элементов с активизированной. Кол- ? ? n
1 k(k-1) n b ящего из k значений, можно составить C2 = k
2 лизионные значения, необходимые для различения, могут отсутствовать или появиться на входе от одной пар, и вероятность того, что значения не повторятся ни до nb -1 перестановок (коллизии по всем элементам в одной паре, равна
( ) возможны только для случайной функции, но не
(
)
1 * 1 k R 2n перестановки). P* h (f(x ),...,f(x ))=1:f I s =
Соответственно,вероятностьпоявленияколли-
(
)
(
) n n n
2
2
? ? ? ?
? ? ? ? ? ? k k-1
? ? ? ?
? ? ?
? ? ? ?
? ? ? ? ? ?
? ? ? ?
= =
?
? ?
? ? nc?ne b nc?ne b nc?ne b n ?n n зии на входе одной перестановки равна ps = 2- c b e , ?2 nb -1 ? ?2 nb -1 -1 ?...? ?2 nb -1 - 1 а появления хотя бы одной коллизии на входе всех подстановок второго раунда вычисляется как 2nc?ne ?(2nc?ne -1)?...??2nc?ne - k k-1 1 n ?n nb -1
-
? ?
? ?
? ? c e p =1- 1-2 nb . (4) ?? nc?ne ?nb ?
2
( ) n i 0
2 i
=
? ?
- -
?
? ?
? ?
-
.
-1
O k(k-1) ?2 b 1 i 2 ? ?
=
Выражение (4) определяет вероятность разли- nc?ne чения SPN-структуры и случайной перестановки на одной паре запросов. nc?ne
{ }
? ?
? ?
Для запроса, состоящего из k входных значений, При малом размере выборки ?# xi << 2 nb ? ве-можно составить C2 = k(k-1) различных пар. Веро- роятность появления коллизии на входе блоков, соответствующих границе Super-S-box, изменяется незна- k
2 ятность появления коллизии среди промежуточных значительно, откуда можно воспользоваться аппрокси-чений на входе случайных подстановок для всех пар равна мацией
7
Восточно-Европейский журнал передовых технологий ISSN 1729-3774 6/9 ( 72 ) 2014
1 R
P* (h*(f(x1),...,f(xk ))=1:f I s2n )» n k(k-1) nc?ne?k? k-1) nc?ne 2 b
(
? ?
?
? ?
-
» 2 2 ??2 nb -1 .
Теорема доказана.
7. Алгоритм-различитель для 2-цикловой SPN-структуры
В этом случае существует определенное количество запросов, при котором преимущество различения ста-новитсяравнымнулю.Приуменьшениичислазапросов резко возрастает вероятность определения случайной перестановки (второе слагаемое суммы под модулем в (3), рис. 4), при увеличении количества аргументов алгоритма-различителя увеличивается вероятность определения SPN-структуры (первое слагаемое суммы под модулем в (3), рис. 5), которая становится равной 1 после порогового значения (см. утверждение 1). nc?ne
? ?
? ?
Для k входных аргументов 2? k ? 2 nb 1 , ? ? выполняющих активизацию одной перестановки: x(t) ? x(t),x(l) = x(l),1? l? nb,l ? t,t = const, i j i j xi =(x(1) ·x(2) ·...·x(nb )), xj =(x(1) ·x(2) ·...·x(nb )), i i i j j j
1? i< j? k проверяется наличие коллизий на выходе каждой перестановки второго цикла: y l = y l ,1? l? n , 1? i< j? k.
( ) ( ) i j b
В случае выполнения равенства хотя бы для одного аргумента возвращаемое значение будет «1» (обнаружена SPN-структура), иначе «0».
Утверждение (сложность работы алгоритма-различителя).
2-цикловая SPN-структура с размером блока 2n битов и внутренним состоянием, представляемым в виде матрицы размером n ?n элементов, каждый из которых имеет размер ne битов (2n = nc ?nb ?ne), при соответствии соотношений размеров матрицы условию n = n ?2l,LI 1,2,... , применении случайных перестановок s 2n в раундовом преобразовании, бу- c b
{ } c b nc?ne дет определена алгоритма-различителем не более чем nc?ne за 2 nb 1 запросов.
Доказательство следует из теоремы 1.
График зависимости верхней границы вероятности различения 2-цикловой SPN-структуры с параметрами nc = 4,nb = 4,ne = 8 (шифр, эквивалентный 2-цикловому AES на случайных перестановках Super-S-box) от количества запросов, приведен на рис. 3.
Рис. 3. График зависимости верхней границы вероятности различения 2-цикловой SPN-структуры от количества запросов
Рис. 4. График зависимости верхней границы вероятности определения случайной перестановки алгоритмом-различителем 2-цикловой SPN-структуры от количества запросов
Как видно из графиков на рис. 3-5, различение даже 2-цикловой SPN-структуры является сложной задачей. Значение, возвращаемое алгоритмом-различителем, в значительной степени зависит не только от типа исследуемого преобразования (блочный шифр или случайная перестановка), но и от количества по-данных запросов.
Если для других высокоуровневых структур блочных шифров существует оптимальное количество запросов или некоторый предел, максимизирующий преимущество, то для 2-цикловой SPN-структуры такого значения не существует. Можно определить только по-роговое значение, при котором алгоритм-различитель с равной вероятностью будет определять как SPN-структуру, так и случайную перестановку. При меньшем числе запросов предпочтение будет отдаваться случайной перестановке, при большем - SPN-структуре.
Рис. 5. График зависимости верхней границы вероятности различения 2-цикловой SPN-структуры алгоритмом-различителем от количества запросов
8
Информационно-управляющие системы
8. Различение 3-цикловой SPN-структуры
Как и для 2-циклового преобразования, в соответствии с для s = 3 на вход SPN-структуры подается открытый текст x = x1 ·x 2 ·...·x nb , на выходе формируется шифртекст yi = yi1 ·yi2 ·...·yinb . В отличие от предыдущего случая, для обнаружения коллизии на выходенеобходимопоявлениесовпадающихзначений, как на выходе первого цикла, так и на выходе второго.
( ) ( ) ( )
( ) i i i i
( ) ( ) ( )
( )
Теорема 2 (эффективность различения 3-цикловой SPN-структуры и случайной перестановки).
Преимущество произвольного алгоритма-различителя случайной перестановки s2n и 3-цикловой SPN-структуры с размером блока 2n битов и внутренним состоянием, представляемым в виде матрицы размером n ?n элементов, каждый из которых имеет размер ne битов (2n = nc ?nb ?ne), при соответствии соотношений размеров матрицы условию n = n ?2l,LI 1,2,... , применении случайных перестановок s 2n в раундовом преобразовании, для c b
{ } c b nc?ne произвольного количества запросов равно нулю: Таким образом, для различения 3-цикловой SPN-структуры нужно одновременное появление не менее nc коллизионных элементов в промежуточных состояниях (после первого и второго цикла).
Вероятность появления такого количества одина-nc?ne nc nc ?ne
- -
? ?
2 ковых элементов равна ?2 nb ? = 2 nb .
? ?
Соответственно, для k запросов вероятность одновременного появления nc коллизионных элементов хотя бы в одном из них равна k(k-1) ? nc ?ne ? 2
2
( )
( )
1 R
-
? ?
? ?
P h*(f(x1),...,f(xk ))=1:f I J 3 =1-?1-2 nb ? . (7)
Для случайной перестановки степени 2n вероятность появления совпадающих n элементов на выходе P* h*(f(x1),...,f(xk ))=1:f I s2n определяется следующим образом. c
( )
1 R n
Каждый элемент содержит nc ?ne битов, и для b nc элементов вероятность совпадения равна
Adv (J,s2n)=
= P (h*(f(x1),...,f(xk ))=1:f R J(3))-P* (h*(f(x1),...,f(xk ))=1:f R s2n ) = 0. (6) h*
1 1
I I
nc?ne nc nc ?ne
- -
? ?
? ?
2
2 nb = 2 nb . ? ?
Доказательство. Аналогично, для k запросов можно сформировать Для появления совпадающих значений на выходе
(
) k k-1
SPN-преобразования необходимо, чтобы на входе, по C2 = пар, и вероятность одновременного по-крайней мере, одной подстановки последнего цикла k
2 были только коллизионные значения, т.е. требуется не явления n коллизионных элементов хотя бы в одной менее nc одинаковых элементов (2nc?ne бит) после 2-го из них равна c цикла. k(k-1) Оптимальная активизация подразумевает по - ? nc ?ne ? 2
2
-
( )
1 R дачу разных значений на вход одной перестановки P* h*(f(x1),...,f(xk ))=1:f I s2n =1-?1-2 nb ? . (8) и одинаковые значения на все остальные переста -
? ?
? ? новки первого цикла. Только в этом случае можно добиться максимального количества одинаковых Преимуществопроизвольногоалгоритма-различи-элементов на входе второго цикла, соответственно, теля (использующего как оптимальную активизацию, максимальной вероятности появления коллизион- так и случайные запросы), равна модулю разности (7) ных значений на выходе. и (8): Для запроса из двух элементов
( )
(при оптимальной активи ации входных
( )
1 R 1 R
Adv (J,s )= xi,xj ,1? i< j? k совпадающие значения h* 2n значений) появятся толькозпри возникно- = P h*(f(x1),...,f(xk ))=1:f I J(3) -P* (h*(f(x1),...,f(xk ))=1:f I s2n ) = вении коллизии в одном из следующих слу - k(k-1) k(k-1) чаев: ? nc ?ne ? 2 ? nc ?ne ? 2
- -
2 2
- один совпадающий элемент после 2-го = 1-?1-2 nb ? -1 ?1-2 nb ? = 0. цикла, nc -1 элементов после 1-го цикла; ? ? ? ?
? ? ? ?
( )
- два совпадающих элемента после 2-го цикла, nc -2 элементов после 1-го цикла;
( )
- … Доказательство окончено. - nc -1 совпадающих элементов после 2-го цикла, ( ) один элемент после 1-го цикла. Следствие (неразличимость 3-цикловой SPN- Одновременное появление nc одинаковых эле- структуры и случайной перестановки). ментов во внутреннем состоянии после первого или Не существует эффективного алгоритма-разли-второго цикла при оптимальной стратегии невоз- чителя для 3-цикловой SPN-структуры и случайной можно, но такое событие имеет ненулевую вероят- перестановки. Выходные значения любого такого ность при случайных значениях на входе SPN-пре- алгоритма являются некоторой случайной величи -образования, активизирующих не менее двух ной, не зависящей от типа анализируемого преобра-перестановок первого цикла. зования.
9
Восточно-Европейский журнал передовых технологий ISSN 1729-3774 6/9 ( 72 ) 2014
Вывод
В ходе исследований были получены количественные оценки эффективности SPN-структуры основанные на вероятности ее отличения от случайной перестановки. Данный подход уже был применен к цепи Фейстеля и схеме Лей-Месси, поэтому целесообразно было сделать аналогичное исследование для SPN-структуры.
Для этого в первую очередь была найдена максимально возможная вероятность различения SPN-структуры и случайной перестановки. Была выдвинута и доказана теорема описывающая математическое выражения для получения такой вероятности.
Также проводились исследования по поиску конкретных алгоритмов-различителей для различного числа раундов. В результате был найден алгоритм-различитель для 2-х раундовой SPN-структуры. Для 3-х и более раундов было доказано, что построение такого алгоритма невозможно.
В целом результаты исследований могут свидетельствовать о высокой эффективности SPN-структуры от атак подобного рода, основанных на поиске отличий от случайной перестановки.
В дальнейшем полученные результаты могут быть использованы для сравнения с другими высокоуров-невымиконструкциямиблочныхсимметричныхшиф-ров, что позволит более взвешенно подходит к их проектированию.
Список литературы
1. Vaudenay, S. Decorrelation: a theory for block cipher security [Text] / S. Vaudenay // Journal of Cryptology. - 2003. - Vol. 16, Issue 4. - Р. 249-286. doi: 10.1007/s00145-003-0220-6
2. Luby, M. How to construct pseudorandom permutations from pseudorandom functions [Text] / М. Luby, С. Rackoff // SIAM Journal on Computing. - 1988. - Vol. 17, Issue 2. - Р. 373-386. doi: 10.1137/0217022
3. Maurer, U. M. A simplified and generalized treatment of Luby-Rackoff pseudorandom permutation generators [Text] / U. M. Maurer // Advances in Cryptology - EUROCRYPT’92 : proceedings of the Workshop on the Theory and Application of of Cryptographic Techniques, Balatonfured, Hungary. - Berlin ; Heidelberg : Springer, 1993. - Р. 239-255.
4. Олейников, Р. В. Уточнение эффективности различения цепи Фейстеля и случайной перестановки [Текст] / Р. В. Олейников, Д. С. Кайдалов // Радиотехника : Всеукр. межвед. науч.-техн. сб. - 2011. - Вып. 167. - С. 190-202.
5. Олейников, Р. В. Оценка сложности различения схемы Лей-Месси и случайной перестановки [Текст] / Р. В. Олейников, Д. С. Кайдалов // Прикладная радиоэлектроника. - 2012. - Т. 11, № 2. - С. 152-159.
6. Patarin, J. Security of random Feistel schemes with 5 or more rounds [Text] / J. Patarin // Advances in Cryptology - CRYPTO 2004 : proceedings of the 24th Annual International CRYPTOLOGYCONFERENCE, Santa Barbara, California, USA. - Berlin ; Heidelberg : Springer, 2004. - Р. 106-122.
7. Patarin, J. Generic attacks on Feistel schemes [Text] / J. Patarin // Advances in Cryptology - ASIACRYPT 2001 : proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security, Gold Coast, Australia. - Berlin ; Heidelberg : Springer, 2001. - Р. 222-238.
8. Patarin, J. About Feistel schemes with six (or more) rounds [Text] / J. Patarin. - Lecture Notes in Computer Science, 1998. - Р. 103-121. doi: 10.1007/3-540-69710-1_8
9. Vaudenay, S. On the Lai-Massey Scheme [Text] / S. Vaudenay. - Lecture Notes in Computer Science, 1999. - P. 8-19. doi: 10.1007/978-3-540-48000-6_2
10. Шеннон, К. Теория связи в секретных системах [Текст] / К. Шеннон. - Работы по теории информации и кибернетике. М., 1963. - С. 333-369.
11. Gilbert, Н. Super-Sbox Cryptanalysis: Improved Attacks for AES-like permutations [Electronic resource] : report 2009/531 / H. Gilbert, T. Peyrin. - Cryptology EPRINT Archive, 2009. - Available at: https://eprint.iacr.org/2009/531.pdf
10
Вы можете ЗАГРУЗИТЬ и ПОВЫСИТЬ уникальность своей работы
