Рейтинг@Mail.ru

25 сентября 2013

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

В 2008-2009 гг. вышло еще несколько работ, посвященных анализу различных применений алгоритма MD5.

Прежде всего, отметим работу [1], авторы которой предложили новую атаку, позволяющую вычислить секретный ключ алгоритма NMAC-MD5 (предыдущие атаки на алгоритмы HMAC-MD5 и NMAC-MD5 рассматривались в четвертой части статьи).

Для успешной атаки требуется 245 блоков данных при трудоемкости 2100 операций, что находится за гранью практической применимости. Кроме того, как и предыдущие атаки, данная атака использует связанные ключи, что резко сужает возможности ее применения. Тем не менее, работа [1] в очередной раз показала недостаточный запас криптостойкости надстроек HMAC и NMAC и их зависимость от криптографических свойств нижележащих хэш-функций.

Интересный аспект опубликованной в [1] атаки состоит в том, что для ее успешного проведения атакующему достаточно знания не полных, а усеченных до 64 битов выходных значений алгоритма NMAC-MD5, что является частой практикой при применении данных надстроек.

В том же году вышла работа [2], в которой также была представлена новая атака на алгоритм NMAC-MD5. В отличие от всех опубликованных ранее атак на HMAC-MD5 и NMAC-MD5, ее авторы использовали near-коллизии вместо коллизий, что позволило им существенно снизить трудоемкость вычислений (до 275 операций) за счет значительного увеличения требуемых для проведения атаки блоков данных – до 275 (общая ресурсоемкость атаки при этом снижается по сравнению с атакой, опубликованной в [1], с 2100 до 276). В данной атаке также используются связанные ключи, что, вместе с высокими требованиями к ресурсам, делает атаку также неприменимой на практике.

В 2009 г. коллектив авторов из Китая опубликовал работу [3], в которой, в числе прочего, анализировался алгоритм MD5-MAC.

Данный алгоритм является частным случаем алгоритма аутентификации данных MDx-MAC, который был предложен еще в 1995 г. как надстройка над алгоритмами хэширования семейства MD известными криптологами Бартом Пренелом (Bart Preneel) и Полом Ван Оршотом (Paul Van Oorschot) в работе [4] (алгоритм MDx-MAC запатентован его авторами – см. [5]).

Разрабатывая MDx-MAC, эксперты пытались создать криптографически стойкий и быстрый алгоритм, требования к структуре которого были сформулированы ими следующим образом [4]:

  • секретный ключ должен участвовать в вычислениях в начале и конце алгоритма, а также на каждой итерации используемого алгоритма хэширования;
  • отличия от используемого алгоритма хэширования должны быть минимальными (прежде всего, для упрощения реализации алгоритма);
  • потери производительности по сравнению с используемым алгоритмом хэширования должны быть минимальны;
  • дополнительные требования к ресурсам также должны быть минимальными;
  • данный алгоритм должен позволять использовать любые алгоритмы хэширования, соответствующие схеме Меркля-Дамгаарда (подробно обсуждалась в [6]).

Рассмотрим подробно алгоритм MD5-MAC. Помимо собственно хэшируемых данных, параметром алгоритма является секретный ключ K, который расширяется на 3 подключа K0K2 следующим образом:

  1. Если K имеет размер меньше 128 бит, он дополняется до данного размера путем конкатенации с самим собой необходимое количество раз. Из результата конкатенации (или из исходного ключа, если его размер больше или равен 128 бит) выбираются левые 128 бит, которые обозначим как K’.
  2. Подключи K0K2 вычисляются из K’ так:

Ki = MD5’(K’ || Ui || K’),

где:

  • || – операция конкатенации;
  • MD5’() – алгоритм хэширования, аналогичный MD5, но без дополнения входных данных;
  • Ui – модифицирующие константы, определение которых будет дано далее.
  • Подключ K1 разбивается на 4 фрагмента по 32 бита K1[0]…K1[3].

