|
Обзор атак на приложения и протоколы, использующие алгоритм MD5, часть 9
© Сергей Панасенко, 2013
Данная статья завершает цикл статей, посвященных атакам на различные применения алгоритма хэширования MD5.
В шестой части статьи мы рассматривали работу [1], в которой были предложены атаки на команду APOP, используемую для усиленной (по сравнению с парольной) аутентификации пользователя на сервере электронной почты с применением алгоритма MD5. В 2009 г. вышла работа [2] тех же авторов с участием Казуо Сакиямы (Kazuo Sakiyama), результатом которой было двукратное уменьшение требуемого для проведения успешной атаки на APOP количества запросов пользователя на соединение с сервером электронной почты. Однако, минимальная трудоемкость атаки с уменьшенным количеством запросов составляет 246 операций, что превышает трудоемкость атаки, описанной в [1].
В 2011 г. была опубликована работа [3], авторы которой (в основном, за счет усовершенствования технологии модификации сообщений при поиске коллизии) добились значительного снижения трудоемкости атак на команду APOP по сравнению с работой [1]. Кроме того, в [3] был предложен усиленный вариант технологии «IV Bridge» (см. шестую часть статьи), для применения которой теперь требуется 219 операций вычисления хэша MD5 по сравнению с 242 операциями, требовавшимися согласно методике, предложенной в работе [1]. Следовательно, резко уменьшилась трудоемкость раскрытия паролей пользователей различной длины, а максимальная теоретическая возможность по поиску пароля была расширена с 61 до 67 символов.
Авторы опубликованной в [3] атаки особо отметили также, что предложенная ими методика атаки наиболее точно соответствует реальному сценарию атаки на команду APOP, которую могло бы проводить зловредное программное обеспечение. Данную атаку ее авторы рассматривают как еще одно подтверждение факта полного взлома команды APOP.
Сделаем небольшое отступление и рассмотрим варианты создания стойких однонаправленных хэш-функций на основе алгоритмов блочного шифрования. Существует несколько таких вариантов с доказанной криптостойкостью. В частности, в работе [4] подробно описаны 12 алгоритмов, представляющих собой хэширующие надстройки над блочными шифрами.
Рассмотрим два из таких алгоритмов более подробно. Первый из них – это алгоритм Матиаса-Мейера-Осиса (Matyas-Meyer-Oseas – MMO), функция сжатия которого представлена на рис. 1. В данном алгоритме нижележащий блочный шифр используется следующим образом [5]:
Поскольку размеры блока шифруемых данных и ключа алгоритма шифрования могут быть различными (и чаще всего бывают различными), а размер состояния алгоритма хэширования является фиксированным, в алгоритме MMO существует необходимость в функции g(), задача которой состоит лишь в адаптации значения Hi-1 под требуемый размер ключа шифрования. Поскольку функция g() не влияет на безопасность алгоритма, она может быть максимально простой и, например, может выполнять только дополнение Hi-1 до требуемого размера [6].
Формально алгоритм MMO представляется так:
Hi = E(Mi, g(Hi-1)) 
Mi,
где E(P, K) – блочный шифр, шифрующий открытый текст P на ключе K.
Существует также вариант алгоритма MMO, который вместо операции XOR использует сложение 32-битных субблоков Mi и C по модулю 232. В работе [7] такой вариант называется предпочтительным для алгоритмов MD4 и MD5.
Еще один вариант формирования алгоритма хэширования на основе блочного шифра – алгоритм Миягучи-Пренела (Miyaguchi-Preneel), который отличается от предыдущего только тем, что предыдущее состояние алгоритма хэширования также участвует в операции XOR с блоком сообщения и результатом его зашифрования (см. рис. 2) [5]:
Hi = E(Mi, g(Hi-1)) Mi Hi-1.
Аналогично предыдущей схеме, здесь также возможна (и рекомендуется для алгоритмов MD4 и MD5 [7]) замена операции XOR на операцию сложения субблоков операндов по модулю 232.
В качестве блочного шифра может использоваться функция сжатия какого-либо алгоритма хэширования, поскольку, как и блочный шифр, функция сжатия любого алгоритма хэширования принимает на вход два параметра (состояние и хэшируемый блок данных вместо ключа шифрования и шифруемого блока), выдавая в качестве результата модифицированное состояние. В этом случае схемы MMO и Миягучи-Пренела можно рассматривать как надстройки, усиливающие криптографические свойства нижележащего алгоритма хэширования.
В работе [7] Ю Сасаки проанализировал алгоритмы MMO и Миягучи-Пренела при использовании их в качестве надстроек над алгоритмом MD5 (первый из данных алгоритмов известен под названием MMO-MD5). Оба проанализированных алгоритма оказались недостаточно стойкими – предложенная Сасаки атака по поиску коллизии для данных алгоритмов требует выполнения 239 операций, т. е. данная атака является применимой на практике. Кроме того, теоретически возможно применение модификации данной атаки против алгоритма NMAC-MD5 и еще одного варианта надстройки над алгоритмом хэширования MD5 – алгоритма Дэвиса-Мейера (Davies-Meyer), показанного на рис. 3.
Отметим вышедший в марте 2011 г. документ [8], в котором Интернет-сообществу не рекомендуется в дальнейшем использовать алгоритм MD5 во всех применениях, где требуется стойкость к нахождению коллизий, в частности, в схемах электронной цифровой подписи. Кроме того, документ [8] рекомендует отказаться от алгоритма MD5 и во всех других применениях в новых приложениях и протоколах.
Судя по информации, рассмотренной в данном цикле статей, изложенные в [8] рекомендации выглядят существенно запоздавшими. А в статье [9] отмечается, что организации и пользователи крайне медленно реагируют на подобные рекомендации, следствием чего является активное использование уже взломанных алгоритмов. Известна, как минимум, одна глобальная атака, использовавшая коллизии с выбранным префиксом и возможность подделки сертификата (см. седьмую часть статьи), при подписании которого использован алгоритм MD5: в 2012 г. шпионская программа Flame (выполняющая перехват информации различных форматов и ее отправку в управляющий центр) атаковала множество компьютеров в странах Ближнего Востока (преимущественно в Иране). Данная программа была подписана с помощью поддельного сертификата компании Microsoft, что существенно упрощало ее внедрение на компьютер пользователя [10, 11].
На этом историю атак на применения алгоритма MD5 можно считать завершенной. По крайней мере, впоследствии не было опубликовано каких-либо широко известных работ, предлагающих новые методы атак на приложения и протоколы, использующие алгоритм MD5. Стоит отметить только две работы 2012 г.: работу Стивенса, Ленстры и де Вегера [12], более подробно описывающую коллизии с выбранным префиксом и построение атак на различные приложения на их основе, а также диссертацию Марка Стивенса [13], в которой дается обзор атак на хэш-функции (в основном, Стивенс рассматривает алгоритмы MD5 и SHA-1) и их приложения.
Можно утверждать, что алгоритм MD5 является одним из двух алгоритмов (наряду с SHA-1), в результате анализа которых был достигнут наибольший прогресс в криптоанализе алгоритмов хэширования и их применений. В рамках криптоанализа MD5 было предложено множество новых методов и основанных на них атак на данный алгоритм, часть из которых впоследствии была распространена и на другие алгоритмы хэширования. Одними из наиболее масштабных результатов криптоанализа MD5 можно считать выявленное наличие слабостей в самой схеме Меркля-Дамгаарда, а также доказательства опасности абстрактных коллизий.
Мы не будем в отдельной статье рассматривать описание применений алгоритма MD5 (как это было сделано ранее для алгоритма MD4 в [14]), поскольку, во-первых, некоторые из основных применений MD5 были рассмотрены в обзоре атак на приложения и протоколы, а во-вторых, «нельзя объять необъятное». Поэтому следующая статья данного цикла будет посвящена еще одному алгоритму семейства MD – алгоритму MD6.
Литература
Рисунки:
