Коллизионные атаки на функцию сжатия Кнудсена-Пренеля

Аннотация. Кнудсен и Пренэль (Asiacrypt'96 и Crypto'97) представили хэш-функцию, в которой линейный исправляющий ошибки код используется для построения широко-пропускающей функции сжатия из лежащих в основе шифров способом Дэвиса-Майера. Их главная целью было предложить функцию сжатия с увеличенной устойчивостью к коллизиям и, более того, блочный размер лежащих в основе блочных кодов. В этой работе мы представляем новые атаки на эти функции сжатия, использую идеи из неопубликованных работ Ватанабе и атаку Озена, Шримптона и Стэма. Вкратце, наша лучшая атака имеет временную сложность строго меньше чем размер блока кода на всех наборах, кроме двух. Следовательно, нижняя граница временной сложности, доказанная Кнудсеном и Пренелем неверна и функция сжатия не дает того уровня защищенности, для которого она была создана. Ключевые слова: Коллизионные атаки, теория кодирования, функция сжатия.

Введение

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

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

Уже определено ранее, что размер вывода традиционного блочного кода недостаточен для получения защищенной функции сжатия [1] . Это верно и сейчас: для всех оптимально защищенных PGV, основанных на блочных кодах, функциях сжатия [2] , [3] , [4] основанных на блочном коде длины n, временная сложность коллизионных и атак нахождения прообраза в лучшем случае 2 n / 2 , а в общем 2 n , когда n=128 (напр AES) граница преимущественно неприемлиема (в частности, для противостояния коллизиям).

Чтобы добиться приемлемой безопасности (основанной на маленьких размерах блоков), необходимо вывести множество длин блоков. В 90-х годах многие ставили перед собой такую цель, в основном выводя 2n бит с точным сопротивлением колиизиям в ( [5] , [6] - пример). Стандартная цель для этих разработок - оптимальное сопротивление коллизиям: необходимый размер вывода фиксирован и функция сжатия должна быть достаточно устойчивой к границе дней рождения этого размера. В трех работах [7] , [8] , [9] , Кнудсен и Пренель применили другой подход, а именно установили конкретную цель и дали размеру вывода (и количеству вызовов блочного кода) различаться, как необходимо чтобы гарантировать защищенность конкретной цели без громадной общей безопасности.

Наш вклад. В этой работе мы описываем то, что на наш взгляд, положит конец функциям сжатия Кнудсена-Пренеля. Краткое описание нашего вклада вы видете в таблице 1. Для полноты картины, мы также изучили временную сложность, которая было получена с помощью сложностей OSS; детально описанную в работе [11] .

В Разделе 4 находится детальное математическое описание начального шага работы функции сжатия Кнудсена-Пренеля. Результатом этого стало выполнение нами атаки Ватанабе методом, который немного снижает требования по времени, но значительно повышает количество коллизий. Строго говоря, за d 2 n , мы можем сделать до 2 ( k − d ) n коллизий за константное время (для k > d ).

В третьих, в Разделе 6.1 мы представляем параметрическую теоретичесую коллизионную атаку. Выяснено, что новая симбиотичная атака и хорошо известная ОСС атака находятся на противоположных концах спектра этой параметрической атаки, причем оптимальность достигается где-то в середине - со сложностью ( 2 k n / ( 3 k − r ) ) (кроме K P ( [ 5 , 2 , 4 ] 8 ) и K P ( [ 4 , 2 , 3 ] 8 ) ).

Ну и напоследок, мы снизили время нашей оптимизированной атаки. Для этого мы использовали те же идеи, что и ОСС, но с важным изменением: там где в ОСС используется двойственный код для эффективного нахождения прообраза, мы используем двойственный укороченный код.Как результат, для 12 из 16 предложенных параметров мы смогли устроить такую атаку, сложность по времени которой совпадает со сложностью по памяти (не считая констант и логарифомов). Более того, только для K P ( [ 5 , 2 , 4 ] 8 ) мы не смогли превзойти временную сложность любой ранее существующей атаки, которой мы опасаемся.

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

С небольшими изменениями, мы будем придерживаться тех же обозначений, что и Озен, Шримтпон и Стам.

Большинство PuRF-based (и основанных на блочных шифрах) функций сжатия имеют специальный тип. Вместо случайной пре- и постобработки, находятся только блочно-линейные функции. Конструкция Кнудсена-Пренеля также блочно-линейна, поэтому вернемся к блочно-линейной схеме.