Бикликская атака

Бикличная атака — это вариант «встреча посередине» (MITM) метода криптоанализа . Он использует бикличную структуру для увеличения количества возможных атакованных раундов с помощью атаки MITM. Поскольку бикликовый криптоанализ основан на атаках MITM, он применим как к блочным шифрам , так и к (итеративным) хеш-функциям . Атаки Biclique известны тем, что ослабили как полноценные AES , так и и полная ИДЕЯ , хотя и лишь с небольшим преимуществом перед грубой силой. Он также был применен к шифру KASUMI и устойчивости к прообразу хэш-функций Skein-512 и SHA-2 .

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

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

История

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

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

Биклика

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

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

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

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

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

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

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

Грубая сила

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

ключей

(Этот метод был предложен Богдановым, Ховратовичем и Рехбергером в их статье «Бикликовый криптоанализ полного AES». )

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

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

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

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

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

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

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

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

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

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

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

Процедура криптоанализа Biclique

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

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

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

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

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

Пример атаки

Следующий пример основан на бикличной атаке на AES из статьи «Бикликовый криптоанализ полного AES». ".
В описаниях в примере используется та же терминология, которую использовали авторы атаки (т.е. имена переменных и т. д.).
Для простоты ниже описана атака на вариант AES128.
Атака состоит из 7-раундовой атаки MITM, причем биклика охватывает последние 3 раунда.

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

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

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

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

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

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

Конструкция биклика

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

MITM-атака

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

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

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

Результаты

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