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

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 15:27, 4 декабря 2015.
Collision Attacks against the Knudsen-Preneel Compression Functions
Collision Attacks against the Knudsen-Preneel Compression Functions.png
Авторы Onur O ̈zen[@: 1] and
Martijn Stam[@: 2]
Опубликован 2010 г.
Сайт International Association for Cryptologic Research
Перевели Alexander Zelinsky
Год перевода 2015 г.
Скачать оригинал

__NUMBEREDHEADINGS__


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

Введение

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

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

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

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

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

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

Эффект такого строения заключается в том, что когда 2 входных набора к "большой" функции различаются, соответствующие входы для основных функций будут различны как минимум в d функциях. В частном случае, использую систематический генератор, изменение в систематической части входов повлечет за собой минимум так называемых активных функций в несистематической части. Это значит, что найдется прообраз или коллизия для функции в параллели. Основываясь на этом наблюдении, Кнудсен и Пренель утверждают (предполагают), что любой коллизионной атаке необходимо как минимум (и определений) и они выдвинули гипотезу, что атака нахождения прообраза потребует времени. Более того, они описали коллизионные и атаки нахождения прообраза (иногда равные их нижним границам).

Таблица 1. Краткая информация о коллизионных атаках на функцию Кнудсена-Пренеля (константами пренебрежено). NON-MDS коды выделены курсивом, для базис , а для

Таблица 1

Ватанабе [10] уже нашел коллизионную атаку, превосходящую данную Кнудсеном и Пренелем на многих наборах. В частности, его атака работает всегда при и имеет сложность в . Таким образом, он показал, что доказанность сопротивления коллизиям нижней границы, данной Кнудсеном и Пренелем, неверна для и . Для кода с минимальным расстоянием , наблюдается совпадение с нижней границей Кнудсена-Пренеля в ; 2 предложенных Кнудсеном и Пренелем кода с (а именно и ) представляются неудовлетворяющими этой границе. Это стало первым признаком ошибочности заявления Кнудсена и Пренеля. Второй был найден на FSE'10, когда Озен, Шримптон и Стам показали весьма эффективную атаку нахождения прообраза, которая в 9 из 16 попыток, завершилось за время, равное , что было признано оптимальным. Более того, они показали, что теоретически враг вполне может найти коллизии за .

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

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

В нашей версии атаки Ватанабе, мы взяли тензор и дифференцировали. Взяв случайный тензор и используя методы Озена, Шримптона и Стама, в Разделе 5.2 мы получаем новую, симбиотичную атаку нахождения коллизий с временной сложностью . Атака работает всегда при (как и в случае Ватанабе). Еще более невероятен тот факт, что если неравенство строгое, , то противник может создать еще коллизии за константное время (до коллизий).

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

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

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

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


Линейные исправляющие ошибки коды. линейный исправляющий защиту код С это набор элементов (кодовых слов) в k-ичном подпространстве поля (для ), в котором минимальное кодовое расстояние d равно минимальному весу Хэмминга (на всех ненулевых кодовых словах в С). Двоичный код это набор всех элементов в -ичном подпространстве, ортогональном к С, и минимальное кодовое расстояние d перп. Граница Синглтона устанавливает границу для кодового расстояния: . Важной свойство MDS кода это двойственность, таким образом .


код С может быть порожден матрицей , C= (построчно). Порождающая матрица G называется порождающей, если имеет вид для и тождественна в . Более того, G - порождающая матрица MDS кода если любые k столбцов линейно независимы. Для набора мы определим . Для кода и любого набора , мы хотим определить такое, что ортогональна и или . Для MDS кодов, существование такого легко может быть показано (и однозначно). Для не-MDS кодов существует такое для которого такое не существует (например ), однако для требуемой мощности возможно найти (требуемой мощности) у которого есть (из систематических разрядов), такое - допустимое.


Данный код С может быть сокращен до C'. Пусть , затем возьмем набор всех кодовых слов в С, которые =0 в i бите. Новый код C' состоит из этих кодовых слов без i битов, однако иногда мы "квази-сокращаем" и оставляем эти нули. Легко заметить, что C' это код если только все кодовые слова в С не имеют 0 в i бите или k=1 (тогда мы получим тривиальный код ). Cокращенный MDS код является MDS кодом. Повторением данного алгоритма можно уменьшить любой набор , для которого и получить MDS код C'. Если G систематическая и мы можем генерировать сокращенный код отбросив первые рядов , где . (Для 4 non-MDS кодов, используемых Кнудсеным и Пренелем, анализ мы проведем позднее).


