Рейтинг@Mail.ru

09 октября 2013

Обзор атак на приложения и протоколы, использующие алгоритм MD5
Часть 9

Данная статья завершает цикл статей, посвященных атакам на различные применения алгоритма хэширования 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]:

  • блок хэшируемых данных Mi подается на вход алгоритма в качестве открытого текста (P);
  • ключом блочного шифра (K) служит текущее состояние алгоритма хэширования Hi-1 , обработанное некоторой функцией g() (см. далее);
  • на результат шифрования (C) блока Mi на ключе g(Hi-1 ) накладывается операцией XOR блок Mi , в результате чего получается новое состояние алгоритма хэширования Hi.

Поскольку размер блока шифруемых данных и ключа алгоритма шифрования могут быть различными (и чаще всего бывают различными), а размер состояния алгоритма хэширования является фиксированным, в алгоритме MMO существует необходимость в функции g(), задача которой состоит лишь в адаптации значения Hi-1 под требуемый размер ключа шифрования. Поскольку функция g() не влияет на безопасность алгоритма, она может быть максимально простой и, например, может выполнять только дополнение Hi-1 до требуемого размера [6].

Формально алгоритм MMO представляется так:

Hi = E (Mi , g ( Hi-1 )) ⊕ Mi ,

где E(PK) – блочный шифр, шифрующий открытый текст P на ключе K.

Существует также вариант алгоритма MMO, который вместо операции XOR использует сложение 32-битных субблоков Mi и C по модулю 232. В работе [7] такой вариант называется предпочтительным для алгоритмов MD4 и MD5.

 

Рис. 1 Схема алгоритма MMO

Еще один вариант формирования алгоритма хэширования на основе блочного шифра – алгоритм Миягучи-Пренела (Miyaguchi-Preneel), который отличается от предыдущего только тем, что предыдущее состояние алгоритма хэширования также участвует в операции XOR с блоком сообщения и результатом его зашифрования (см. рис. 2) [5]:

Hi = E ( Mi , g ( Hi-1 )) ⊕ Mi ⊕ Hi-1 .

Аналогично предыдущей схеме, здесь также возможна (и рекомендуется для алгоритмов MD4 и MD5 [7]) замена операции XOR на операцию сложения субблоков операндов по модулю 232.

Рис. 2 Схема алгоритма Миягучи-Пренела

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

В работе [7] Ю Сасаки проанализировал алгоритмы MMO и Миягучи-Пренела при использовании их в качестве надстроек над алгоритмом MD5 (первый из данных алгоритмов известен под названием MMO-MD5). Оба проанализированных алгоритма оказались недостаточно стойкими – предложенная Сасаки атака по поиску коллизии для данных алгоритмов требует выполнения 239 операций, т. е. данная атака является применимой на практике. Кроме того, теоретически возможно применение модификации данной атаки против алгоритма NMAC-MD5 и еще одного варианта надстройки над алгоритмом хэширования MD5 – алгоритма Дэвиса-Мейера (Davies-Meyer), показанного на рис. 3.

Рис. 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.

 

Литература

  1. Sasaki Y., Wang L., Ohta K., Kunihiro N. Security of MD5 Challenge and Response: Extension of APOP Password Recovery Attack. // http://link.springer.com – 2008.
  2. Wang L., Sasaki Y., Sakiyama K., Ohta K. Bit-Free Collision: Application to APOP Attack. // http://link.springer.com (Abstract) – 2009.
  3. Liu F., Liu Y., Xie T., Feng Y. Fast Password Recovery Attack: Application to APOP. // http://eprint.iacr.org.
  4. Preneel B. Analysis and Design of Cryptographic Hash Functions. // http://homes.esat.kuleuven.be – February 2003.
  5. Menezes A., van Oorschot P., Vanstone S. Handbook of Applied Cryptography. CRC Press, 1996. // http://www.cacr.math.uwaterloo.ca.
  6. One-way compression function. From Wikipedia, the free encyclopedia. // http://en.wikipedia.org.
  7. Sasaki Y. Collisions of MMO-MD5 and Their Impact on Original MD5. // http://books.google.ru (Preview) – 2011.
  8. Turner S., Chen L. RFC 6151. Updated Security Considerations for the MD5 Message-Digest and the HMAC-MD5 Algorithms. // http://tools.ietf.org – March 2011.
  9. Stevens M. Advances in Hash Function Cryptanalysis. // http://ercim-news.ercim.eu.
  10. Flame (malware). From Wikipedia, the free encyclopedia. // http://en.wikipedia.org.
  11. Ness J. Flame malware collision attack explained. // http://blogs.technet.com – Microsoft Corporation – 6 Jun 2012.
  12. Stevens M., Lenstra A., de Weger B. Chosen-prefix collisions for MD5 and applications. // http://marc-stevens.nl – International Journal of Applied Cryptography, Vol. 2, No. 4, 2012.
  13. Stevens M. Attacks on Hash Functions and Applications. // http://marc-stevens.nl – Universiteit Leiden – Amsterdam, 2012.
  14. Панасенко С. Алгоритм хэширования MD4: обзор применений. // Sec.ru. – http://daily.sec.ru/publication.cfm?pid=34648 – 25.06.2012 г.

 

