Автоматический поиск атак на алгоритм AES с сокращенным раундом и на приложения

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 23:05, 21 декабря 2015.
Automatic Search of Attacks on round-reduced AES and Applications
Automatic Search of Attacks on round-reduced AES and Applications.png
Авторы Charles Bouillaguet[@: 1]
Patrick Derbez[@: 2]
Pierre-Alain Fouque[@: 3]
Опубликован 2011 г.
Сайт CRYPTO 2011
Перевели Nikita Vasiliev
Год перевода 2015 г.
Скачать оригинал

__NUMBEREDHEADINGS__

Аннотация. В этой статье мы опишем универсальные и мощные алгоритмы для поиска атак типа "человек по середине" и "предполагать и определять" на байтно-ориентированные симметричные примитивы. Для демонстрации возможностей таких инструментов мы покажем, что они позволяют автоматически определять новые атаки на алгоритм AES с сокращенным раундом с очень низкой сложностью данных и находить улучшенные атаки на алгоритмы, основанные на AES, такие как Alpha-MAC и Pelican-MAC, а также на поточный шифр LEX также основанный на стандарте AES. В конечном итоге, инструменты могут быть использованы в контексте аварийных атак. Эти алгоритмы эксплуатируют алгебраически простые байт-ориентированные структуры стандарта AES. Если атаки, найденные с помощью инструментов, практичны, то они будут утверждены и осуществлены.

Введение

С момента введения AES в 2001 году, было поставлено под сомнение его простая алгебраическая структура, может ли она быть использована в криптоаналитики. Вскоре после его публикации в качестве стандарта [1], Мерфи и Robshaw показали в 2002 году интересное алгебраическое свойство: процесс шифрования AES можно охарактеризовать только с простыми алгебраическими операциями в GF() [2]. Такой результат проложил путь для многомерных алгебраических методов [3][4], так как функция шифрования AES может описывается очень редкими и многовариантными квадратичными системами по GF(2). Тем не менее, до сих пор этот подход не был многообещающим [5][6], и первоначальная цель этой простой структуры,была выполнена, обеспечить хорошую защиту безопасности против дифференциального и линейного криптоанализа.

В последнее время много внимания уделялось блочному шифру AES в качестве побочного продукта NIST SHA-3. Низкое свойство распространение ключа было использовано для установки нескольких связанных атак [7][8][9][10] ,а различные дифференциальные характеристики, разработанные для хэш-функций, были использованы для улучшения одноключевых нападений [11]. Для того, чтобы улучшить эти нападения, новые автоматические инструменты были разработаны для автоматизированного поиска ключевых атак или столкновений нападения на байто-ориентированные блочные шифры [12] или функции AES на основе хэша[10]. В этой статье мы рассмотрим снижение безопасности AES блочного шифра в практической модели безопасности [13]. Противник знает очень небольшое количество зашифрованных пар/открытого текста, одну или две, и его целью является восстановить секретный ключ. Изучение версии алгоритма AES с сокращенным раундом мотивируется его быстрым распространением. А именно, в последние годы появились такие алгоритмы для хеширования или аутентификации, основанные на AES, такие как Grøstl, ECHO, Shavite, хэш-функции, переулок, LEX [14] потоковый шифр, или Альфа-MAC [15] и Пеликан-MAC [16] код аутентификации сообщений. Возможное объяснение этому пристрастию - это то, что аес отличается очень интересными свойствами безопасности по противостоянию статистическим атакам. В частности, два этапа могут достигнуть полного распространения, и там будет существовать хорошие нижние оценки для лучшего дифференциала на четырех раундах [17][18][19]. Следовательно, для некоторых приложений, таких как хеширование и аутентификация, где противник практически ничего не имеет или вообще не имеет доступа к внутренней структуре, все десять раундов AES могут быть излишним, а некоторые разработчики предложили использовать меньше раундов для большей эффективности. В этих приложениях противник имеет меньше контроля над AES, чем в обычном блочном шифре, и имеет доступ к очень немногим номерам из открытого текста / зашифрованного пар. Например, в потоке шифра LEX [2], четверть государственной информации утекает в каждом раунде и следующие 32 бита ключевого потока выполняются в одном раунде AES. Кроме того, в некоторых конкретных атак, таких как боковой канал, только небольшое количество раундов шифра должно быть изучено [20][21]. В последнем случае, противник не знает, открытого текста/зашифрованных пар, но некоторые различия в промежуточных результатах, состояний двух разных шифротекстов. Наконец, в симметричном криптоанализе,статистические атаки, как правило, используют отличительные признаки на небольшом количестве раундов и затем, распространяют эти отличительные признаки к большенству раундов. Следовательно, это важно, чтобы найти лучшую атаку в этой модели.

