Легкий способ подделки контрольной суммы и ЭЦП с помощью коллизий

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

Введение

Всегда ли ты проверяешь контрольную сумму скачанных из сети файлов? Думаю, нет. Хотя, конечно, для большинства юниксоидов это привычное дело, ведь целостность и достоверность скачанных образов и исходников порой играет важную роль. Достаточно вспомнить недавний взлом kernel.org: тогда лишь самые опытные администраторы заметили подвох, сравнив контрольную сумму скачанных исходников с контрольной суммой, представленной на сайте.

Ты наверняка знаешь, что контрольная сумма файла зачастую представляет собой криптографические хэш-функции, самыми известными из которых являются MD4, MD5 и SHA-1. Однако с недавних пор встала огромная проблема подтверждения целостности исходной информации при помощи более криптостойких алгоритмов хэширования (контрольных сумм). Имя этой проблемы — коллизии криптографических хэш-функций. Так, например, если хэш-функция используется для создания цифрового ключа, то умение строить для нее коллизии равносильно умению подделывать цифровой ключ! Именно поэтому в идеале не должно существовать способа поиска коллизий для криптографических хэш-функций более быстрого, чем полный перебор (брутфорс). Если для некоторой хэш-функции находится более быстрый способ, то эта хэш-функция перестает считаться криптостойкой, а также использоваться для передачи и хранения секретной информации. Но всегда ли это так? Оказывается, далеко не всегда.

Другие статьи в выпуске:

Хакер #159. Подделка контрольной суммы и ЭЦП с помощью коллизий

• Содержание выпуска
• Подписка на «Хакер»-60%

Матчасть

Итак, коллизией хэш-функции F называются два различных входных блока данных — x и y — таких, что F(x) = F(y). Рассмотрим в качестве примера хэш-функцию F(x) = x|19|, определенную на множестве целых чисел. Ее ОДЗ (из школьного курса математики ты должен знать, что это такое) состоит из 19 элементов (кольца вычетов по модулю 19), а область определения стремится к бесконечности. Так как множество прообразов заведомо больше множества значений, коллизии обязательно существуют. Что это значит? Давай построим коллизию для этой хэш-функции, используя входное значение 38, хэш-сумма которого равна нулю. Так как функция F(x) периодическая с периодом 19, то для любого входного значения y значение y+19 будет иметь ту же хэш-сумму, что и y. В частности, для входного значения 38 той же хэш-суммой будут обладать входные значения 57, 76 и так далее. Таким образом, пары входных значений (38,57), (38,76) образуют коллизии для хэш-функции F(x).

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

1. Необратимость: для заданного значения хэш-функции m должно быть практически невозможно найти блок данных x, для которого F(x) = m.
2. Стойкость к коллизиям первого рода: для заданного сообщения m должно быть практически невозможно подобрать другое сообщение n, для которого F(n) = F(m).
3. Стойкость к коллизиям второго рода: должно быть практически невозможно подобрать пару сообщений, имеющих одинаковый хэш.

Существует большое количество алгоритмов хэширования с различными характеристиками (разрядность, вычислительная сложность, криптостойкость и так далее). Простейшим примером хэш-функций может служить CRC, который не является алгоритмом хэш-функции, а представляет из себя алгоритм вычисления контрольной суммы. По скорости вычисления он в десятки и сотни раз быстрее, чем криптографические хэш-функции, а также значительно проще в аппаратной реализации. Однако платой за высокую скорость является возможность легко подогнать большое количество сообщений под заранее известную сумму. Так разрядность контрольных сумм (типичное число — 32 бита) ниже, чем у криптографических хэшей (типичные числа: 128, 160 и 256 бит), что означает возможность возникновения непреднамеренных коллизий. В качестве примера можно привести следующий код на C, демонстрирующий получение трех CRC-коллизий на 100 000 итераций:

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>

#define INTERATION 100000

int main(){
int count =0;
int i,j;
unsigned hash;
char c;
unsigned* table;
table = calloc(INTERATION,sizeof(unsigned));
for(i = 0; i< INTERATION; i++){
hash = 0;
for(j=0; 32 > j;j++){
  c = 33 + (char) (63.0*rand()/(RAND_MAX+1.0));
  hash = (hash * 33) + c;
}
hash = hash + (hash >> 5);
for(j=0; i > j ;j++){
if (table[j] == hash) count++;
}
table[i]=hash;
}
free(table);
printf("%d values %d collisions\n",INTERATION, count);
return 0;
}

