Расширенные атаки медотом Meet-in-the-Middle на прообразы: результаты получены на хэш-функции Tiger и улучшенные результаты на основе MD4 и SHA-2

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 13:36, 28 ноября 2015.
Advanced Meet-in-the-Middle Preimage Attacks: First Results on Full Tiger, and Improved Results on MD4 and SHA-2
Advanced Meet-in-the-Middle Preimage Attacks- First Results on Full Tiger, and Improved Results on MD4 and SHA-2.png
Авторы Jian Guo;
San Ling;
Huaxiong Wang[@: 1] and
Christian Rechberger[@: 2]
Опубликован 2009 г.
Сайт International Association for Cryptologic Research
Перевели Roman Vinogradov
Год перевода 2015 г.
Скачать оригинал


Содержание

Аннотация. Мы возвращаемся к практически используемым алгоритмам криптоанализа методом narrow-pipe в настощее время, и их защите от атак нахождения прообраза.Наши результаты - это наиболее известные атаки на прообраз хэш-функций Tiger, MD4(Message Digest 4), и сокращенной SHA-2(Secure Hash Algorithm Version 2). И первая успешная криптоаналитическая атака на полную хэш-функцию Tiger. Наши атаки за находили первый прообраз функции, и за второй прообраз.Для обеих атак необходим объем памяти что гораздо меньше, чем в любых недавних атаках на прообраз сокращенной хэш-функции Tiger. Используя методы предварительных вычислений, временная сложность для нахождения нового первого прообраза или второго прообраза для MD4 теперь могут составить и соответственно. Второй прообраз атаки работает для всех сообщений длиннее двух блоков.
Для получения этих результатов, мы воспользовались расширенным методом "встречи посередине"(далее MITM-метод) недавно разработанным Аоки и Сасаки в ряде своих работ.В дополнение к различным алгоритмически-специфичным методам, мы используем ряд принципиально новых идей, которые применимы к широкому классу хэш-функций. Среди них (1) включение много-целевых сценариев в рамках MITM-метода, что приводит к более быстрому нахождению прообразов из псевдо-прообразов, (2) метод простых предварительных расчетов, который позволяет находить новые прообразы ценой одного псевдо-прообраза, и (3) вероятностные исходные структуры, чтобы уменьшить затраты времени на атаку. Все разработанные методы могут быть применены в других хэш-функций. Чтобы проиллюстрировать это, мы показываем еще один пример, как улучшился прообраз атаки на хэш-функцию SHA-2 семейства.
Ключевые слова: прообраз, MD4, Tiger, SHA-2, хэш-функция, криптоанализ, MITM-метод

Введение

После впечатляющих коллизионных атак на MD5 и SHA-1 Ванга и др., и последовавшей за этим дополнительной работы [[1][2][3][4]], разработчики пересмотрели свои приоритеты. В то время, как началась весьма продуктивная стадия исследования проектирования и анализа криптографических функций хеширования, воздействие этих результатов на активные атаки оказалось ниже ожидаемых (за исключением примеров [[5][6][2]]). Вместо сопротивляемости коллизиям, другая характеристика хеш-функций стала считаться более важной для практической безопасности – это сопротивляемость прообраза. Следовательно, исследование атак нахождения прообраза и повышения барьера защиты хеш-функций от подобных атак кажутся вполне обоснованными, особенно в области функций, используемых на практике. Важной и сложной задачей на текущий момент является нахождение эффективной и надежной новой хеш-функции для долгосрочного использования (как например, было на конкурсе на создание функции SHA-3). Для новых хеш-функций важнейшим шагом для завоевания доверия к себе является их применение к известным крипто-аналитических методам их взлома. Для этого инструментарий крипто-аналитиков должен быть хорошо оснащен. Новые методы, которые мы представляем вашему вниманию в этой статье, способствуют решению обеих проблем сразу. Они дают новые инструменты крипто-аналитикам , в общем случае применимые для анализа функций сжатия и хеш-функций, и в то же время их применение существенно повышает практическую эффективность алгоритмов, направленных на отражение атак нахождения прообраза, таких как MD4, Tiger, и SHA-256/512. Далее мы вкратце опишем эти инструменты и новые результаты, которые будут описаны позже. Мы описываем их с точки зрения применимости к методу MITM - структуре, разработанной Aoki and Sasaki, как недавно описывалось в ряде печатных изданий[7][8][9][10][6], хотя, хотелось бы заметить, что впервые этот метод был открыт Lai and Massey [23]. Другие интересные подходы к решению проблемы атак нахождения прообраза также появлялись в [11][12][13][14][15][16][17][18][19] [20]

Новые методы

Новые методы, описанные в данной работе, которые не зависят от некой конкретной атаки или определенных хеш-функций – следующие:

- Вероятностная исходная структура, в сравнении с детерминистической исходной структурой, кажется более полезной в плане значительного снижения сложности крипто атаки, во-первых. Чтобы понизить временную сложность атаки MITM , атакующим обычно нужно найти больше нейтральных слов. Это обычно снижает количество шагов в поиске уязвимостей, в связи с тем, что, чем большим количеством нейтральных слов они располагают, тем быстрее разрушается сетевой нейтралитет, и меньше шагов потратится на независимые фрагменты, исходный код, и частичные совпадения. Следовательно, существует определенная зависимость между объемом нейтральных слов (ключей) и трудозатратами для крипто атаки. В данной работе, используя как пример хеш-функцию MD4 (в 3-ей главе), мы покажем как можно использовать большее кол-во нейтральных слов и в то же время поддерживать большой объем исходных данных , за счет перевода исходной структуры в вероятностную. Подобная методика уже использовалась в [10], однако там она использовалась в целях аппроксимации исходной структуры и проблема крипто атак не уменьшилась, ибо возможности для работы с частичными совпадениями были ограничены количеством бит.

