25 июня 2012
Алгоритм хэширования MD4: обзор применений
В предыдущих статьях было приведено подробное описание алгоритма хэширования MD4, а также дан обзор результатов его криптоанализа. Данная статья посвящена обзору основных применений алгоритма MD4, который весьма широко использовался в различных сетевых протоколах и приложениях.
Криптографические стандарты PKCS
Широчайшее распространение алгоритма MD4 во многом проистекало благодаря тому, что MD4 был предусмотрен как один из трех алгоритмов хэширования (наряду с алгоритмами MD2 и MD5), используемых в стандарте PKCS #1 (Public-Key Cryptography Standard) [1]. Данный стандарт является первым из семейства имеющих мировое признание стандартов компании RSA, посвященных асимметричным криптографическим алгоритмам и связанным с ними протоколам.
Алгоритм MD4 появился в версии 1.5 стандарта PKCS #1, вышедшей в начале 1998 г. [1]. В тексте стандарта было отмечено, что «не известно причины, по которой алгоритм MD4 не должен использоваться в схемах электронной подписи с очень большими требованиями к безопасности, но поскольку MD4 был разработан как исключительно быстрый, он находится «на грани» в смысле риска успешных криптоаналитических атак». Следовательно, несмотря на отсутствие прямых атак на полнораундовый MD4, его использование в критичных схемах электронной подписи может быть поставлено под сомнение. До определения окончательного статуса алгоритма MD4 рекомендуется в таких случаях использовать MD5 или MD2 (с учетом крайне низкого быстродействия последнего).
Уже в октябре того же 1998 г. вышла версия 2.0 стандарта PKCS #1 [2], в которой был отмечен значительный прогресс в криптоанализе MD4, в результате которого авторами стандарта было рекомендовано отказаться от использования данного алгоритма. Алгоритмы хэширования MD2 и MD5 были оставлены для совместимости с существующими применениями, а в качестве основного алгоритма предполагалось использование стандарта хэширования США SHA-1 [3].
Одноразовые пароли
Еще одно широко известное применение алгоритма хэширования MD4 – в качестве основной однонаправленной функции (допускалось также использование алгоритма MD5) в системе одноразовых паролей S/KEY [4].
В системе S/KEY предполагается, что однонаправленная функция используется для генерации N одноразовых паролей на основе исходного пароля пользователя и случайного значения, которое клиент системы S/KEY должен получить у сервера (см. рис. 1). В дальнейшем сгенерированные (или динамически генерируемые) одноразовые пароли передаются в обратном порядке серверу – сначала N-й одноразовый пароль, затем – N-1-й и т. д. Сервер, получив очередной пароль, однократно применяет к нему функцию хэширования и сравнивает с предыдущим полученным паролем – эквивалентность данных значений означает успешную аутентификацию для клиента. Система позволяет проводить парольную аутентификацию, не передавая исходный пароль пользователя по сети, что несравнимо безопаснее обычной парольной аутентификации.
Рис. 1 Одноразовые пароли S/KEY
В последующих версиях системы одноразовых паролей используемые однонаправленные функции сменялись в соответствии с результатами их криптоанализа:
- в документах [5] (1996 г.) и [6] (1998 г.) в качестве обязательного алгоритма хэширования в системе одноразовых паролей установлен алгоритм SHA, а алгоритмы MD4 и MD5 стали опциональными;
- авторы текущей версии системы одноразовых паролей [7] отошли от прямого использования алгоритма хэширования в качестве однонаправленной функции; вместо этого в системе используется алгоритм ключевого хэширования HMAC, являющийся надстройкой над алгоритмом хэширования [8] (HMAC будет описан в следующей статье данного цикла); в качестве единственного варианта однонаправленной функции в [7] предписано использование алгоритма HMAC-SHA-1.
Протоколы аутентификации
Алгоритм хэширования MD4 активно применялся и в различных протоколах аутентификации. Приведем несколько примеров.
Несмотря на то, что к 2005 г. алгоритм MD4 уже считался взломанным, в спецификации алгоритмов шифрования и контроля целостности для широко используемого протокола аутентификации Kerberos версии 5 [9] от 2005 г. MD4 указан в качестве одного из основных алгоритмов контроля целостности (правда, не в чистом виде, а с HMAC-надстройкой).
Поскольку алгоритм MD4 используется в операционных системах семейства Microsoft Windows NT для однонаправленной обработки пользовательских паролей, он неявно используется в чистом виде в ряде протоколов аутентификации, используемых в данных операционных системах, например:
- в варианте протокола Kerberos 5 для Microsoft Windows [10]; в качестве основного алгоритма хэширования в данном варианте Kerberos предполагается использование HMAC-MD5, в том числе, по причине наличия сомнений в криптостойкости алгоритма HMAC-MD4 (отметим, что использование MD4 без HMAC-надстройки еще менее безопасно);
- в расширении протокола CHAP (Challenge-Handshake Authentication Protocol), используемом для аутентификации при установлении PPP-соединений (Point-to-Point Protocol) в Microsoft Windows [11].
Генерация псевдослучайных чисел
Вышедший в 1994 г. документ [12] содержал рекомендации разработчикам систем защиты в части генерации псевдослучайных чисел, для чего, среди прочих алгоритмов хэширования, рекомендовалось использовать алгоритм MD4 (хотя и с оговоркой, что он слабее остальных рекомендуемых алгоритмов). Удивительно, что в существенно более поздней редакции данного документа [13], вышедшей в 2005 г. (когда недостаточная криптостойкость MD4 уже была явной), из списка рекомендуемых алгоритмов исчез алгоритм MD2, но MD4 остался практически с той же оговоркой. При этом, в документе [13] в качестве обоснования потенциальной слабости MD4 были указаны атаки на два раунда данного алгоритма, но не были рассмотрены уже известные к тому времени атаки на полнораундовый MD4 (например, описанная в [14]).
Заключение
Практически во всех применениях алгоритма MD4 можно наблюдать один и тот же цикл с незначительными вариациями:
- сначала алгоритм MD4 рекомендуется к использованию (возможно, наряду с другими алгоритмами хэширования);
- впоследствии появляются примечания о его вероятно недостаточной криптостойкости совместно с рекомендациями использовать данный алгоритм только для совместимости с существующими реализациями; основным алгоритмом хэширования становится какой-либо из алгоритмов, считающихся более стойким на тот момент времени (обычно MD5 или SHA-1);
- наконец, MD4 исключается из списка рекомендуемых или обязательных для реализации.
Алгоритм MD4 все еще достаточно широко используется, однако видно, что его жизненный цикл подошел к концу и алгоритм в ближайшем будущем будет представлять только исторический интерес. Статус «исторический» был присвоен алгоритму MD4 в 2011 г. [15]
Литература
- Kaliski B. RFC 2313. PKCS #1: RSA Encryption. Version 1.5. // http://tools.ietf.org – March 1998 – RSA Laboratories East.
- Kaliski B., Staddon J. RFC 2437. PKCS #1: RSA Cryptography Specifications. Version 2.0. // http://tools.ietf.org – October 1998 – RSA Laboratories.
- FIPS PUB 180-1. Secure Hash Standard. // http://www.itl.nist.gov – National Institute of Standards and Technology – 1995 April 17.
- Haller N. RFC 1760. The S/KEY One-Time Password System. // http://tools.ietf.org – February 1995 – Bellcore.
- Haller N., Metz C. RFC 1938. A One-Time Password System. // http://tools.ietf.org – May 1996.
- Haller N., Metz C., Nesser P., Straw M. RFC 2289. A One-Time Password System. // http://tools.ietf.org – February 1998.
- M’Raihi D., Bellare M., Hoornaert F., Naccache D., Ranen O. RFC 4226. HOTP: An HMAC-Based One-Time Password Algorithm. // http://tools.ietf.org – December 2005.
- Krawczyk H., Bellare M., Canetti R. RFC 2104. HMAC: Keyed-Hashing for Message Authentication. // http://tools.ietf.org – February 1997.
- Raeburn K. RFC 3961. Encryption and Checksum Specifications for Kerberos 5. // http://tools.ietf.org – February 2005 – MIT.
- Jaganathan K., Zhu L., Brezak J. RFC 4757. The RC4-HMAC Kerberos Encryption Types Used By Microsoft Windows. // http://tools.ietf.org – December 2006 – Microsoft Corporation.
- Zorn G. RFC 2759. Microsoft PPP CHAP Extensions, Version 2. // http://tools.ietf.org – January 2000 – Microsoft Corporation.
- Eastlake D. 3rd, Crocker S., Schiller J. RFC 1750. Randomness Recommendations for Security. // http://tools.ietf.org – December 1994.
- Eastlake D. 3rd, Schiller J., Crocker S. RFC 4086. Randomness Requirements for Security. // http://tools.ietf.org – June 2005.
- Dobbertin H. Cryptanalysis of MD4 (Abstract). // http://www.springerlink.com – German Information Security Agency, Bonn, Germany – 23 October 1995 – Journal of Cryptology (1998) 11: 253-271.
- Turner S., Chen L. RFC 6150. MD4 to Historic Status. // http://tools.ietf.org – March 2011.