Алгоритм MD5-MAC представляет собой модифицированный следующим образом алгоритм MD5 (см. рис. 1, на котором h() обозначает функцию сжатия алгоритма MD5-MAC):

  • Вместо стандартного вектора инициализации алгоритма используется K0.
  • Модифицирующие константы Tj , используемые на каждой итерации алгоритма MD5 (j – номер итерации, см. [7]), заменяются значениями Tj + K1[i] mod 232, где i – номер раунда алгоритма MD5, считая с 0.
  • После последнего блока хэшируемых данных (т. е. блока, содержащего дополнение и размер данных) обрабатывается дополнительный блок, содержащий следующие данные:

K2 || K2 ⊕ X0 || K2 ⊕ X1 || K2 ⊕ X2 ,

где X0X2 – дополнительные константы (см. далее).

В качестве выходного значения используются m левых бит результата; авторы [4] рекомендуют m = 64.

Рис. 1 Схема алгоритма MD5-MAC

Константы Ui и Xi определены через дополнительные константы R и S0S2, первая из которых представляет собой 62-байтовую строку «ab…yzAB…YZ01…89», а константы Si (также строковые) приведены в таблице:

S0

«11»

S1

«22»

S2

«33»

Xi и Ui вычисляются из R и S0S2 по следующим формулам:

Xi = MD5’(Si || R),

Ui = Xi || Xi+1 mod 3 || Xi+2 mod 3 || Xi || Xi+1 mod 3 || Xi+2 mod 3

Шестнадцатеричные значения X0X2 приведены в таблице согласно [4]:

X0

97 ef 45 ac 29 0f 43 cd 45 7e 1b 55 1c 80 11 34

X1

b1 77 ce 96 2e 72 8e 7c 5f 5a ab 0a 36 43 be 18

X2

9d 21 b4 21 bc 87 b9 4d a2 9d 27 bd c7 5b d7 c3

MD5-MAC выглядит существенно более усиленным по сравнению с классическими конструкциями образования MAC на основе хэш-функций (все три варианты ранее были признаны небезопасными [4, 8]):

  • «секретный префикс» (secret prefix):

MAC(km) = hash(k || m),

где:

  • k – ключ;
  • m – сообщение;
  • hash() – нижележащая бесключевая хэш-функция;
  • «секретный суффикс» (secret suffix):

MAC(km) = hash(m || k);

  • «конверт» (envelope):

MAC(k1k2, m) = hash(k1 || m || k2),

где подключи k1 и k2 являются различными.

В рассматриваемой работе [3] представлена атака, позволяющая вычислить один из подключей алгоритма MD5-MAC – K1 – путем применения коллизий, эквивалентных используемым в технологии «IV Bridge», которая обсуждалась в шестой части статьи. Трудоемкость атаки весьма велика – 297 операций вычисления MAC; кроме того, знания K1 недостаточно для какого-либо практического использования атаки (знание K1 не позволяет, в частности, определить значения K0 или K2). Тем не менее, атака показала недостаточный запас криптостойкости алгоритма MDx-MAC при использовании недостаточно стойкой функции хэширования.

Крайне интересное исследование выполнили в 2009 г. специалисты из Технологического Университета г. Грац, Австрия (Graz University of Technology), результаты которого опубликованы в работе [9]. Они проанализировали криптостойкость комбинированного алгоритма хэширования MD5 || SHA-1, под которым подразумевается конкатенация результатов хэширования одних и тех же данных алгоритмами MD5 и SHA-1 [10] (см. рис. 2).

Рис. 2 Комбинированный алгоритм MD5 || SHA-1

Подобные комбинированные алгоритмы (и их варианты) используются не так уж редко – в качестве примера в [9] приводится протокол защищенной передачи данных TLS (Transport Layer Security) версий 1.0 [11] и 1.1 [12], в котором одновременно используются именно алгоритмы MD5 и SHA-1 (однако, в другой комбинации).

