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

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

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

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

История

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

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

Биклика

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

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

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

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

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

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

Грубая сила

Получать ${\displaystyle 2^{d}}$ промежуточные состояния и ${\displaystyle 2^{d}}$ зашифрованные тексты, а затем вычислить ключи, которые сопоставляются между ними. Это требует ${\displaystyle 2^{2d}}$ восстановление ключей, поскольку каждое промежуточное состояние должно быть связано со всеми зашифрованными текстами.

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

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

Предварительный:
Помните, что функция biclique - отображать промежуточные значения, ${\displaystyle S}$, к значениям зашифрованного текста, ${\displaystyle C}$, на основе ключа ${\displaystyle K[i,j]}$ такой, что:
${\displaystyle \forall i,j:S_{j}{\xrightarrow[{f}]{K[i,j]}}C_{i}}$

Процедура:
Первый шаг: Промежуточное состояние (${\displaystyle S_{0}}$), зашифрованный текст (${\displaystyle C_{0}}$) и ключ (${\displaystyle K[0,0]}$) выбирается так, чтобы: ${\displaystyle S_{0}{\xrightarrow[{f}]{K[0,0]}}C_{o}}$, куда ${\displaystyle f}$ - это функция, которая отображает промежуточное состояние в зашифрованный текст с использованием заданного ключа. Это обозначается как базовое вычисление.

Шаг второй: Два набора связанных ключей размера ${\displaystyle 2^{d}}$ выбран. Ключи подбираются так, чтобы:

• Первый набор ключей - это ключи, которые удовлетворяют следующим дифференциальным требованиям по сравнению с ${\displaystyle f}$ относительно базового вычисления: ${\displaystyle 0{\xrightarrow[{f}]{\Delta _{i}^{K}}}\Delta _{i}}$
• Второй набор ключей - это ключи, которые удовлетворяют следующим дифференциальным требованиям по сравнению с ${\displaystyle f}$ относительно базового вычисления: ${\displaystyle \nabla _{j}{\xrightarrow[{f}]{\nabla _{j}^{K}}}0}$
• Ключи подобраны так, чтобы следы ${\displaystyle \Delta _{i}}$- и ${\displaystyle \nabla _{j}}$-дифференциалы независимы, т. е. они не имеют общих активных нелинейных компонентов.

Другими словами:
Входная разница 0 должна отображаться на выходную разницу ${\displaystyle \Delta _{i}}$ под ключевым отличием ${\displaystyle \Delta _{i}^{K}}$. Все отличия касаются базовых вычислений.
Разница на входе ${\displaystyle \nabla _{j}}$ должен отображаться на выходную разницу 0 при ключевой разнице ${\displaystyle \nabla _{J}^{K}}$. Все отличия касаются базовых вычислений.

Шаг третий: Поскольку трейлы не имеют общих нелинейных компонентов (таких как S-блоки), трейлы можно объединить, чтобы получить:
${\displaystyle 0{\xrightarrow[{f}]{\Delta _{i}^{K}}}\Delta _{i}\oplus \nabla _{j}{\xrightarrow[{f}]{\nabla _{j}^{K}}}0=\nabla _{j}{\xrightarrow[{f}]{\Delta _{i}^{K}\oplus \nabla _{j}^{K}}}\Delta _{i}}$,
что соответствует определениям обоих дифференциалов из шага 2.
Нетривиально увидеть, что кортеж ${\displaystyle (S_{0},C_{0},K[0,0])}$ от базового вычисления, также соответствует по определению обоим дифференциалам, как и дифференциалы по отношению к базовому вычислению. Подстановка ${\displaystyle S_{0},C_{0}}$ ${\displaystyle K[0,0]}$ в любое из двух определений, даст ${\displaystyle 0{\xrightarrow[{f}]{0}}0}$ поскольку ${\displaystyle \Delta _{0}=0,\nabla _{0}=0}$ и ${\displaystyle \Delta _{0}^{K}=0}$.
Это означает, что кортеж базовых вычислений также может быть объединен с помощью операции XOR для объединенных следов:${\displaystyle S_{0}\oplus \nabla _{j}{\xrightarrow[{f}]{K[0,0]\oplus \Delta _{i}^{K}\oplus \nabla _{j}^{K}}}C_{0}\oplus \Delta _{i}}$

