Улучшенные одноключевые атаки на 8-раундовые AES-192 и AES-256

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 13:10, 2 декабря 2015.
Improved Single-Key Attacks on 8-Round AES-192 and AES-256
AC2010 6.PNG
Авторы Orr Dunkelman, Nathan Keller[@: 1]
Опубликован 2010 г.
Сайт Weizmann Institute of Science
Перевели Arseniy Kolobaev
Год перевода 2015 г.
Скачать оригинал

Аннотация:
AES - наиболее широко используемый блочный шифр сегодня, и его безопасность - одна из самых важных проблем в криптографическом анализе. После 13 лет анализа недавно были обнаружены атаки методом связанных ключей на две из его разновидностей (AES-192 и AES-256). Однако такой сильный тип нападения универсально не принят как действительная модель нападения, и в более стандартной одноключевой модели нападения, вероятнее всего, в настоящее время могут подвергнуться нападению 8-раундовые модели этих двух версий. В случае AES-192 с 8 раундами, единственное известное нападение (найдено 10 лет назад) является незначительным, требует вычисление по существу всех 2128 возможных пар открытого текста/зашифрованного текста, чтобы ускорить полный перебор ключей множителем 16.

В этой статье мы вводим три новых метода криптографического анализа, и используем их, чтобы получить первое существенное нападение на AES-192 с 8 раундами (их временная сложность примерно в миллион раз быстрее, чем полный перебор, и сложность данных уменьшена приблизительно до 1/32, 000 из полной книги шифров). Кроме того, наши новые методы могут уменьшить самые известные временные сложности для всех других комбинаций AES-192 с 8 раундами и с 7 раундами и AES-256.


Введение

Блочный шифр Rijndael был разработан в конце 1990-ых Джоан Дэемен и Винсентом Риджменом, и был выбран как симметричный алгоритм блочного шифрования (AES) в 2001 году. За прошедшие десять лет он заменил стандарт шифрования данных (DES) в большинстве приложений, и стал предпочтительным блочным шифром для любого нового безопасного приложения. У него есть три возможных ключевых размера (128, 192, и 256 бит), и в 2003 году американское правительство публично объявило, что AES-128 может использоваться, чтобы защитить сведения, составляющие государственную тайну до уровня "секретно", и что AES-192 и AES-256 могут использоваться, чтобы защитить сведения, составляющие государственную тайну до уровня "совершенно секретно".

Своей важностью и популярностью, безопасность AES привлекла много внимания, и считается одной из самых острых областей исследования в криптографическом анализе. Самым крупным достижением было недавнее открытие атак методом связанных ключей на полные версии AES-192 и AES-256, которые быстрее чем полный перебор, но имеют непрактичные сложности. С другой стороны исследования, связно-ключевые атаки, требующие практической временной сложности 245, были найдены на AES-256 с 10 раундами, и атаки связанного ключа, требующие, чтобы полупрактическая сложность времени была 270 найдена на AES-256 с 11 раундами.

Основная слабость AES-192 и AES-256, использованная в этих атаках, заключалась в их чрезвычайно простом алгоритме генерирования дополнительных ключей. В модели связано-ключевой атаки это позволяло устранять разницу в данных с соответствующими основными заменами AES высоких раундов. Что привело к очень высокой характеристике дифференциальной вероятности, которая привела к значительно улучшенной временной сложности. Однако такие атаки предполагают, что противник может запросить, чтобы поле шифрования изменило неизвестный ключ известным способом. Некоторые из этих атак даже предполагают, что противник может получить большое количество связанных ключей, или, что он может получить связанные промежуточные подключи — это видится возможным. Следовательно, атаки методом связанных ключей нужно учитывать во время этапов проектирования и сертификации новых шифров, но эти методы не считаются реалистической угрозой в практических протоколах системы защиты, которые используют стандартный способ блочного шифрования.

В этой статье мы выбираем классическую модель атаки единственным и хорошо известным ключом или перебором пар открытого текста/зашифрованного текста. В этой модели противник имеет дело с очень хорошо разработанным каналом передачи данных AES, и не может непосредственно извлечь выгоду из его слабого алгоритма генерирования дополнительных ключей (расписание ключей). Следовательно, нет никаких известных атак на полный шифр ни на одной из трех разновидностей AES, и лучшее, что мы можем сделать – это атаковать версии AES меньших раундов.

  • В случае AES-256, наибольшее число раундов, которые могут подвергнуться нападению - 8.
  • В случае AES-192 есть одна атака на AES с 8 раундами, которая был опубликована в книге "Усовершенствованный Криптоанализ"[1], это крайний случай: она требует вычисление по существу всех возможных пар открытого/зашифрованного текста под неизвестным ключом, и даже тогда время, требуемое для получения ключа, только в 16 раз меньше, чем полный перебор (можно утверждать, что предлагая полную книгу шифров размера 2128, нет никакой потребности к нахождению фактического ключа, чтобы легко дешифровать зашифрованный текст).
  • В случае АES-128, нет никаких известных атак на его 8 – раундовую версию, но на разновидностях с 7 раундами некоторые есть.

Чтобы улучшить все эти известные атаки, и особенно незначительную атаку на AES-192 с 8 раундами, которую никто не смог улучшить за прошедшие десять лет, мы разрабатываем три новых метода криптоанализа.

Начнем с атаки на AES с 7 раундами, разработанной Гилбертом и Минером, которая создает большую таблицу из 272 записей, где каждая запись содержит последовательность 256-байтовых значений. Эта идея была расширена на AES с 8 раундами Demirci и Selcuk, которые создали еще бОльшую таблицу из 2192 записей (снова содержащую последовательности 256-байтовых значений, которые созданы немного измененным способом). Из-за того, что требуется 2200 раз создать эту таблицу, эта атака хуже, чем полный перебор AES-192 с 8 раундами, и может быть применена только к AES-256 с 8 раундами.

