Криптография, защита компьютерных данных: информация, исследования, аналитика, экспертиза

Rambler's Top100

OZON.ru

Перейти на главную страницу

Карта сайта

Список статей

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

© Сергей Панасенко, 2013

 

В 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]:

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

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

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

где:

 

  1. Подключ K1 разбивается на 4 фрагмента по 32 бита K1[0]…K1[3].

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

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

K2 || K2 XOR X0 || K2 XOR X1 || K2 XOR X2,

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

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

Константы 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]):

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

где:

 

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

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).

Подобные комбинированные алгоритмы (и их варианты) используются не так уж редко – в качестве примера в [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]. Опишем мультиколлизии, для чего введем следующие обозначения:

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

  1. В качестве начального значения переменных состояния h0 используется стандартный вектор иниициализации алгоритма.
  2. В цикле по i от 1 до t выполняются следующие действия:

f(hi-1Bi) = f(hi-1Bi’);

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

(b1, …, btpad),

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

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

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

Общая трудоемкость атаки на комбинированный алгоритм 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. – 19.03.2012 г.
  7. Панасенко С. Алгоритм хэширования MD5. // Sec.ru. – 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. – 17.01.2013 г.
  15. McDonald C., Hawkes P., Pieprzyk J. Differential Path for SHA-1 with complexity O(252). // http://eprint.iacr.org.

Рисунки:

  1. Схема алгоритма MD5-MAC.
  2. Комбинированный алгоритм MD5 || SHA-1.
  3. Мультиколлизия.
  4. Коллизия для алгоритма MD5 || SHA-1.

Предыдущая часть статьи

Следующая часть статьи