Бикликовая атака

Атака по полной двудольной графой является вариантом встречается в-середина методы (MITM) из криптоанализа . Он использует бикликовую структуру, чтобы увеличить количество раундов, которые могут быть атакованы MITM-атакой. Поскольку бикликовый криптоанализ основан на атаках MITM, он применим как к блочным шифрам, так и к (итерационным) хеш-функциям . Biclique-атаки известны тем, что взломали как полный AES ^{[1], так} и полную IDEA , ^[2], хотя и с небольшим преимуществом над грубой силой. Он также был применен к шифру KASUMI и устойчивости к прообразу Skein-512 иХеш-функции SHA-2 . ^[3]

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

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

История [ править ]

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

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

Биклика [ править ]

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

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

Способ, которым biclique помогает справиться с вышеупомянутым, состоит в том, что он позволяет, например, атаковать 7 раундов AES, используя атаки MITM, а затем, используя biclique структуру длины 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, должна отображаться на выходную разницу в соответствии с ключевой разницей . Все различия относятся к базовому вычислению. Входная разница должна отображаться на выходную разность 0 при ключевой разнице в . Все различия относятся к базовому вычислению.${\displaystyle \Delta _{i}}$${\displaystyle \Delta _{i}^{K}}$
${\displaystyle \nabla _{j}}$${\displaystyle \nabla _{J}^{K}}$

Шаг три: Поскольку трассы не имеют общих нелинейных компонентов (например, S-боксы), следы могут быть объединены , чтобы получить: , что соответствует определениям обоих дифференциалов с шага 2. Это тривиально , чтобы видеть , что кортеж из базового вычисления также соответствует по определению обоим дифференциалам, как и дифференциалы по отношению к базовому вычислению. Подставляя в любой из этих двух определений, даст так и . Это означает, что кортеж базового вычисления также может быть объединен с помощью операции XOR с объединенными следами:
${\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}}$

${\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}$
${\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}}$

${\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 [ править ]

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

Шаг второй: злоумышленник строит биклик для каждой группы ключей. Биклика имеет размерность-d, поскольку она отображает внутренние состояния , в зашифрованные тексты , с помощью ключей. В разделе «Как построить биклику» рассказывается, как построить биклику, используя «Независимые дифференциалы связанных ключей». В этом случае биклика строится с использованием дифференциалов набора ключей и , принадлежащих субшифрам.${\displaystyle 2^{2d}}$${\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}}$

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

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

Пример атаки [ править ]

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

Разделение ключей [ править ]

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

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

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

${\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 выбираются по отношению к базовому ключу, дифференциальные трейлы, использующие ключи, никогда не используют какие-либо активные S-блоки (что является единственным нелинейным компонентом в AES), а дифференциальные трейлы используют ключ . Следовательно, можно выполнить операцию XOR дифференциальных следов и создать биклику.${\displaystyle \Delta _{i}}$${\displaystyle K[i,0]}$${\displaystyle \nabla _{j}}$${\displaystyle K[0,j]}$

Атака 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 может быть осуществлена. Чтобы проверить ключ , необходимо только пересчитать части шифра, которые, как известно, будут варьироваться от до . Для обратного вычисления от до это 4 S-блока, которые необходимо пересчитать. Для прямого вычисления от до это всего 3 (подробное объяснение объема необходимого перерасчета можно найти в статье «Biclique Cryptanalysis of the full AES ^[1] », откуда взят этот пример).${\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}}]{}}}$${\displaystyle P_{i}}$${\displaystyle {\xrightarrow[{v_{i}}]{}}}$

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

Результаты [ править ]

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

Ссылки [ править ]