Наша первая новая идея (названная табулированием мультимножества) состоит в том, чтобы заменить последовательность 256-байтовых значений в каждой записи таблицы мультимножеством ее значений. Даже при том, что мы теряем некоторую информацию, мы показываем, что все еще возможно использовать такую таблицу, чтобы с высокой вероятностью отбросить неверные предположения ключа. Это преобразование позволяет сократить количество записей таблицы (и, таким образом, время, требуемое для подготовки таблицы) множителем 216. Лучшее сохранение (множителем 257) в размере таблицы получено другим новым методом, который мы называем дифференциальным исчислением. Он использует некоторый усеченный дифференциал (у которого не должно быть слишком высокой или низкой вероятности, как требуется в стандартных или невозможных дифференциальных атаках), чтобы перечислить записи такой таблицы более эффективным способом: Вместо того чтобы непосредственно перечислить значения, противник получает их косвенно, перечисляя значения дифференциала входа и выхода определенных внутренних таблиц подстановок S. Уменьшая огромную сложность таким способом, мы можем теперь использовать его попеременно со сложной атакой Demirci и Selcuk, чтобы значительно улучшить его. Наконец, мы разрабатываем новый метод формирования ключа, который использует слабый алгоритм формирования дополнительных ключей AES при использовании следующего удивительного наблюдения: В особом случае AES-192 с 8 раундами, возможно вычислить один байт подключа (используемого перед первым раундом) непосредственно от четырех байтов последнего подключа (используемого в конце восьмого раунда), несмотря на их расстояние. Так как наша атака требует угадывания этих пяти байтов подключа в первых и последних раундах, мы получаем дополнительные сбережения 28 в нашей временной сложности[прим. 1]. Комбинируя эти три метода, мы можем теперь взломать AES-192 с 8 раундами примерно в миллион раз проще, чем полным перебором. Наши новые результаты и их сравнение с ранее известными одно-ключевыми нападениями представлены в Таблице 1. Можно заметить, что наша временная сложность для AES с 8 раундами значительно меньше, чем лучшие предыдущие результаты и для AES-192 и для AES-256.

Краткое описание AES

Расширенным стандартом шифрования (AES) является SP-сеть, которая поддерживает ключевые размеры 128, 192, и 256 битов. 128-битовый открытый текст рассматривают как матрицу байт размером 4x4, где каждый байт представляет значение в поле GF(28). Раундовая AES применяет четыре операции к главной матрице:

  • SubBytes (SB) — применение того же самого, 8-битового к 8-битовой обратимой таблице подстановок S- 16 раз параллельно на каждом байте State,
  • ShiftRows (SR) — циклический сдвиг i-ого ряда на i байт влево,
  • MixColumns (MC) — умножение каждой колонки константой матрицы 4x4 поля GF(28), и
  • AddRoundKey (ARK) — добавляется ключ итерации (Round Key; побитовая операция XOR)
Рисунок 1. Раунд AES

В первом раунде, применена дополнительная операция AddRoundKey (использующая подключ), а в последнем раунде опущена операция MixColumns. Раунды, которые включают операцию MixColumns, называют полными раундами.

Число раундов зависит от длины ключа: 10 раундов для 128-битовых ключей, 12 раундов для 192-битовых ключей, и 14 раундов для 256-битовых ключей. Раунды пронумерованы , где является числом раундов. Ради простоты мы обозначим AES с n-bit ключами AES-n, например, AES с 128-битовыми ключами (и таким образом с 10 раундами) обозначим AES-128. И используем AES, чтобы обозначать все три разновидности AES.

Алгоритм генерирования дополнительных ключей AES берет пользовательский ключ и преобразовывает его в подключей по 128 битов каждый. Множество подключей обозначено , где каждое слово состоит из 32 бит. Пусть длина ключа будет – число 32-ух битных слов, тогда первые слов , загруженных пользователем, подставляются в ключ. Оставшиеся слова обновлены согласно следующему правилу:

For , do
  • If then
  • else if ,
  • Otherwise ,
где - множество предопределенных констант, и <<<8 обозначает смещение слова на 8 битов влево.

Примечания к статье

В продолжении мы используем следующие определения и примечания: массив State начала i-ого раунда обозначим , и его байты обозначим , как показано на Рисунке 1. Точно так же массив State после операции SubBytes и операции ShiftRows i-ого раунда обозначим и соответственно.

Мы обозначаем подключ i-ого раунда как , и первый ключ как , т.е., .

В некоторых случаях мы интересуемся порядком чередования операции MixColumns и дополнения подключа. Поскольку эти операции линейны, их можно чередовать: сначала бинарный оператор XOR с эквивалентным подключом и только тогда применение операции MixColumns. Мы обозначаем эквивалентный подключ для измененной версии как , то есть, . Байты подключей пронумерованы , в соответствии с соответствующими байтами массива State.

Мы используем следующие примечания для значений среднего уровня шифрования: промежуточное состояние в начале i-ого раунда в шифровании обозначено как , и его байты обозначены , где . Точно так же значения среднего уровня после операции SubBytes и операции ShiftRows i-ого раунда обозначим как и , соответственно.

В наших атаках мы главным образом рассматриваем шифрование -множества, которые являются структурированными наборами 256 открытых текстов , в которых каждый активный байт принимает каждое из 256 возможных значений ровно однажды, и каждый из других 15 байтов (возможно различных) постоянен. Байт массива State называют симметричным если бинарная операция XOR его 256 значений во время шифрования -множества - ноль.

Во всех наблюдениях, рассматривая версии уменьшения раунда AES, нумерация раундов запускается с нулевого раунда. Когда мы анализируем поведение некоторых последовательных внутренних раундов AES, мы смещаем нумерацию раундов соответственно, в зависимости от числа раундов, которые мы добавляем вначале.

Наконец, мы измеряем временную сложность всех атак в модулях, которые эквивалентны единственной операции шифрования, соответствующей разновидности раундового уменьшения AES. Мы измеряем сложность пространства в модулях, которые эквивалентны хранению единственного открытого текста (а именно, 128 битов). Чтобы быть абсолютно справедливыми, мы считаем все операции выполненными во время наших атак, и в особенности мы не игнорируем время и пространство, требуемое для подготовки таблиц замен, которые мы используем.

Предыдущая работа

Первая атака, разработанная против AES, была Square - атака, которая была протестирована ее разработчиками[2]. Square - атака основана на:

TemplateDifinitionIcon.svg Определение «Замечание 1»
Рассмотрите шифрование -множества посредством трех полных раундов AES. Набор 256 соответствующих шифрованных текстов сбалансирован, то есть, бинарная операция XOR 256 значений в каждом из его 16 байтов - нуль.

Это видно из структуры AES, показаной на рисунке 2. Это свойство основано на многих вариантах атак на уменьшенные раунды AES. Исходное представление предлагает атаку с 6 раундами с временной сложностью 272, которая была позже улучшена в[1], используя метод частичных сумм, чтобы предложить самую известную атаку на AES с 6 раундами (со временем 242).

В [3], Гилберт и Минер предложили совершенствовать информацию о промежуточных значениях шифрования -множеств, использованного в Square-атаке. Их атака основана на следующем замечании:

TemplateDifinitionIcon.svg Определение «Замечание 2»
Рассмотрите шифрование -множества посредством трех полных раундов AES. Для каждого из 16 байтов шифрованного текста мы можем определить последовательность 256 значений для этого байта, упорядочивая открытые тексты согласно значению их активного байта. Затем любая такая последовательность полностью определена только на 9 байтов, которые являются комплексными функциями констант в -множестве и ключевых байтах. Следовательно, для любой фиксированной позиции байта, есть самое большее 272 возможных последовательностей, когда мы рассматриваем все возможные варианты ключей и -множества (из "теоретически возможных" 256-байтовых последовательностей, и из последовательностей, которые могли быть потенциально определены выбором 15 постоянных байтов и 256 ключевых битов.)
Рисунок 2. Разработка -множества через 3 раунда AES, где А - обозначение активного байта, B - обозначение сбалансированного байта, и C - обозначение постоянного байта

Это наблюдение использовалось в [3], чтобы предпринять атаку на AES-128 с 7 раундами и временной сложностью, немного меньшей, чем у метода полного перебора ключей. Так как алгоритм атаки сложен и не используется в нашей статье, мы опускаем его здесь.

В своей работе [4], Demirci и Selёcuk расширяли наблюдение другим раундом.[3]

Они показали следующее:

TemplateDifinitionIcon.svg Определение «Замечание 3»
Рассмотрите шифрование -множества посредством четырех полных раундов AES. Для каждого из 16 байтов массива State упорядоченная последовательность 256 значений того байта в соответствующих шифрованных текстах полностью определена только 25-байтовыми параметрами. Следовательно, для любой фиксированной позиции байта, есть самое большее возможных последовательностей, когда мы рассматриваем все возможные варианты ключей и -множества[прим. 2].

Это замечание использовалось в [4], чтобы предпринять атаки на разновидности AES-256 с 8 раундами и с 7 раундами. Атака на AES-256 с 7 раундами примерно следующая:

1. Фаза предварительной обработки: Вычислите все 2192 возможных значений 255-байтовых последовательностей, данных в Замечании 3, и сохраните их в хэш-таблице.

2. Онлайн-Фаза:

(a) Угадайте значение четырех байтов в ключе и одного байта в , и для каждого предположения, создайте -множество из данных. (Например, если активный байт -множества – 0 байт, то предполагаемые байты - байты 0, 5, 10, 15 из и 0 байт из . Отметьте, что 0 байт из используется только, чтобы вычислить порядок значений в -множества.
(b) Угадайте четыре байта эквивалентного подключа и один байт эквивалентного подключа и частично дешифруйте шифрованные тексты -множества, чтобы получить последовательность 256 промежуточных значений одного байта массива . (Например, если байт, который будет проверен, является 0 байтом, то байты подключа, которые должен угадать противник, являются 0 байтом из и 0, 7, 10, 13 байтами из ).
(c) Проверьте, существует ли последовательность в хэш-таблице. В противном случае отбросьте предположение ключа.

Сложность атаки данных - 232 выбранных открытых текстов. Временная сложность фазы - онлайн относительно скромна - 280, но сложность пространства и временная сложность в операциях шифрования требует подготовить эту большую таблицу, что приблизительно 2200. Эти сложности больше, чем полный перебор и AES-192 и AES-128. Однако, Demirci и Selёcuk представили компромисс, который позволяет уменьшить сложность памяти за счет увеличения как данных, так и онлайновой временной сложности. Это приводит к атаке на AES-192 с 7 раундами со сложностью данных, равной 296 выбранных открытых текстов, и временой и пространственной сложностям, равным 2144.

Атака из данной работы[4] может быть расширена на AES-256 с 8 раундами, предполагая полный подключ последнего раунда. Это увеличивает временную сложность онлайн-фазы шифрования от 280 до 2208, и лишает возможности повторно балансировать параметры, чтобы атаковать AES-192 с 8 раундами[прим. 3].

Наши новые методы

В этом разделе мы представляем три новых метода. Сначала, мы представляем новую разновидность Замечания 3, которая более сильна и ее проще проанализировать. Затем мы показываем, как анализ комбинации -множества с дифференциалом с 4 раундами позволяет уменьшать сложность памяти атаки множителем 257.

Наконец, мы показываем, что для AES-192 и AES-256, временная сложность атаки с 8 раундами может быть уменьшена, используя соображения алгоритма генерирования дополнительных ключей множителями 232 и 28, соответственно.

Разновидность мультимножества Demirci - Selcuk

Мы начинаем с нашего нового варианта Замечания 3.

TemplateDifinitionIcon.svg Определение «Замечание 4»
Рассмотрите шифрование -множества посредством четырех полных раундов AES. Для каждого из , (неупорядоченное) мультимножество [прим. 4] полностью определено 24-байтовыми параметрами:
  • Полные 16 байт ;
  • Четыре байта . (Например, если активный байт -множества - 0, тогда эти байты - 0, 1, 2, 3);
  • Четыре байта подключа . ((Например, если тогда эти байты: 0, 5, 10, 15).

Кроме того, это мультимножество может принять только 2184 значений (из "теоретически возможных" значений).

У нашего варианта есть несколько преимуществ перед Замечанием 3:

  • Параметры, от которых зависит последовательность, задаются явно. Это крайне важно для уменьшений в числовых параметрах, представленных в следующем разделе.
  • Меньшее число возможных конфигураций в нашем варианте (2184 вместо 2192) позволяет уменьшать требования к памяти атаки и временную сложность предварительной обработки фазы множителем 28.
  • Так как мы рассматриваем мультимножество вместо упорядоченной последовательности, противник не должен знать порядок значений в -множестве в начале четырех раундов. Это позволяет пропускать предположение одного байта в подключе (сокращение временной сложности онлайн-фазы до 28).

Доказательство. Доказательство раскрывает метод "сведение к середине".

Мы начинаем с "конца" четырех раундов. Во-первых, мы замечаем что, если известны, то знание 0, 5, 10, 15 байтов из приводит к знанию всего первого столбца перед операцией AddRoundKey 3 раунда во всех этих 256 шифрованиях. Так как AddRoundKey сохраняет разницу, это приводит к требуемым значениям вектора замены

Во-вторых, чтобы знать значения , достаточно, знать значение , который дан как часть параметров, и замены

Так как операции ShiftRows MixColumns и AddRoundKey линейны, достаточно знать замены

Теперь, мы возвращаемся к "началу" четырех раундов. В 0 раунде, замены известны — это есть точно 256 возможных замен в 0 байте (остальная часть байтов равна).

Отметим, что порядок замен не известен, но это уже не тревожит противника в нашей атаке, он интересуется только мультимножеством, а не последовательностью.

Так как операции ShiftRows, MixColumns, и AddRoundKey линейны, замены в байтах также известны

Из-за структуры -множества эти замены являются активными в 0, 1, 2, 3 байтах и пассивными в остальной части байтов. Так как 0, 1, 2, 3 байты из даны как часть параметров, значения байтов 0, 1, 2, 3 из , таким образом, также известны, и так являются 0, 1, 2, 3 байтами из .

Так как замены во всех байтах, за исключением 0, 1, 2, 3 являются нулем для всех j=1, 2,...,255, это подразумевает, что полный вектор замены известен, как требовалось выше.

Наконец, так как мультимножество зависит от 24-байтовых параметров, оно может принять 2192 возможных значений. Однако, в этом количестве, каждое -множество представлено 28 мультимножествами согласно 256 возможным вариантам . Мы можем тогда сократить количество параметров одним, выбирая так, что (это возможно, так как 0 байт в состоянии является активным). Это сокращает количество возможных мультимножеств до 2184, завершая доказательство.

Метод вычисления дифференциалов

Замечание 4 показывает, что возможные мультимножества зависят от 24 явно установленных параметров. Чтобы уменьшить размер предварительно вычисленной таблицы, мы хотели бы выбрать -множество так, что, несколько из этих параметров будут равняться предопределенным константам. Конечно, ключевые байты не известны противнику и таким образом не могут быть "заменены" такими константами. На первый взгляд кажется, что байты в промежуточных состояниях и также не могут быть сделаны равными предопределенным константам, выбирая простые тексты соответственно, так как они разделены от открытых текстов операциями, включающими неизвестный ключ. Однако мы показываем это при использовании дифференциала ожидаемой вероятности (то есть дифференциал, вероятность которого, как предполагается, не особенно высока или особенно низка) для AES с 4 раундами, открытый текст может быть выбран так, что полное 128-разрядное состояние примет большее из 264 определенных значений (которые могут быть вычислены заранее и независимы от выбора ключа) вместо 2128 возможных значений.

Рассмотрите усеченный дифференциал для четырех полных раундов AES, в которых как вводные, так и выводные замены ненулевые в единственном байте (например, 0 байт и во вводе и в выводе). Вероятность этого дифференциала, как ожидают, будет приблизительно 2-120 [прим. 5], и таким образом ожидается, что 2120 случайно выбранных пар с заменами только в 0 байте будут содержать одну пару, которая удовлетворяет дифференциалу.

Кроме того, так как каждое -множество содержит 215 пар замен в единственном байте, набор 2105 в произвольном порядке выбранных -множеств, в которых 0 байт является активным и, как ожидают, будет содержать правильную пару относительно дифференциала. Для правильных пар мы отметим следующее:

Рисунок 3. Характеристика дифференциала с 4 раундами, используемая в нашей атаке
TemplateDifinitionIcon.svg Определение «Замечание 5»
Пусть - правильная пара относительно дифференциала (то есть, замена является ненулевой только в 0 байте и замена для соответствующих шифрованных текстов , также ненулевая только в 0 байте). Затем промежуточное принимает большее из 264 заданных значений.

Доказательство. Доказательство – параметр сведения к середине. Мы начинаем с "начала" четырех раундов. Из-за структуры AES, замена и (то есть, промежуточные значения после операции SubBytes 1 раунда) являются ненулевым только в 0, 1, 2, 3 байтах. Таким образом, эта замена может принять большее из 232 отличных значений.

Так как операции ShiftRows MixColumns, и AddRoundKey линейны, это подразумевает, что замена может принять большее из 232 значений.

С другой стороны от "нижней стороны" мы видим, что замена является ненулевым только в 0, 5, 10, 15 байтах. Так как операции ShiftRows MixColumns, и AddRoundKey линейны, это подразумевает, что замена может принять большее из 232 значений.

Известно, что получившиеся замены ввода и вывода операции SubBytes – есть, в среднем, одна возможность для фактической пары значений ввода/вывода[прим. 6].

Кроме того, эта пара фактических значений не зависит от ключа, и может быть легко найдена, предварительно вычислив полную таблицу распределения замен операцией SubBytes. Так как мы рассматриваем правильную пару, есть пар возможных замен ввода/вывода операции SubBytes во 2 раунде, и есть 264 возможных значений полного состояния , как утверждается.

Это следует из замечания, что, если мы выбираем -множество так, что, -элемент правильной пары относительно этого дифференциала ожидаемой вероятности, нас уверяют, что состояние может принять большее из 264 возможных значений. Кроме того, так как эти значения не зависят от ключа и могут быть вычислены заранее, это позволяет создавать "таблицу возможных мультимножеств" только для этих 264 значений, что уменьшает размер таблицы и временной сложности фазы предварительной обработки множителем 257 как показано ниже.

Три дополнительных комментария:

  • Во-первых, чтобы использовать дифференциал ожидаемой вероятности, мы должны рассмотреть целых 2113 выбранных открытых текстов, что увеличивает сложность данной атаки. Однако, результант выгоден, так как сложность данных была меньшей, чем другие сложности.
  • Во-вторых, чтобы обнаружить правильную пару относительно дифференциала, противник должен угадать несколько ключевых байтов в раундах до и после дифференциала. Однако, оказывается, что, если дифференциал выбран так, что, ненулевые замены находятся в байтах, которые являются активными в -множестве, эти байты ключа совпадают с байтами ключа, которые должны быть угаданы в исходной атаке Demirci-Selёcuk. Следовательно, это не увеличивает временную сложность онлайн-фазы атаки.
  • Наконец, общее количество возможных мультимножеств после комбинации с дифференциалом не , а скорее 2127. Причина этого увеличения состоит в том, что в исходной атаке, количество мультимножеств сокращено множителем 28, так как каждое -множество соответствует 28 заменам мультимножеств согласно возможным вариантам (см. доказательство Замечания 4). В новой версии атаки мы вынуждены выбрать , чтобы быть одним из элементов правильной пары относительно дифференциала, и таким образом каждое -множество соответствует только двум "специальным" мультимножествам[прим. 7].

Поэтому, сложность памяти и временная сложность фазы предварительной обработки уменьшены множителем 257, а не 264, по сравнению с Замечанием 4.

Метод формирования ключа

В этом разделе мы показываем, что временная сложность онлайн - фазы в атаках на AES-192 и AES-256 с 8 раундами может быть значительно уменьшена исходя из соображений относительно расписания ключа (алгоритма формирования дополнительных ключей). В то время как большинство этих соображений просты, одно из них - новое наблюдение, которое позволяет противнику выводить некоторые байты подключа из некоторых других байтов подключа, даже при том, что они разделены многими ключевыми шагами смешивания.

Мы начнем с атаки на AES-192 с 8 раундами. Вспомните, что в онлайн - фазе этой атаки противник должен угадать четыре байта подключа , один байт эквивалентного подключа , четыре байта эквивалентного подключа , и полный . Точное число байтов, которые должны быть угаданы, зависит от выбора активного байта -множества и байта, в котором создано мультимножество. Оказывается что, если байт, который будет исследован в конце 4 раунда, является одним из 1, 6, 11, 12 байтов, то количество предполагаемых ключевых байтов сокращается до трех. Действительно, расписанием ключей AES-192, знание приводит к знанию первых двух столбцов (и таким образом также ) и последнего столбца (и таким образом также ).

Если байт, который будет проверен в конце 4 раунда, является 1 байтом, тогда угадываем, что 13 байт из , байты 3, 6, 9, 12 из , и полный подключ . Однако как только угадывается, байты 3, 6 из и 13 байт из могут быть вычислены из расписания ключей, таким образом, уменьшая временную сложность онлайн-фазы атаки множителем 224.

Сложность может быть далее уменьшена другим множителем 28, используя следующее новое наблюдение:

TemplateDifinitionIcon.svg Определение «Замечание 6»
При помощи расписания ключей AES-192, знание столбцов 0, 1, 3 подключа позволяет выводить 3 столбец ключа (который является фактически 3 столбцом главного ключа).

Основная новинка в этом наблюдении - то, что оно использует слабое расписание ключей AES-192, чтобы обеспечить удивительно длинный "мост" между двумя подключами, которые разделены 8 ключевыми смешенными шагами (примененные в обратном направлении). В частности это позволяет вычислить один байт в подключе непосредственно от четырех байтов в последнем подключе [прим. 8], который сохраняет множитель 28 во временной сложности любой атаки, которая должна угадать эти пять байт подключа. Так как угадывание ключа в первом и последнем раунде очень общее в атаке, это Замечание может быть широко применимым (например, оно может уменьшить временную сложность связано-ключевой атаки на AES-192 с 8 раундами представленной в [14] от 2180 до 2172).

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

.

Так как атака 8-раундовая, то один из байтов подключа, предполагаемых противником, включен в столбец (независимо от активного байта в -множестве), что уменьшает временную сложность другим множителем 28. В итоге, предположения расписания ключей уменьшают временную сложность онлайн - фазы атаки на AES-192 множителем 232.

В атаке на AES-256 с 8 раундами, предположения расписания ключей могут помочь противнику совсем немного. В соответствии с расписанием ключей, подключ независим от подключа , и таким образом единственный байт подключа, который может получить противник, является единственным байтом . Поскольку новое замечание не подходит для AES-256, параметры расписания ключей могут уменьшить временную сложность только множителем 28.

Наша новая атака на AES С 7 раундами

В этом разделе мы представляем нашу новую атаку на AES с 7 раундами. Ради простоты мы представляем здесь только основную разновидность атаки, которая используется позже в качестве части атаки с 8 раундами. В Приложении A мы показываем, как улучшить атаку, используя изменение дифференциала ожидаемой вероятности и компромиссов времени/памяти/данных, так, что получающаяся временная сложность будет ниже, чем сложность всех ранее известных атак на AES с 7 раундами (во всех его трех разновидностях).

Основная атака

В этой атаке байт с ненулевой заменой в дифференциале ожидаемой вероятности – 0 (нулевой) байт, и в вводе и в выводе различен. Активный байт -множества и байт, который проверен в , выбраны так, чтобы быть 0 байтом также. Атака работает так же, если эти байты заменены какой-либо другой парой байтов, пока соответствие между дифференциалом и -множеством сохранено.

Алгоритм основной атаки следующий:

1. Фаза предварительной обработки:

Вычислите 2127 возможных значений "специальных" мультимножеств, используя Замечания 4 и 5, и сохраните их в хэш-таблице.

2. Онлайн-фаза:

(a) Фаза A – Обнаружение правильной пары
i. Выполните 281 операций шифрования 232 открытых текстов, так в каждой операции, 0, 5, 10, 15 байты предполагают 232 возможных значений, а остальная часть байтов является постоянной.
ii. Для каждой операции сохраните шифрованные тексты в хэш-таблице и ищите пары без замен в 1, 2, 3, 4, 5, 6, 8, 9, 11, 12, 14, 15 байтах[прим. 9]. Так как это - 96-разрядная фильтрация, то приблизительно 248 пар остаются.
iii. Для каждой оставшейся пары предположите 0, 5, 10, 15 байты из и проверьте, является ли только 0 байт ненулевым в . Для каждого предположения ключа останутся приблизительно 224 пары, как ожидается.
iv. Для каждой оставшейся пары предположите 0, 7, 10, 13 байты из и проверьте, является ли ненулевым только 0 байт в . Для каждого предположения ключа останется только одна пара, как ожидается.
(b) Фаза B – Проверка -множества
i. Для каждого предположения восьми байтов подключа, сделанных в фазе A и для соответствующей пары, возьмите один из элементов пары, обозначьте это , и найдите его -множество, используя знание 0, 5, 10, 15 байтов из . (Это сделано, взяв , применив бинарную операцию XOR с 255 возможными значениями, которые являются ненулевыми только в 0 байте, и дешифровав 255 полученных значений посредством 0 раунда, используя известные байты подключа. Получившиеся открытые тексты - другие элементы -множества.)
ii. Угадайте 0 байт из , и использовав знания 0, 7, 10, 13 байтов из , частично дешифруйте шифрованные тексты -множества, чтобы получить мультимножество
iii. Проверьте, существует ли мультимножество в хэш-таблице. В противном случае отбросьте предположение ключа (возможно использование вспомогательных методов, таких как повторение атаки с заменой выходного байта).
(c) Внимательно ищите остальную часть ключа: Для каждого оставшегося предположения ключа, найдите оставшиеся байты ключа полным перебором.

Понятно, что временная сложность онлайн-фазы атаки зависит от шифрования 2113 открытых текстов, и следовательно, сложность данных и временная сложность этой части атаки - 2113. Сложность памяти - 2129 128-разрядных блоков, так как каждое мультимножество содержит приблизительно 512 битов информации, и ее представление может быть легко сжато в 512 битов пространства. Временная сложность фазы предварительной обработки атаки примерно операций шифрования.

В Приложении A мы показываем, что атака может быть улучшена, изменяя дифференциал ожидаемой вероятности, используя несколько дифференциалов параллельно, и применяя компромиссы времени/памяти/данных. Получающиеся сложности лежат на следующем кривой компромисса: сложность данных - выбранных простых текстов, временная сложность – операций шифрования, требование к памяти – блоков AES, для любого .

Выбирая n = 13, все эти три сложности компенсируются в 2116, что ниже, чем сложности времени всех известных атак на AES с 7 раундами во всех его трех разновидностях (см. Таблицу 1).

Расширения атак на AES-192 с 8 раундами и AES-256

В этом разделе мы представляем первую существенную атаку на AES-192 с 8 раундами. Сложность данных атаки - 2113 выбранных открытых текстов, требование к памяти - 2129 128-разрядных блоков, и временная сложность - 2172 операций шифрования. Разновидность атаки может быть применена к AES-256 с 8 раундами. Требования к данным и требования к памяти остаются неизменными, но временная сложность увеличена до 2196 шифрования. Мы представляем атаку на AES-192; атака на AES-256 подобна.

В атаке, представленной ниже, мы выбираем, чтобы ненулевым байтом в замене выходного дифференциала ожидаемой вероятности, был 1 байт. Соответственно, байт, который будет проверен в -множестве, также будет выбран в качестве 1 байта. Это изменение требуется, чтобы применить размышления относительно расписания ключей, представленные в Разделе 4.3. Единственный ненулевой байт в замене входного дифференциала и единственный активный байт -множества могут быть все еще выбраны произвольно, пока они - те же самые. Без потери общности, в продолжении, мы предполагаем, что этот байт – 0 байт.

Тривиальное обобщение атаки с 7 раундами, представленной в Разделе 5 с восьми-раундовой определит полный , и для каждого предположения, дешифрует все шифрованные тексты через последний раунд и применит атаку с 7 раундами. В нашей атаке этот подход приводит чрезвычайно большой временной сложности. Определенно, обнаружение правильной пары потребовало бы операций шифрования. Вместо этого мы используем ранний метод аварийного прекращения работы, который был описан в [5]. Мы представляем здесь метод только кратко, и отправляем читателя к [5] для полного представления.

Таблица 1. Сравнение предыдущих результатов с нашими новыми атаками

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

**[4] оценка стоимости частичного шифрования как 2-8 операций шифрования. Поскольку по крайней мере шесть столбцов, которые принимают участие в частичном шифровании/дешифровании, мы полагаем, что 2-2.4 более точная оценка.

*** — сложность выше, чем говорится в [6] из-за недостатков в анализе.

Если сказать иначе, временная сложность измеряет время в модулях шифрования.

Сложность памяти измерена в блоках AES.

CP — Выбранный открытый текст, MA — Доступная память.

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

Отметьте что, если правильная пара, то у соответствующих промежуточных состояний есть ненулевая замена только в 3, 6, 9, 12 байтах. Следовательно, в каждом столбце только 28 возможных замен. Так как операции MixColumns и AddRoundKey линейны, это подразумевает, что в каждом столбце есть только 28 возможных замен, и таким образом только возможных пар фактических значений. В методе, представленном в [5], противник рассматривает эти 240 пар заранее, шифрует их через 7 раунд, и хранит фактические значения до последней операции AddRoundKey в хэш-таблице, сортированной выходными заменами. В онлайн-фазе атаки, для каждой исследованной пары, противник рассматривает каждый смещенный столбец (например, 0, 7, 10, 13 байты) независимо, и получает доступ к хэш-таблице в строке, соответствующей замене в шифрованном тексте. Ожидается, что значений появляются в каждой строке. Так как таблица дает фактические значения перед операцией AddRoundKey, и шифрованные тексты оценены после этой операции, каждая из пар в таблице предлагает одно значение для 32-разрядных подключей, соответствующих тому смещенному столбцу.

Поэтому, для каждой исследованной пары, и для каждого смещенного столбца, противник получает список 28 кандидатов на 32-разрядный подключ, соответствующий тому столбцу. В основной разновидности атаки противник соединял эти предположения с 232 предположениями для полного , и для каждого предположения, он дешифрует пару шифрованного текста через 7 раунд. Затем он использует подобную предварительно вычисленную таблицу для 6 раунда, чтобы получить список 28 возможных значений 3, 6, 9, 12 байтов из . Для каждого такого значения противник проверяет отношения между 3, 6 байтами из и подключа как описано в Разделе 4.3. В противном случае предположение подключа отброшено. Так как это - 16 разрядная фильтрация, противник оставляет 224 кандидатов на полный и 3, 6, 9, 12 байты из . Наконец, используя предварительно вычисленную таблицу еще в 0 раунде, противник получает список 28 возможных значений 0, 5, 10, 15 байтов из . Для каждого такого значения противник проверяет, есть ли отношение между 15 байтом из и подключом как описано в Разделе 4.3. В противном случае предположение подключа отброшено. Так как это - 8-разрядная фильтрация, противник оставляет с 224 кандидатов на полный , 3, 6, 9, 12 байты из , и 0, 5, 10, 15 байты из . Для каждого из этих кандидатов, - правильная пара относительно дифференциала ожидаемой вероятности и может быть применена вторая фаза атаки.

Временная сложность этой процедуры - 240 простых операций для каждой исследованной пары, или операций шифрования всего. Временная сложность может быть немного уменьшена при использовании более сложной предварительно вычисленной таблицы, чтобы проверить непротиворечивость между 3, 6 байтами из и подключа . Таблица берет 3, 6 байты из в обеих парах, наряду с 2, 3, 5, 6 байтами из , и возвращает непротиворечивые значения для байтов 3, 6 из , если есть такие. Предварительное вычисление сделано, исходя из всех возможных кандидатов на пару байтов для наряду с соответствующими байтами , чтобы видеть, удовлетворяют ли дешифрованные значения линейной зависимости замен перед операцией SubBytes 5 раунда. Если это верно, запись, соответствующая и все подключи , которые удовлетворяют связке ключей сохранены с соответствующими байтами . Мы отмечаем, что для каждого ключа и каждой пары, есть вероятность , что условие удовлетворено, и таким образом, только 256 из записей в таблице непусты.

Во второй части онлайн - фазы атаки, выполняемой для каждой из этих 2144 пар и каждого из этих 224 подключей, соответствующих паре, противник создает -множество и проверяет, появляется ли соответствующее мультимножество в таблице. Отметьте, что, в то время как в атаке с 7 раундами эта фаза требует предположения дополнительного байта подключа (который является 13 байтом из ), в этой атаке, байт подключа может быть получен из подключа . Временная сложность второй части операций шифрования.

Поэтому, полное требование к памяти атаки - 2129 128-разрядных блоков (как в основной версии атаки с 7 раундами), сложность данных - 2113 выбранных открытых текстов, и временная сложность - 2172 операций шифрования. Эти сложности гораздо лучше, судя по единственной ранее известной атаке на AES-192 - SQUARE - атаке [1], которая требует почти всю книгу шифров и временную сложность 2188 операций шифрования.

Краткое изложение

В этой статье мы представили три новых метода криптографического анализа, которые могут использоваться, чтобы улучшить самые известные сложности всех известных атак на 7 и 8 раундовые версии AES, как детализировано в Таблице 1. В частности мы описываем первую реальную атаку на AES-192 с 8 раундами, которая не использует полную книгу шифров, чтобы незначительно улучшить временную сложность полного перебора. Однако во всех наших атак есть непрактичные сложности, и таким образом они не подвергают опасности безопасность любой представленной системы.

А. Улучшение атаки на AES С 7 раундами

А.1 Изменение дифференциала ожидаемой вероятности

Наше первое улучшение уменьшает сложности данных и времени атаки множителем 28, не влияя на требования к памяти.

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

Такой компромисс достигнут, немного изменяя дифференциал ожидаемой вероятности, используемый в атаке. Вместо требования, чтобы входная замена была ненулевой только в 0 байте, мы можем позволить замене быть ненулевой также в одном из 5, 10, 15 байтов. Эти байты выбраны так, что число возможных замен в состоянии, не увеличено, и таким образом, сложность памяти сохранена.

Это изменение уменьшает сложность данных атаки до 2105, так как оно позволяет противнику использовать структуры размера 216, которые содержат 231 пар с входной заменой дифференциала. С другой стороны изменение требует, чтобы предположения четырех дополнительных байтов , чтобы обнаружить правильную пару (если дополнительный байт – 5 байт, то дополнительные предполагаемые 3, 4, 9, 14 байты). В результате число пар, остающихся после шага первой фильтрация атаки, увеличено до 272 (вместо 248). Для каждой такой пары, есть 224 возможных значения 12 байтов подключа (8 байтов и 4 байта ), для которых эта пара удовлетворяет дифференциалу ожидаемой вероятности. Поскольку в атаке с 8 раундами, эти значения могут быть найдены с временной сложностью 224 поиска по таблице для каждой пары, используя ранний метод аварийного прекращения работы. Таким образом, временная сложность Фазы A измененной атаки - 296 просмотров таблицы.

В фазе B, мы замечаем, что так как значения 3, 4, 9, 14 байтов из не важны исследованию -множества, фаза должна быть выполнена только 216 раз для каждой из этих 272 пар (вместо 224 раз). Таким образом, ее временная сложность операций шифрования. Поэтому, полная временная сложность атаки все еще во власти шифрования открытых текстов, и таким образом и сложность данных и временная сложность атаки уменьшены до 2105.

А.2 Использование нескольких дифференциалов параллельно

Наше второе улучшение уменьшает сложность данных и сложность времени множителем 5, не влияя на требования к памяти.

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

Однако в измененной атаке сложность данных может быть уменьшена другим образом не влияя сложность памяти. Мы замечаем, что, так как дополнительный "активный" байт в дифференциале ожидаемой вероятности не используется в анализе -множества, он может быть выбран, не влияя на сложность памяти. Есть шесть возможных способов выбрать этот байт (5, 10, 15 байты во вводе и 1, 2, 3 байты вывода), и пять из них могут быть использованы параллельно с тем же самым набором выбранных открытых текстов[прим. 10].

Это уменьшает сложность данных атаки множителем 5, не влияя на сложность памяти. Так как временная сложность зависит шифрования открытых текстов, она также уменьшено множителем 5. Поэтому, сложность данных и сложность времени измененной атаки меньше, чем 2103. В продолжении мы предполагаем ради простоты, что эти сложности равны 2103.


А.3 Компромиссы времени/памяти/данных

Мы завершаем точной настройкой сложностей, используя простой компромисс между данными, временем, и памятью как предложено в [4]. В фазе предварительной обработки мы предварительно вычисляем таблицу только для некоторых из значений, и затем для каждого предположения ключа, мы выполняем атаку для нескольких -множеств, чтобы компенсировать недостающую часть таблицы. Для каждого , этот компромисс уменьшает сложность памяти и временную сложность фазы предварительной обработки множителем 2n, и увеличивает сложность данных и онлайновую временную сложность тем же самым множителем . Получающиеся сложности лежат на следующей кривой компромисса: сложность данных – выбранных открытых текстов, временная сложность – операций шифрования, требование к памяти – блоков AES, для любого . Выбирая , все эти три сложности компенсируются до 2116, что ниже, чем сложности времени всех известных атак на AES с 7 раундами во всех его трех разновидностях.

Контакты авторов материала

  1. Faculty of Mathematics and Computer Science, Weizmann Institute of Science, P.O. Box 26, Rehovot 76100, Israel, E-mail: orr.dunkelman@weizmann.ac.il, nathan.keller@weizmann.ac.il, adi.shamir@weizmann.ac.il

Примечания

  1. Та же самая идея может использоваться, чтобы улучшить временную сложность нескольких других атак, таких как [10,14] тем же самым множителем 28
  2. В [4] авторы отмечают, что функция может быть записана как , и таким образом можно сократить количество возможных последовательностей, выбирая некоторый , и при рассмотрении увеличенной функции . В этом случае количество параметров сокращено до 24, количество "интересных" записей в каждой последовательности сокращено к 255 (так , независимо от выбора и ), и количество возможных последовательностей сокращено до .
  3. Мы отмечаем, что в более свежей статье, Demirci и др. [5] говорили, что, оптимизируя их метод они могут также атаковать AES-128 с 7 раундами быстрее, чем полный перебор. Однако мы отмечаем, что анализ [5] неверно, и корректное время выполнения атаки приблизительно в 232 раза больше, чем утверждается, и в особенности больше сложность, чем поиск ключа полным перебором для 128-разрядной ключевой версии.
  4. В отличие от множеств, элементы могут встречаться многократно, и мультимножество сохраняет это разнообразие наряду со значениями
  5. Вероятность 2-120 базируется при условии, что AES с 4 раундами ведет себя как случайная перестановка относительно этого дифференциала. Если дело обстоит не так, ожидается, что могут существовать другие более мощные атаки на AES
  6. Фактически, учитывая различия ввода/вывода, с вероятностью приблизительно 1/2 нет таких пар, с вероятностью приблизительно 1/2 есть две пары, и с вероятностью приблизительно 1/256 есть четыре пары
  7. Мы отмечаем, что, в то время как таблица возможных мультимножеств создана согласно одному элементу правильной пары, может произойти так, что в фактической атаке, другой элемент выбран в качестве , и таким образом мультимножество не соответствует таблице (даже для правильного ключевого предположения). Простое решение состоит в том, чтобы повторить атаку для обоих элементов правильной пары. Более усовершенствованное решение, которое позволяет сохранять дополнительный второй фактор во временной сложности атаки, состоит в том, чтобы сохранить мультимножества только до бинарной операции XOR с постоянной величиной. Это может быть достигнуто маленьким изменениями в предварительной обработке фазы, строя из бинарной операции XOR каждое мультимножество с 256 возможными значениями байта и храня в таблице получающееся мультимножество, которое является наименьшим в лексикографическом порядке среди этих 256 возможностей
  8. Четыре байта 0 и 4 (для того, чтобы получить 0 байт из ) и байты 7 и 15 (для того, чтобы получить 3 байт из )
  9. В описании нашей атаки мы предполагаем, что последний раунд не содержит операцию MixColumns. Если она действительно содержит ее, то можно поменять порядок MixColumns последнего раунда и AddRoundKey и применить атаку с соответствующими изменениями
  10. Чтобы сделать это, противник считает структуры размера 296 открытых текстов каждая, в которых 1, 6, 11, 12 байты являются постоянными, а другие байты берут все 296 возможных значений. Это позволяет использовать 5 и 10 байты как дополнительный активный байт во вводе дифференциала

Литература

  1. 1,0 1,1 1,2 Ferguson, N., Kelsey, J., Lucks, S., Schneier, B., Stay, M., Wagner, D., Whiting, D.: Improved Cryptanalysis of Rijndael. In: Schneier, B. (ed.) FSE 2000. LNCS, vol. 1978, pp. 213–230. Springer, Heidelberg (2001)
  2. Daemen, J., Rijmen, V.: AES Proposal: Rijndael, AES proposal (1998)
  3. 3,0 3,1 3,2 Gilbert, H., Minier, M.: A collision attack on 7 rounds of Rijndael. In: Proceedings of the Third AES Candidate Conference (AES3), New York, USA, pp. 230–241 (2000)
  4. 4,0 4,1 4,2 4,3 4,4 Demirci, H., Selёcuk, A.A.: A Meet-in-the-Middle Attack on 8-Round AES. In: Nyberg, K. (ed.) FSE 2008. LNCS, vol. 5086, pp. 116–126. Springer, Heidelberg (2008)
  5. 5,0 5,1 5,2 Lu, J., Dunkelman, O., Keller, N., Kim, J.: New Impossible Differential Attacks on AES. In: Chowdhury, D.R., Rijmen, V., Das, A. (eds.) INDOCRYPT 2008. LNCS, vol. 5365, pp. 279–293. Springer, Heidelberg (2008)
  6. Demirci, H., Taskin, I., C ёoban, M., Baysal, A.: Improved Meet-in-the-Middle Attacks on AES. In: Roy, B., Sendrier, N. (eds.) INDOCRYPT 2009. LNCS, vol. 5922, pp. 144–156. Springer, Heidelberg (2009)