Установка связи с работой

В этой модели безопасности статистические атаки могут быть не самыми возможными атаками, так как они обычно требуют много пар с определенными входными различиями, а алгебраические атаки более подходят. Тем не менее, подобные атаки, использующие либо SAT или Gröbner алгоритмы [2][22], никогда не были компетентными, чтобы поставить под угрозу версии AES, хотя его структура имеет некоторые алгебраические свойства. Эти атаки кодируют проблему в системе уравнений, затем снабжает уравнениями непатентованное средство, иногда стандартное устройство, такими как SAT-solve или Gröbner алгоритм. Главным препятствием в этих подходах является S-box, что допускает «плохое» представление (например, это высокая степень многочлена над конечным полем AES), а также увеличение сложности уравнений, хотя низкая степень неявных уравнений может также существовать. Наши инструменты, вместо того, чтобы использовать существующие универсальные устройства, сначала запускают поиск специального решающего устройства, а затем запускают его, чтобы получить фактическое решение. Они могут быть применены к системам линейных уравнений, содержащих нелинейную перестановку области, как S-box. Наша идея заключается в рассмотрении S-box, как черный ящик перестановки. Мы используем только несколько свойств этой функции, и наши атаки работают для любого экземпляра S-box. Этот подход напоминает идеи, использованные в [10]. Ховратовича, др., где аналогичные системы линейных уравнений написаны, чтобы описать хэш-функцию. Дальнейшее решение уравнений даст столкновение. Основная стратегия нахождения пары сообщения, подтверждающее отличительные особенности, состоит в исчерпание значений, переменных и проверки,если ограничения удовлетворены. Для того, чтобы ускорить поиск столкновений, предлагаеться взглянуть на максимальный размера набора переменных, которые могли бы свободно брать любые значения, не нарушая ограничений. Для этого используют линейную алгебру, по сути рассмотреть и , чтобы были независимые переменные, чтобы найти такой набор, используя максимально жадные стратегии. В поисках соответствующей пары сообщений, свободные переменные могут принимать все возможные значения, а значение других переменных выводятся из свободных. Следовательно, поиск избегает попытки выбора плохого значения для последних переменных, которые улучшают вероятностную стадию испытаний. Алгоритм [27] ограничен в том, что, когда жадная стратегия прерывается, никакие другие решения не исследуются.

Наши методы и результаты.

