Поиск MD 5 коллизий? семечки для ноутбука!

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

Одним из наиболее важных событий в криптографии за последние несколько лет стало обнаружение в августе 2004 года китайскими специалистами коллизий для набора хэш-функций (MD4, MD5, HAVAL-128, RIPEMD) [1]. Авторы сохранили свой алгоритм в тайне. В октябре 2004 года австралийская команда Хокиса (Hawkes) попыталась реконструировать эти методы в своей весьма солидной работе [3]. Самый важный секрет «китайского способа» им раскрыть не удалось, однако они преуспели в составлении схемы условий, которая подходила к опубликованным коллизиям. Тем не менее, сложность вычислений по этой схеме получилась намного большей по сравнению с результатом, о котором шла речь в статье [1].

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

Мы нашли способ генерации, который позволяет найти первый блок коллизии за две минуты с помощью обычного ноутбука (платформа PC), то есть в 1000- 2000 раз быстрее, чем при использовании метода, предложенного китайской командой. Достижение такого результата потребовало у коллег из Китая около часа работы суперкомпьютера IBM P690. C другой стороны, китайской команде удалось вычислять второй блок коллизии в 2-80 раз быстрее. Следует отметить, что наш метод и метод китайской команды, скорее всего, имеют отличия в обеих фазах вычислений. В общем случае наш способ быстрее в 3-6 раз. Если уточнить, то нахождение первой (полной) коллизии требует около восьми часов работы PC-ноутбука (Intel Pentium 1,6 GHz). Обратите внимание: наш способ применим для любого вектора инициализации. Как указывается в работах [4,5,6], он может быть применен для подделки сигнатур программных пакетов и цифровых сертификатов.

Таким образом, мы доказали, что коллизии MD5 можно найти с помощью обычного домашнего компьютера. Это должно стать предупреждением для всех, использующих алгоритм MD5. В приложении мы приводим новые примеры коллизий для стандартного и выбранного инициализационного вектора. Напомним, что в работе [1] не был раскрыт алгоритм, и не было дано объяснение способа нахождения коллизий – были приведены только краткие и сухие данные. Давайте их вспомним. Совпадающая пара сообщений (M,N) и (M', N') состоят из двух блоков. Первые блоки отличаются только в заранее определенном константном векторе C1(M' = M + C1). Вторые блоки также отличаются только заранее определенном константным вектором C2 = -C1 mod 232 (N' = N + C2), тогда как MD5(M, N) = MD5(M', N').

Команда Вонга утверждает, что для нахождения блока M суперкомпьютеру IBM P690 требуется один час. На поиск N требуется всего от 15 секунд до 5 минут. В первой версии статьи [1] были приведены две пары сообщений с коллизией. Избранное авторами значение инициализационного вектора (IV), однако, не было тем, которое используется в алгоритме MD5 – порядок битов был обратным (little-endian vs. big-endian). В исправленной версии упомянутой статьи приводится две пары сообщений с коллизией для MD5, на этот раз с правильным IV. Было также сделано примечание, что их методика действенна при любом инициализационном значении IV.

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

В октябре 2003 года была опубликована работа Хокиса [3]. Автор предпринял попытку раскрыть суть «китайского способа», основываясь на данных, которые были опубликованы в статье [1]. В данной работе исследовались внутренние различия и условия упорядочивания сообщений для создания коллизий с использованием «китайского способа». Это была первая попытка тщательного анализа «китайского способа» и первая же попытка раскрыть его суть. Основываясь на одной паре сообщений (с корректным IV), авторы получили схему, которая подходит к опубликованной коллизии. Возможно, что в основе получения коллизии лежала именно эта схема. Однако авторы не пожелали объяснить, как им удалось получить эту схему. Авторы также показали, какие условия должны соблюдаться для одного сообщения из пары с коллизией для того, чтобы такая схема сработала. Список условий получился весьма длинным. Первый набор условий (так называемые ft- и Tt-условия) относятся к первому блоку, проходящему 64 раунда MD5. Если условия были соблюдены в первых 16 раундах (это более двухсот условий) благодаря удачному подбору M-блока, в оставшихся раундах остается выполнить 39 ft-условий и "3.2" Tt-условий. Эти условия могут быть найдены только на вероятностной основе. Таким образом, нам требуется сгенерировать около 242.2 M-сообщений для нахождения одного, которое будет соответствовать всем ft- and Tt-условиям раундов 17 – 64. Для генерирования сообщений необходимо также выполнить ft- и Tt-условия для второго блока N, что производится подобным образом. Общая сложность теперь будет равна 243. Хокис и соавторы полагали, что такая сложность вычислений чересчур велика для нахождения коллизии не более чем за час. Основываясь на данном наблюдении, они заключили, что Ванг и его коллеги должны были использовать какой-то иной подход. Это и есть ключевой момент истории.