- Включение многоцелевых сценариев в структуре MITM, повышающих скорость атак нахождения прообраза. Данная структура является основой для нескольких теоретически интересных результатов на устойчивость прообразов различных хеш-функций, в основном, - с наиболее высокой сложностью поиска. Причина этого в том, что при использовании всех возможностей этой структуры, точки совпадения с фазой "MITM" могут быть где угодно в расчете функции сжатия, и не обязательно в начале или в конце. Хотя это и дает взломщику больше свободы в проектировании атаки на функцию сжатия, это всегда приводит к значительному снижению эффективности в момент, когда функция сжатия преобразуется в атаку на хеш-функцию. Таким образом, взломщику по существу приходится выбирать между более ограниченной в возможностях (и потенциально более затратной по времени) стратегии атаки на функцию сжатия, позволяющей лучше контролировать цепочки значений и в свою очередь допускающей применение эффективных методов преобразования, основанных на графике или «структуре дерева», либо в полной мере использовать свободу, которую обеспечивает последними версиями MITM в проведении атаки на функцию сжатия за счет малоэффективных методов преобразования. В части 2.2 мы описываем способы взять и скомбинировать лучшее из обоих методик. Далее в этой работе будут рассмотрены результаты самых известных атак на функции вида Tiger и SHA-2. -Простая техника предварительного расчета, позволяющая находить новые прообразы

с помощью одного псевдо-прообраза. В разделе 3 читайте о применении данного метода для функции MD4, где этот подход показательно опережает по всем пунктам (время / память) показатели на кривой Хэлмана[21] , которые в целом были признаны оптимальными.

Новые результаты в перспективе

В дополнение к концептуальным идеям, которые вносят большой вклад в арсенал крипто аналитики в целом, мы также рассматриваем эти идеи в cравнении с конкретными результатами настоящего времени. Фактически, нам удастся улучшить самый известный прообраз атаки на ряд практически используемых хэш-функций. Таблица лучших работ по данной тематике и сравнение с нашими основными результатами можно найти в[22].

Tiger

Tiger (Тигр): Одна из немногих проверенных временем и устойчивых к взлому хеш-функций, разработанная Андерсоном и Бихамом [5] в 1996 г. Tiger иногда рекомендуется как альтернатива функциям подобным MD4, таким как SHA-1, в особенности потому, что она быстрее, чем SHA-1 при использовании на общеизвестных платформах. Tiger используется на практике например в децентрализованных файловых системах, или в многочисленных протоколах обмена файлами и приложениями, часто в «дереве Меркла», также известном как TigerTree [23]

Хэш Атака Временная сложность Память Источник Замечания
MD4
псевдо-прообраз
[24]
Раздел 3
Раздел 3
последовательный отступ
без отступа
последовательный отступ
прообраз
[24]
Раздел 3
Раздел 3
-
сообщение перед отступомблоков
сообщение перед отступомблоков,procomp.
второй прообраз
[20]
[25]
[24]
Раздел 3
Раздел 3
сообщение перед отступом около блоков
сообщение перед отступом около блоков
-
сообщение перед отступомблоков
сообщение перед отступомблоков,procomp.
Tiger
прообраз
negl.
[21]
[26]
[27]
[28]
Раздел 4
13 шагов
16 шагов, один блок
17 шагов
23 шага
полные 24 шага
SHA-256
прообраз
[26]
[7]
Приложение А
[7]
24 из 64 шагов, один блок
42 шага
42 шага
43 шага
SHA-512
прообраз
[26]
[7]
Приложение А
[7]
24 из 80 шагов, один блок
42 шага
42 шага
46 шагов

Лучшая коллизионная атака на Tiger состоит из 19 раундов [29][прим. 1] На сегодняшний день лучшей атакой нахождения прообраза на Tiger считается хеш-функция, разработанная Ванг и Сасаки [30]. Работая независимо от нас, они применили MITM атаку нахождения прообраза к Tiger, урезанной до 2 шагов, с временной сложностью выше, чем у нас при требуемых ячеек памяти. Наша новая атака улучшена по многим параметрам, и похоже, что она первая из криптоаналитических быстрых атак на полную версию функции Tiger. Наша атака на функции полного цикла из 24-х раундов имеет временную сложность (атака функции сжатия ) и объемом оперативной памяти всего порядка . Эти результаты получены с использованием многоцелевого метода, описанного выше, и технологии, используемые для конструирования первоначальной структуры на стадии предварительных вычислений.

MD4

Даже при условии, что уже существуют очень эффективные методы поиска коллизий для MD4 [31][32], это хеш-функция еще находится в практическом использовании. Примеры включают в себя пароли обработки для Windows NT, одноразовых S / Key-паролей систем [22], проверка целостности в популярных протоколах, например, rsync[33]или протоколы обмена файлами[34] и приложениями. Временная сложность атак на самые известные функции сжатия снижена с до . Проделывая предварительных вычислений с использованием техники больших вычислений, которые упомянули выше, и хранения, сложность для нахождения каких-либо новых прообразов (будь то для той же или другой цели хэш-функции) теперь могут быть меньше, чем .

SHA-2

Хеш-функции, принадлежащие к семейству SHA-2, возможно, являются наиболее интересными криптоаналитическими мишенями не только из-за их применимости к любой сфере, где требуется использование хеш-функций (а их бесчисленное множество), но также и потому, что они используются в качестве примеров для сравнения с кандидатами, проходящего в настоящее время конкурса на создание SHA-3. Мы используем функции класса SHA-2 как пример, иллюстрирующий эффект использования многоцелевого сценария. Также таким образом мы совершенствуем наиболее широко известные атаки нахождения прообраза в применении к усеченным SHA-256 и SHA-512. Они описаны в [22] [см. Приложение 1].

Краткое описание

Данная статья построена следующим образом. Раздел 2 описывает атаку нахождения прообраза «встречи посередине» (MITM), четыре различных метода преобразования псевдо прообраза в прообраз (включая 2 новых метода), а также кратко резюмирует приемы расширенных атак нахождения прообраза на базе MITM. Мы применяем эти новые приемы к хеш-функциям MD4 и Tiger в Разделах 3 и 4 соответственно. Раздел 5 заключительный.

Атака нахождения прообраза методом «встречи посередине»(MITM)