Наши инструменты пытаются найти нападения автоматически, с помощью поиска некоторых классов предполагается встречается в средних нападениях. Они принимают в качестве входных данных систему уравнений, которая описывает криптографические примитивы, некоторые ограничения на текст и зашифрованные переменных, например. Затем он решает уравнения сначала работает (потенциально экспоненциальный) поиск устройства для входной системы. Затем, Процесс запускается, и решения вычисляются. Мы опишем два инструмента. Наш предварительный инструмент использует поиск в глубину, чтобы определить атаки. Это (тайно) использовалось, чтобы произвести некоторые нападения, найденные в [13]., и превзошло криптоаналитиков в нескольких случаях. Однако класс нападения, разыскиваемого этим предварительным инструментом, вполне ограничен, и это не принимает во внимание важные отличительные свойства S-box. Наш второй, более продвинутый инструмент, позволяет найти более мощные атаки, такие как "Встреча в середине нападения". Например, он автоматически использует полезный факт, что различие на входе и выходе на S-box определяет почти уникальные фактические ценности входа и выхода. Алгоритмические методы, используемые этим инструментом, напоминают об алгоритме Buchberger [23]. Полученные результаты этих алгоритмов приведены в таблицах 1 и 2. Мы улучшаем много существующих нападений в классе “очень низкой сложности данных”. Например, мы находим нападение сертификации на 4 полных раунда AES, использующие единственный известный текст и практическое нападение на те же самые 4 полных раунда AES с 4 выбранными обычными текстами. Мы также рассмотрим AES-приложения. Мы независимо обнаружили (наряду с [24]) самое известное нападение на Pelican-MAC, и автоматически открыли лучшие нападения на Alpha-MAC and LEX. Мы также использовали наш инструмент, чтобы найти новый, более быстрое, нападение на LEX. Мы повышаем эффективность государственного восстановления после ошибки Piret-Quisquater на полный AES. В то время, как это требует элементарных операций, то в настоящее время это занимает около одной секунды на ноутбуках.

Таблица №1

Нападения на круглую уменьшенную версию AES-128
№Раунды Данные Документы Лучшие предыдущие нападения
1 1 KP / /1 /[19]
1.5 1 KP /1
1.5 2 KP /
2 1 KP / /1 /[8]*
2 2 KP / /1 /[8]
2 2 CP / /1 /[8]
2.5 1 KP /
2.5 2 KP /
2.5 2 CP /
3 1 KP / /1 /[8]*
3 2 CP / /1 /[8]
4 1 KP /
4 2 CP / /1 /[8]
4 4 CP /
4.5 1 KP /


Подготовительные мероприятия

Пусть обозначает конечное поле с 256 элементов, используемых в AES. Мы обозначим Sbox преобразования SubBytes, как S:\rightarrow (or \to). В этой статье мы рассмотрим только 128-разрядную версию AES. Ключи открытого текста, зашифрованного и внутренние состояния шифра представлены 4x4 матрицей . В такой матрице, мы используем следующую нумерацию байтов: нулевой байт верхний левый угол, первая колонка сделана из байтов 0-3, в то время как последний столбец состоит из байтов 12-15 с байта 15 в правый нижний угол.В r-раунде AES, главный ключ, расширен в r круглые ключи Нападения на примитивы основанные на AES

Таблица 2. Резюме, предлагаемой нами атаки, на основе примитивов на АЭС. Сложность времени измерена в единицах шифрования, если не упомянуто. Сложность памяти измерена приблизительно : инструменты могут найти автоматически сопоставимое нападение

круговые ключи,..., алгоритмов ключевого графика, который описан следующими уравнениями:

2.PNG

AES выполняет следующую последовательность операций: SubBytes, ShiftRows, MixColumns и круглое дополнение под ключ. Мы отсылаем читателя к спецификации AES для получения дополнительной информации [1]. Мы обозначаем раунд i входа внутреннего состояния ( перед SubBytes), в то время как и обозначают внутреннее состояние прежде и после деятельности MixColumns, соответственно. Главный ключ - XORed к обычному тексту, прежде чем войти в первый раунд. Процесс получен, в итоге с этими уравнениями, где MC обозначает матрицу MixColumns:

3.PNG

Предварительный инструмент для вычисления атак

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

  1. Для всех значений некоторой части (неизвестного) внутреннего состояния.
  2. Вычисление полного внутреннего состояния.
  3. Восстановление тайны.
  4. Попытайтесь восстановить доступные данные, используя секретные данные.

