В современном IT-мире контрольную сумму файла или любых других важных данных принято считать фундаментом для подтверждения неизменности исходной информации. Но если ты вспомнишь историю с руткитом Stuxnet, то поймешь, что уязвимости в популярных алгоритмах для расчета таких сумм могут привести к большим катастрофам. Давай проверим это.
Содержание
Введение
Всегда ли ты проверяешь контрольную сумму скачанных из сети файлов? Думаю, нет. Хотя, конечно, для большинства юниксоидов это привычное дело, ведь целостность и достоверность скачанных образов и исходников порой играет важную роль. Достаточно вспомнить недавний взлом 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 считалась криптографически стойкой, она должна удовлетворять трем основным требованиям, на которых основано большинство применений хэш-функций в криптографии.
- Необратимость: для заданного значения хэш-функции m должно быть практически невозможно найти блок данных x, для которого F(x) = m.
- Стойкость к коллизиям первого рода: для заданного сообщения m должно быть практически невозможно подобрать другое сообщение n, для которого F(n) = F(m).
- Стойкость к коллизиям второго рода: должно быть практически невозможно подобрать пару сообщений, имеющих одинаковый хэш.
Существует большое количество алгоритмов хэширования с различными характеристиками (разрядность, вычислительная сложность, криптостойкость и так далее). Простейшим примером хэш-функций может служить CRC, который не является алгоритмом хэш-функции, а представляет из себя алгоритм вычисления контрольной суммы. По скорости вычисления он в десятки и сотни раз быстрее, чем криптографические хэш-функции, а также значительно проще в аппаратной реализации. Однако платой за высокую скорость является возможность легко подогнать большое количество сообщений под заранее известную сумму. Так разрядность контрольных сумм (типичное число — 32 бита) ниже, чем у криптографических хэшей (типичные числа: 128, 160 и 256 бит), что означает возможность возникновения непреднамеренных коллизий. В качестве примера можно привести следующий код на C, демонстрирующий получение трех CRC-коллизий на 100 000 итераций:
Среди множества существующих хэш-функций принято особенно выделять криптографически стойкие, — они применяются в криптографии. К примеру, существуют два наиболее часто встречающихся в повседневной жизни алгоритма: MD4 и MD5. В плане безопасности MD5 является более надежным, чем его предшественник MD4. В новый алгоритм разработчики добавили еще один раунд — теперь вместо трех их стало четыре. Также была добавлена новая константа, чтобы свести к минимуму влияние входного сообщения. В каждом раунде на каждом шаге константа всегда разная, она суммируется с результатом F и блоком данных. Изменилась функция G = XZ v (Y not(Z)) (вместо XY v XZ v YZ). Результат каждого шага складывается с результатом предыдущего, из-за этого происходит более быстрое изменение результата. Изменился порядок работы с входными словами в раундах 2 и 3. Даже небольшое изменение входного сообщения (в нашем случае на один бит: ASCII символ «5» с кодом 0×3516 = 0001101012 заменяется на символ «4» с кодом 0×3416 = 0001101002) приводит к полному изменению хэша. Такое свойство алгоритма называется лавинным эффектом. Вот так выглядит пример 128-битного (16-байтного) MD5-хэша:
Кстати, если говорить конкретно о коллизиях в алгоритме MD5, то здесь мы можем получить одинаковые значения функции (F) для разных сообщений и идентичного начального буфера. Так, например, для известного сообщения можно построить второе — такое, что оно будет иметь такой же хэш, как и исходное. C точки зрения математики это означает следующее: MD5(IV,L1) = MD5(IV,L2), где IV — начальное значение буфера, а L1 и L2 — различные сообщения. Например, если взять начальное значение буфера
и задать входное сообщение
то добавляя число 2^9 к определенному 32-разрядному слову в блочном буфере, можно получить второе сообщение с таким же хэшем. Есть несколько программ, которые помогут тебе все это дело провернуть (обрати внимание на ссылки в боковом выносе).
Методы получения профита
Перед тем как начать практическую часть, мы должны добить теорию. Дело в том, что так называемые коллизии мы можем использовать в качестве ключа/пароля для аутентификации в различном ПО и на веб-ресурсах. Это значит, что даже без знания пароля, имея на руках только лишь его хэш, мы можем сгенерировать правдоподобный пассворд с помощью коллизии, причем за вполне приемлемое время. Однако на данный момент существуют и повсеместно используются лишь несколько видов «взлома» хэшей MD4/5, то есть подбора сообщения с заданным хэшем.
- Перебор по заданному словарю: никаких гарантий удачного результата нет, из плюсов можно отметить лишь малое время, затраченное на перебор.
- Брутфорс: банальный перебор случайных или последовательных комбинаций, большим минусом которого является значительное количество затраченного времени и ресурсов компьютера.
- RainbowCrack: атака по радужным таблицам является самым эффективным методом «взлома»; плюс заключается в быстром переборе, минусы — в гигантском размере радужных таблиц и большом количестве времени, затраченном на их генерацию.
Для полного перебора или перебора по словарю можно использовать, к примеру, следующие программы: PasswordsPro, MD5BFCPF, John the Ripper. Теперь же я предлагаю тебе познакомиться с новым методом атаки на хэши — методом коллизий.
От теории к практике
Ну что же, теперь перейдем к долгожданной практике. Среди профессиональных криптоаналитиков есть вполне определенная классификация типов устойчивости алгоритмов хэширования, их всего три.
-
CR2-KK — свободный от коллизий, устойчивый к коллизиям. -
CR1-KK — универсальный односторонний. -
CR0 — универсальный.
Также существуют три вида соответствующих атак для нахождения коллизий:
-
CR2-KK — найти коллизии для конкретной функции. -
CR1-KK — подобрать к заданному значению пару, образующую коллизию для конкретной функции. -
СК0 — найти коллизию для семейства функций.
Сегодня я продемонстрирую тебе два первых вида атак на практике. Для начала приведу два блока данных в HEX (пара коллизий из научной работы китайского ИБ-исследователя Ван Сяоюня), их нужно вбить в hex-редакторе и сохранить в виде двух файлов:
Если сравнить размер и контрольную сумму в MD5 у полученных файлов, то мы не заметим никакой разницы! Теперь давай найдем еще несколько коллизий к этим файлам. Программа MD5 Collision Generator от Патрика Стэча поможет нам разобраться в атаке CR2-KK. Смело компилируй ее и запускай на исполнение. Первая коллизия на моем самом слабом компьютере была получена менее чем за 15 минут, а вторая — примерно через два с половиной часа! Не так уж и плохо, согласись.
Теперь перейдем к реальной атаке, для этого будем использовать эксплойт-библиотеку evilize (снова обрати внимание на ссылки). После компиляции данной библиотеки в текущей директории должны появиться три файла: evilize, md5coll и объектный файл goodevil.o. В качестве подопытной программы будем использовать пример hello-erase.c, идущий в комплекте с исходниками. Итак, компилируем нашу программу и линкуем ее с объектным файлом goodevil.o:
Смотрим контрольную сумму подопытного файла:
Разбиваем на блоки нашу полученную контрольную сумму, и запускаем на исполнение генератор MD5-коллизий:
Далее запускаем evilize для создания двух различных исполняемых файлов с одинаковым размером и MD5-хэшем. Смотрим на контрольную сумму и размер, а затем запускаем полученные бинарники:
Как видишь, одна программа выводит известную всем безобидную фразу «Hello, world!», а вторая якобы стирает данные на диске. Мы можем переделать наш hello-erase.c так, чтобы вместо шуточного стирания данных произошло реальное, и тогда будет не до шуток. Но все это цветочки по сравнению со следующей атакой, которую я провел при своих исследованиях CR1-KK.
Взлом CR1-KK
В качестве «жертвы» для исследований я выбрал цифровые ключи компании Unicon, являющейся в Узбекистане монополистом в области ЭЦП (электронно-цифровой подписи) и сертификации. Основываясь на трудах Властимила Климы, я написал программу CR1-KK-collision keygen для подбора пары к значению, образующей коллизию для конкретной функции при генерации электронно-цифровых ключей. Изначально было несколько данных, которые я и использовал в качестве входных параметров. Очень облегчил задачу тот факт, что пароль для закрытой ЭЦП у всех сертификатов один и тот же: 000000. Это была фатальная ошибка — самая грубая из встреченных мной за весь опыт работы в области ИБ. Имея на руках только контрольные суммы файлов и открытые ключи, мне удалось сгенерировать примерный оригинальный закрытый ключ для подписи различного рода документов, ключей и идентификации пользователя в нескольких CRM-системах (к примеру, E-hujjat от того же монополиста). Проделанную работу ты сможешь увидеть воочию на соответствующих скриншотах, в консоли же все это выглядело примерно так:
Как видишь, у сертификатов 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 и так далее. Со временем этот список будет только пополняться.
Источник