Линейно-блочные функции сжатия. Функция сжатия это отображение для какого-либо блока длины и целочисленных . Для положительных c и n мы положим Func(cn,n) задающую все отображения из в . Функция сжатия является PuRF-based, если ее отображение находимо ограниченным набором оракулов , где . Когда PuRF-based функция действует на входе W, результатом будет . Для нас более интересны однослойные PuRF-based функции сжатия. Они вызывают оракулы параллельно и считают выходное значение основываясь только на результатах этих вызовов, в частности, вход функции сжатия не учитывается.

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


TemplateDifinitionIcon.svg Определение «Определение 1 (Блочно-линеная схема).»

Пусть r,c,b,t,s - положительные целые и пусть даны . Определим как семейство однослойных PuRF-based функций сжатия ,для всех положительных целых n с . Более точно, пусть и . Затем на входе (векторе-столбце), считает следующим образом:

1. Считает

2. Парсит и для считает

3. Парсит и выход

где произведение Кронекера и тождественна в .

В вышеуказанном определении мы определили с помощью векторного пространства . Отображению соответствует и его образ . Нам удобнее записывать как сумму, определим как где для . Если и , то соответственно будет в . (Это применимо к , когда )

Функции сжатия Кнудсена-Пренеля. Кнудсен и Пренель [7],[7] представили семейство хэш функций с исправляющими ошибки кодами. (Мы используем [9] как ссылку). Хотя их работа якобы ориентирована на блочное строение, основная идея работы - разработка способа преобразования "идеальной" функция сжатия (как основанной на блочных кодах, так и нет) так, чтобы обеспечивался требуемый уровень безопасности. Сейчас мы осознаем, что идеальная функция сжатия - это PuRF. КР преобразует указанный в определении 1 пример блочно-линейной схемы, в которой входы PuRF-функции определены линейным кодом над бинарным пространством со степенью расширения , и единична над .Поле расширения представляет собой подкольцо кольца степени e над базовым полем. Определим это как гомоморфизм и положим как применение и последующего определения через (будем использовать для матриц над случайных степеней. Для полноты картины, также существует гомоморфизм групп такой, что для всех

TemplateDifinitionIcon.svg Определение «Определение 2 (Преобразование Кнудсена-Пренеля.»

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

Если , то с определено для всех , для которых - делитель. Более того, основано на r PuRF в . Для использования H как итеративную хэш функцию, надо учитывать, что за один вызов сжимается блоков (сжатие обуславливается требованием ), и степень сжатия . Мы сконцентрируемся на случае и затем, в частности, на 16 данных Кнудсеном и Пренелем наборах[прим. 1]. Так как уникально определяется с помощью ), будем это опускать.

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

Основные атаки на хэш-функцию Кнудсена-Пренеля

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

Кнудсен и Пренель также представили две атаки, одна нахождения прообраза [9], одна нахождения коллизий [9]. Обе атаки касаются нахождения мультипрообразов для систематической части строения для достаточного числа чисел чтоб показать, что применение этого к несистематической части приведет к нахождению полного прообраза, соответственно и коллизии.

Атака нахождения коллизий Ватанабе. Кнудсен и Пренель оставили большое различие между реальной сложностью атак и нижней границей в случае противостоянии коллизиям. Ватанабе [10] предложил атаку нахождения коллизий, которая работает за (и такое же количество PuRF оценок.). Таким образом, для многих наборов, она превосходит данную Кнудсеном и Пренелем. Еще интереснее, эта атака показывает, что нижняя граница, данная Кнудсеном и Пренелем неверна для большого количества наборов: при и (см. Таблицу 1)

Будем считать, что порождающая матрица кода систематическая, с . Тогда целью будет получить для каждого дающую коллизии пару входов ) таким образом, чтоб их дополнение до полных кодовых слов доказывало для . Это выполнимо, так как , где в ядре (так как , то ядро точно содержит нетривиальный элемент). Независимость между собой входов для PuRF функций позволяет независимо искать коллизии. Увы, коллизии должны быть достаточно разные (из-за фиксированного , парадокс дней рождения не применим, и стоимость поиска коллизий равна . C положительной стороны, атака не требует много памяти и распараллеливаемая.

Атака нахождения прообраза Озена-Шримптона-Стама. Исчерпывающий анализ сопротивления атакам нахождения прообраза KP-конструкций, опровергнувший заявленную нижнюю границу, был проведен Озеном, Шримптоном и Стамом [12]. Более того, они также предоставили атаку нахождения коллизий с неожиданно низкой сложностью по памяти: (но ничего не сказали о временной сложности).

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

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

Расшифровка обработки Кнудсена-Пренеля

Важное свойство, используемое как Ватанабе так и OSS это линейность . В самом деле, образ можно представить как ekn'-нное подпространство или код (где минимальное кодовое расстояние d' ни на что не влияет, ). Из этого следует, что если и , то , то есть разница представляет собой ненулевое кодовое слово в . Ниже мы дадим более детальное математическое описание , уделив особенное внимание улучшению алгоритмам поиска коллизий. Большинство результатов достаточно математически просты; техника нужны только для того, чтоб в этом удостовериться, использую канонический базис для различных векторных пространств, все сходится с функций сжатия КП.

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

Представление как суммы. Мы уже определили как сумму PuRF входов определив как где для . Здесь мы рассмотрим другое определение. Примем где для . Так как и - расширение над полем , мы не можем определить изоморфизм векторных пространств (как и ранее для прямой суммы). Тем не менее, мы можем определить гомоморфизм групп из в .

Чтобы определить гомоморфизм будем использовать арифметику над , обеспеченную , хотя '' в показывает обратное. Чтобы формализовать это, пусть - гомоморфизм групп такой, что для всех и .

TemplateDifinitionIcon.svg Определение «Лемма 1»

Пусть , пусть сокращение на и пусть для . Тогда с для всех если такой что .

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

TemplateDifinitionIcon.svg Определение «Утверждение 1»

Пусть даны , и ненулевой . Предположим что для некоторого , тогда если для всех положительных целых .

Так как изоморфно , то можно определить функцию из в , где с и . Так, для ненулевого .

TemplateDifinitionIcon.svg Определение «Лемма 2»

Если и , то если или .

Данная лемма утверждает. что невырожденность матрицы достаточное условие для невырожденности .

TemplateDifinitionIcon.svg Определение «Лемма 3»

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

Новая симбиотичная атака нахождения коллизий.

Улучшение атаки Ватанабе.

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

В его работе, Ватанабе описал свою атаку как отличительную. Обычно берется как нетривиальный элемент ядра, а мы находим его основываясь на кодовом слове достаточно низкого веса и случайном . В частности, . Атака наиболее эффективна при использовании кодового слова минимального веса.

Algorithm 1 (Revised Watanabe Collision Attack)

Для улучшенной атаки нам надо еще кое-что. Ватанабе использовал систематический код, когда то существует ненулевое кодовое слово для которого . Это позволяет легко получать полную коллизию из частичной. Наша улучшенная версия допускает случайное кодовое слово веса как максимум (что требует ). Таким образом, может больше не отображать к систематической части кода. К счастью, Лемма 3 объясняет дополнение до полной коллизиии. Для MDS-кодов все кодовые слова допустимы, для 4 не-MDS-кодов предложенных Кнудсеном и Пренелем может быть доказано что минимальное кодовое расстояние допустимо.

TemplateTheoremIcon.svg Теорема Теорема 1(Улучшеннная атака Ватанабе.)
Пусть задан с . Примем ). Тогда Алгоритм 1, использующий кодовое слово (и ненулевое случайное ) найдет коллизии для за ожидаемое время (и такое же количество PuRF вычислений)
Доказательство
Без доказательства.


Algorithm 2 (New Symbiotic Collision Attack)

Новая симбиотичная атака

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

TemplateTheoremIcon.svg Теорема Теорема 2(Новая симбиотичная атака)
Пусть задан с . Примем ). Тогда Алгоритм 2 найдет коллизии для за (и такое же количество PuRF вычислений) и памяти (в блоках длины n)
Доказательство

Мы не будем здесь доказывать корректность этого алгоритма [11] и только докажем, что коллизия ожидаема и временная и сложность по памяти равна заявленной.

Так как , то атака имеет заявленную сложность (на PuRF) для , так как все запросы запросы делаются на этапе запросов. Достаточно простым способом, локальное распознавание коллизий может быть выполнено за (грубо) сравнений, что даст список частичных коллизий с для .

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