Свою работу мы начали, отталкиваясь от результатов [3]. Мы нашли схему на основе аддитивных разностей (арифметическая разность по модулю 232) и бинарных разностей (xor, модуль 2), так же, как это было сделано в работе [3]. Кроме того, мы исследовали другую коллидирующую пару с коллизией (с неправильным IV). Мы установили, что дифференциальная схема подходит для обеих пар с коллизией. Иных данных у нас не было. В ходе дальнейшей работы выяснилось, что некоторые ft- и Tt-условия могут быть найдены способами, не описанными Хокисом. Теоретически это могло сократить сложность последующих вычислений. С другой стороны, это могло усложнить программу нахождения коллизий и увеличить ее требования к объему доступной памяти. Как бы то ни было, мы избрали иной путь. Анализ ft- и Tt-условий показал, что реальная сложность нахождения коллизий может быть меньшей, чем в теоретической модели. По мере продвижения работы мы нашли способ очень быстрой генерации первых блоков сообщений с коллизией. Используя обычный PC-ноутбук мы находили первый блок сообщения за две минуты, в то время, как ранее для этого требовался час работы суперкомпьютера [1]. Поскольку наш исследовательский проект был кратковременным, мы не вели работы по оптимизации времени поиска второго блока, как мы это сделали для первого блока. Даже в такой конфигурации мы достигли сложности намного меньшей, чем 242 (в соответствии с работой [3]). Это подтверждает тот факт, что мы смогли обнаружить коллизию за 8 часов работы с ноутбуком. В соответствии с [1], поиск второго блока должен быть в 12-240 раз быстрее, чем поиск первого блока. Это позволяет получить коллизию за 2 минуты вместо 8 часов на ноутбуке.

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

Все результаты были получены с помощью вполне обычного ноутбука (Acer Travelmate 450 LMi, Intel Pentium 1.6 GHz). Они таковы: за 8 часов были найдены 331 коллизия для первого блока и получена одна полная коллизия. Поскольку китайской команде для нахождения коллизии первого блока понадобился час, поиск 331 коллизии должен занимать 331 час, то есть в 40 раз больше, чем потребовалось нам. Сравнивать производительность ноутбука и суперкомпьютера из-за их различной архитектуры довольно сложно. Мы исходили из того, что IBM P690 быстрее ноутбука примерно в 25-50 раз (оценка предоставлена Ондреем Микле (Ondrej Mikle)). В итоге мы получаем, что наш метод поиска коллизий для первого блока в 1000-2000 раз быстрее способа, предложенного в [1]. С другой стороны, поиск коллизий для второго блока происходит в 2-80 раз медленней. Если сравнивать общее время поиска полной коллизии, понадобившееся китайской команде (1 - 1.08 часа) с нашим результатом, полученным на машине, которая была в 25-50 раз медленнее(8 часов), то получается, что предложенный нами способ в 3-6 раз быстрее. Все эти сравнения предназначены исключительно для иллюстрации рассказа, и автор может ошибаться в точности приведенных значений, в полной мере гарантируя только точность оценки затраченного времени.

Таким образом, можно сделать следующие выводы:
- MD5 коллизии могут быть найдены с помощью обычного ноутбука;
- методы, предлагаемые нами и командой из Китая [1], различаются как по достигнутым значениям затраченного времени, так и, вероятно, по применяемым в обеих фазах вычислений подходам;
- в общем случае наш метод быстрее;
- данный метод работает при любом избранном IV.

примечание

В ходе эксперимента, проведенного Ондрием Покорным (Ond?ej Pokornэ) на его домашнем компьютере (Intel Pentium 1GHz), он получил 14 коллизий за 58 часов 32 минуты. Данный результат (1 коллизия за 4 часа 11 минут) лучше полученного на ноутбуке автора.

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

сайт

заключение

