13 февраля 2012

Алгоритм хэширования MD2: применение, быстродействие и криптоаналитические исследования
Часть 2

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

Быстродействие MD2

Алгоритм MD2 является весьма медленным по сравнению с другими известными алгоритмами хэширования. Приведенные в работе [1] данные по скорости хэширования различными алгоритмами таковы:

Алгоритм	Скорость хэширования, кбит/сек.
MD2	78
SHA	710
RIPEMD	1334
MD5	1849
MD4	2669

Из таблицы видно, что по быстродействию алгоритм MD2, как минимум, на порядок уступает другим широко используемым алгоритмам хэширования. Приведенные в таблице данные подтверждаются и другими источниками, в частности, измерениями быстродействия различных реализаций алгоритмов хэширования, выполненных в рамках проекта eBASH (ECRYPT Benchmarking of All Submitted Hashes) [2]. Проект eBASH является частью проекта eBACS (ECRYPT Benchmarking of Cryptographic Systems), посвященного измерению производительности различных криптографических алгоритмов [3]. Отметим, что поскольку алгоритм MD2 является байт-ориентированным, на 8-битных платформах скорость MD2 не так низка по сравнению с другими алгоритмами, как, например, на 32-битных платформах.
Тем не менее, можно сделать вывод, что MD2 является крайне медленным алгоритмом хэширования.

Обзор криптоаналитических исследований

В 1994 г. Брюс Шнайер (Bruce Schneier) написал про алгоритм MD2, что, хотя он и более медленный, чем другие алгоритмы хэширования, но на текущий момент является криптографически стойким [4]. С тех пор криптоаналитики достигли существенных успехов в анализе MD2; сейчас алгоритм считается взломанным. Рассмотрим прогресс в криптоанализе алгоритма MD2.
Барт Пренел (Bart Preneel) в работе [5] отметил, что, поскольку последние 32 байта внутреннего состояния алгоритма не используются в выходном хэш-значении, можно пропустить обновление этих байтов в последней итерации обработки внутреннего состояния для последнего блока входных данных. При этом стоит отметить, что реализации алгоритма MD2, представленные в его спецификации [6-7], выполняют и эти операции, результат которых не учитывается в выходном значении алгоритма.
В той же работе [5] отмечается, что количество раундов алгоритма (18) всего на один раунд превышает минимально возможное для того, чтобы выходное значение алгоритма могло достигать всех возможных из 2¹²⁸ вариантов. Следовательно, можно сделать вывод, что запас криптостойкости алгоритма является минимальным и что невозможно без потери стойкости увеличить скорость хэширования путем уменьшения количества раундов. Барт Пренел также предложил методику проведения атак на полнораундовый MD2 с использованием дифференциального криптоанализа, но не описал конкретных атак на алгоритм.
В 1995 г. был предложен метод поиска коллизий¹ в функции сжатия алгоритма MD2, который, однако, не был распространен на весь алгоритм благодаря наличию контрольной суммы, дополняющей хэшируемые данные [8]. Вообще, в ряде работ, посвященных криптоанализу MD2 (например, в [9]) отмечается, что благодаря оригинальному дизайну алгоритма MD2, к данному алгоритму неприменимы известные результаты криптоанализа хэш-функций с классической структурой. Тем не менее, в 2006 г. компания RSA в [10] порекомендовала не использовать алгоритм MD2 в тех новых приложениях, в которых требуется отсутствие коллизий. Там же отмечается, что в остальных случаях использование MD2 остается безопасным.
Первую атаку на алгоритм MD2 целиком предложил в 2004 г. Фредерик Мюллер (Frederic Muller) в работе [9]. Прежде всего, он предложил атаки на функцию сжатия алгоритма со следующими требованиями к ресурсам:

Цель атаки	Трудоемкость	Требуемая память
Поиск прообраза²	2⁹⁵	2³⁸
Поиск псевдо-прообраза³	2⁷³	2⁷⁸

