Rebound-атака

редактировать

Rebound-атака - это инструмент в криптоанализе криптографического хэша функции. Нападение было впервые опубликовано в 2009 году Флорианом Менделем, Кристианом Рехбергером, Мартином Шлеффером и Сёреном Томсеном. Он был задуман для атаки на AES подобные функции, такие как Whirlpool и Grøstl, но позже было показано, что он применим и к другим проектам, таким как Keccak, JH и Skein.

Содержание

1 Атака
2 Подробное описание атаки на хеш-функции с помощью AES-подобных функций сжатия
3 Пример атаки на Whirlpool
- 3.1 Предварительные вычисления
- 3.2 Выполнение атаки
  - 3.2.1 Входящая фаза
  - 3.2.2 Исходящая фаза
- 3.3 Расширение атаки
4 Примечания
5 Ссылки

Атака

Rebound Attack - это тип статистической атаки на хэш-функции с использованием таких методов, как ротационный и дифференциальный криптоанализ для поиска коллизий и других интересных свойств.

Основная идея атаки состоит в том, чтобы наблюдать определенную дифференциальную характеристику в блочном шифре (или в его части), перестановку или другой тип примитива. Нахождение значений, соответствующих характеристике, достигается путем разделения примитива $E {\ displaystyle E}$ $E$ на три части, так что $E = E fw ∘ E in ∘ E bw {\ displaystyle E = E_ {\ text {fw}} \ circ E _ {\ text {in}} \ circ E _ {\ text {bw}}}$ ${\ displaystyle E = E _ {\ text {fw }} \ circ E _ {\ text {in}} \ circ E _ {\ text {bw}}}$ . $E in {\ displaystyle E _ {\ text {in}}}$ $E _ {\ text {in}}$ называется входящей фазой, а $E fw {\ displaystyle E _ {\ text {fw}}}$ ${\ displaystyle E _ {\ text {fw}}}$ и $E bw {\ displaystyle E _ {\ text {bw}}}$ ${\ displaystyle E _ {\ text {bw}}}$ вместе называются исходящей фазой. Затем злоумышленник выбирает значения, которые детерминистически реализуют часть дифференциальной характеристики во входящей фазе, и вероятностным образом удовлетворяют оставшейся части характеристики.

Таким образом, рикошетная атака состоит из двух фаз:

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

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

Подробное описание атаки на хэш-функции с помощью AES-подобных функций сжатия

Рассмотрим хэш-функцию , которая использует AES -подобную замену- блочный шифр перестановки как его функция сжатия. Эта функция сжатия состоит из ряда циклов, состоящих из S-блоков и линейных преобразований. Общая идея атаки состоит в том, чтобы построить дифференциальную характеристику, которая имеет наиболее затратную в вычислительном отношении часть посередине. Затем эта часть будет охвачена входящей фазой, тогда как более легко достижимая часть характеристики будет охвачена исходящей фазой. Система уравнений, описывающая характеристику входящей фазы, должна быть недоопределенной, чтобы можно было сгенерировать множество начальных точек для исходящей фазы. Поскольку более сложная часть характеристики содержится во входящей фазе, здесь можно использовать стандартные дифференциалы, тогда как усеченные дифференциалы используются на исходящей фазе для достижения более высоких вероятностей.

Входящая фаза, как правило, будет иметь небольшое количество активных состояний байтов (байтов с ненулевой разницей) в начале, которые затем распространяются на большое количество активных байтов в середине цикла, прежде чем вернуться к меньшему количеству активных байтов в конце фазы. Идея состоит в том, чтобы иметь большое количество активных байтов на входе и выходе S-блока в середине фазы. Затем характеристики могут быть эффективно вычислены путем выбора значений различий в начале и в конце входящей фазы, распространения их к середине и поиска совпадений на входе и выходе S-блока. Для шифров, подобных AES, это обычно может выполняться по строкам или по столбцам, что делает процедуру относительно эффективной. Выбор разных начальных и конечных значений приводит к множеству различных дифференциальных характеристик на входящей фазе.

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

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

Пример атаки на Whirlpool

Rebound Attack можно использовать против хэш-функции Whirlpool, чтобы найти коллизий на вариантах где функция сжатия (AES -подобный блочный шифр, W) сокращается до 4,5 или 5,5 раундов. Ближайшие столкновения встречаются на патронах 6.5 и 7.5. Ниже приводится описание атаки с 4,5 раундами.

Предварительное вычисление

Количество решений	Частота
0	39655
2	20018
4	5043
6	740
8	79
256	1

До Чтобы сделать обратную атаку эффективной, перед атакой вычисляется таблица поиска для различий S-блока. Пусть $S: {0, 1} 8 → {0, 1} 8 {\ displaystyle S: \ {0,1 \} ^ {8} \ to \ {0,1 \} ^ {8}}$ $S: \ {0,1 \} ^ {8} \ to \ {0,1 \} ^ {8}$ представляют собой S-блок. Затем для каждой пары $(a, b) ∈ {0, 1} 8 {\ displaystyle (a, b) \ in \ {0,1 \} ^ {8}}$ $(a, b) \ in \ {0,1 \} ^ {8}$ мы находим решения $x {\ displaystyle x}$ $x$ (если есть) уравнения