Трудность в поиске такого нападения, чтобы найти части внутреннего состояния, и найти, как восстановить все остальное. В этой секции мы представляем предварительный инструмент, который находит такие нападения автоматически. Это в качестве входа в систему уравнений в () и набор из первоначально известных переменных -- это переменные, соответствующие доступным данным, например обычный текст, зашифрованный текст, и т.д. Возвращение инструментов C++, функция, которая перечисляет ее решения, наряду с точным числом элементарных операций. Эти подготовительные мероприятия используются,чтобы найти обычный текст,нападений на 1, 1.5, 2, 2.5 и 3 раунда AES . Некоторые из этих нападений были изданы в [13]. Например, до публикации[13], лучшее нападение на один раунд AES со сложностью , описанный в [25]. Этот предварительный инструмент находится менее чем за секунду:С++ файл доступен на веб-странице первого автора.


Распространение знаний

Центральная идея подготовительных мероприятий довольно проста: если есть линейная комбинация уравнений в которой ценности всех условий известны кроме одного, тогда ценность этого последнего срока может быть определена эффективно. При применение AES, простая процедура автоматически использует чистую алгебраическую структуру шифра.Он автоматически использует линейные отношения, существующие в ключевом графике, а также свойства MixColumns: если = MixColumns(x), тогда знание любых четырех байтов в (X, Y) достаточно, чтобы восстановить оставшиеся четыре.

“Алгебраическая” точка зрения.

Приобретение дополнительных знаний "догадка" или "определение" имеет алгебраическое воздействие на уравнение. множество переменных, значение которых известно. Если замещенные значения переменных в известных исходных уравнениях , мы получили систему с меньшим количеством переменных. Фактически, эта уменьшенная система, по существу коэффициент : начало с уравнения , его класс эквивалентности в коэффициенте содержится образец, где все переменные в исчезли. Кроме того, переменная может быть выведена из либо или принадлежат частному.

Автоматический поиск минимального числа предположений

Учитывая набор "известных" переменных = мы можем размножить знание и получите новые переменные, приведя к новому набору известных переменных.Но может оказаться, что новые переменные могут снова быть получены из. Поэтому мы определяем функцию , которая возвращает наименьшее количество фиксированной точки , содержащая . Решающее устройство было найдено, как только мы нашли набор из "догадок", что. В этом случае мы скажем это достаточно.Таким образом, задача сводится к автоматическому поиску достаточного набора минимального размера. Процесс исчерпывающего поиска такого нападения может быть замечен как исследование DAG, узлы которого - наборы переменных. Стартовый узел - набор и предельный узел . Для любого набора переменных и любой есть ребро подразумевать, что мы всегда можем перечислить y, чтобы получить значение.

jvjh


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

Местное сокращение

Говоря простыми словами, если мы должны угадать новую переменную, и если угадать х , то можно вывести у, то бесполезно гадать у вместо х. Более формально, мы увидим, что, если )

 )   )

Разумная стратегия сокращения состоит в том, чтобы рассмотреть только предположения кандидата, которые не “включены в категорию”.

Глобальное сокращение

Лемма №1. недостаточный набор переменных, и пусть достаточный набор переменных. Тогда:

(-())