Шаг четвертый: Увидеть, что:
${\displaystyle S_{j}=S_{0}\oplus \nabla _{j}}$
${\displaystyle K[i,j]=K[0,0]\oplus \Delta _{i}^{K}\oplus \nabla _{j}^{K}}$
${\displaystyle C_{i}=C_{0}\oplus \Delta _{i}}$
Если это подставить в приведенные выше комбинированные дифференциальные трассы, результатом будет:
${\displaystyle S_{j}{\xrightarrow[{f}]{K[i,j]}}C_{i}}$
Это то же самое, что определение, приведенное выше для biclique:
${\displaystyle \forall i,j:S_{j}{\xrightarrow[{f}]{K[i,j]}}C_{i}}$

Таким образом можно создать биклик размером ${\displaystyle 2^{2d}}$ (${\displaystyle 2^{2d}}$ так как все ${\displaystyle 2^{d}}$ ключи первого набора ключей, могут быть объединены с ${\displaystyle 2^{d}}$ ключи от второго набора ключей). Это означает биклику размера ${\displaystyle 2^{2d}}$ можно создать, используя только ${\displaystyle 2*2^{d}}$ вычисления дифференциалов ${\displaystyle \Delta _{i}}$ и ${\displaystyle \nabla _{j}}$ над ${\displaystyle f}$. Если ${\displaystyle \Delta _{i}\neq \nabla _{j}}$ за ${\displaystyle i+j>0}$ тогда все ключи ${\displaystyle K[i,j]}$ в биклике тоже будет иначе.

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

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

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

Процедура Biclique Cryptanalysis

Первый шаг: Атакующий группирует все возможные ключи в подмножества ключей по размеру. ${\displaystyle 2^{2d}}$ для некоторых ${\displaystyle d}$, где ключ в группе индексируется как ${\displaystyle K[i,j]}$ в матрице размера ${\displaystyle 2^{d}\times 2^{d}}$. Злоумышленник разбивает шифр на два субшифра, ${\displaystyle f}$ и ${\displaystyle g}$ (такой, что ${\displaystyle E=f\circ g}$), как в обычной атаке MITM. Набор ключей для каждого из субшифров имеет мощность ${\displaystyle 2^{d}}$, и называется ${\displaystyle K[i,0]}$ и ${\displaystyle K[0,j]}$. Комбинированный ключ субшифров выражается с помощью вышеупомянутой матрицы ${\displaystyle K[i,j]}$.

Шаг второй: Атакующий строит биклику для каждой группы ${\displaystyle 2^{2d}}$ ключи. Биклика имеет размерность -d, поскольку она отображает ${\displaystyle 2^{d}}$ внутренние состояния, ${\displaystyle S_{j}}$, к ${\displaystyle 2^{d}}$ шифртексты, ${\displaystyle C_{i}}$, с помощью ${\displaystyle 2^{2d}}$ ключи. В разделе «Как построить биклику» предлагается, как построить биклику, используя «Независимые дифференциалы связанных ключей». Биклика в этом случае строится с использованием дифференциалов набора ключей, ${\displaystyle K[i,0]}$ и ${\displaystyle K[0,j]}$, принадлежащих к подшифрам.

Шаг третий: Злоумышленник берет ${\displaystyle 2^{d}}$ возможные шифртексты, ${\displaystyle C_{i}}$, и просит оракул дешифрования предоставить соответствующие открытые тексты, ${\displaystyle P_{i}}$.

Шаг четвертый: Атакующий выбирает внутреннее состояние, ${\displaystyle S_{j}}$ и соответствующий открытый текст, ${\displaystyle P_{i}}$, и выполняет обычную атаку MITM поверх ${\displaystyle f}$ и ${\displaystyle g}$ путем атаки из внутреннего состояния и открытого текста.

Шаг пятый: Как только будет найден ключевой кандидат, соответствующий ${\displaystyle S_{j}}$ с ${\displaystyle P_{i}}$, этот ключ проверяется на другой паре открытого / зашифрованного текста. если ключ проверяется на другой паре, весьма вероятно, что это правильный ключ.

Пример атаки

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

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