Фредерику Мюллеру удалось распространить данную атаку на полный алгоритм MD2 и предложить атаку, позволяющую найти прообраз с трудоемкостью 2¹⁰⁴ операций. Данная трудоемкость существенно меньше теоретической трудоемкости поиска прообраза для MD2, которая составляет 2¹²⁸ операций, из чего Мюллер делает вывод, что алгоритм MD2 можно считать взломанным, хотя стоит заметить, что трудоемкость атаки является все же слишком большой для возможности осуществления данной атаки на практике.
Результаты Мюллера были существенно улучшены в 2005 г. Ларсом Кнудсеном (Lars R. Knudsen) и Джоном Матиассеном (John E. Mathiassen) [11]. Они предложили следующие атаки на алгоритм MD2:

Цель атаки	Трудоемкость
Поиск псевдо-коллизии⁴	2¹⁶
Поиск псевдо-прообраза	2⁹⁵
Поиск прообраза	от 2^97,6

Кроме уменьшения требуемой трудоемкости, данные атаки позволяют также для каждого вида атак варьировать размерами искомых сообщений, тогда как атака Мюллера позволяла находить прообразы только размером в 128 блоков по 16 байтов. При этом трудоемкость атаки, направленной на поиск прообраза, растет при уменьшении размера искомого прообраза; минимальный прообраз в этом случае может иметь размер в 43 блока при трудоемкости его поиска в 2^112,2 операций. Отметим, что атаки Кнудсена и Матиассена, направленные на поиск прообраза, по-прежнему являются неприменимыми на практике из-за большой трудоемкости.
Следующий шаг в криптоанализе MD2 сделал Сорен Томсен (Soren S. Thomsen) в 2008 г., существенно улучшив атаки, направленные на поиск прообраза [12]. Атака Томсена требует 2⁷³ операций; следовательно, данную трудоемкость можно считать уже находящейся на грани реально достижимой для проведения практической атаки на алгоритм.
В 2009 г. авторы предыдущих работ по криптоанализу алгоритма MD2 выпустили совместную работу [13], в которой улучшили собственные результаты в части нахождения коллизий для алгоритма MD2 целиком. Предложенный криптоаналитиками метод атаки на MD2 позволяет находить коллизии с трудоемкостью 2^63,3 операций, что несколько меньше теоретической трудоемкости поиска коллизий в 2⁶⁴ операций.
На текущий момент (январь 2012 г.) результаты работы [13] не были улучшены; какие-либо дальнейшие криптоаналитические исследования алгоритма MD2 не получили широкой известности.

Где применялся алгоритм MD2

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

Протокол защищенной электронной почты PEM (Privacy-Enhanced Mail), изначально определенный в [14] (подробное описание можно найти также в [4]). Спецификация криптоалгоритмов, используемых в PEM, была определена в [6], где в качестве единственного алгоритма хэширования (но не единственного алгоритма контроля целостности) предполагалось использовать MD2. В последующих версиях протокола PEM [15] наряду с MD2 предполагалось использовать также алгоритм хэширования MD5.
Алгоритм MD2 использовался наряду с алгоритмами MD5 и SHA-1 в инфраструктуре открытых ключей (Public Keys Infrastructure, PKI); однако, уже в спецификации PKI 1999 года [16], в частности, сказано, что MD2 должен использоваться только в целях совместимости со старыми приложениями, в новых же следует применять алгоритмы SHA-1 и MD5.
Широко используемый стандарт асимметричных криптоопераций PKCS #1 (Public Key Cryptography Standard) разрешал использование шести алгоритмов хэширования: MD2, MD5, SHA-1, SHA-256, SHA-384 и SHA-512, причем MD2 и MD5 – только в целях совместимости со старыми приложениями [17].

Таких примеров существенно больше – MD2 использовался в различных версиях различных протоколов и в множестве других применений (достаточно большой список применений можно найти, например, в [18]). MD2 пока не взломан, но, предвидя дальнейший прогресс в криптоанализе MD2 и предполагая, что полная отмена данного алгоритма с переходом на какой-либо более стойкий алгоритм хэширования займет годы, эксперты IETF (Internet Engineering Task Force) в марте 2011 г. в документе [18] порекомендовали не использовать MD2 в дальнейшем и во всех приложениях, применяющих MD2, реализовать более стойкий алгоритм (например, алгоритм SHA-256 [19]). Таким образом, после выполнения данной рекомендации алгоритм MD2 будет представлять только исторический интерес.