Так как у нас есть PuRF, вероятность нахождения общего элемента среди d таких списков равна или . Чтобы убедиться в том, что мы найдем одну коллизию, необходимо, чтобы второй показатель степени был как минимум 0, и тогда, для нуля, получим требуемое


Параметрическая атака нахождения коллизий.

Оптимизация сложности

Algorithm 3 (Parameterized Collision Attack).

Симбиотичная атака и информационная-теоритеческая атака Озена, Шримптона и Стама имеют разные сложности, в зависимости от набора параметров. Однако, выяснилось, что обе атаки - специальные случаи общей параметрической атаки (см. Алгоритм 3).

TemplateTheoremIcon.svg Теорема Теорема 3
Пусть задан . Примем ). Тогда коллизии для могут быть найдены с помощью Алгоритма 3 за операций (на PuRF), где

Доказательство

То, что атака имеет заявленную сложность следует из простого наблюдения, что и вычисления . Остается показать, что коллизии ожидаются с очень высокой вероятностью.

Пусть - выход алгоритма и , а . Во-первых, заметим, что Лемма 3 утверждает, что проекция на есть. Шаги 6-8 убеждают, что . Наконец, так как , то для и мы имеем .

Более того, шаг 5 доказывает, что и шаг 7 доказывает, что проекции и на эквивалентны. Отсюда, для всех .

Перейдем к количеству ожидаемых коллизий. Так как , ожидаемое количество локальных коллизий на PuRF для равно . Учитывая что , общее количество потенциальных коллизий равно . Для того, чтоб случилась истинная коллизия, необходимо найти такое, что как , так и могут быть дополнены до кодовых слов.