Причина использования комбинации алгоритмов хэширования состоит в принципиальном повышении криптостойкости по сравнению с любым из участвующих в комбинации алгоритмов, поскольку, даже если один из алгоритмов будет полностью взломан (в части нахождения коллизий), найденная коллизия для данного алгоритма крайне маловероятно окажется коллизией для другого алгоритма связки. Следовательно, для успешной атаки на комбинированный алгоритм необходим успешный поиск коллизии для каждого из входящих в комбинацию алгоритмов хэширования, и ранее (в 2004 г. в работе [13]) было доказано, что ориентир для трудоемкости такой атаки – трудоемкость поиска коллизии для алгоритма с максимальным размером хэша, т. е. 280 для связки MD5 || SHA-1, поскольку SHA-1 вычисляет 160-битные хэш-значения.

Авторам работы [9] удалось значительно снизить трудоемкость поиска коллизии для комбинированного алгоритма MD5 || SHA-1 – до значения, меньшего теоретической трудоемкости поиска коллизии для алгоритма с минимальным размером хэша (264 для MD5), а именно, до 260 операций. Они использовали для атаки следующий вид коллизии: при различных заданных префиксах сообщений (приводящих к различным значениям переменных состояния AiDi и Ai’…Di’) требуется найти такое (эквивалентное для обоих сообщений) значение блока данных Mi, чтобы в результате получилась коллизия (данный вид коллизии обсуждался нами ранее – см., например, рис. 1 в [14]). Трудоемкость поиска такой коллизии существенно выше трудоемкости поиска коллизии с различающимися дополнениями, но именно коллизия с эквивалентными дополнениями была необходима для атаки.

Кроме того, в работе [9] были использованы мультиколлизии, предложенные ранее в уже упоминавшейся работе [13]. Опишем мультиколлизии, для чего введем следующие обозначения:

  • f(ab) – функция сжатия алгоритма хэширования, где a – предыдущее значение переменных состояния, а b – обрабатываемый блок данных; предполагается, что функция сжатия является слабой, т. е., в данном случае, существует эффективный метод поиска коллизий для данной функции сжатия;
  • hi – значение переменных состояния на i-й итерации (см. далее);
  • Bi и Bi’ – блоки сообщений, дающие коллизию на i-й итерации;
  • t – количество итераций (определяется атакующим, исходя из требований атаки).

Тогда алгоритм поиска мультиколлизий выглядит следующим образом:

  1. В качестве начального значения переменных состояния h0 используется стандартный вектор иниициализации алгоритма.
  2. В цикле по i от 1 до t выполняются следующие действия:
    • определяется значение блоков Bi и Bi’, дающих коллизию функции сжатия:
    • f(hi-1Bi) = f(hi-1Bi’);

    • текущим значением переменных состояния становится значение f(hi-1Bi).
  3. После выполнения цикла атакующий получает 2t сообщений с эквивалентным хэш-значением (мультиколлизия – см. рис. 3), каждое из которых имеет следующий вид:

(b1, …, btpad),

где bi – это одно из значений Bi и Bi’, а pad – стандартное дополнение сообщения.

Рис. 3 Мультиколлизия

В результате авторы работы [9] предложили атаку, позволяющую найти пару сообщений, дающих одновременно коллизию как для алгоритма MD5, так и для алгоритма SHA-1 (см. рис. 4):

  1. Сначала выполняется поиск мультиколлизии для алгоритма SHA-1. Авторы работы [9] исходили из предположения, что существует эффективный метод поиска коллизий для алгоритма SHA-1 с трудоемкостью 252 операций (именно такова была трудоемкость атаки по поиску коллизий для полнораундового алгоритма SHA-1, опубликованной в 2009 г. в [15]). Тогда трудоемкость поиска мультиколлизии, дающей 264 сообщений, составляет 252 * 64 = 258 операций (см. выше).
  2. Полученные в результате поиска мультиколлизии сообщения используются для поиска дающего коллизии дополнительного блока (как было сказано ранее, эквивалентного для обоих сообщений, следовательно, не нарушающего коллизию для SHA-1). В результате поиска определяются два из 264 сообщений и дополнительный блок, формирующие результирующую коллизию для комбинированного алгоритма.

