Some conditions for the applicability of the integral cryptanalysis to 4-rounds of aes-like ciphers.pdf Современное состояние систем защиты информации характеризуется наличием так называемого квантового вызова. Появление квантового компьютера с соответствующим набором характеристик, которые, согласно мнению ряда экспертов, будут достигнуты в ближайшее десятилетие, приведёт к потере некоторыми существующими системами защиты информации или отдельными их элементами своего практического значения. Таким образом, актуальной становится задача разработки, исследования и программно-аппаратной реализации криптографических примитивов, которые смогут противостоять квантовому вызову. В настоящее время существует несколько подходов к решению данной проблемы, одним из которых является использование симметричных криптографических систем, стойкость которых понизится с появлением гипотетического квантового вычислителя незначительно. Поэтому продолжает оставаться актуальным вопрос об оценке криптографической стойкости симметричных шифр-систем, применяемых как в современных информационно-телекоммуникационных системах, так и в системах интернета вещей (IoT). Отметим, что, согласно информации, приведённой в [1, 2], в условиях ограниченных ресурсов в системах IoT наиболее рационально использовать алгоритмы блочного шифрования. В соответствии с [3] одним из основных методов криптоанализа подобных алгоритмов является интегральный метод. Интегральный метод, впервые названный так в [4], предложен в работе [5] и является развитием метода из [6]. Этот метод ещё называют square-атака [5] или saturation-атака [7] (метод квадрата и метод статистического насыщения). Он аналогичен по схеме применения известному дифференциальному методу, также являясь атакой на основе адаптивно подобранного открытого текста [8]. Общую схему метода можно описать следующим образом. Преобразование Fk, реализуемое блочным алгоритмом шифрования и зависящее от ключа k, представляется как композиция двух отображений Fk = Fk2 ◦ Fk1. Допустим, что имеется такое множество I С X блоков открытого текста, что «интеграл» Fj (x) обладает определённым xei легко проверяемым «отличительным» свойством (например, равен нулевому ветору). Предположим, что известны пары «открытый - шифрованный текст» (x, Fj (x)) для всех x G I. Тогда для любого k можно определить элемент (Fj2) 1 (Fk (x)), который xei при истинном варианте k должен обладать «отличительным» свойством «интеграла». Применению различных модификаций интегрального метода к ряду блочных шифрсистем, поиску путей развития этого метода и изучению связанных с ним характеристик посвящён ряд работ [9-12]. Интегральный метод в основном применяется к блочным алгоритмам с малым числом раундов, например к редуцированным вариантам AES [13] или Кузнечика [14], что является актуальным именно в условиях низкоресурсной криптографии. Рассмотрим вопрос об условиях возможности применения интегрального метода к системам шифрования типа AES (алгоритмы SQUARE, Rijndael, Crypton) с четырьмя итерациями G = f4* ◦ f3 ◦ f2 ◦ f1, в которой первые три итерации f1, f2, f3 обычные (но, например, в первую итерацию Rijndael мы включаем прибавление к блоку открытого текста начального ключа), а последняя итерация f4 может отличаться (например, в Rijndael она не содержит преобразования MixColumn). Схемы примения интегрального метода к перечисленным алгоритмам рассматриваются в работах [5, 15, 16]. Промежуточный блок после третьей итерации обозначим через E (x, k0) = = (Eo (x, k0) ,... , E15 (x, k0)), где k0 - ключ начального преобразования в терминах [17]. При фиксированном k0 его можно рассматривать в обозначениях [18] как вектор-функцию E (x, ko) = Ek0 (x) : Vm V128, E (x, ko) = ◦ /2 ◦ fi (x, ko). Пусть подвектор Bi = z, i G {0,...,15}, принимает все возможные значения из V8, а остальные подвекторы блока данных фиксированы. Полученное множество обозначим Ii = {(B0, . . . , Bi-1, z, Bi+1, . . . , B15) : z G V8}. Рассмотрим для каждого индекса m G G {0,. . . ,15} при фиксированном k0 G V128 значение интеграла Em(x,k0). x^Ii Теорема 1. В AES-подобных схемах (SQUARE, Rijndael, Crypton) для четырёх итераций для любого непустого множества J С {1 + 8s,... , 8 + 8s}, s G {0,... , 15}, и любого множества I = {1,...,128} \\{8l+ k : k = 1,...,8}, l G {0,...,15}, для отображения E (•, k0) при фиксированном ключе k0 G V128 в обозначениях [18] верно, что Em (x, ko) = 0. xeii Следствие 1. В AES-подобных схемах (SQUARE, Rijndael, Crypton) для четырёх итераций для любого непустого множества J С {1 + 8s, . . . , 8 + 8s}, s G {0, . . . , 15}, и любого множества I = {1,...,128} \\{8l+ k : k = 1,...,8}, l G {0,...,15}, для отображения E (•, k0) при фиксированном ключе k0 G V128 в обозначениях [18] верно, что wIJ (Ek0 (x)) = 0 (mod 2). Следствие 2. В условиях следствия 1 в обозначениях [19] выполняется AJ (Eko (x)) = 0 (mod 2). Предположим, что нам известно 256 пар открытого и шифрованного текстов (x, y), x G Ii, y = y(x) = G(x, k0) = f4*(E(x,k0),k4) = s(E(x, k0)) ф k4, где k0 -истинный ключ, а s - некоторое нелинейное преобразование, зависящее от конкретного алгоритма; ключ j-й итерации вычисляется из ключа (j - 1)-й с помощью функции ф: kj = ф^-^) -нелинейной подстановки на множестве двоичных векторов V128; k4 = = ф4(k0). Требуется определить ключ четвёртой итерации k4 = (k4,0,... , k4,15). Опробование ключа будем осуществлять по байтам k4,0, . . . , k4,15 G V8. Блок шифртекста разобьём на компоненты по 8 битов: y(x) = (y0(x), . . . , y15(x)), ym(x) G V8. Для каждого индекса m G {0,... , 15} для каждого варианта k4,m вычисляем s-1 (ym(x) ф k4,m). xeii Если эта сумма оказывается не равной нулю, то опробуемый вариант для k4,m отбраковываем. Если в результате ключ определился неоднозначно, то алгоритм можно повторить для другого i. Итак, пусть у нас имеется отображение G : V128 X V128 V128, G = f1f2f3f4-При фиксированном k0 G V128 отображение Gko(x) = G(x, k0) : V128 V128 является биективным. Очевидно, что G(x, k0) = s ◦ E(x, k0) ф ф4(^). Теорема 2. Необходимым условием для того, чтобы интегральный метод позволял в AES-подобных схемах (SQUARE, Rijndael, Crypton) для четырёх итераций получить информацию о k4,j, является то, что при любом фиксированном ключе k0 G V128 для отображения E(x,ko) = (gi(x),... ,gi2s(x)), где gm(x) : Vm Vi, m G {1,... , 128}, существует вектор а G V8 \\ {0}, такой, что для любого (в1, . . . , в120) G V120 в обозначениях [18] выполняется (а> (g1+8j, . . . , g8+8j))i17-.7,if120 = 128 для некоторого I = {1,...,128} \\{8j + k : k = 1,...,8} = {i1,...,i120}. Следствие 3. Необходимым условием для того, чтобы интегральный метод позволял в AES-подобных схемах (SQUARE, Rijndael, Crypton) для четырёх итераций получить информацию о k4,j, является то, что в условиях теоремы 2 существует непустое множество J С {1 + 8j,..., 8 + 8j}, такое, что wJ (E(x, k0)) = 128. Следствие 4. Необходимым условием для того, чтобы интегральный метод позволял в AES-подобных схемах (SQUARE, Rijndael, Crypton) для четырёх итераций получить информацию о k4,j, является то, что в условиях теоремы 2 существует непустое множество J С {1 + 8j,..., 8 + 8j}, такое, что A^(E(x, k0)) = 0. Нас интересует, в каком случае выполняется равенство Int (k4,j,j) = E s-1(yj(x) ф k4,j) = 0 xeii Очевидно, что это произойдёт, если байт ключа угадан верно. Следствие 5. Необходимым условием для того, чтобы интегральный метод позволял в AES-подобных схемах (SQUARE, Rijndael, Crypton) для четырёх итераций получить информацию о k4,j, является то, что существуют такие x1, x2 G Ii, x1 = x2, что yj(xi) = yj(x2). Теорема 3. Необходимым условием для того, чтобы интегральный метод позволял в AES-подобных схемах (SQUARE, Rijndael, Crypton) для четырёх итераций получить информацию о k4,j для некоторого j G {0, . . . , 15}, является то, что отображение s является нелинейной подстановкой. Рассмотрим мультимножество {yj(x) : x G I»}, где (y0(x),... , y15(x)) = G(x, k0), состоящее из 256 элементов, и его подмножество (уже не являющееся мультимножеством) Yj = {a G V8 : |{x G Ii : yj(x) = а}| = 2k - 1,k G N}. Теорема 4. Необходимым условием для того, чтобы интегральный метод позволял в AES-подобных схемах (SQUARE, Rijndael, Crypton) для четырёх итераций получить информацию о k4,j, является то, что множество Yj* не пусто. Пусть I* -произвольное подмножество I, такое, что {yj(x) : x G I*} = Y*. Очевидно, что Int (k4,j,j) = E s-1(yj(x) ф k4,j) = E s-1(yj (x) ф k4,j). xGli xGl* Следовательно, можно модифицировать технику применения интегрального метода тем, что интеграл будет вычисляться по меньшему множеству I*. Рассмотрим отображение Tj(k4) E s у(x) ф k4,j), Tj(k4) : V8 V8. xei* Теорема 5. Необходимым условием для того, чтобы интегральный метод позволял в AES-подобных схемах (SQUARE, Rijndael, Crypton) для четырёх итераций получить информацию о k4,j, является то, что существует такой элемент а G V8, что Tj(a) = 0. Теорема 6. Достаточным условием для того, чтобы интегральный метод позволял в AES-подобных схемах (SQUARE, Rijndael, Crypton) для четырёх итераций найти k4,j, является то, что существует единственный элемент в G V8, такой, что Tj(в) = 0. В рамках исследования интегрального метода проведено 16 наборов экспериментов для редуцированного до четырёх раундов алгоритма Rijndael по схеме из [20], в которых в качестве набора открытых текстов взято множество из 256 векторов Io = {x = (xo, . . . , x15) G V128}, где xo принимает все значения из V8, а остальные xj равны нулю. На фиксированных множествах из 256 ключей {k0}t, t G {1,... , 16}, вычислялось множество шифртекстов {y = (y0(x),... , y15(x)) = G(x,k0) : x G I0}, а затем для заданного номера байта j = j(t) для всех k4,j G V8 вычислялся интеграл Int(k4,j, j, Io) = s-1(yj(x) Ф k4,j). Среди тех k4,j, для которых Int(k4,j, j,Io) обращалxeio ся в ноль, обязательно содержится истинный байт четвёртой итерации ключа, но он далеко не всегда единственен. В каждом из наборов экспериментов для каждого ключа из {k0}t подсчитывалось, на скольких байтах k4,j интеграл Int(k4,j, j,I0) обращался в ноль. В качестве множеств {k0}t = {(k0 0,..., k0 15) G V128 : k0,l G Иь l G {0,..., 15}}t брались векторы, у которых байт k0 m принимал все значения из V8 при фиксированном m = m(t) = j(t), а остальные байты равны нулю. Данные экспериментов сведены в таблицу, в которой приведено количество ключей из множества {k0}t, для которых интеграл Int(k4,j, j, Io) равен нулю на v байтах при всех v G {1, . . . , 7}. t j (t) v 1 2 3 4 5 6 7 1 0 97 88 49 15 7 0 0 2 1 102 97 37 11 7 2 0 3 2 102 89 38 21 4 2 0 4 3 86 97 51 17 4 1 0 5 4 104 95 42 9 5 1 0 6 5 95 93 47 17 3 1 0 7 6 82 109 47 11 5 2 0 8 7 80 105 45 18 8 0 0 9 8 102 86 42 22 3 1 0 10 9 110 85 43 16 2 0 0 11 10 95 93 54 10 2 1 1 12 11 102 85 52 12 5 0 0 13 12 106 89 48 11 2 0 0 14 13 86 106 44 16 4 0 0 15 14 91 105 40 17 3 0 0 16 15 83 97 52 12 12 0 0

Скачать электронную версию публикации