Бикликовая атака - Biclique attack - Wikipedia

А бикликовая атака это вариант встреча посередине (MITM) метод криптоанализ. Он использует биклика структура для увеличения количества раундов, которые могут быть атакованы MITM-атакой. Поскольку бикликовый криптоанализ основан на атаках MITM, он применим как к блочные шифры и (повторяется) хеш-функции. Бикликовые атаки известны тем, что сломали оба AES[1] и полный ИДЕЯ,[2] правда, только с небольшим преимуществом над грубой силой. Он также был применен к КАСУМИ шифр и прообраз сопротивление Моток-512 и SHA-2 хэш-функции.[3]

Атака biclique продолжается (по состоянию на апрель 2019 г.) лучшая общеизвестная одноключевая атака на AES. Вычислительная сложность атаки составляет , и для AES128, AES192 и AES256 соответственно. Это единственная публично известная атака с одним ключом на AES, которая атакует полное количество раундов.[1] Предыдущие атаки атаковали варианты с уменьшенным количеством раундов (обычно варианты с уменьшенным количеством раундов до 7 или 8).

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

История

Первоначальная атака MITM была впервые предложена Диффи и Хеллман в 1977 году, когда они обсуждали криптоаналитические свойства DES.[4] Они утверждали, что размер ключа слишком мал и что многократное повторное применение DES с разными ключами может быть решением проблемы размера ключа; однако они посоветовали не использовать двойной DES и предложили как минимум тройной DES из-за атак MITM (атаки MITM могут быть легко применены к двойному DES для снижения безопасности от чтобы просто , поскольку можно независимо подобрать первое и второе DES-шифрование, если они имеют открытый и зашифрованный текст).

С тех пор, как Диффи и Хеллман предложили атаки MITM, появилось много вариантов, которые полезны в ситуациях, когда базовая атака MITM неприменима. Вариант бикликовой атаки был впервые предложен Дмитрий Ховратович, Рехбергер и Савельева для использования с криптоанализом хеш-функций.[5] Однако именно Богданов, Ховратович и Рехбергер показали, как применить концепцию бикликов к настройке секретного ключа, включая криптоанализ блочного шифра, когда они опубликовали свою атаку на AES. До этого MITM-атакам на AES и многие другие блочные шифры уделялось мало внимания, в основном из-за необходимости в независимых битах ключа между двумя `` подшифрами MITM '', чтобы облегчить атаку MITM - чего трудно достичь со многими современные ключевые графики, такие как AES.

Биклика

Общее объяснение того, что такое бикликовая структура, можно найти в статье для биклики.

В атаке MITM ключевые биты и принадлежащие первому и второму подшифру, должны быть независимыми; то есть они должны быть независимыми друг от друга, иначе согласованные промежуточные значения для открытого и зашифрованного текста не могут быть вычислены независимо в атаке MITM (существуют варианты атак MITM, в которых блоки могут иметь общие биты ключа. См. то Атака MITM из трех подмножеств ). Это свойство часто трудно использовать в большем количестве раундов из-за распространения атакованного шифра.
Проще говоря: чем больше раундов вы атакуете, тем больше у вас будет подшифров. Чем больше у вас подшифр, тем меньше независимых битов ключей между подшифрами вам придется перебирать независимо. Конечно, фактическое количество независимых битов ключа в каждом подшифре зависит от свойств распространения расписания ключей.

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

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

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

Как построить биклику

Грубая сила

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

Независимые ключевые дифференциалы

(Этот метод был предложен Богдановым, Ховратовичем и Рехбергером в их статье: Biclique Cryptanalysis of the Full AES[1])

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

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

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

  • Первый набор ключей - это ключи, которые удовлетворяют следующим дифференциальным требованиям по сравнению с относительно базового вычисления:
  • Второй набор ключей - это ключи, которые удовлетворяют следующим дифференциальным требованиям по сравнению с относительно базового вычисления:
  • Ключи подобраны так, чтобы следы - и -дифференциалы независимы, т. е. они не имеют общих активных нелинейных компонентов.

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

Шаг третий: Поскольку трейлы не имеют общих нелинейных компонентов (таких как S-блоки), трейлы можно объединить, чтобы получить:
,
что соответствует определениям обоих дифференциалов из шага 2.
Нетривиально увидеть, что кортеж от базового вычисления, также соответствует по определению обоим дифференциалам, как и дифференциалы по отношению к базовому вычислению. Подстановка в любое из двух определений, даст поскольку и .
Это означает, что кортеж базовых вычислений также может быть объединен с помощью операции XOR для объединенных следов:

Шаг четвертый: Увидеть, что:



Если это подставить в приведенные выше комбинированные дифференциальные трассы, результатом будет:

Это то же самое, что определение, приведенное выше для biclique:

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

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

Другие способы построения биклики

Богданов, Ховратович и Рехбергер также описывают другой способ построения биклика, названный «Чередование дифференциальных следов связанных ключей» в статье «Бикликовый криптоанализ полного AES.[1]".

Процедура Biclique Cryptanalysis

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

Шаг второй: Атакующий строит биклику для каждой группы ключи. Биклика имеет размерность -d, поскольку она отображает внутренние состояния, , к шифртексты, , с помощью ключи. В разделе «Как построить биклику» предлагается, как построить биклику, используя «Независимые дифференциалы связанных ключей». Биклика в этом случае строится с использованием дифференциалов набора ключей, и , принадлежащих к подшифрам.

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

Шаг четвертый: Атакующий выбирает внутреннее состояние, и соответствующий открытый текст, , и выполняет обычную атаку MITM поверх и путем атаки из внутреннего состояния и открытого текста.

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

Пример атаки

Следующий пример основан на biclique-атаке на AES из статьи «Biclique Cryptanalysis of the Full AES.[1]".
В описаниях в примере используется та же терминология, что и авторы атаки (например, для имен переменных и т. Д.).
Для простоты ниже описана атака на вариант AES128.
Атака состоит из 7-раундового MITM-нападения с бикликом, охватывающим последние 3 раунда.

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

Ключевое пространство разделено на группы ключей, где каждая группа состоит из ключи.
Для каждого из группы, уникальный базовый ключ для базового вычисления выбрано.
Базовый ключ имеет два конкретных байта, установленных в ноль, как показано в таблице ниже (которая представляет ключ так же, как AES в матрице 4x4 для AES128):

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

Это дает и , что в совокупности дает разные ключи, . эти ключи составляют ключи в группе для соответствующего базового ключа.

Бикликовая конструкция

bicliques конструируется с использованием техники «независимых дифференциалов связанных ключей», как описано в разделе «Как построить biclique».
Требование для использования этого метода заключалось в том, чтобы прямая и обратная дифференциальные трассы, которые необходимо объединить, не имели общих активных нелинейных элементов. Как известно, что это так?
Из-за того, как ключи на шаге 1 выбираются по отношению к базовому ключу, дифференциал следует используя ключи никогда не разделяйте какие-либо активные S-блоки (это единственный нелинейный компонент в AES), с дифференциальными следами используя ключ . Следовательно, можно выполнить операцию XOR дифференциальных следов и создать биклику.

MITM атака

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

Теперь атака MITM может быть осуществлена. Чтобы проверить ключ , необходимо только пересчитать части шифра, которые, как известно, будут варьироваться между и . Для обратного вычисления из к , это 4 S-блока, которые необходимо пересчитать. Для прямого вычисления от к , это всего лишь 3 (подробное объяснение объема необходимого пересчета можно найти в "Biclique Cryptanalysis полного AES[1]"бумага, откуда взят этот пример).

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

Полученные результаты

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

Рекомендации

  1. ^ а б c d е ж Богданов Андрей; Ховратович, Дмитрий; Рехбергер, Кристиан. «Криптоанализ Biclique полного AES» (PDF). Архивировано из оригинал (PDF) на 2012-06-08. Цитировать журнал требует | журнал = (помощь)
  2. ^ "Narrow-Bicliques: криптоанализ полной идеи". CiteSeerX  10.1.1.352.9346. Цитировать журнал требует | журнал = (помощь)
  3. ^ Bicliques для прообразов: атаки на Skein-512 и семейство SHA-2
  4. ^ Диффи, Уитфилд; Хеллман, Мартин Э. «Исчерпывающий криптоанализ стандарта шифрования данных NBS» (PDF). Цитировать журнал требует | журнал = (помощь)
  5. ^ Ховратович, Дмитрий; Рехбергер, Кристиан; Савельева Александра. «Bicliques для прообразов: атаки на Skein-512 и семейство SHA-2» (PDF). Цитировать журнал требует | журнал = (помощь)