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

В научных статьях термин «интегральный криптоанализ» был предложен в 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го раунда шифрования Дальнейшие шаги есть попытки усовершенствовать атаку, увеличивая число раундов, используя различные допущения, неминуемо увеличивающие число итераций перебора, тем самым и сложность взлома.

Атака на 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-го раунда и проверить, равен ли интеграл от соответствующего блока нулю. Если равен, то байт раундового ключа можно считать найденным.

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}}$

• 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) in 4th International Workshop on Fast Software Encryption (FSE '97), Volume 1267 of Lecture Notes in Computer Science.: 149–165, Haifa: Springer-Verlag.