¹ Поиск коллизии – это поиск двух различных сообщений, результаты хэширования которых эквивалентны.

² Поиск прообраза – это поиск сообщения, результат хэширования которого равен заданному значению. Контексты применения различных видов атак на алгоритмы хэширования подробно обсуждаются, в частности, в [10].

³ Аналогично поиску прообраза, но с произвольным начальным значением (т. е. с не обязательно нулевым начальным заполнением внутреннего состояния алгоритма).

⁴ Аналогично поиску коллизии, но при произвольных начальных значениях (т. е. при не обязательно нулевых начальных заполнениях внутреннего состояния), в том числе, не совпадающих для двух сообщений, для которых ищется псевдо-коллизия.

Литература

Bakhtiari S., Safavi-Naini R., Pieprzyk J. Practical and Secure Message Authentication. // http://citeseerx.ist.psu.edu – April 27, 1995 – University of Wollongong.
eBASH: ECRYPT Benchmarking of All Submitted Hashes. // http://bench.cr.yp.to.
eBACS: ECRYPT Benchmarking of Cryptographic Systems. // http://bench.cr.yp.to.
Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. – Пер. с англ.: М.: Издательство ТРИУМФ, 2002 – 816 с.
Preneel B. Analysis and Design of Cryptographic Hash Functions. // http://homes.esat.kuleuven.be – February 2003.
Linn J. RFC 1115. Privacy Enhancement for Internet Electronic Mail: Part III -- Algorithms, Modes, and Identifiers. // http://tools.ietf.org – August 1989 – DEC.
Kaliski B. RFC 1319. The MD2 Message-Digest Algorithm. // http://tools.ietf.org – April 1992 – RSA Laboratories.
Rogier N., Chauvaud P. MD2 is not Secure without the Checksum Byte. Abstract. // http://ehash.iaik.tugraz.at – 1995.
Muller F. The MD2 Hash Function is Not One-Way. // http://www.ssi.gouv.fr – DCSSI Crypto Lab.
Robshaw M. J. B. On Recent Results for MD2, MD4 and MD5. // ftp://ftp.rsa.com – RSA Laboratories’ Bulletin. – Number 4 – November 12, 1996.
Knudsen L. R., Mathiassen J. E. Preimage and Collision Attacks on MD2. // http://www.ii.uib.no.
Thomsen S. S. An improved preimage attack on MD2. // http://eprint.iacr.org – 2008 – Technical University of Denmark.
Knudsen L. R., Mathiassen J. E., Muller F., Thomsen S. S. Cryptanalysis of MD2. // http://www.springerlink.com – Journal of Cryptology, 2010, 23, pp. 72-90 – International Association for Cryptologic Research, 2009.
Linn J. RFC 989. Privacy Enhancement for Internet Electronic Mail: Part I: Message Encipherment and Authentication Procedures. // http://tools.ietf.org – February 1987 – IAB Privacy Task Force.
Balenson D. RFC 1423. Privacy Enhancement for Internet Electronic Mail: Part III: Algorithms, Modes, and Identifiers. // http://tools.ietf.org – February 1993.
Housley R., Ford W., Polk W., Solo D. RFC 2459. Internet X.509 Public Key Infrastructure Certificate and CRL Profile. // http://tools.ietf.org – January 1999.
Jonsson J., Kaliski B. RFC 3447. Public-Key Cryptography Standards (PKCS) #1: RSA Cryptography Specifications Version 2.1. // http://tools.ietf.org – February 2003 – RSA Laboratories.
Turner S., Chen L. MD2 to Historic Status. // http://tools.ietf.org – March 2011.
FIPS PUB 180-2. Secure Hash Standard. // http://www.securitytechnet.com – 2002 August 1 – National Institute of Standards and Technology.