Рис. 4 Коллизия для алгоритма MD5 || SHA-1

Общая трудоемкость атаки на комбинированный алгоритм MD5 || SHA-1 определяется трудоемкостью поиска коллизии описанного выше типа для MD5, которая (260 операций) не только меньше теоретической трудоемкости поиска коллизий перебором для SHA-1, но и меньше таковой для MD5.

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

Продолжение следует

 

Литература

  1. Rechberger C., Rijmen V. New Results on NMAC/HMAC when Instantiated with Popular Hash Functions. // http://www.jucs.org – Journal of Universal Computer Science, vol. 14, no 3 (2008), 347-376 – Graz University of Technology, Austria.
  2. Wang L., Ohta K., Kunihiro N. New Key-Recovery Attacks on HMAC/NMAC-MD4 and NMAC-MD5. // http://www.iacr.org – The University of Electro-Communications, Tokyo, Japan.
  3. Wang X., Yu H., Wang W., Zhang H., Zhan T. Cryptanalysis on HMAC/NMAC-MD5 and MD5-MAC. // http://www.iacr.org.
  4. Preneel B., van Oorschot P. C. MDx-MAC and Building Fast MACs from Hash Functions. // ftp://ftp.esat.kuleuven.be – August 1995.
  5. Preneel B. K. B., Van Oorschot P. C. U. S. Patent #5 664 016. Method of Building Fast MACs from Hash Functions. Sep. 2, 1997.
  6. Панасенко С. Алгоритм хэширования MD4. // Sec.ru. – http://daily.sec.ru/publication.cfm?pid=32437 – 19.03.2012 г.
  7. Панасенко С. Алгоритм хэширования MD5. // Sec.ru. – http://daily.sec.ru/publication.cfm?pid=35484 – 13.08.2012 г.
  8. Preneel B. Analysis and design of cryptographic hash functions. // http://homes.esat.kuleuven.be – February 2003.
  9. Mendel F., Rechberger C., Schlaffer M. MD5 is Weaker than Weak: Attacks on Concatenated Combiners. // http://online.tugraz.at – 2009 – Graz University of Technology, Austria.
  10. FIPS PUB 180-1. Secure Hash Standard. // http://www.itl.nist.gov – National Institute of Standards and Technology – 1995 April 17.
  11. Dierks T., Allen C. RFC 2246. The TLS Protocol. Version 1.0. // http://tools.ietf.org – Certicom – January 1999.
  12. Dierks T., Rescorla E. RFC 4346. The Transport Layer Security (TLS) Protocol. Version 1.1. // http://tools.ietf.org – April 2006.
  13. Joux A. Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions. // http://wb.cecs.pdx.edu – DCSSI Crypto Lab, Paris, France – 2004.
  14. Панасенко С. Обзор атак на алгоритм хэширования MD5: поиск коллизий, часть 4. // Sec.ru. – http://daily.sec.ru/publication.cfm?pid=38374 – 17.01.2013 г.
  15. McDonald C., Hawkes P., Pieprzyk J. Differential Path for SHA-1 with complexity O(252). // http://eprint.iacr.org.

 

Об авторе:

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

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

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

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

Автор статьи продолжает повествование на ранее заявленную тему. В рамках данного материала приводятся примеры опубликованных способов атак, с одной стороны, не имеющих применения на практике, но, с другой стороны, характеризующих наличие слабых сторон алгоритма NMAC-MD5. Помимо этого рассматривается алгоритм MD5-MAC и пример, теоретически показывающий его недостаточную криптостойкость. Также в представленном материалы приводится информация в отношении комбинированных алгоритмов: в чем преимущество их использования, а также результаты исследования их криптостойкости на примере алгоритма MD5||SHA-1. Материал снабжен необходимыми пояснениями, ссылками на первоисточники, дополнен иллюстрациями. Полагаю данный материал может быть интересен как специалистам в области криптографии, так и интересующимся вопросами криптоанализа и рекомендуется к публикации.

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

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

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


Автор

Информация

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

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

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

    Мотор!

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

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