Ключевое пространство разделено на ${\displaystyle 2^{112}}$ группы ключей, где каждая группа состоит из ${\displaystyle 2^{16}}$ ключи.
Для каждого из ${\displaystyle 2^{112}}$ группы, уникальный базовый ключ ${\displaystyle K[0,0]}$ для базового вычисления выбрано.
Базовый ключ имеет два конкретных байта, установленных в ноль, как показано в таблице ниже (которая представляет ключ так же, как AES в матрице 4x4 для AES128):

${\displaystyle {\begin{bmatrix}-&-&-&0\\0&-&-&-\\-&-&-&-\\-&-&-&-\end{bmatrix}}}$

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

${\displaystyle {\begin{bmatrix}-&-&i&i\\j&-&j&-\\-&-&-&-\\-&-&-&-\end{bmatrix}}}$

Это дает ${\displaystyle 2^{8}K[i,0]}$ и ${\displaystyle 2^{8}K[0,j]}$, что в совокупности дает ${\displaystyle 2^{16}}$ разные ключи, ${\displaystyle K[i,j]}$. эти ${\displaystyle 2^{16}}$ ключи составляют ключи в группе для соответствующего базового ключа.

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

${\displaystyle 2^{112}}$ bicliques конструируется с использованием техники «независимых дифференциалов связанных ключей», как описано в разделе «Как построить biclique».
Требование для использования этого метода заключалось в том, чтобы прямая и обратная дифференциальные трассы, которые необходимо объединить, не имели общих активных нелинейных элементов. Как известно, что это так?
Из-за того, как ключи на шаге 1 выбираются по отношению к базовому ключу, дифференциал следует ${\displaystyle \Delta _{i}}$ используя ключи ${\displaystyle K[i,0]}$ никогда не разделяйте какие-либо активные S-блоки (это единственный нелинейный компонент в AES), с дифференциальными следами ${\displaystyle \nabla _{j}}$ используя ключ ${\displaystyle K[0,j]}$. Следовательно, можно выполнить операцию XOR дифференциальных следов и создать биклику.

MITM атака

Когда биклики созданы, атака MITM почти может начаться. Перед выполнением атаки MITM ${\displaystyle 2^{d}}$ промежуточные значения из открытого текста:
${\displaystyle P_{i}{\xrightarrow[{}]{K[i,0]}}{\xrightarrow[{v_{i}}]{}}}$,
то ${\displaystyle 2^{d}}$ промежуточные значения из зашифрованного текста:
${\displaystyle {\xleftarrow[{v_{j}}]{}}{\xleftarrow[{}]{K[0,j]}}S_{j}}$,
и соответствующие промежуточные состояния и подключи ${\displaystyle K[i,0]}$ или же ${\displaystyle K[0,j]}$, однако предварительно вычисляются и сохраняются.

Теперь атака MITM может быть осуществлена. Чтобы проверить ключ ${\displaystyle K[i,j]}$, необходимо только пересчитать части шифра, которые, как известно, будут варьироваться между ${\displaystyle P_{i}{\xrightarrow[{}]{K[i,0]}}{\xrightarrow[{v_{i}}]{}}}$ и ${\displaystyle P_{i}{\xrightarrow[{}]{K[i,j]}}{\xrightarrow[{v_{i}}]{}}}$. Для обратного вычисления из ${\displaystyle S_{j}}$ к ${\displaystyle {\xleftarrow[{v_{j}}]{}}}$, это 4 S-блока, которые необходимо пересчитать. Для прямого вычисления от ${\displaystyle P_{i}}$ к ${\displaystyle {\xrightarrow[{v_{i}}]{}}}$, это всего лишь 3 (подробное объяснение объема необходимого пересчета можно найти в "Biclique Cryptanalysis полного AES^[1]"бумага, откуда взят этот пример).

Когда промежуточные значения совпадают, ключ-кандидат ${\displaystyle K[i,j]}$ между ${\displaystyle P_{i}}$ и ${\displaystyle S_{j}}$ находится. Ключ-кандидат затем проверяется на другой паре открытый / зашифрованный текст.

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

Эта атака снижает вычислительную сложность AES128 до ${\displaystyle 2^{126.18}}$, что в 3–5 раз быстрее, чем метод грубой силы. Сложность данных атаки составляет ${\displaystyle 2^{88}}$ и сложность памяти ${\displaystyle 2^{8}}$.

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

1. Богданов Андрей; Ховратович, Дмитрий; Рехбергер, Кристиан. «Криптоанализ 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).