В данной статье показано, что в настоящее время для нахождения MD5 коллизии достаточно обычного PC-ноутбука. Предложенный метод пригоден для любого IV и быстрее исходного «китайского способа». Следует ожидать, что после публикации подробностей «китайского способа» общее время на нахождение полной коллизии может быть сокращено до двух минут при использовании PC-ноутбука.

источники

[1] Xiaoyun Wang, Dengguo Feng , Xuejia Lai, Hongbo Yu: Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD, rump session, CRYPTO 2004, Cryptology ePrint Archive, Report 2004/199, first version (August 16, 2004), second version (August 17, 2004),
сайт
[2] Ronald Rivest: The MD5 Message Digest Algorithm, RFC1321, April 1992,сайт
[3] Philip Hawkes, Michael Paddon, Gregory G. Rose: Musings on the Wang et al. MD5 Collision, Cryptology ePrint Archive, Report 2004/264, 13 October 2004,сайт
[4] Ondrej Mikle: Practical Attacks on Digital Signatures Using MD5 Message Digest, Cryptology ePrint Archive, Report 2004/356,
сайт2 December 2004.
[5] Dan Kaminsky: MD5 To Be Considered Harmful Someday, Cryptology ePrint Archive, Report 2004/357,сайт6 December 2004.
[6] Arjen Lenstra, Xiaoyun Wang and Benne de Weger: Colliding X.509 Certificates, Cryptology ePrint Archive, Report 2005/067,
сайт
[7] Vlastimil Klima: Several observations regarding Chinese collisions of MD5, 3rd International Scientific Conference Security and Protection of Information, Brno, Czech Republic, May 3 - 5, 2005,сайтin preparation.

приложение (примеры)

Пример: MD5 коллизия со стандартным IV

IV according to [2]:
context->state[0] = 0x67452301;
context->state[1] = 0xefcdab89;
context->state[2] = 0x98badcfe;
context->state[3] = 0x10325476;
Первое сообщение:
0xA6,0x64,0xEA,0xB8,0x89,0x04,0xC2,0xAC,
0x48,0x43,0x41,0x0E,0x0A,0x63,0x42,0x54,
0x16,0x60,0x6C,0x81,0x44,0x2D,0xD6,0x8D,
0x40,0x04,0x58,0x3E,0xB8,0xFB,0x7F,0x89,
0x55,0xAD,0x34,0x06,0x09,0xF4,0xB3,0x02,
0x83,0xE4,0x88,0x83,0x25,0x71,0x41,0x5A,
0x08,0x51,0x25,0xE8,0xF7,0xCD,0xC9,0x9F,
0xD9,0x1D,0xBD,0xF2,0x80,0x37,0x3C,0x5B,
0x97,0x9E,0xBD,0xB4,0x0E,0x2A,0x6E,0x17,
0xA6,0x23,0x57,0x24,0xD1,0xDF,0x41,0xB4,
0x46,0x73,0xF9,0x96,0xF1,0x62,0x4A,0xDD,
0x10,0x29,0x31,0x67,0xD0,0x09,0xB1,0x8F,
0x75,0xA7,0x7F,0x79,0x30,0xD9,0x5C,0xEB,
0x02,0xE8,0xAD,0xBA,0x7A,0xC8,0x55,0x5C,
0xED,0x74,0xCA,0xDD,0x5F,0xC9,0x93,0x6D,
0xB1,0x9B,0x4A,0xD8,0x35,0xCC,0x67,0xE3.
Второе сообщение:
0xA6,0x64,0xEA,0xB8,0x89,0x04,0xC2,0xAC,
0x48,0x43,0x41,0x0E,0x0A,0x63,0x42,0x54,
0x16,0x60,0x6C,0x01,0x44,0x2D,0xD6,0x8D,
0x40,0x04,0x58,0x3E,0xB8,0xFB,0x7F,0x89,
0x55,0xAD,0x34,0x06,0x09,0xF4,0xB3,0x02,
0x83,0xE4,0x88,0x83,0x25,0xF1,0x41,0x5A,
0x08,0x51,0x25,0xE8,0xF7,0xCD,0xC9,0x9F,
0xD9,0x1D,0xBD,0x72,0x80,0x37,0x3C,0x5B,
0x97,0x9E,0xBD,0xB4,0x0E,0x2A,0x6E,0x17,
0xA6,0x23,0x57,0x24,0xD1,0xDF,0x41,0xB4,
0x46,0x73,0xF9,0x16,0xF1,0x62,0x4A,0xDD,
0x10,0x29,0x31,0x67,0xD0,0x09,0xB1,0x8F,
0x75,0xA7,0x7F,0x79,0x30,0xD9,0x5C,0xEB,
0x02,0xE8,0xAD,0xBA,0x7A,0x48,0x55,0x5C,
0xED,0x74,0xCA,0xDD,0x5F,0xC9,0x93,0x6D,
0xB1,0x9B,0x4A,0x58,0x35,0xCC,0x67,0xE3.
MD5 хэш:
0x2B,0xA3,0xBE,0x5A,0xA5,0x41,0x00,0x6B,
0x62,0x37,0x01,0x11,0x28,0x2D,0x19,0xF5.
Пример: MD5 коллизия с избранным IV