Среди множества существующих хэш-функций принято особенно выделять криптографически стойкие, - они применяются в криптографии. К примеру, существуют два наиболее часто встречающихся в повседневной жизни алгоритма: MD4 и MD5. В плане безопасности MD5 является более надежным, чем его предшественник MD4. В новый алгоритм разработчики добавили еще один раунд — теперь вместо трех их стало четыре. Также была добавлена новая константа, чтобы свести к минимуму влияние входного сообщения. В каждом раунде на каждом шаге константа всегда разная, она суммируется с результатом F и блоком данных. Изменилась функция G = XZ v (Y not(Z)) (вместо XY v XZ v YZ). Результат каждого шага складывается с результатом предыдущего, из-за этого происходит более быстрое изменение результата. Изменился порядок работы с входными словами в раундах 2 и 3. Даже небольшое изменение входного сообщения (в нашем случае на один бит: ASCII символ «5» с кодом 0x3516 = 0001101012 заменяется на символ «4» с кодом 0x3416 = 0001101002) приводит к полному изменению хэша. Такое свойство алгоритма называется лавинным эффектом. Вот так выглядит пример 128-битного (16-байтного) MD5-хэша:

MD5("md5") = 1bc29b36f623ba82aaf6724fd3b16718

Кстати, если говорить конкретно о коллизиях в алгоритме MD5, то здесь мы можем получить одинаковые значения функции (F) для разных сообщений и идентичного начального буфера. Так, например, для известного сообщения можно построить второе — такое, что оно будет иметь такой же хэш, как и исходное. C точки зрения математики это означает следующее: MD5(IV,L1) = MD5(IV,L2), где IV — начальное значение буфера, а L1 и L2 — различные сообщения. Например, если взять начальное значение буфера

A = 0x12AC2375
В = 0x3B341042
C = 0x5F62B97C
D = 0x4BA763ED

и задать входное сообщение

AA1DDABE   D97ABFF5   BBF0E1C1   32774244
1006363E   7218209D   E01C136D   9DA64D0E
98A1FB19   1FAE44B0   236BB992   6B7A779B
1326ED65   D93E0972   D458C868   6B72746A

то добавляя число 2^9 к определенному 32-разрядному слову в блочном буфере, можно получить второе сообщение с таким же хэшем. Есть несколько программ, которые помогут тебе все это дело провернуть (обрати внимание на ссылки в боковом выносе).

Методы получения профита

Перед тем как начать практическую часть, мы должны добить теорию. Дело в том, что так называемые коллизии мы можем использовать в качестве ключа/пароля для аутентификации в различном ПО и на веб-ресурсах. Это значит, что даже без знания пароля, имея на руках только лишь его хэш, мы можем сгенерировать правдоподобный пассворд с помощью коллизии, причем за вполне приемлемое время. Однако на данный момент существуют и повсеместно используются лишь несколько видов «взлома» хэшей MD4/5, то есть подбора сообщения с заданным хэшем.

1. Перебор по заданному словарю: никаких гарантий удачного результата нет, из плюсов можно отметить лишь малое время, затраченное на перебор.
2. Брутфорс: банальный перебор случайных или последовательных комбинаций, большим минусом которого является значительное количество затраченного времени и ресурсов компьютера.
3. RainbowCrack: атака по радужным таблицам является самым эффективным методом «взлома»; плюс заключается в быстром переборе, минусы — в гигантском размере радужных таблиц и большом количестве времени, затраченном на их генерацию.

Для полного перебора или перебора по словарю можно использовать, к примеру, следующие программы: PasswordsPro, MD5BFCPF, John the Ripper. Теперь же я предлагаю тебе познакомиться с новым методом атаки на хэши — методом коллизий.

От теории к практике

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

1. CR2-KK — свободный от коллизий, устойчивый к коллизиям.
2. CR1-KK — универсальный односторонний.
3. CR0 — универсальный.

Также существуют три вида соответствующих атак для нахождения коллизий:

1. CR2-KK — найти коллизии для конкретной функции.
2. CR1-KK — подобрать к заданному значению пару, образующую коллизию для конкретной функции.
3. СК0 — найти коллизию для семейства функций.

Сегодня я продемонстрирую тебе два первых вида атак на практике. Для начала приведу два блока данных в HEX (пара коллизий из научной работы китайского ИБ-исследователя Ван Сяоюня), их нужно вбить в hex-редакторе и сохранить в виде двух файлов:

    1-й файл
d131dd02c5e6eec4693d9a0698aff95c2fcab58712467eab4004583eb8fb7f89
55ad340609f4b30283e488832571415a085125e8f7cdc99fd91dbdf280373c5b
d8823e3156348f5bae6dacd436c919c6dd53e2b487da03fd02396306d248cda0
e99f33420f577ee8ce54b67080a80d1ec69821bcb6a8839396f9652b6ff72a70

    2-й файл
d131dd02c5e6eec4693d9a0698aff95c2fcab50712467eab4004583eb8fb7f89
55ad340609f4b30283e4888325f1415a085125e8f7cdc99fd91dbd7280373c5b
d8823e3156348f5bae6dacd436c919c6dd53e23487da03fd02396306d248cda0
e99f33420f577ee8ce54b67080280d1ec69821bcb6a8839396f965ab6ff72a70

