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

 

WARNING

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

 

Введение

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

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

Таблица хэш-функций, для которых были найдены коллизии
Таблица хэш-функций, для которых были найдены коллизии
 

Матчасть

Итак, коллизией хэш-функции 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. Стойкость к коллизиям второго рода: должно быть практически невозможно подобрать пару сообщений, имеющих одинаковый хэш.
Проверка подлинности сертификата на VeriSign
Проверка подлинности сертификата на VeriSign

Существует большое количество алгоритмов хэширования с различными характеристиками (разрядность, вычислительная сложность, криптостойкость и так далее). Простейшим примером хэш-функций может служить 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-разрядному слову в блочном буфере, можно получить второе сообщение с таким же хэшем. Есть несколько программ, которые помогут тебе все это дело провернуть (обрати внимание на ссылки в боковом выносе).

 

Stuxnet и поддельные сертификаты

Надеюсь, ты не забыл историю с руткитом Stuxnet, когда троян-дроппер прогружал и запускал в системе свои драйверы, спокойно обходя всяческие системы предотвращения вторжений и антивирусы? Тогда при реверс-инжиниринге сэмплов выяснилось, что драйверы руткита были подписаны «настоящими» сертификатами крупных производителей контроллеров и чипов JMicron и Realtek. Было много шума, все кинулись обвинять эти компании в некомпетентности. Аналогичная история повторилась и с «братом» Stuxnet — червем Duqu. На этот раз обвинили компанию C-Media Electronics, сертификаты которой также были якобы украдены. Все вроде бы верно, но никаких краж возможно и не было! Я думаю, ты уже понял, о чем идет речь. Поддельные сертификаты были сгенерированы при помощи фундаментального бага — коллизий. Антивирусы, проверяя контрольную сумму файлов, не заметили никакого подвоха, а ведь все держалось именно на них :). Как бы парадоксально это не было, но существует ряд доказательств, подтверждающих мои слова. Во-первых, на одном закрытом форуме, где тусовались разработчики этих нашумевших руткитов (хотелось бы особо отметить человека под ником orr, статьи которого присутствуют на ряде авторитетных паблик-ресурсов, посвященных ИБ и реверс-инжинирингу: woodman и openrce), существовал топик о возможности кражи доверенных сертификатов. В нем приводился пример с Duqu, сертификат (c закрытым ключом) которого был сгенерирован с помощью коллизии. Во-вторых, если сравнить два сертификата (настоящий и тот, что был сгенерирован для Duqu) по размеру, то окажется, что существует хоть и малая, но все же разница в 15 байт! Таким образом, файлы получались разные по размеру, но одинаковые по контрольной сумме. История с украденными сертификатами осталась бы практически незамеченной, если бы не работа независимых ИБ-исследователей.

Оригинальный сертификат
Оригинальный сертификат
 

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

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

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

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

Коллизия в действии
Коллизия в действии
 

Немного истории

  • 1996: Ганс Доббертин нашел псевдоколлизии в MD5, используя определенные инициализирующие векторы, отличные от стандартных.
  • 2004: Китайские исследователи Ван Сяоюнь (Wang Xiaoyun), Фен Дэнгуо (Feng Dengguo), Лай Сюэцзя (Lai Xuejia) и Юй Хунбо (Yu Hongbo) объявили об обнаруженной ими уязвимости в алгоритме, позволяющей находить коллизии за крайне малое время (1 час на кластере IBM p690).
  • 2005: Те же самые Ван Сяоюнь и Юй Хунбо опубликовали алгоритм, позволяющий найти две различные последовательности в 128 байт, которые дают одинаковый MD5-хэш.
  • 2006: Чешский исследователь Властимил Клима опубликовал алгоритм, дающий возможность находить коллизии на обычном компьютере с любым начальным вектором (A,B,C,D) при помощи метода, названного им «туннелирование».
  • 2007: Эдуардо Диаз по специально разработанной схеме создал два различных архива с двумя разными программами, но абсолютно идентичными MD5-хэшами.
  • 2009: Дидье Стивенс использовал библиотеку evilize для создания двух разных программ с одинаковым кодом цифровой сигнатуры (Authenticode digital signature), authenticode используется Microsoft для подписи своих библиотек и исполняемых файлов.
 

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

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

  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 и так далее. Со временем этот список будет только пополняться.

 

Оставить мнение

Check Also

Защита дисков UHD Blu-ray оказалась под угрозой: в сеть утекли ключи AACS 2.0

В интернете были опубликованы 72 ключа AACS 2.0, которые могут нанести огромный урон Голли…