MITM-метод.png

Рис. 1. MITM атака нахождения псевдопрообраза против хеш-функции Дейвиса-Мейера.

Основную идею атаки нахождения прообраза, изображенной на рис.1, можно толковать следующим образом:

1. Разбить функцию сжатия на 2 части, с тем чтобы значения одной части не зависели от одного слова в сообщении , а значения в другой части не зависели от другого слова в сообщении (). Мы следуем этим условиям и называем такие слова нейтральными по отношению к первой и второй части функции соответственно.

2. Установить все остальные значения кроме , как случайные числа и присвоить случайные значения цепочке записей в точке разделения.

3. Начать вычисление в обоих направлениях от точки разделения чтобы сформировалось два списка и перечисляющие все возможные значения и и содержащие вычисленные значения цепочек наборов в точках совпадения.

4. Сравнить два списка, чтобы найти частичные совпадения (совпадения по одному из нескольких чисел вместо совпадения полной цепочки) в точке совпадения.

5. Повторять 3 предыдущих шага с другими начальными конфигурациями (значение для точки разрыва и другими словами в сообщении), пока не будет найдено полное соответствие.

6. Иметь в виду, что это соответствие создает псевдо-прообраз, тогда как во время атаки определяется исходное значение. Однако, можно преобразовать псевдо-прообраз в собственно прообраз, используя обычные приемы, описанные в книге 33 [35] Однако, можно вычислить много псевдо-прообразов, а затем найти сообщение, которое связывает IV с одной из цепочек наборов псевдо-прообразов, как показано на рис.2.

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

Замечание по битам для частичного совпадения. При условии, что мы имеем m бит для частичного совпадения, мы ожидаем получить подходящих кандидатов совпадением в m бит. Однако нам все же нужно проверить, не дает ли какой-то из остальных кандидатов полного совпадения (псевдо-прообраза), проверка займет что-то около (на самом деле, немного меньше, т.к. мы можем сохранять вычисленных кандидатов с совпадениями ниже частичного, и повторно проверять только партию данных с частичным совпадением). Чтобы минимизировать временную сложность, нам требуется , так что частичное совпадение займет чем можно пренебречь.

MITM 2.png

Рис.2 Преобразование псевдо-прообразов к прообразу: круг обозначает состояние, стрелка обозначает блокировку сообщения

Многоцелевой псевдо-прообраз

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

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

Заметим, что данное преобразование необязательно повысит объем оперативной памяти, т.е. она может быть такой же, как и для поиска псевдо-прообраза, поскольку мы последовательно рассчитываем псевдо-прообразов.

Расширенная проблема трех сумм