context->state[0] = 0xabaaaaaa;
context->state[1] = 0xaaacaaaa;
context->state[2] = 0xaaaadaaa;
context->state[3] = 0xaaaaaaea;
Первое сообщение:
0x9E,0x83,0x2A,0x4C,0x95,0x64,0x5E,0x2B,
0x2E,0x1B,0xB0,0x70,0x47,0x1E,0xBA,0x13,
0x7F,0x1A,0x53,0x43,0x22,0x34,0x25,0xC1,
0x40,0x04,0x58,0x3E,0xB8,0xFB,0x7F,0x89,
0x55,0xAD,0x34,0x06,0x09,0xF4,0xB3,0x02,
0x83,0xE4,0x88,0x83,0x25,0x71,0x41,0x5A,
0x08,0x51,0x25,0xE8,0xF7,0xCD,0xC9,0x9F,
0xD9,0x1D,0xBD,0xF2,0x80,0x37,0x3C,0x5B,
0x89,0x62,0x33,0xEC,0x5B,0x0C,0x8D,0x77,
0x19,0xDE,0x93,0xFA,0xA1,0x44,0xA8,0xCC,
0x56,0x91,0x9E,0x47,0x00,0x0C,0x00,0x4D,
0x40,0x29,0xF1,0x66,0xD1,0x09,0xB1,0x8F,
0x75,0x27,0x7F,0x79,0x30,0xD5,0x5C,0xEB,
0x42,0xE8,0xAD,0xBA,0x78,0xCC,0x55,0x5C,
0xED,0xF4,0xCA,0xDD,0x5F,0xC5,0x93,0x6D,
0xD1,0x9B,0x0A,0xD8,0x35,0xCC,0xE7,0xE3.
Второе сообщение:
0x9E,0x83,0x2A,0x4C,0x95,0x64,0x5E,0x2B,
0x2E,0x1B,0xB0,0x70,0x47,0x1E,0xBA,0x13,
0x7F,0x1A,0x53,0xC3,0x22,0x34,0x25,0xC1,
0x40,0x04,0x58,0x3E,0xB8,0xFB,0x7F,0x89,
0x55,0xAD,0x34,0x06,0x09,0xF4,0xB3,0x02,
0x83,0xE4,0x88,0x83,0x25,0xF1,0x41,0x5A,
0x08,0x51,0x25,0xE8,0xF7,0xCD,0xC9,0x9F,
0xD9,0x1D,0xBD,0x72,0x80,0x37,0x3C,0x5B,
0x89,0x62,0x33,0xEC,0x5B,0x0C,0x8D,0x77,
0x19,0xDE,0x93,0xFA,0xA1,0x44,0xA8,0xCC,
0x56,0x91,0x9E,0xC7,0x00,0x0C,0x00,0x4D,
0x40,0x29,0xF1,0x66,0xD1,0x09,0xB1,0x8F,
0x75,0x27,0x7F,0x79,0x30,0xD5,0x5C,0xEB,
0x42,0xE8,0xAD,0xBA,0x78,0x4C,0x55,0x5C,
0xED,0xF4,0xCA,0xDD,0x5F,0xC5,0x93,0x6D,
0xD1,0x9B,0x0A,0x58,0x35,0xCC,0xE7,0xE3.
Хэш:
//значение было исправлено благодаря Яну Каспржаку (Jan Kasprzak)
0xef,0x2e,0xae,0x54,0xe0,0x34,0x70,0x7c,
0xa2,0x6e,0xb0,0x9b,0x45,0xc7,0xe4,0x87.

Vlastimil Klima, перевод Алексея Кутовенко.
Опубликовано: "Сетевые решения"
Оригинал: http://eprint.iacr.org/2006/105