25 сентября 2013

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

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

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

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

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

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

В 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 подключа K₀…K₂ следующим образом:

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

K_i = MD5’(K’ || U_i || K’),

где:

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

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

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

K₂ || K₂ ⊕ X₀ || K₂ ⊕ X1 || K2 ⊕ X₂ ,

где X₀…X₂ – дополнительные константы (см. далее).

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

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

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

S₀	«11»
S₁	«22»
S₂	«33»

X_i и U_i вычисляются из R и S₀…S₂ по следующим формулам:

X_i = MD5’(S_i || R),

U_i = X_i || X_i_+1 mod 3 || X_i_+2 mod 3 || X_i || X_i_+1 mod 3 || X_i_+2 mod 3

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

X₀	97 ef 45 ac 29 0f 43 cd 45 7e 1b 55 1c 80 11 34
X₁	b1 77 ce 96 2e 72 8e 7c 5f 5a ab 0a 36 43 be 18
X₂	9d 21 b4 21 bc 87 b9 4d a2 9d 27 bd c7 5b d7 c3

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

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

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

где:

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

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

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

MAC(k₁, k₂, m) = hash(k₁ || m || k₂),

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

В рассматриваемой работе [3] представлена атака, позволяющая вычислить один из подключей алгоритма MD5-MAC – K₁ – путем применения коллизий, эквивалентных используемым в технологии «IV Bridge», которая обсуждалась в шестой части статьи. Трудоемкость атаки весьма велика – 2⁹⁷ операций вычисления MAC; кроме того, знания K1 недостаточно для какого-либо практического использования атаки (знание K₁ не позволяет, в частности, определить значения K₀ или K₂). Тем не менее, атака показала недостаточный запас криптостойкости алгоритма 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]) было доказано, что ориентир для трудоемкости такой атаки – трудоемкость поиска коллизии для алгоритма с максимальным размером хэша, т. е. 2⁸⁰ для связки MD5 || SHA-1, поскольку SHA-1 вычисляет 160-битные хэш-значения.

Авторам работы [9] удалось значительно снизить трудоемкость поиска коллизии для комбинированного алгоритма MD5 || SHA-1 – до значения, меньшего теоретической трудоемкости поиска коллизии для алгоритма с минимальным размером хэша (2⁶⁴ для MD5), а именно, до 2⁶⁰ операций. Они использовали для атаки следующий вид коллизии: при различных заданных префиксах сообщений (приводящих к различным значениям переменных состояния A_i…D_i и A_i’…D_i’) требуется найти такое (эквивалентное для обоих сообщений) значение блока данных M_i, чтобы в результате получилась коллизия (данный вид коллизии обсуждался нами ранее – см., например, рис. 1 в [14]). Трудоемкость поиска такой коллизии существенно выше трудоемкости поиска коллизии с различающимися дополнениями, но именно коллизия с эквивалентными дополнениями была необходима для атаки.

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

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

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

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

определяется значение блоков B_i и B_i’, дающих коллизию функции сжатия:

f(h_i_-1, B_i) = f(h_i_-1, B_i’);

текущим значением переменных состояния становится значение f(h_i_-1, B_i).

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

(b₁, …, b_t, pad),

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

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

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

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

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

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

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

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

Литература

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.
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.
Wang X., Yu H., Wang W., Zhang H., Zhan T. Cryptanalysis on HMAC/NMAC-MD5 and MD5-MAC. // http://www.iacr.org.
Preneel B., van Oorschot P. C. MDx-MAC and Building Fast MACs from Hash Functions. // ftp://ftp.esat.kuleuven.be – August 1995.
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.
Панасенко С. Алгоритм хэширования MD4. // Sec.ru. – http://daily.sec.ru/publication.cfm?pid=32437 – 19.03.2012 г.
Панасенко С. Алгоритм хэширования MD5. // Sec.ru. – http://daily.sec.ru/publication.cfm?pid=35484 – 13.08.2012 г.
Preneel B. Analysis and design of cryptographic hash functions. // http://homes.esat.kuleuven.be – February 2003.
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.
FIPS PUB 180-1. Secure Hash Standard. // http://www.itl.nist.gov – National Institute of Standards and Technology – 1995 April 17.
Dierks T., Allen C. RFC 2246. The TLS Protocol. Version 1.0. // http://tools.ietf.org – Certicom – January 1999.
Dierks T., Rescorla E. RFC 4346. The Transport Layer Security (TLS) Protocol. Version 1.1. // http://tools.ietf.org – April 2006.
Joux A. Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions. // http://wb.cecs.pdx.edu – DCSSI Crypto Lab, Paris, France – 2004.
Панасенко С. Обзор атак на алгоритм хэширования MD5: поиск коллизий, часть 4. // Sec.ru. – http://daily.sec.ru/publication.cfm?pid=38374 – 17.01.2013 г.
McDonald C., Hawkes P., Pieprzyk J. Differential Path for SHA-1 with complexity O(252). // http://eprint.iacr.org.