Отскок атаки

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

Атака

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

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

Таким образом, рикошетная атака состоит из 2 фаз:

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

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

Подробное описание атаки на хэш-функции с помощью 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}\to \{0,1\}^{8}$ представляют собой S-box . Тогда для каждой пары $(a,b)\in \{0,1\}^{8}$ мы находим решения $x$ (если они есть) к уравнению

$S(x)\oplus S(x\oplus a)=b$,

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

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

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

Усеченная дифференциальная характеристика на 4,5 раундах хеш-функции Whirlpool.

$E_{\text{bw}}$
$E_{\text{in}}$
$E_{\text{fw}}$

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

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

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

Эти шаги можно повторить с 2 ⁶⁴ разные начальные значения на шаге 1, в результате всего получается 2 ¹²⁸ фактические значения, которые соответствуют дифференциальной характеристике во входной фазе. Каждый набор из 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 ¹²⁸ .

Ссылки

• Атака отскока: криптоанализ уменьшенного водоворота и Грёстля Флориана Менделя, Кристиана Рехбергера, Мартина Шлаффера и Сорена С. Томсена (Fast Software Encryption 2009: 260-276)
• Отскок атаки на уменьшенную хеш-функцию Грёстля Флориана Менделя, Кристиана Рехбергера, Мартина Шлаффера и Сорена С. Томсена (След криптографа на конференции RSA 2010: 350-365)
• Атака с отскоком без согласования - заявление к Кечаку Александра Дюка, Цзянь Го, Томаса Пейрина, Лэй Вэя (Архив криптологии ePrint IACR, 2011/420 год)
• «Как улучшить атаки с отскоком» , Мария Ная-Пласенсия FHNW, Виндиш, Швейцария (Материалы 31-й ежегодной конференции CRYPTO'11 по достижениям в криптологии, страницы 188-205)
• Атака отскока и различители подпространства: приложение к Whirlpool Марио Ламбергера, Флориана Менделя, Кристиана Рехбергера, Винсента Реймена и Мартина Шлеффера (Архив криптологии ePrint IACR, год. 2010/198).
• Криптоанализ хеш-функций на основе AES. Кандидатская диссертация Мартина Шлеффера.