Описанное выше преобразование исходит из предположения, что совпадение может быть найдено в течение . Заметим, что в каждой наборе мы имеем потенциальных совпадений (обозначенных как и ), и целей (обозначенных как ), нам надо найти все возможные , , , при том что , и , так что . Мы называем эту проблему Расширенная проблема трех сумм , где стандартная проблема трех сумм определяет, есть ли решение [36]. Текущие результаты исследований [37] показывают, что данная проблема может быть решена за время или немного быстрее. Таким образом применяя данный подход, мы ожидаем, что совпадение будет найдено в течение (для ) вместо ожидаемых .Во всяком случае совпадение произойдет в конечных операциях с прямым поточным шифрованем (“+” у большинства функций семейства MD) при невысокий уровне сжатия. Следовательно, данный метод предполагает совершение “+” операций, чтобы стать хоть сколько нибудь сопоставимым с вычислений с использованием функции сжатия путем подсчета количества“+” в сжатии, при относительно маленьком (например, \le 7\ </math> для MD4 и Tiger, поскольку в сжатии MD4 содержится порядка “+” , то мы просто подсчитаем кол-во операций (“+”, “−”, “×” и обращения к S-блоку - для Tiger).

Универсальный многоцелевой псевдо-прообраз

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


с заданным оптимальным . Чтобы данный метод работал, нам понадобится больше совпадающих бит: бит вместо l (у нас кандидатов на совпадение в обоих направлениях). Требования к памяти из-за этого возрастает до . Здесь мы улучшаем скорость за счет памяти с / (время/память) до / при . И мы имеем полный контроль над балансом скорость/память на всех остальных промежуточных этапах путем использования нужного количества заданных целей, т.е. меньше чем .

Нахождение прообразов методом большого предварительных вычислений

Здесь мы опишем простую технологию преобразования многочисленного класса атак на псевдо-прообраз в атаки на прообраз без какой-либо потери скорости. Данный метод требует изначально большого предварительного вычисления порядка и поэтому его нужно сравнивать с компромиссом времени и памяти, предложенным Хэллманом[38] Это значит, что значения требуемых памяти и времени для отдельно взятой атаки должно быть ниже кривой компромисса, для того, чтобы показатели считались улучшенными по сравнению с универсальной атакой.

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

Четыре различных метода преобразования суммированы табл. 2. Наша цель – проиллюстрировать и сравнить различные подходы и предположения, которые они делают в применении к атакам функции сжатия. С целью упрощения, другие методы преобразования, в той или иной мере схожие с “встречей по середине”(дерево данных [39], альтернативные древовидные и графические структуры [12]) не перечисляются. Как пример, новая атака на функцию сжатия MD4, отвечает только ожиданиям традиционного подхода и метода большого предворительного вычисления, новая атака на функцию сжатия Tiger и SHA-2, отвечают ожиданиям метода GMTPP.

       Таблица 2.png

Таблица 2. Сравнение методов преобразования псевдо-прообразов в прообраз

Введение в некоторые техники метода "встречи посередине"(MITM) для атаки на функции сжатия

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

Исходная структура

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

3MD4 1.png
Рис.3 Исходная структура

Частичное совпадение

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

3MD4 2.png
Рис.4 Частичное совпадение

Оптимизированная атака нахождения прообраза против хэш-функции MD4

Описание хэш функции MD4

MD4 следует традиционному MD-усилению, исходное сообщение дополняется единицами, следующими после множества нулей и 64-ех битной информационной последовательности так, что длина дополненного сообщения становится кратной 512. Затем разделяет дополненные сообщения на блоки по 512 бит и последовательно применяет функцию сжатия. После сжатия на выходе получается хэш. Функция сжатия следует из конструкции Девиса-Мейера и состоит из двух основных частей: разбивка сообщения и шагов функции. Разбивка сообщение делит 512-битный текстовый блок на 16 слов (по 32 бита каждое) и расширяет их до 48 с помощью перестановок, как показано в таблице.

MD4.png

Начиная со входной последовательности, расширенные слова последовательно поступают в каждый шаг функции. Выход последнего шага складывается с входной цепочкой для того, чтобы дать выход функции сжатия. На каждом шаге функция на вход принимает четыре последовательности и обновляет их согласно формуле: для , где и предопределенные константы, - эта перестановка определена в таблице выше, и функции -определенные как в следующей таблице. Мы используем машинный шрифт для обозначения шестнадцатиричных чисел таких как 5А827999, 1 для FFFFFFFF, и 0 для 00000000.

MD4 2.png

Ускоренные атаки на псевдо-прообразы

В этом разделе мы покажем атаку на псевдо-прообраз за . Разделение на блоки(показоно на рис.5): шаги {10, . . . ., 26} для исходной структуры, шаги {40, . . . , 47, 0, . . . , 9} для первой части, шаги {27, . . . , 36} для второй части, шаги {37, 38, 39} для частичного соответствия. Мы выбираем как и как . Начальная структура охватывает 17 шагов от 10-ого до 26-ого, как показано на рис. 2 с a = b =1. Обратите внимание, что каждый реестр и информационное слово, в рамках исходной структуры (кроме ), закрепляются за некоторыми случайными значениями. Концепция пути локальной коллизии была использована в [30][40][24] Однако, ни один из данных путей помощи не используется в нашей атаке нахождения прообраза методом встречи посередине, поскольку мы не можем найти более правильных решений и подходящих слов. В нашей исходной структуре отношение между и выражается через функцию Функция фиксируется, когда фиксируются все остальные реестры/информационные слова.

3MD4 3.png
Рис.5 Разделение на фрагменты для псевдо-прообразов на примере MD4

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

3MD4 4.png

Подробности можно найти в книге Халлера[22].Все необходимые значения указаны на рис.6. Однако, при таких параметрах решений нет, поскольку функция ограниченна по и . Чтобы преодолеть данную проблему, мы предлагаем вероятностную исходную структуру.


Вероятностная исходная структура

Рассмотрим вероятность, если , где – фиксированные константы, и – случайная величина в . Уравнение не всегда справедливо для всех . Однако, если (вес Хэмминга) очень близок к 32, мы можем ожидать высокую вероятность правильности равенства. Вместо установки на входе строго 0 или 1, мы используем некоторые другие значения, которые близки к 0 или 1 (таким образом, мы наиболее близко располагаем два входа функции ), которые позволяют нам найти некоторые решения для исходной последовательности, как показано на Рис.7, где являются переменными, которые будут решены позже. Перечислим уравнения ограничения здесь:

3MD4 5.png
Рис.6 17-ступенчатая исходная структура для MD4
MD4 3.png
Рис.7 17-ступенчатая вероятностная исходная структура для MD4
MD4 4.png

Приведенная выше система уравнений дает нам большой выбор вариантов для и Обратите внимание, что мы использовали две вероятностные аппроксимации в двух местах, то есть, на 13-ом шаге и функция на 20-ом шаге. Каждая происходит с вероятностью и , соответственно (предполагается, что и равномерно распределены). Есть высокая вероятность, что мы найдем , которые максимизируют точность . Мы нашли и , которые дают точность . Решив эту систему уравнений, мы получили , , , и . Чтобы гарантировать, что это работает, как ожидалось, мы верифицировали вероятность используя программу верификации С [41], и эксперимент подтвердил результат.

3-ступенчатое частичное соответствие

Как показано на рис.8, частичное соответствие работает в течение 3 шагов. и может быть непосредственно соответствовать или с помощью косвенного частичного соответствия. Итак, мы имеем 64 бита для частичного совпадения (без использования )

Алгоритм нахождения псевдо-прообраза

1. Расположить все указанные слова сообщения/регистры, как указано на рис.2 выше;

2. Случайным образом присвоить все остальные слова сообщений, кроме ;

3. Вычислить и ;

4. Для всех произвести вычисления от 27 шага до 36, и получить наборы значений (ожидаемый размер );

5. Для всех вычислить назад от шага 9 до шага 0, и получить наборы значений (ожидаемый размер );

6. Сделать прямую связь и добавить цель, продолжить вычисления в обратном порядке до 40 шага, и получим наборы значений (ожидаемый размер );

7. Сделать частичное соответствие с и ( пар слева), затем сопоставить с ( пар слева);

8. Для каждой левой пары остается вычислить правильный , такой, который также соответсвует (у нас есть пары которые полностью соответствуют);

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

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

Атака на прообраз хэш-функции MD4

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

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

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

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

3MD4 6.png
Рис.6 3-ступенчатое частичное соответствие для MD4

Атака на второй прообраз хэш-функции MD4

В отличие от поиска прообразов, мы можем избежать проблем при нахождении второго прообраза, находя псевдо-прообразы для предпоследнего блока и т.д., как это сделано в [24]. Учитывая предварительных вычислений, сложность в этой атаке на второй прообраз будет с затратами по памяти , когда , то есть это работает для всех сообщений с первоначальной длиной перед отступом, не менее двух блоков (1024 бита, по крайней мере 3 блока после отступа). Аналогично это работает за время и памяти без предварительных вычислений. Хотя существует более быстрый второй прообраз атаки [20], атака работает только на очень длинных сообщениях, то есть, по крайней мере блоков. Для сравнения, второй прообраз можно найти в , если данное сообщение является более блоков, согласно расчетам Келси и Шнайера [25]( и для времени и для памяти, если может быть достигнуто ).

Атака на прообраз хэш-функции Tiger

Перед тем, как переходить непосредственно к результатам, дадим несколько обозначений, используемых в этом разделе. Пусть и обозначаются как нечетные байты и другие байты из множества X, соответсвенно. В целом давайте обозначим таким образом, что биты с индексом "s" входят в множество Х, а остальные оставим 0. Определим, что и .

Описание Tiger

Tiger является хэш-функцией на основе хш-функции MD. Входное сообщение последовательно делится на 64-битные блоки, так что длина сообщения становиться кратной 512. Затем она делится на блоки по 512 бит и последовательно подается на функцию сжатия. Функция Сжатия Tiger на вход принимает три последовательности и 8 информационных слов(каждое слово имеет по 64 бита) и на выход выводит обновленные три последовательности. Она состоит из двух частей: разбивкой сообщения и ступенчатая функции. Вначале подается входная последовательность вместе с последним шагом ступенчатой функции, чтобы на выход получить сжатую функцию. которая называется конструкцией Дэвиса-Майера.

Ступенчатая функция

Назовем три входных последовательности слов сжатой функции как А, В и С. Эти три последовательности будут в дальнейшем обновляться:

;

;

;

Так, что результат смещается с А, В, С в С, А, В как показано на рис.9. Здесь +, -, * являются сложением, вычитанием и умножением в поле , соответственно. А две нелинейные нечетные и четные функции выражаются следующим образом:

4Tiger 1.png
Рис.9 Ступенчатая функция на хэш-функции Tiger

где это 4 S-бокса определенные на и обозначает i-ый младший байт из х, подробно можно найти в книге Росса [42].

Разбивка сообщения

512-битный блок сообщений разбивается на 8 слов по 64 бита. Затем с помощью ключа функция хэширования рекурсивно преобразует входные слова в и и т.д. Так, что , где ключ для последующей функции определяется рекурсивно с помощью предыдущих значений. Для примера, мы разберем .

Tiger 1.png

где и обозначает побитовое дополнение к .

Краткое описание атаки

Атака на прообраз методом "встречи посередине" уже примялась на хэш-функцию Tiger, во всяком случае на различных вариациях сокращенных хэш-функциях на 16 и 23 шаге [26], [28], однако не на полную функцию Tiger. Сложность заключается в поиске хороших нейтральных последовательностей, длинных исходных наборах и сложном поиске частичных соответствий. В нашей атаке, мы находим 4-ступенчатую структуру, расширяем ее с помощью частичного соответствия до 5 ступеней и обосновываем выбор нейтрального слова для достижения этого. Во всяком случае, каждое из них обладает сдерживающим воздействием на сообщения/регистры, в связи с очень сложным алгоритмом соответствия для сообщений, использующийся в Tiger. В описании атаки, мы показываем все эти ограничения, и показываем как они могут быть выполнены, используя алгоритм вычисления нескольких слова сразу, то есть используя степени свободы большинства слов и регистров для выполнения этих ограничений, которые обычно заполняются случайным образом в атаках на прообраз методом "встречи посередине".

Предварительные вычисления для исходной структуры

Первоначальная структура не применялась к Tiger, по сколько сообщения ксорились в последовательности, следующая после операций сложения/вычитания. Мы не можем поменять порядок ксора и сложения/вычитания, если цепочка значений находится в определенном диапазоне. Мы можем на вход подать 0, а на выход 1, в качестве примера: и тогда и только тогда, когда . В соответствии с этим замечанием, мы можем взять 4-ступенчатую первоначальную структуру, как показано на рис.10 (а), имеющая три ограничения:

Ограничение 1

Переменные из лежат только только в нечетных байтах, так что фиксировано.

Ограничение 2

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

Ограничение 3

должно равняться единице для тех битов, где переменные из не принадлежат

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

Компенсирование сообщений

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

Tiger 2.png
Рис.10 4-ступенчатая исходная структура и 5-ступенчатая структура частичного соответствия для хэш-функции Tiger
Tiger 3.png
Рис.11 Нейтральные слова с ключом, задающим функцию для Tiger

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

Ограничение 4:

Мы используем самые наименее значимые 23 бита в , потому что эти биты исчезают, когда выполняется (как показано на рис. 11 (а), следовательно, это никак не влияет на и т.д.

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

Ограничение 5:

Два нейтральных слова влияют на некоторые общие слова сообщений: . Нам нужно выбрать из биты из двух нейтральные слова и таким образом, что:

Ограничение 6: и не могут повлиять на какие-либо общие биты любого из слов одновременно, т.е., для .

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

Частичное совпадение и частичное исправление

Прямое частичное совпадение вычисляется в обратном направлении и состоит из 3 действий. Дальше больше, исправляя четные байты слов из первого сообщения (частично исправляя метод) в прямом направлении, Исоб и Шибутани [26]способны достичь 4-ого шага, и 5-ого шага, как показали Ванг и Сасаки [28]. В дополнение к 4-ступеньчатой исходной структуре, мы в дальнейшем учитываем дополнительные условия, применяемые к словам в сообщении, в целях достижения 5-ого шага частичного соответствия, как показано на рис. 10 (с), они охватывают со 2-ого по 6-ой шаг.

Ограничение 7: Частичная информация, представленная ниже на рис. 10 (с), вычисленная из должна охватывать все четные байты, так что мы можем вычислить четную функцию в 3-ем действии.

Ограничение 8:

должна быть связана только с , так что мы можем вычислить нечетную функцию 2-ым действием независимо от .

Чтобы просуммировать, мы должны использовать как один фрагмент, как другой фрагмент, предварительно вычислив исходную структуру используя (раздел 4.2); и частичное соответствие действий для . Таким образом, алгоритм Tiger охватывает все 24 действия.

Описание атак и сложности анализа

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

Выполнение всех ограничений

Есть ограничения при выполнении (т. е. ограничения 2, 4 и 8 байтов), мы выбираем нейтральный биты из , где . Аналогично, есть ограничение на выполнение , мы ограничиваем нейтральный биты из байтов 3, 5, 7 - , т. е. с (56 бит зарезервирован для заполнения). В связи с тем, что сложение/вычитание будет распространяться только в сторону старшего разряда, наименее значащих битов из что может повлиять на , так как 43 , 62 (вдвое ), 24, и 24, соответственно. Однако, имеет очень низкий шанс (близок к 0) воздействия вплоть до 43 бита из , 62 бита из , бита 24 из , и мы будем фильтровать кандидатов так, чтобы влияние на ограничивалось до 23 битов. Следовательно, ограничение 6 может быть выполнено. Чтобы выполнить ограничение 5, мы приравняем значения (установив ), и . Мы оставляем ограничение 3 для PIS установки, и ограничение 7 для частичного соответствия, которые должны быть проработаны позже.

Предварительно вычисленная исходная структура

Для работы предварительно вычисляемой исходной структуры, мы должны заранее составить несколько сообщений из слов. Кроме того мы по-прежнему и должны проявить внимание к заполнению. Мы устанавливаем , т. е. длина из исходного сообщения в последнем блоке составляет 447 (7 × 64 − 1). Следовательно, мы должны установить . Обратите внимание, что от добавления блоков будет зависеть длина кратная , которая не эффективна для 9 младших разрядов из . Для уменьшения влияния на , мы дополнительно установим , так что влиять будет только . Обратите внимание, что PIS может состоять из оценок ключевого планирования (оставив ограничение на лишь вероятным). Это ничтожно мало, так как мы можем повторно использовать PIS не менее раз, но это мы обсудим позже.

Поиск хороших значений – используя, обратный порядок действий

Мы используем биты для вычисления хороших значений в обратном направлении. Ограничение 2 дополнительно ограничивает нас при выборе значений из и кратных 9 (кратность = 9 для третьего прохода). Следовательно, у нас есть хороших значений. Наконец, мы отфильтровали значения, которые отвечают ограничению 6. Эксперименты показывают, что остальные хорошие значения равны . Примечание: хорошие значения должны быть вычислены в соответствии с ограничениями PIS, мы используем методы модификации сообщений, чтобы ограничения PIS были выполнены, и чтобы получить хороших значений менее чем за ключевых оценок планирования. Подробности можно найти в [41].

Поиск хороших значений - используя, прямой порядок действий

Мы используем биты для вычисления хороших значений в обратном направлении. Чтобы ограничения 3 были выполнены, нужно фильтровать значения, таким образом, чтобы получить 1 для , как на рис.3 (б), это уменьшает количество значений на . Следует отметить, что эта конструкция может повторно использоваться для различных параметров (по крайней мере ) , изменяя даже байты, которые мы можем свободно поставить в самом начале MITM атаки на прообраз. Таким образом, временная сложность для этой части также незначительна.

Вероятностное частичное совпадение

Частичное совпадение соответствует с обеих сторон, поэтому мы можем вычислить в прямом направлении без каких-либо проблем. Однако, в обратном направлении, мы знаем только информацию байтов 0, 1, 2, 4, 6 для (красный), при вычислении . Отметим, что (кратность = 5 для первого прохода), где и нам известны. Мы перепишем формулу так: , где . Мы можем вычислить байты 0, 1, 2 , но нам пока еще нужны байты 4, 6, так как они обладают информацией необходимой для . Обратите внимание, что , где обозначим при заимствование бита 31, когда выполняется "/ 5" , и обозначим при выполнение "+" для бита 31. Мы имеем дело с при вычислении всех возможных вариантов, и считаем , которое приводит к вероятности для , что верно. Это предоставляет нам пример для байта 4, и мы можем поступить с 6 байтом аналогично. Результаты процесса в 25 раз больше вычислений для частичного совпадения, вместе с вероятностью . Однако, нам необходимо повторить действия и '-' на 3 шаге, так что важно, чтобы повторение было эквивалентно менее ) сжатия вычислений на значение.

Сложность нахождения (второго) прообраза

Следуя структуре атаки MITM на прообраз, атаки на псевдо-прообраз работает следующим образом:

1. Случайным образом выбрать , , .

2. Вычислить предварительно вычисляемую первоначальную структуру.

3. Вычислить значения в прямых и обратных направлениях.

4. Повторите для значений из , используя перебор всех значений в байте 4 и 6 (этот шаг - сделает временную сложность для первых трех шагов незначительной):

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

(б) Выполняем вероятностное частичное совпадение. Если будет обнаружена полная совместимость с , далее повторно проверить, если “предполагать”, что это верно.

5. Повторять шаги 1-4 до тех пор, пока не будет найден псевдо-прообраз.

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

Заключение

В заключение мы приводим результаты и некоторые открытые проблемы, которые являются независимыми в частности, хэш-функции. В данной работе мы расширили рамки вокруг темы “атаки методом встречи посередине”, которая в настоящее время была разработана сообществом с рядом основных подходов. Мы проиллюстрировали эти расширения с улучшенными атаками на прообразы на различных проверенных временем хэш-функциях, по-видимому, наиболее интересный пример бы представлен в первой крипто-аналитической атаке на хэш-функцию full Tiger. Другие примеры включают в себя различные улучшенные атаки на прообразы хэш-функций MD4 и SHA-2.

В качестве одной из основных идей была представлена следующая информация. Под структурой “встречи по седеине”(MITM) , мы представили новые методы, позволяющие преобразовывать псевдо-прообраз в прообраз быстрее, чем общепринятым методом, т. е. универсальный мульти-целевой псевдо прообраз и простая предварительно вычисленная техника. Интересно было посмотреть алгоритм решения “Проблема трех сумм” быстрее, чем на размер набора из существует, так, что MTPP может быть действительным для любой l. С другой стороны, мы обнаружили псевдо-прообраз для алгоритмов MD4 в , интересно посмотреть, новые методы преобразования или другие неизвестные приемы при преобразовании псевдо-прообраза для прообразов алгоритмов MD4. Мы также ожидаем, что методы, изложенные в этой работе, улучшат существующие прообразы атак на хорошо изученные функции хеширования, такие как MD5 и SHA-1, HAVAL, и другие. Хорошей целью является узко-изученный алгоритм SHA-3.

Благодарности

Мы хотели бы поблагодарить Казумаро Аоки, Гетанг Лоурента, Юу Сасаки, Кюоджи Шибутани, Лай Ванга, и анонимных обозревателей из Eurocrypt 2010 и Asiacrypt 2010 за интересные дискуссии. Часть этой работы была написана, в то время как Кюоджи Шибутани работал в “Graz University of Technology” вместе с Казумаор Аоки, который приехал ему помочь. Работа над этими материалами частично поддерживалась Сингапурским Национальным исследовательским Фондом в рамках исследовательского гранта NRF-CRP2-2007-03, Сингапурским Министерством образования в рамках исследовательского гранта T206B2204, программой IAP Р6/26 BCRYPT Бельгийского государства (Министерство Науки Бельгии), и Европейской комиссией в рамках контракта ICT-2007-216646 (ECRYPT II).

Приложение 1. Улучшенная атака на прообраз атаки SHA-2

В работе [7] Аоки и др. представлен прообраз укороченной 42-ступенчатой SHA-2. Отметим, что соответствующий пункт (вместе с выбор нейтральных слов) может быть перемещен в конец функции сжатия, как это было сделано для атаки на . Количество нейтральных битов в обоих случаях колеблется около (для SHA-512) и количество битов для частичного совпадения 32 (64 для ), которых является более чем достаточно. Применяя метод MTPP, мы находим прообразы за (заменой и , по сравнению с для 42-ступенчатой ​​ и (заменой и , по сравнению с для 42-ступенчатой . Требования к памяти одинаковые.

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


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

  1. Nanyang Technological University, Singapore,E-mail:ntu.guo@gmail.com
  2. Katholieke Universiteit Leuven, ESAT/COSIC, and IBBT, Belgium

Примечание

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

Литература

  1. Christophe De Canni`ere and Christian Rechberger. Finding SHA-1 Characteristics: General Results and Applications. In Xuejia Lai and Kefei Chen, editors, ASIACRYPT, volume 4284 of LNCS, pages 1–20. Springer, 2006.
  2. 2,0 2,1 Marc Stevens, Arjen K. Lenstra, and Benne de Weger. Chosen-Prefix Collisions for MD5 and Colliding X.509 Certificates for Different Identities. In Moni Naor, editor, EUROCRYPT, volume 4515 of LNCS, pages 1–22. Springer, 2007.
  3. . Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu. Finding Collisions in the Full SHA-1. In Victor Shoup, editor, CRYPTO, volume 3621 of LNCS, pages 17–36. Springer, 2005.
  4. Xiaoyun Wang and Hongbo Yu. How to Break MD5 and Other Hash Functions. In Ronald Cramer, editor, EUROCRYPT, volume 3494 of LNCS, pages 19–35. Springer, 2005.
  5. Ga¨etan Leurent. Message Freedom in MD4 and MD5 Collisions: Application to APOP. In Alex Biryukov, editor,FSE, volume 4593 of LNCS, pages 309–328. Springer, 2007.
  6. 6,0 6,1 Yu Sasaki and Kazumaro Aoki. Finding Preimages in Full MD5 Faster than Exhaustive Search. In Antoine Joux,editor, EUROCRYPT, volume 5479 of LNCS, pages 134–152. Springer, 2009.
  7. 7,0 7,1 7,2 7,3 7,4 7,5 Kazumaro Aoki, Jian Guo, Krysitan Matusiewicz, Yu Sasaki, and Lei Wang. Preimages for Step-Reduced SHA-2. In Mitsuru Matsui, editor, ASIACRYPT, volume 5912 of LNCS, pages 578–597. Springer, 2009
  8. Kazumaro Aoki and Yu Sasaki. Meet-in-the-Middle Preimage Attacks Against Reduced SHA-0 and SHA-1. In Shai Halevi, editor, CRYPTO, LNCS, pages 70–89. Springer, 2009.
  9. Kazumaro Aoki and Yu Sasaki. Preimage Attacks on One-Block MD4, 63-Step MD5 and More. In Roberto Avanzi, Liam Keliher, and Francesco Sica, editors, SAC, volume 5381 of LNCS, pages 103–119. Springer, 2009.
  10. 10,0 10,1 Yu Sasaki and Kazumaro Aoki. Preimage attacks on 3, 4, and 5-pass HAVAL. In Josef Pawel Pieprzyk, editor, ASIACRYPT, volume 5350 of LNCS, pages 253–271. Springer, 2008.
  11. Eli Biham. New Techniques for Cryptanalysis of Hash Functions and Improved Attacks on Snefru. In Kaisa Nyberg, editor, FSE, volume 5086 of LNCS, pages 444–461. Springer, 2008.
  12. 12,0 12,1 Christophe De Canni`ere and Christian Rechberger. Preimages for Reduced SHA-0 and SHA-1. In David Wagner, editor, CRYPTO, volume 5157 of LNCS, pages 179–202. Springer, 2008.
  13. Dmitry Khovratovich, Ivica Nikolic, and Ralf-Philipp Weinmann. Meet-in-the-Middle Attacks on SHA-3 Candidates. In Orr Dunkelman, editor, FSE, volume 5665 of LNCS, pages 228–245. Springer, 2009.
  14. Lars R. Knudsen, John Erik Mathiassen, Fr´ed´eric Muller, and Søren S. Thomsen. Cryptanalysis of MD2. Journal of Cryptology, 23(1):72–90, 2010.
  15. Mario Lamberger, Norbert Pramstaller, Christian Rechberger, and Vincent Rijmen. Second Preimages for SMASH. In Masayuki Abe, editor, CT-RSA, volume 4377 of Lecture Notes in Computer Science, pages 101–111. Springer, 2007
  16. Mario Lamberger, Norbert Pramstaller, Christian Rechberger, and Vincent Rijmen. Analysis of the Hash Function Design Strategy Called SMASH. IEEE Transactions on Information Theory, 54(8):3647–3655, 2008.
  17. Florian Mendel, Norbert Pramstaller, and Christian Rechberger. A (Second) Preimage Attack on the GOST Hash Function. In Kaisa Nyberg, editor, FSE, volume 5086 of LNCS, pages 224–234. Springer, 2008.
  18. Florian Mendel, Norbert Pramstaller, Christian Rechberger, Marcin Kontak, and Janusz Szmidt. Cryptanalysis of the GOST Hash Function. In David Wagner, editor, CRYPTO, volume 5157 of LNCS, pages 162–178. Springer, 2008
  19. Fr´ed´eric Muller. The MD2 Hash Function Is Not One-Way. In Pil Joong Lee, editor, ASIACRYPT, volume 3329 of LNCS, pages 214–229. Springer, 2004.
  20. 20,0 20,1 20,2 Hongbo Yu, Gaoli Wang, Guoyan Zhang, and Xiaoyun Wang. The Second-Preimage Attack on MD4. In Yvo Desmedt, Huaxiong Wang, Yi Mu, and Yongqing Li, editors, CANS, volume 3810 of LNCS, pages 1–12. Springer, 2005.
  21. 21,0 21,1 Sebastiaan Indesteege and Bart Preneel. Preimages for Reduced-Round Tiger. In Stefan Lucks, Ahmad-Reza Sadeghi, and Christopher Wolf, editors, WEWoRC, volume 4945 of Lecture Notes in Computer Science, pages 90–99. Springer, 2007.
  22. 22,0 22,1 22,2 22,3 N. Haller. RFC1760 - The S/KEY One-Time Password System, 1995.
  23. TigerTree Hash Code. http://tigertree.sourceforge.net/.
  24. 24,0 24,1 24,2 24,3 24,4 24,5 Ga¨etan Leurent. MD4 is Not One-Way. In Kaisa Nyberg, editor, FSE, volume 5086 of LNCS, pages 412–428. Springer, 2008.
  25. 25,0 25,1 John Kelsey and Bruce Schneier. Second Preimage on n-bit hash functions for much less than 2n work. In Ronald Cramer, editor, EUROCRYPT, volume 3494 of LNCS. Springer, 2005.
  26. 26,0 26,1 26,2 26,3 26,4 Takanori Isobe and Kyoji Shibutani. Preimage Attacks on Reduced Tiger and SHA-2. In Orr Dunkelman, editor, FSE, volume 5665 of LNCS, pages 139–155. Springer, 2009.
  27. Florian Mendel. Two Passes of Tiger Are Not One-Way. In Bart Preneel, editor, AFRICACRYPT, volume 5580 Takanori Isobe and Kyoji Shibutani. Preimage Attacks on Reduced Tiger and SHA-2. In Orr Dunkelman, editor, FSE, volume 5665 of LNCS, pages 139–155. Springer, 2009.
    of LNCS, pages 29–40. Springer, 2009.
  28. 28,0 28,1 28,2 Lei Wang and Yu Sasaki. Finding Preimages of Tiger Up to 23 Steps. In Seokihie Hong and Tetsu Iwata, editors, FSE, volume 6147 of LNCS, pages 116–133. Springer, 2010.
  29. Florian Mendel, Bart Preneel, Vincent Rijmen, Hirotaka Yoshida, and Dai Watanabe. Update on Tiger. In Rana Barua and Tanja Lange, editors, INDOCRYPT, volume 4329 of LNCS, pages 63–79. Springer, 2006.
  30. 30,0 30,1 Serge Vaudenay. On the Need for Multipermutations: Cryptanalysis of MD4 and SAFER. In Bart Preneel, editor, FSE, volume 1008 of LNCS, pages 286–297. Springer, 1994.
  31. Xiaoyun Wang, Xuejia Lai, Dengguo Feng, Hui Chen, and Xiuyuan Yu. Cryptanalysis of the Hash Functions MD4 and RIPEMD. In Ronald Cramer, editor, EUROCRYPT, volume 3494 of LNCS, pages 1–18. Springer, 2005.
  32. Yusuke Naito, Yu Sasaki, Noboru Kunihiro, and Kazuo Ohta. Improved Collision Attack on MD4 with Probability Almost 1. In Dongho Won and Seungjoo Kim, editors, ICISC, volume 3935 of LNCS, pages 129–145. Springer, 2005.
  33. Rsync. http://rsync.samba.org/
  34. Multisource File Transfer Protocol. http://en.wikipedia.org/wiki/Multisource_File_Transfer_Protocol
  35. Florian Mendel and Vincent Rijmen. Weaknesses in the HAS-V Compression Function. In Kil-Hyun Nam and Gwangsoo Rhee, editors, ICISC, volume 4817 of LNCS, pages 335–345. Springer, 2007.
  36. 3-Sum Problem. http://en.wikipedia.org/wiki/3SUM
  37. Ilya Baran, Erik D. Demaine, and Mihai Patrascu. Subquadratic algorithms for 3SUM. Algorithmica, 50(4):584–596, 2008.
  38. Martin E. Hellman. A Cryptanalytic Time - Memory Trade-Off. IEEE Transactions on Information Theory, 26(4):401–406, 1980.
  39. Florian Mendel and Vincent Rijmen. Cryptanalysis of the Tiger Hash Function. In Kaoru Kurosawa, editor, ASIACRYPT, volume 4833 of LNCS, pages 536–550. Springer, 2007.
  40. Hans Dobbertin. The First Two Rounds of MD4 are Not One-Way. In Serge Vaudenay, editor, FSE, volume 1372 of LNCS, pages 284–292. Springer, 1998.
  41. 41,0 41,1 Jian Guo. The C Program Verifies the Preimage Attacks against Tiger and MD4, 2010. Available: http://www.jguo.org/docs/Tiger-MD4-AC10.zip.
  42. Ross J. Anderson and Eli Biham. TIGER: A Fast New Hash Function. In Dieter Gollmann, editor, FSE, volume 1039 of LNCS, pages 89–97. Springer, 1996.