Атака по полному двудольному графу (Gmgtg hk hklukbr ;fr;kl,ukbr ijgsr)

Перейти к навигации Перейти к поиску

Атака по полному двудольному графу (англ. Biclique attack) — одна из разновидностей атаки «встречи посередине»[1]. В данной атаке используется структура полного двудольного графа для увеличения количества попыток атаки посредника. Так как эта атака основа на методе атаки посредника, то она применима как к блочным шифрам, так и к криптографическим хеш-функциям. Данная атака известна тем, что позволяет вскрыть шифры AES[2] и IDEA[3], хотя по скорости лишь немного обгоняет метод полного перебора. Вычислительная сложность атаки составляет , и для AES128, AES192 и AES256 соответственно. Так как вычислительная сложность – теоретическое значение, то это означает, что AES не был взломан и его использование остается относительно безопасным. Также эта атака поставила под сомнение достаточность количества раундов, используемых в AES.

Метод атаки посредника был впервые предложен Диффи и Хеллманом в 1977 году в процессе обсуждения свойств алгоритма DES.[4] Они рассуждали о том, что размер ключа был слишком мал, и что повторное использование DES с разными ключами могло быть решением данной проблемы. Однако, было предложено не использовать "double DES", а сразу применять как минимум triple DES из-за особенностей атаки посредника. С тех пор, как Диффи и Хеллман предложили метод атаки посредника, появилось много вариаций, которые могут использоваться, когда классический вариант MITM неприменимы. Идея атаки по полному двудольному графу была впервые высказана Хоратовичем, Рехбергером и Савельевой для варианта с использованием хеш-функций.[5] Впоследствии Богданов, Хоратович и Рехбергер опубликовали атаку на AES, в которой показали, как можно применить концепцию полного двудольного графа к секретному ключу, включающий в себя блочный шифр[6].

Полный двудольный граф

[править | править код]

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

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

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

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

Построение полного двудольного графа

[править | править код]

Данный метод был предложен Богдановым, Ховратовичем и Рехбергером в работе Biclique Cryptanalysis of the Full AES.

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

Второй шаг: Выбирается два множества ключей, каждое размером , таким образом, что:

  • Первое множество ключей — это ключи, которые удовлетворяют дифференциальным требованиям функции на основе базовые вычислений:
  • Второе множество ключей — это ключи, которые удовлетворяют дифференциальным требованиям функции на основе базовые вычислений:

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

Четвертый шаг: Легко заметить, что:



Таким образом, имеем:

Что совпадает с определением функции полного двудольного графа, показанной выше:

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

Криптографический анализ атаки

[править | править код]

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

2. Криптоаналитик строит полный двудольный граф для каждой группы ключей. Граф имеет размерность , так как он сопоставляет внутренних состояний, , с шифротекстами, , используя ключей. В данном случае полный двудольный граф строится на основе отличий двух множеств ключей, и .

3. Криптоаналитик выбирает возможных шифротекстов, , и запрашивает соответствующие им открытые тексты, .

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

5. Как только находиться ключ, сопоставляющий с , он тестируется на другой паре 'внутреннее состояние-шифротекст'. Если ключ работает и на этой паре, то с большой долей вероятности это корректный ключ.

Пример атаки

[править | править код]

Ниже представлен пример атаки на AES128. Атака состоит из 7 раундовой атаки посредника, полный двудольный граф используется в 3 последних итерациях.

Разделение ключей

[править | править код]

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

Оставшиеся 14 байт (112 бит) заполняются последовательно. Таким образом получается уникальных базовых ключей; по одному на каждую группу ключей.
Обычно ключей в каждой группе выбираются в соответствии с базовым ключом группы. Они отличаются только 2 байтами (либо из , либо из ) из представленных ниже 4 байт:

Таким образом, получается и , что в сумме даёт различных ключей, .

Построение графа

[править | править код]

Полный двудольный граф размером строится так, как это указано в разделе "Построение полного двудольного графа".

Атака посредника

[править | править код]

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

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

Когда состояния совпадут, ключ-кандидат , принимающий значения от до найден. Далее этот ключ тестируется на другой паре открытый-/шифротекст

Результаты

[править | править код]

Эта атака позволяет уменьшить сложность вычислений для взлома AES128 до , что в свою очередь в 3-5 раз быстрее метода полного перебора.

Примечания

[править | править код]
  1. Ernest Foo, Douglas Stebila. Improving the Biclique Cryptoanalysis of AES // Information Security and Privacy: 20th Australasian Conference, ACISP 2015, Brisbane, QLD, Australia, June 29 -- July 1, 2015, Proceedings. — Springer, 2015. — С. 39.
  2. Архивированная копия. Дата обращения: 14 ноября 2015. Архивировано из оригинала 6 марта 2016 года.Архивированная копия. Дата обращения: 14 ноября 2015. Архивировано из оригинала 6 марта 2016 года.
  3. Narrow-Bicliques: Cryptanalysis of Full IDEA. Архивировано 17 ноября 2015 года.
  4. Whitfield Diffie, Martin E. Hellman. Exhaustive Cryptanalysis of the NBS Data Encryption Standard. Архивировано 3 марта 2016 года.
  5. Dmitry Khovratovich, Christian Rechberger, Alexandra Savelieva. Bicliques for Preimages: Attacks on Skein-512 and the SHA-2 family. Архивировано 22 июля 2016 года.
  6. Andrey Bogdanov, Dmitry Khovratovich, Christian Rechberger. Biclique Cryptanalysis of the Full AES (англ.) // Advances in Cryptology – ASIACRYPT 2011 / Dong Hoon Lee, Xiaoyun Wang. — Berlin, Heidelberg: Springer, 2011. — P. 344–371. — ISBN 978-3-642-25385-0. — doi:10.1007/978-3-642-25385-0_19. Архивировано 20 августа 2020 года.

Литература

[править | править код]