Rebound attack

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

Основная идея[править | править код]

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

Основной идеей атаки является изучение дифференциальных характеристик блочного шифра (или его фрагментов), перестановки или других низкоуровневых криптографических алгоритмов. Нахождение значений, удовлетворяющих характеристикам, достигается разделением примитивного алгоритма на 3 части: .  — внутренняя фаза, а и вместе составляют внешнюю фазу. Злоумышленник выбирает значения, детерминированно реализующие часть дифференциальных характеристик внешней фазы, и дополняет оставшуюся часть характеристик в вероятностной форме.

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

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

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

Подробное описание атаки хеш-функций с помощью 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-блок. Затем для каждой пары мы найдём решения (при их наличии) следующего равенства

,

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

Выполнение атаки[править | править код]

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

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

Внутренняя фаза[править | править код]

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

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

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

Внешняя фаза[править | править код]

Внешняя фаза дополняет данные характеристики вероятностным путём. Она использует усечённые дифференциалы в отличие от внутренней фазы. Каждая точка отсчёта считается в прямом и обратном направлении. Чтобы получить исходные характеристики, 8 активных байтов должны образовать 1 активный байт в обоих направлениях. Преобразование 8 байтов в 1 случается с вероятностью в 2−56,[1], поэтому получение характеристик имеет шанс 2−112. Чтобы однозначно получить коллизию, необходимо, чтобы байты на входе и на выходе блокировали все последующие операции. Это происходит с вероятностью приблизительно 2−8, в общем вероятность успеха внешней фазы составляет 2−120.

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

Усовершенствование атаки[править | править код]

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

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

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

Примечания[править | править код]

  1. Lamberger, Mendel, Rechberger, Rijmen, Schläffer, 2010, p. 18
  2. Lamberger, Mendel, Rechberger, Rijmen, Schläffer, 2010, p. 22
  3. 1 2 Lamberger, Mendel, Rechberger, Rijmen, Schläffer, 2010, p. 25
  4. Lamberger, Mendel, Rechberger, Rijmen, Schläffer, 2010, p. 31

Литература[править | править код]