Rebound attack

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

Основная идея

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

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

Rebound-атака включает в себя 2 этапа:

1. Внутренняя фаза охватывает часть дифференциальных характеристик, которые трудно выполнить в вероятностной форме. Здесь преследуется цель найти много решений для этой части характеристик с низкой средней временной сложностью. Для достижения этой цели соответствующая система уравнений, описывающая характеристику в этой фазе, должна быть недоопределенной. При поиске решения появляется множество степеней свободы, дающих много отправных точек. Входная фаза может быть повторена несколько раз, чтобы получить достаточное количество точек для удачного исполнения выходной фазы.
2. Во внешней фазе подобранные пары внутренней фазы используются в вычислениях в прямом и обратном направлении. Обычно $E_{fw}$ и $E_{bw}$ имеют низкую вероятность, так что необходимо повторять внутреннюю фазу для получения большего количества стартовых точек.

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

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

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

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

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

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

Rebound-атака может быть использована на хеш-функции Whirlpool для нахождения коллизий за 4.5 или 5.5 раундов. Почти-коллизии могут быть обнаружены за 6.5 и 7.5 раундов. Ниже описана 4.5-раундовая атака.

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

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

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

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

где $a$ — разность на входе, а $b$ — разность на выходе S-блока. Эта таблица 256х256 позволяет найти значения, удовлетворяющие характеристикам для всех возможных пар, проходящих через S-блок. Таблица справа показывает возможное число решений и вероятность их появления. Первая строка показывает случай отсутствия решений, последняя описывает случай с нулевой разностью.

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

Для нахождения коллизии в Whirlpool за 4.5 раунда, дифференциальные характеристики в таблице ниже должны быть вычислены. Характеристика с наименьшим числом активных байтов отмечена красным. Характеристика может быть описана количеством активных байтов в каждом раунде, например, 1 → 8 → 64 → 8 → 1 → 1.

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

$E_{bw}$
$E_{in}$
$E_{fw}$

Внутренняя фаза

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

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

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

Внешняя фаза

Внешняя фаза дополняет данные характеристики вероятностным путём. Она использует усечённые дифференциалы в отличие от внутренней фазы. Каждая точка отсчёта считается в прямом и обратном направлении. Чтобы получить исходные характеристики, 8 активных байтов должны образовать 1 активный байт в обоих направлениях. Преобразование 8 байтов в 1 случается с вероятностью в 2⁻⁵⁶,, поэтому получение характеристик имеет шанс 2⁻¹¹². Чтобы однозначно получить коллизию, необходимо, чтобы байты на входе и на выходе блокировали все последующие операции. Это происходит с вероятностью приблизительно 2⁻⁸, в общем вероятность успеха внешней фазы составляет 2⁻¹²⁰.

Для обнаружения коллизии, во внутренней фазе необходимо сгенерировать хотя бы 2¹²⁰ точек. После этого операция обнаружения может выполняться со временной сложностью 1 на одну стартовую точку, потому итоговая временная сложность атаки — 2¹²⁰.

Усовершенствование атаки

Базовая 4.5-раундовая атака может быть улучшена до 5.5-раундовой добавлением ещё 1 раунда во внутреннюю фазу. Это повысит временную сложность алгоритма до 2¹⁸⁴.

Усовершенствование внешней фазы с её началом и окончанием с 8 активными байтами привело к почти-коллизии в 52 байтах Whirlpool, продлевающей атаку до 7.5 раундов с временной сложностью 2¹⁹².

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

Литература

• The Rebound Attack: Cryptanalysis of Reduced Whirlpool and Grøstl by Florian Mendel, Christian Rechberger, Martin Schlaffer, and Soren S. Thomsen (Fast Software Encryption 2009: 260—276)
• The Rebound Attack on Reduced Grøstl Hash Function by Florian Mendel, Christian Rechberger, Martin Schlaffer, and Soren S. Thomsen (The Cryptographer’s Track at RSA Conference 2010: 350—365)
• Unaligned Rebound Attack — Application to Keccak by Alexandre Duc, Jian Guo, Thomas Peyrin, Lei Wei (IACR Cryptology ePrint Archive Year 2011 / 420)
• How to Improve Rebound Attacks by María Naya-Plasencia FHNW, Windisch, Switzerland (CRYPTO’11 Proceedings of the 31st annual conference on Advances in cryptology Pages 188—205)
• The Rebound Attack and Subspace Distinguishers: Application to Whirlpool by Mario Lamberger, Florian Mendel, Christian Rechberger, Vincent Rijmen, and Martin Schläffer(IACR Cryptology ePrint Archive, Year. 2010 /198).
• Cryptanalysis of AES based hash functions A PHd theses by Martin Schläffer