Если сравнить размер и контрольную сумму в MD5 у полученных файлов, то мы не заметим никакой разницы! Теперь давай найдем еще несколько коллизий к этим файлам. Программа MD5 Collision Generator от Патрика Стэча поможет нам разобраться в атаке CR2-KK. Смело компилируй ее и запускай на исполнение. Первая коллизия на моем самом слабом компьютере была получена менее чем за 15 минут, а вторая — примерно через два с половиной часа! Не так уж и плохо, согласись.

Теперь перейдем к реальной атаке, для этого будем использовать эксплойт-библиотеку evilize (снова обрати внимание на ссылки). После компиляции данной библиотеки в текущей директории должны появиться три файла: evilize, md5coll и объектный файл goodevil.o. В качестве подопытной программы будем использовать пример hello-erase.c, идущий в комплекте с исходниками. Итак, компилируем нашу программу и линкуем ее с объектным файлом goodevil.o:

gcc hello-erase.c goodevil.o -o hello-erase

Смотрим контрольную сумму подопытного файла:

md5sum ./hello-erase
23d3e4873e3ea619c7bdd6fa2d0271e7
/home/satsura/md5coll/source/evilize/hello-erase

Разбиваем на блоки нашу полученную контрольную сумму, и запускаем на исполнение генератор MD5-коллизий:

./md5coll 0x23d3e487 0x3e3ea619 0xc7bdd6fa 0x2d0271e7 > init.txt

Далее запускаем evilize для создания двух различных исполняемых файлов с одинаковым размером и MD5-хэшем. Смотрим на контрольную сумму и размер, а затем запускаем полученные бинарники:

./evilize hello-erase -c init.txt -g good -e evil
du -sh ./evil ./good & md5sum ./evil ./good
8,0K./evil
8,0K./good
d8bf211b61624d331fe06c75bd6e3c89  ./evil
d8bf211b61624d331fe06c75bd6e3c89  ./good
./good
Hello, world!

./ evil
This program is evil!!!
Erasing hard drive...1Gb...2Gb... just kidding!
Nothing was erased.

Как видишь, одна программа выводит известную всем безобидную фразу «Hello, world!», а вторая якобы стирает данные на диске. Мы можем переделать наш hello-erase.c так, чтобы вместо шуточного стирания данных произошло реальное, и тогда будет не до шуток. Но все это цветочки по сравнению со следующей атакой, которую я провел при своих исследованиях CR1-KK.

Взлом CR1-KK

В качестве «жертвы» для исследований я выбрал цифровые ключи компании Unicon, являющейся в Узбекистане монополистом в области ЭЦП (электронно-цифровой подписи) и сертификации. Основываясь на трудах Властимила Климы, я написал программу CR1-KK-collision keygen для подбора пары к значению, образующей коллизию для конкретной функции при генерации электронно-цифровых ключей. Изначально было несколько данных, которые я и использовал в качестве входных параметров. Очень облегчил задачу тот факт, что пароль для закрытой ЭЦП у всех сертификатов один и тот же: 000000. Это была фатальная ошибка — самая грубая из встреченных мной за весь опыт работы в области ИБ. Имея на руках только контрольные суммы файлов и открытые ключи, мне удалось сгенерировать примерный оригинальный закрытый ключ для подписи различного рода документов, ключей и идентификации пользователя в нескольких CRM-системах (к примеру, E-hujjat от того же монополиста). Проделанную работу ты сможешь увидеть воочию на соответствующих скриншотах, в консоли же все это выглядело примерно так:

C:\coll_test> md5sum *
b2d1a3f63f9784e0fe8c237ff2484a78 *key((faked by collision).key
a654bd700b5e6cf47ca0b042b2f30575 *cer(faked by collision).cer
c5d6aaa28639316614e3d95987fcb612 *pfx(faked by collision).pfx
a654bd700b5e6cf47ca0b042b2f30575 *cer.cer

Как видишь, у сертификатов cer.cer и cer(faked by collision).cer одинаковая контрольная сумма.

Заключение

Надо признать, что MD5-хэши стали неотъемлемой частью нашей жизни. Они вездесущи. Их используют в качестве алгоритмов для хэширования паролей как в программном обеспечении, так и на веб-ресурсах. Они не зависят ни от платформы, ни от ОС, на которых исполняются. Векторы атак также довольно широки: от банкоматов до цифровых подписей, от авторизации клиент-сервер и до целостности передаваемых по сети файлов. Являясь быстрыми и менее криптостойкими, 128-битные алгоритмы хэширования принесут еще немало бед. На сегодняшний день коллизии и псевдоколлизии были найдены в большом ряде алгоритмов, среди которых MD2, MD4, MD5, DES, DES-IDEA, RIPE-MD, HAVAL(~128, ~256), SHA-1, ГОСТ Р 34.10-2001 и так далее. Со временем этот список будет только пополняться.