Если обозначает достаточный набор минимального размера, то лемма 1 дает нам априорное знание , и это позволяет выбрать первое предположение о процедуре поиска в-(,не рискуя выбрасывать лучшее решение. Также возможно использовать лемму 1 в любом пункте поиска, но тогда должно быть, чтобы быть супернабором известных переменных (иначе мы не можем изучите что-либо).

Ограничения

Основным ограничением этого подхода является то, что не принимает во внимание дифференциальные свойства S-box.Например, он не может использовать тот факт, что, когда различия входа и выход на S-box фиксирован и не равен нулю, то не более 4 возможных входных значений возможно. Таким образом, этот подход сам по себе не принесет полезный результат, когда более чем один открытый текст доступен. Тем не менее, он может быть использован в качестве подкомпонента в более сложной техники. Теперь мы переходим к описанию обобщения этой техники, что позволяет найти более мощные атаки.

Инструмент для встречи атак

Уравнения, описывающие AES, обладают интересной и важной собственностью. Давайте рассмотрим разделение набора переменных =.Тогда любое уравнениеможет быть написано =+ с ( (. В каком-то смысле, эти уравнения могут быть отделены.

Рекурсивное решение подсистемы

Простая алгебраическая структура уравнений позволяет нам эффективно извлекать из системыподсистема, содержащая только определенные переменные, просто вычисляя векторное пространство ().В продолжении мы обозначим его(). Теперь давайте будут даны разделения=и два решающих устройства черного ящика и , чтобы найти все решения() и (). Эти два подрешающих устройства и может использоваться, чтобы найти решения полной задачи. Однако возможно добиться большего успеха.Во-первых, мы замечаем,что векторы в автоматически удовлетворяют уравнениям() и ()внутри.Решения - фактически элементы, удовлетворяющие уравнениям . Это уже делает меньше ограничений для проверки. Во-вторых, отфильтрованные элементы, удовлетворяющие этим ограничениям можно сделать примерно + операции, используя переменную разделение и таблицу. Обозначим функцией, которая оценивает все на его входе. Мы строим две таблицы:

Снимок.PNG7.PNG




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

  1. ENS, CNRS, INRIA, 45 rue d’Ulm, 75005 Paris, France, E-mail: charles.bouillaguet@ens.fr
  2. ENS, CNRS, INRIA, 45 rue d’Ulm, 75005 Paris, France, E-mail: patrick.derbez@ens.fr
  3. ENS, CNRS, INRIA, 45 rue d’Ulm, 75005 Paris, France, E-mail: pierre-alain.fouque@ens.fr

Примечание

Литература

  1. 1,0 1,1 NIST: Advanced Encryption Standard (AES), FIPS 197. Technical report, NIST(November 2001
  2. 2,0 2,1 Murphy, S., Robshaw, M.J.B.: Essential Algebraic Structure within the AES. In Yung, M., ed.: CRYPTO. Volume 2442 of Lecture Notes in Computer Science., Springer (2002) 1–16
  3. Courtois, N., Pieprzyk, J.: Cryptanalysis of Block Ciphers with Overdefined Sys-tems of Equations. In Zheng, Y., ed.: ASIACRYPT. Volume 2501 of Lecture Notes in Computer Science., Springer (2002) 267–287
  4. Cid, C.: Some Algebraic Aspects of the Advanced Encryption Standard. [16] 58–66
  5. Monnerat, J., Vaudenay, S.: On Some Weak Extensions of AES and BES. In Lopez, J., Qing, S., Okamoto, E., eds.: ICICS. Volume 3269 of Lecture Notes in Computer Science., Springer (2004) 414–42
  6. Cid, C., Leurent, G.: An Analysis of the XSL Algorithm. In Roy, B.K., ed.: ASIACRYPT. Volume 3788 of Lecture Notes in Computer Science., Springer (2005) 333–352
  7. Biryukov, A., Khovratovich, D., Nikolic, I.: Distinguisher and Related-Key Attack on the Full AES-256. [23] 231–24
  8. Biryukov, A., Khovratovich, D.: Related-Key Cryptanalysis of the Full AES-192 and AES-256. In Matsui, M., ed.: ASIACRYPT. Volume 5912 of Lecture Notes in Computer Science., Springer (2009) 1–18
  9. Biryukov, A., Dunkelman, O., Keller, N., Khovratovich, D., Shamir, A.: Key Recovery Attacks of Practical Complexity on AES-256 Variants with up to 10 Rounds.[22] 299–319
  10. 10,0 10,1 10,2 Khovratovich, D., Biryukov, A., Nikolic, I.: Speeding up Collision Search for Byte-Oriented Hash Functions. In Fischlin, M., ed.: CT-RSA. Volume 5473 of Lecture Notes in Computer Science., Springer (2009) 164–18
  11. Dunkelman, O., Keller, N., Shamir, A.: Improved Single-Key Attacks on 8-Round AES-192 and AES-256. In Abe, M., ed.: ASIACRYPT. Volume 6477 of Lecture Notes in Computer Science., Springer (2010) 158–17
  12. Biryukov, A., Nikolic, I.: Automatic Search for Related-Key Differential Characteristics in Byte-Oriented Block Ciphers: Application to AES, Camellia, Khazad and Others. [22] 322–344
  13. 13,0 13,1 13,2 13,3 Bouillaguet, C., Derbez, P., Dunkelman, O., Keller, N., Fouque, P.A.: Low Data Complexity Attacks on AES. Cryptology ePrint Archive, Report 2010/633 (2010)http://eprint.iacr.org/
  14. Biryukov, A.: The Design of a Stream Cipher LEX. In Biham, E., Youssef, A.M.,eds.: Selected Areas in Cryptography. Volume 4356 of Lecture Notes in Computer Science., Springer (2006) 67–75
  15. Daemen, J., Rijmen, V.: A New MAC Construction ALRED and a Specific Instance ALPHA-MAC. In Gilbert, H., Handschuh, H., eds.: FSE. Volume 3557 of Lecture Notes in Computer Science., Springer (2005) 1–1
  16. Daemen, J., Rijmen, V.: The Pelican MAC Function. Cryptology ePrint Archive, Report 2005/088 (2005) http://eprint.iacr.org/
  17. Keliher, L., Meijer, H., Tavares, S.E.: New Method for Upper Bounding the Maximum Average Linear Hull Probability for SPNs. In Pfitzmann, B., ed.: EUROCRYPT. Volume 2045 of Lecture Notes in Computer Science., Springer (2001) 420–436
  18. Keliher, L., Meijer, H., Tavares, S.E.: Improving the Upper Bound on the Maximum Average Linear Hull Probability for Rijndael. In Vaudenay, S., Youssef, A.M.,eds.: Selected Areas in Cryptography. Volume 2259 of Lecture Notes in Computer Science., Springer (2001) 112–128
  19. Keliher, L.: Refined Analysis of Bounds Related to Linear and Differential Cryptanalysis for the AES. [16] 42–57
  20. N Piret, G., Quisquater, J.J.: A Differential Fault Attack Technique against SPN Structures, with Application to the AES and KHAZAD. In Walter, C.D., Çetin Kaya Koç, Paar, C., eds.: CHES. Volume 2779 of Lecture Notes in Computer Science., Springer (2003) 77–88
  21. Biryukov, A., Khovratovich, D.: Two New Techniques of Side-Channel Cryptanalysis. In Paillier, P., Verbauwhede, I., eds.: CHES. Volume 4727 of Lecture Notes in Computer Science., Springer (2007) 195–208
  22. Buchmann, J., Pyshkin, A., Weinmann, R.P.: A Zero-Dimensional Gröbner Basis for AES-128. In Robshaw, M.J.B., ed.: FSE. Volume 4047 of Lecture Notes in Computer Science., Springer (2006) 78–88
  23. Buchberger, B.: Ein Algorithmus zum Auffinden der Basiselemente des Restk-lassenringes nach einem nulldimensionalen Polynomideal. PhD thesis, University of Innsbruck (1965)
  24. Dunkelman, O., Keller, N., Shamir, A.: Alred blues: New attacks on aes-based mac’s. Cryptology ePrint Archive, Report 2011/095 (2011) http://eprint.iacr.org
  25. Dunkelman, O., Keller, N.: The effects of the omission of last round’s mixcolumns on aes. Inf. Process. Lett.110 (8-9) (2010) 304–308