Интегральный криптоанализ

Интегральный криптоанализ — метод криптоанализа, объединяющий ряд атак на симметричные блочные криптографические алгоритмы. В отличие от дифференциального криптоанализа, который рассматривает воздействие алгоритма на пару открытых текстов, интегральный криптоанализ подразумевает исследование отображения в шифротекст множества открытых текстов. Впервые применен в 1997 Ларсом Кнудсеном.

История

В научных статьях термин «интегральный криптоанализ» был предложен в 1999 году в публикации Integral cryptanalysis of SAFER+ (англ.). Сама же концепция была впервые озвучена Ларсом Кнудсеном при анализе шифра Square в 1997 году. По этой причине в литератере часто используется термин «Square-подобные атаки» или просто «Square-атака». На 2011 год революционного прогресса относительно Square-атаки в области интегрального криптоанализа не наблюдается.

Теоретическая основа метода

Пусть ${\displaystyle (G,+)}$ — конечная абелева группа. Тогда, принимая за ${\displaystyle G}$ множество возможных шифртекстов 1ного блока (в общем случае ${\displaystyle G}$ определяется выбранным алфавитом и размером блока), можно рассмотреть группу следующего вида, с той же групповой операцией: ${\displaystyle G^{n}=G\times ...\times G}$. Таким образом построенное множество n-мерного пространства суть множество всех возможных шифртекстов. Соответственно элемент пространства ${\displaystyle v=(v_{1},...,v_{n}),v\in G}$ суть некий шифртекст, компоненты этого вектора — значение блоков шифртекста. Полагаем, что сумма векторов есть вектор, компоненты которого равны суммам соответствующих компонент слагаемых. Интегралом по множеству ${\displaystyle S\subseteq G}$ назовем сумму всех векторов, входящих в ${\displaystyle S}$: ${\displaystyle \int S=\sum _{v\in S}v}$.

Успешный интегральный криптоанализ должен уменьшать число итераций подбора ключа. Для этого пробуем группировать векторы открытого текста, так, чтобы на основании группировки можно было найти какие-либо закономерности. Удобно исследовать алгоритмы, опираясь на следующее разбиение:

1. ${\displaystyle v_{i}=c,\forall v\in S}$
2. ${\displaystyle \{v_{i}:v\in S\}=G}$
3. ${\displaystyle \sum _{v\in S}=c'}$,

где ${\displaystyle i}$ — фиксированное число, ${\displaystyle c,c'=const\in G}$ (векторные)

Ключевую роль играет следующая теорема^[1]:

Пусть ${\displaystyle (G,+)}$ — конечная абелева группа. Обозначим ${\displaystyle H=\{g\in G:g+g=0\}}$, причем порядок g равен 1 или 2. Определим ${\displaystyle s(G)=\sum _{g\in G}g}$. Тогда ${\displaystyle s(G)=\sum _{h\in H}h}$. Более того, ${\displaystyle s(G)+s(G)=0}$

Стоит отметить важный результат теоремы: если ${\displaystyle G=GF(2^{s}}$), то ${\displaystyle s(G)=0}$, так как ${\displaystyle H=\{0\}}$

Отметим ряд обозначений, часто использующихся в публикациях об атаках на основе интегрального криптоанализа:

• Если i-ая компонента интеграла обозначена ${\displaystyle {\mathcal {C}}}$, это означает, что во всех слагаемых интегральной суммы i-ая компонента одинакова
• Аналогично ${\displaystyle {\mathcal {A}}}$ показывает, что во всех слагаемых соответствующая компонента различается.
• ${\displaystyle {\mathcal {S}}}$ показывает, что данную компоненту интеграла можно предсказать.
• ? показывает, что предсказать компоненту интеграла нельзя.

Общий принцип поиска уязвимости на примере сети Фейстеля

Изменение интегралов в процессе шифрования

Рассмотрим, как изменятся интегралы по S, если все элементы этого множества подавать на вход сети Фейстеля. Пусть S есть множество шифротекстов, в которых все, кроме одного, соответствующие блоки одинаковы (между собой они могут разниться). В примере шифротекст представляет собой 16 блоков, расположенных в 2 строки. Для таких шифров, как, например, AES, важно также учитывать и то, что шифротекст задается матрицей, так как в них используются разные операции для строк и столбцов. Рассмотрим воздействие ячеек Фейстеля поэтапно:

1. Считая, что ячейки Фейстеля производят биективные отображения, очевидно, что одинаковые между шифротекстами блоки перейдут в одинаковые между преобразованными шифротекстами блоки (однако почти наверняка старое и новое значение будут различаться). Таким образом можем записать, что 1-я ячейка отобразила множество из класса множеств с одинаковыми по множеству компонентами в множество из такого же класса.
2. Так как значения всех блоков на выходе из ячейки Фейстеля зависит от значения каждого блока на входе, то воздействие одного лишь блока ${\displaystyle {\mathcal {A}}}$ изменяет каждый блок шифротекста на выходе. Таким образом, значения компонент интеграла становятся не более, чем предсказываемыми^[2].
3. Так как на входе для каждого блока, принадлежащего входному шифротексту, множество значений не совпадает с множеством возможных значений блока, то их сумма может не сохраниться при биективном преобразовании, потому на выходе из ячейки можно получить что угодно.

Даже применимо к описанному примеру можно существенно сократить число итераций для подбора или дать дополнительную информацию для различных видов криптоанализа.

Сравнение с дифференциальным криптоанализом

Как и для дифференциального криптоанализа, атаки на основе интегрального можно отнести к типу атак на основе адаптивно подобранного открытого текста.

Ларс Кнудсен также отметил схожесть с атакой усеченных дифференциалов, который имеет идею рассмотрения поведения не разности целиком, как в дифференциальном криптоанализе, а её частей. Причем интегральный криптоанализ имеет превосходство в его возможности рассматривать третье состояние результата — ${\displaystyle {\mathcal {S}}}$, в то время, как атака усеченных дифференциалов различает только два.

Для атаки дифференциалов старших порядков можно заметить, что в поле Галуа ${\displaystyle GF(2^{s})}$ выражение для дифференциала s-го порядка схоже с интегралом^[3]. Таким образом можно пытаться обобщить некоторые приемы дифференциального криптоанализа на интегральный.

Примечательно, что атаки усеченных дифференциалов и дифференциалов старшего порядка также впервые опубликовал Ларс Кнудсен в 1994 году, тоже на конференции FSE^[4]

Известные атаки

Атаки на AES-подобные шифры (Rijndael, SQUARE, CRYPTON) можно обобщить первым шагом — рассмотрением интегралов после 3го раунда шифрования Дальнейшие шаги есть попытки усовершенствовать атаку, увеличивая число раундов, используя различные допущения, неминуемо увеличивающие число итераций перебора, тем самым и сложность взлома.

AES

Атака на 4-раундовый шифр

Ключевые моменты шифрования байтовой матрицы — нелинейное преобразование, сдвиг строк, преобразование столбцов, сложение текста (промежуточной байтовой матрицы) с матрицей раундового ключа.

Рассмотрим шестнадцатибайтный открытый текст. Пусть криптоаналитик имеет в своем распоряжении 256 шифротекстов, обладающих следующим свойством: они получены из байтовых матриц, в которых все байты, кроме одного, одинаковы по множеству этих шифротекстов. В силу их количества, можно сказать, что «неодинаковый» байт будет принимать все возможные значения на данном множестве. Таким образом можно перейти к вышеописанным обозначениям:

Начальное состояние:

${\displaystyle {\mathcal {A}}}$	${\displaystyle {\mathcal {C}}}$	${\displaystyle {\mathcal {C}}}$	${\displaystyle {\mathcal {C}}}$
${\displaystyle {\mathcal {C}}}$	${\displaystyle {\mathcal {C}}}$	${\displaystyle {\mathcal {C}}}$	${\displaystyle {\mathcal {C}}}$
${\displaystyle {\mathcal {C}}}$	${\displaystyle {\mathcal {C}}}$	${\displaystyle {\mathcal {C}}}$	${\displaystyle {\mathcal {C}}}$
${\displaystyle {\mathcal {C}}}$	${\displaystyle {\mathcal {C}}}$	${\displaystyle {\mathcal {C}}}$	${\displaystyle {\mathcal {C}}}$

Рассмотрим состояние текста после каждого раунда:

• Нелинейное преобразование в силу биективности не меняет типа байта, только значения для отдельно взятых текстов.
• Сдвиг строк не воздействует на 1-ю строку, остальные сдвигаются, не меняя интеграл.
• Преобразование столбцов делает каждый результирующий байт зависящим от всех 4 байтов исходного столбца, но опять же, в силу биективности операции, получим, что каждый байт столбца будет принимать каждое своё значение лишь раз.
• Сложение с ключом не изменит типы байтов.

Итого, после первого раунда:

После 1го раунда:

${\displaystyle {\mathcal {A}}}$	${\displaystyle {\mathcal {C}}}$	${\displaystyle {\mathcal {C}}}$	${\displaystyle {\mathcal {C}}}$
${\displaystyle {\mathcal {A}}}$	${\displaystyle {\mathcal {C}}}$	${\displaystyle {\mathcal {C}}}$	${\displaystyle {\mathcal {C}}}$
${\displaystyle {\mathcal {A}}}$	${\displaystyle {\mathcal {C}}}$	${\displaystyle {\mathcal {C}}}$	${\displaystyle {\mathcal {C}}}$
${\displaystyle {\mathcal {A}}}$	${\displaystyle {\mathcal {C}}}$	${\displaystyle {\mathcal {C}}}$	${\displaystyle {\mathcal {C}}}$

• Сдвиг строк распределяет в каждый столбец по 1 байту с типом ${\displaystyle {\mathcal {A}}}$.
• Как и в 1-м раунде, если в столбце есть один байт ${\displaystyle {\mathcal {A}}}$, а остальные ${\displaystyle {\mathcal {C}}}$, то все байты в столбце преобразуются в ${\displaystyle {\mathcal {A}}}$. Таким образом преобразуются все 4 столбца.

После второго раунда:

После 2го раунда:

${\displaystyle {\mathcal {A}}}$	${\displaystyle {\mathcal {A}}}$	${\displaystyle {\mathcal {A}}}$	${\displaystyle {\mathcal {A}}}$
${\displaystyle {\mathcal {A}}}$	${\displaystyle {\mathcal {A}}}$	${\displaystyle {\mathcal {A}}}$	${\displaystyle {\mathcal {A}}}$
${\displaystyle {\mathcal {A}}}$	${\displaystyle {\mathcal {A}}}$	${\displaystyle {\mathcal {A}}}$	${\displaystyle {\mathcal {A}}}$
${\displaystyle {\mathcal {A}}}$	${\displaystyle {\mathcal {A}}}$	${\displaystyle {\mathcal {A}}}$	${\displaystyle {\mathcal {A}}}$

Воспользовавшись результатом описанной в разделе теории теоремы, получаем значения интегралов в каждом байте${\displaystyle {\mathcal {S}}=0}$

После 3го раунда, ${\displaystyle {\mathcal {S}}=0}$:

${\displaystyle {\mathcal {S}}}$	${\displaystyle {\mathcal {S}}}$	${\displaystyle {\mathcal {S}}}$	${\displaystyle {\mathcal {S}}}$
${\displaystyle {\mathcal {S}}}$	${\displaystyle {\mathcal {S}}}$	${\displaystyle {\mathcal {S}}}$	${\displaystyle {\mathcal {S}}}$
${\displaystyle {\mathcal {S}}}$	${\displaystyle {\mathcal {S}}}$	${\displaystyle {\mathcal {S}}}$	${\displaystyle {\mathcal {S}}}$
${\displaystyle {\mathcal {S}}}$	${\displaystyle {\mathcal {S}}}$	${\displaystyle {\mathcal {S}}}$	${\displaystyle {\mathcal {S}}}$

Так как в последнем раунде не происходит преобразования столбцов (по спецификации AES), а остальные преобразования переводят ${\displaystyle {\mathcal {A}}}$ в ${\displaystyle {\mathcal {A}}}$, то для чеотырёхраундовой схемы в результате последнего раунда не происходит изменения значения интеграла вплоть до этапа двоичного сложения с раундовым ключом. В таком случае всё, что осталось — для каждого байта предположить значение соответствующего ему байта раундового ключа, получить предполагаемый текст 3-го раунда и проверить, равен ли интеграл от соответствующего блока нулю. Если равен, то байт раундового ключа можно считать найденным.

Расширения по количеству раундов

Схему можно расширить до семираундовой, рассматривая, от чего зависит преобразование интеграла от конкретного байта. Однако, даже в случае с 7 раундами, число необходимых переборов высоко, в таком случае ищутся связи между раундовыми ключами, анализируя схему кодогенерации.^[5]

Усовершенствования по ресурсам криптографа

Существенно сократить время перебора ключей, вследствие особой организации условий перебора, используя трёхбайтовые векторы, позволяет введение так называемой частичной суммы. Такая модификация для шестираундового шифра снижает мощность перебора с ${\displaystyle 2^{72}}$ до ${\displaystyle 2^{44}}$. Другой подход — использовать факт того, что интеграл по множествам с различными ${\displaystyle {\mathcal {C}}}$ также после заветного третьего раунда обращается в нуль. Для этого метода требуется огромное количество ресурсов памяти и обладание очень большой базой открытый текст — шифротекст.^[6]

При помощи частичных сумм возможно реализовать взлом восьмираундовой системы, однако сложность данного взлома даже больше, чем у полного перебора.

Square

Базовая атака на шифр Square практически не отличается от четырёхраундовой атаки на AES, она тоже позволяет расширить число раундов. Пожалуй, существенное различие только в наличии первого раунда шифрования и, как следствие, два способа расширения (один в сторону последнего раунда, другой — первого). Разработчики шифра при его исследовании смогли построить атаку на шестираундовое шифрование.

Были опубликованы следующие результаты^[7]:

Атаки на Square:

Атака	Количество открытых текстов	Время	Затраты по памяти
На 4 раунда	${\displaystyle 2^{9}}$	${\displaystyle 2^{9}}$	Мало
На 5 раундов 1-м способом	${\displaystyle 2^{11}}$	${\displaystyle 2^{40}}$	мало
На 5 раундов 2-м способом	${\displaystyle 2^{32}}$	${\displaystyle 2^{40}}$	${\displaystyle 2^{32}}$
На 6 раундов	${\displaystyle 2^{32}}$	${\displaystyle 2^{72}}$	${\displaystyle 2^{32}}$

Примечания

1. Herstein, Topics in Algebra, 2nd ed., 1975, стр 116
2. Долгов, Головашич, Руженцев. «Анализ криптостойкости шифра Торнадо» (2003), стр. 7
3. Lars Knudsen (2001). «Integral Cryptanalysis (Extended Abstract), стр. 118»
4. Lars Knudsen (1994). «Truncated and Higher Order Differentials»
5. Niels Ferguson, John Kelsey, Stefan Lucks, Bruce Schneier, Mike Stay, David Wagner, and Doug Whiting. «Improved Cryptanalysis of Rijndael» (2001), стр. 2-3
6. Niels Ferguson, John Kelsey, Stefan Lucks, Bruce Schneier, Mike Stay, David Wagner, and Doug Whiting. «Improved Cryptanalysis of Rijndael» (2001), стр. 4-7
7. Joan Daemen, Lars Knudsen, Vincent Rijmen. «The Block Cipher Square» (1997), стр. 15

Ссылки

• Lars Knudsen and David Wagner. Integral Cryptanalysis (Extended Abstract) (неопр.). — 2003.
• Niels Ferguson, John Kelsey, Stefan Lucks, Bruce Schneier, Mike Stay, David Wagner and Doug Whiting. Improved Cryptanalysis of Rijndael (неопр.). — 2001. Архивировано 8 января 2009 года. Архивная копия от 8 января 2009 на Wayback Machine
• Joan Daemen, Lars Knudsen, Vincent Rijmen (January 1997). The Block Cipher Square (PDF). 4th International Workshop on Fast Software Encryption (FSE '97), Volume 1267 of Lecture Notes in Computer Science. Haifa: Springer-Verlag. pp. 149—165.