S (x) ⊕ S (x ⊕ a) = b {\ displaystyle S (x) \ oplus S (x \ oplus a) = b}

{\ displaystyle S (x) \ oplus S (x \ oplus a) = b}

где $a {\ displaystyle a}$ $a$ представляет входную разницу, а $b {\ displaystyle b}$ $b$ представляет разница вывода S-блока. Эта таблица 256 на 256 (называемая таблицей распределения различий, DDT) позволяет находить значения, которые соответствуют характеристикам для любых конкретных пар ввода / вывода, которые проходят через S-блок. В таблице справа показано возможное количество решений уравнения и как часто они встречаются. Первая строка описывает невозможные дифференциалы, а последняя строка описывает нулевой дифференциал.

Выполнение атаки

Чтобы обнаружить столкновение на 4,5 раундах Whirlpool, необходимо иметь дифференциальную характеристику типа, показанного в таблице ниже. найденный. Эта характеристика имеет минимум активных байтов (байтов с ненулевой разницей), отмеченных красным. Характеристика может быть описана количеством активных байтов в каждом раунде, например 1 → 8 → 64 → 8 → 1 → 1.

Усеченная дифференциальная характеристика на 4,5 раунда хеш-функции Whirlpool.
$E bw {\ displaystyle E _ {\ text {bw}}}$ ${\ displaystyle E _ {\ text {bw}}}$
$E in {\ displaystyle E _ {\ text {in}}}$ $E _ {\ text {in}}$
$E fw {\ displaystyle E _ {\ text {fw}} }$ ${\ displaystyle E _ {\ text {fw}}}$

Входящая фаза

Цель входящей фазы - найти различия, которые соответствуют части характеристики, описываемой последовательностью активных байтов 8 → 64 → 8. Это можно сделать следующим образом. три шага:

Выберите произвольную ненулевую разницу для 8 активных байтов на выходе операции MixRows в раунде 3. Эти различия затем распространяются в обратном направлении на выход SubBytes в раунде 3. Благодаря свойствам операции MixRows получается полностью активное состояние. Обратите внимание, что это можно сделать для каждой строки независимо.
Выберите разницу для каждого активного байта на входе операции MixRows в раунде 2 и распространите эти различия вперед на вход операции SubBytes в раунде 3. Сделайте это для всех 255 ненулевых разностей каждого байта. Опять же, это можно сделать независимо для каждой строки.
На этапе сопоставления посередине мы используем таблицу DDT, чтобы найти совпадающие различия ввода / вывода (как показано на этапах 1 и 2) для операция SubBytes в раунде 3. Каждая строка может быть проверена независимо, и ожидаемое количество решений равно 2 на S-блок. В целом, ожидаемое количество значений, следующих за дифференциальной характеристикой, равно 2.

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

Исходящая фаза

Исходящая фаза завершает дифференциальную характеристику вероятностным образом. Исходящая фаза использует усеченные дифференциалы, в отличие от входящей фазы. Каждая начальная точка, найденная во входящей фазе, распространяется вперед и назад. Чтобы соответствовать желаемой характеристике, 8 активных байтов должны распространяться на один активный байт в обоих направлениях. Один такой переход с 8 на 1 происходит с вероятностью 2, поэтому выполнение характеристики имеет вероятность 2. Чтобы гарантировать коллизию, значения в начале и конце характеристики должны отменяться во время подачи. -передача. Это происходит с вероятностью приблизительно 2, поэтому общая вероятность исходящей фазы равна 2.

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

Расширение атаки

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

Расширение исходящей фазы так, что она начинается и заканчивается 8 активными байтами, приводит к почти конфликту в 52 байтах на Whirlpool сокращено до 7,5 раундов с сложностью, равной 2.

Предполагая, что злоумышленник имеет контроль над значением цепочки и, следовательно, вводом в расписание клавиш Whirlpool, атака может быть расширена до 9,5 раундов в полусвободном запуске, близком к конфликту, на 52 байтах со сложностью , равной 2.

Примечания

Источники

Rebound Attack: Cryptanalysis of Reduced Whirlpool and Grøstl Флориана Менделя, Кристиана Рехбергера, Мартина Шлаффера и Сорена С. Томсена (Fast Software Encryption 2009: 260-276)
Rebound Attack on Reduced Хеш-функция Грёстля Флориана Менделя, Кристиана Рехбергера, Мартина Шлаффера и Сорена С. Томсена (The Cryptographer's Track at RSA Conference 2010: 350-365)
Unaligned Rebound Attack - Application to Keccak Al exandre Duc, Jian Guo, Thomas Peyrin, Lei Wei (IACR Cryptology ePrint Archive Year 2011/420)
Как улучшить обратные атаки, Мария Ная-Пласенсиа FHNW, Виндиш, Швейцария (CRYPTO'11 Proceedings of the 31st ежегодная конференция по достижениям в криптологии, стр. 188-205)
Rebound Attack и Subspace Distinguishers: Application to Whirlpool Марио Ламбергер, Флориан Мендель, Кристиан Рехбергер, Винсент Раймен и Мартин Шлеффер (Архив электронных печатных изданий IACR Cryptology, год. 2010 /198).
Криптоанализ хеш-функций на основе AES Докторская диссертация Мартина Шлеффера