Если коллизия состоит из , тогда - также кодовое слово. Отсюда, применив Лемму 1, получим . Ограничение доказывает нетривиальность сокращенного кода (если уменьшим еще меньше - получим нулевое кодовое слово). Для MDS-кодов сокращенный код имеет параметры , в частности имеет расширение степень . (Для не-MDS-кодов достижима большая степень.

Как итог, частное от производных удовлетворительно, ожидаемое количество . Если или достигается успех при . может быть представлено как , c . Записав и заменив, мы получим или .

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


TemplateTheoremIcon.svg Теорема Следствие 1
Принимая , подстановка в Теореме 3 дает . Это оптимально для .
Доказательство

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


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

Замечание 2. Если мы возьмем в Теореме 3, то получим и итоговая сложность совпадет с данной Озеном, Шримптоном и Стамом. С другой стороны, даст нам (принимая ). Для MDS-кодов это ведет к , что совпадает с нашей симбиотической атакой. Для не-MDS-кодов небольшое несходство имеет место. Причина в том, что если код максимально сокращен, мы пессимистично полагаем (для не-MDS-кодов КП удовлетворяющим ).

Генерирование коллизионной против MDS

Если мы хотим запустить Алгоритм 3 (c и как приведено в Следствии 1) мы хотим, чтобы временная сложность совпала со сложностью запросов. Для , и нам надо выполнить шаги 6 и 7. Мы уже знаем, что шаг 3 выполняется за логарифм, значит необходимо беспокоится только о шагах 4 и 5. В сумме они дают . Можно перечислить все элементы, большие , но это нарационально. Наша задача - имея лист частичных коллизий для , создать максимально эффективно .

Algorithm 4 (Collision Attack against MDS-based schemes).

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

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

Снижение временной сложности. Так как и , из Алгоритма 3 следует что достаточно найти ненулевое вида для для дополнения коллизии. Теперь учтем, что лежит в меньше пространстве , заданном , причем сокращенный код, полученный из (отбросив нули из всех кодовых слов в битах, соответствующих ). Это наблюдение позволяет нам гарантировать, что , как только мы найдем потенциальное в . Отсюда, для наших целей достаточно ограничиться , а не искать в большем пространстве .

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

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

Простая адаптация Определения 1 показывает, что если нам дано кодовое слово и элемент , то может быть только в , если , где единственные значимые в данном случае части - те, которые совпадают с ненулевыми записями . В самом деле, элемент может быть дополнен до элемента, входящего в если . Эффективное создание может быть сделано, адаптируя стандартные методы [13], [14], [15]разделением кодового слова на 2 и поиском всех коллизий на соответствующих входах. Принимая с , определим, для . Тогда состоит из тех элементов , для которых и .

TemplateTheoremIcon.svg Теорема Теорема 4
Пусть дан код и - сокращенный код, сокращенный из для . Пусть - минимальное кодовое расстояние двойственного кода . Будем подразумевать что - MDS код и считать. что атака нахождения коллизий, описанная в Алгоритме 4 действует против за для . Тогда ожидаемое число коллизий равно 1 и ожидаемый размер списков равен:

, , , . Средняя временная сложность равна с требованиями по памяти (в cn-блоках)

Доказательство
Без доказательства


Заключение.

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

Благодарности Благодарим Йоахима Розенталя и Томаса Шримптона за их полезные комментарии и предложения.

Контакты авторов материала

  1. LACAL, EPFL Station 14, CH-1015 Lausanne, Switzerland,E-mail:onur.ozen@epfl.ch
  2. LACAL, EPFL Station 14, CH-1015 Lausanne, Switzerland,E-mail:martijn.stam@epfl.ch

Примечание

  1. Наш анализ также уместен для c=5

Литература

  1. Yuval, G.: How to swindle Rabin. Cryptologia 3, 187–189 (1979)
  2. Black,J.,Rogaway,P.,Shrimpton,T.:Black-boxanalysisoftheblock-cipher-based hash-function constructions from PGV. In: Yung [15], pp. 320–335
  3. Preneel, B., Govaerts, R., Vandewalle, J.: Hash functions based on block ciphers: A synthetic approach. In: Stinson, D. (ed.) Advances in Cryptography—Crypto’93. LNCS, vol. 773, pp. 368–378. Springer, Heidelberg (1993)
  4. Stam, M.: Blockcipher-based hashing revisited. In: Dunkelman, O. (ed.) FSE’09. LNCS, vol. 5665, pp. 67–83. Springer, Heidelberg (2009)
  5. Knudsen, L., Muller, F.: Some attacks against a double length hash proposal. In: Roy, B.K. (ed.) Advances in Cryptography—Asiacrypt’05. LNCS, vol. 3788, pp. 462–473. Springer, Heidelberg (2005)
  6. O ̈zen, O., Stam, M.: Another glance at double-length hashing. In: Parker, M.G. (ed.) CCC’09. LNCS, vol. 5921, pp. 176–201. Springer, Heidelberg (2009)
  7. 7,0 7,1 7,2 Knudsen, L.R., Preneel, B.: Hash functions based on block ciphers and qua- ternary codes. In: Kim, K., Matsumoto, T. (eds.) Advances in Cryptography— Asiacrypt’96. LNCS, vol. 1163, pp. 77–90. Springer, Heidelberg (1996)
  8. Knudsen, L.R., Preneel, B.: Fast and secure hashing based on codes. In: Burt Kaliski, J., Burton, S. (eds.) Advances in Cryptography—Crypto’97. LNCS, vol. 1294, pp. 485–498. Springer, Heidelberg (1997)
  9. 9,0 9,1 9,2 9,3 Knudsen, L.R., Preneel, B.: Construction of secure and fast hash functions using nonbinary error-correcting codes. IEEE Transactions on Information Theory 48(9), 2524–2539 (2002)
  10. 10,0 10,1 Watanabe, D.: A note on the security proof of Knudsen-Preneel construction of a hash function (2006), unpublished manuscript, Available at http://csrc.nist. gov/groups/ST/hash/documents/WATANABE_kp_attack.pdf
  11. 11,0 11,1 ̈zen,O.,Stam,M.:CollisionattacksagainstKnudsen-Preneelcompressionfunc- tions, full version of this paper, Manuscript (2010)
  12. 12,0 12,1 Ozen, O., Shrimpton, T., Stam, M.: Attacking the Knudsen-Preneel compression functions. In: Hong, S., Iwata, T. (eds.) FSE’10. LNCS, vol. 6147, pp. 94–115. Springer, Heidelberg (2010)
  13. Chose, P., Joux, A., Mitton, M.: Fast correlation attacks: An algorithmic point of view. In: Knudsen, L. (ed.) Advances in Cryptography—Eurocrypt’02. LNCS, vol. 2332, pp. 209–221. Springer, Heidelberg (2002)
  14. Schroeppel, R., Shamir, A.: A 𝑇 = 𝑂(2𝑛/2), 𝑆 = 𝑂(2𝑛/4) algorithm for certain NP-complete problems. SIAM Journal on Computing 10, 456–464 (1981)
  15. Wagner, D.: A generalized birthday problem. In: Yung [15], pp. 288–303