Об авторе:

Панасенко Сергей Петрович, нач. отдела разработки программного обеспечения фирмы АНКАД, кандидат технических наук.

Просмотров: 2370

Мнения экспертов

Завершающая статья по обзору криптоанализа алгоритма MD5, как и все предыдущие части, представляет интерес больше с теоретической стороны и, несомненно, будет полезна студентам, обучающимся по направлению информационной безопасности и в частности криптографии и криптоанализа.

Действительно, всё с чего то начинается и обязательно когда-то чем-то заканчивается. Так и в данном случае автор некоторое время назад начал публиковать интереснейший материал и данной частью статьи его заканчивает. Я не побоюсь оказаться банальным и отмечу, что и эта часть материала, как и вся работа в целом, представляет собой подробный, без излишеств, отличный материал, который в одинаковой степени может заинтересовать и профессионалов и просто тех, кому данная тематика интересна. Считаю данная часть статьи обязательно должна быть опубликована, а автору пожелаю дальнейших успехов! До встречи в рамках анонсированной автором работы по MD6!

  • Крюков А.Н.Крюков А.Н.
    Рязанское высшее воздушно-десантное командное училище им. В.Ф.Маргелова
    преподаватель
Предлагаемая для рецензирования статья Сергея Петровича Панасенко завершает блестящий цикл статей, посвящённых криптоанализу уязвимостей алгоритма хэширования MD5. В ней автор полностью самостоятельно, с рисунками и перечнем из 14 иностранных источников рассматривает последние работы в этой области, раскрывает найденные уязвимости и предлагает пользователям быстрее отказываться от использования MD5 в приложениях, имеющих важное значение. Показаны варианты модификации алгоритмов создания стойких хэш-функций с использованием в качестве промежуточных операндов результатов преобразования входных данных. Предлагается к последующей публикации цикл статей, посвящённых алгоритму MD6. Публикация имеет практическую ценность как для специалистов, так и для студентов, изложена коротко, профессиональным языком, и может быть использована как основа для других работ.

Ваши комментарии:

Для того, чтобы оставлять коментарии, Вам нужно авторизоваться на Sec.Ru. Если У Вас еще нет аккаунта, пройдите процедуру регистрации.


Автор

Информация

  • Снимай крутую видеорекламу - выкладывай на Sec.Ru!

    Рекламный ролик - один из самых эффективных способов донесения информации. И он отлично подходит для рекламирования любой продукции, в т.ч. и продукции рынка систем безопасности.
    Поэтому редакция Портала решила составить свой рейтинг лучших рекламных видеороликов. Все они разные и все чем-то покоряют: красотой, задумкой, стилем съемки, посылом, необычным финалом.
    Некоторые из них язык не повернется назвать иначе как шедевром короткого метра. Смотрим, наслаждаемся, делаем заметки, учимся творить рекламу правильно.
    Если Вы хотите выложить видеоролик о своей продукции на Sec.Ru, пишите о своем желании на adv@sec.ru!

    Картинка: Jpg, 100x150, 16,47 Кбайт

    Мотор!

Отраслевые СМИ

Все права защищены 2002 – 2016
Rambler's Top100 �������@Mail.ru