Генерация псевдослучайных чисел

Вышедший в 1994 г. документ [12] содержал рекомендации разработчикам систем защиты в части генерации псевдослучайных чисел, для чего, среди прочих алгоритмов хэширования, рекомендовалось использовать алгоритм MD4 (хотя и с оговоркой, что он слабее остальных рекомендуемых алгоритмов). Удивительно, что в существенно более поздней редакции данного документа [13], вышедшей в 2005 г. (когда недостаточная криптостойкость MD4 уже была явной), из списка рекомендуемых алгоритмов исчез алгоритм MD2, но MD4 остался практически с той же оговоркой. При этом, в документе [13] в качестве обоснования потенциальной слабости MD4 были указаны атаки на два раунда данного алгоритма, но не были рассмотрены уже известные к тому времени атаки на полнораундовый MD4 (например, описанная в [14]).

Заключение

Практически во всех применениях алгоритма MD4 можно наблюдать один и тот же цикл с незначительными вариациями:

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

Алгоритм MD4 все еще достаточно широко используется, однако видно, что его жизненный цикл подошел к концу и алгоритм в ближайшем будущем будет представлять только исторический интерес. Статус «исторический» был присвоен алгоритму MD4 в 2011 г. [15]

 

Литература

1. Kaliski B. RFC 2313. PKCS #1: RSA Encryption. Version 1.5. // http://tools.ietf.org – March 1998 – RSA Laboratories East.
2. Kaliski B., Staddon J. RFC 2437. PKCS #1: RSA Cryptography Specifications. Version 2.0. // http://tools.ietf.org – October 1998 – RSA Laboratories.
3. FIPS PUB 180-1. Secure Hash Standard. // http://www.itl.nist.gov – National Institute of Standards and Technology – 1995 April 17.
4. Haller N. RFC 1760. The S/KEY One-Time Password System. // http://tools.ietf.org – February 1995 – Bellcore.
5. Haller N., Metz C. RFC 1938. A One-Time Password System. // http://tools.ietf.org – May 1996.
6. Haller N., Metz C., Nesser P., Straw M. RFC 2289. A One-Time Password System. // http://tools.ietf.org – February 1998.
7. 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.
8. Krawczyk H., Bellare M., Canetti R. RFC 2104. HMAC: Keyed-Hashing for Message Authentication. // http://tools.ietf.org – February 1997.
9. Raeburn K. RFC 3961. Encryption and Checksum Specifications for Kerberos 5. // http://tools.ietf.org – February 2005 – MIT.
10. 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.
11. Zorn G. RFC 2759. Microsoft PPP CHAP Extensions, Version 2. // http://tools.ietf.org – January 2000 – Microsoft Corporation.
12. Eastlake D. 3rd, Crocker S., Schiller J. RFC 1750. Randomness Recommendations for Security. // http://tools.ietf.org – December 1994.
13. Eastlake D. 3rd, Schiller J., Crocker S. RFC 4086. Randomness Requirements for Security. // http://tools.ietf.org – June 2005.
14. 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.
15. Turner S., Chen L. RFC 6150. MD4 to Historic Status. // http://tools.ietf.org – March 2011.

 

 

Обзор результатов криптоанализа алгоритмов HMAC-MD4 и NMAC-MD4

Данная статья завершает исторический обзор, посвященный алгоритму хэширования MD4. Она описывает результаты криптоанализа алгоритмов аутентификации сообщений на основе MD4: HMAC-MD4 и NMAC-MD4. Конструкции HMAC и NMAC были подробно описаны в предыдущей статье.

Начало атакам на алгоритм HMAC-MD4 положила работа [1], авторы которой сделали вывод о том, что атаки на MD4 могут быть расширены на HMAC-MD4. Это справедливо и для HMAC-алгоритмов, основанных на других алгоритмах хэширования, вопреки существовавшему на тот момент (2006 г.) мнению, что HMAC-надстройка существенно меняет контекст атаки на нижележащий алгоритм хэширования, делая невозможным применение существующих атак на алгоритм к его HMAC-варианту.

Авторы работы [1] предложили альтернативное графическое представление алгоритма HMAC, которое (для одноблочного сообщения M) приведено на рис. 1.

Рис. 1 Графическое представление HMACдля одноблочного сообщения

Для атаки на HMAC используется дифференциальный криптоанализ, в котором применяются квартеты одноблочных сообщений M_i, M_i ’, M_j и M_j ’ с определенной разностью a:

M_i ⊕ M_i ’ = M_j ⊕ M_j ’ = a,

причем сообщения M_i и M_j выбираются случайным образом.

Каждая четверка сообщений проверяется на наличие коллизии, т. е. справедливо ли следующее равенство применительно к выходным значениям алгоритма HMAC C_i, C_i ’, C_j и C_j ’:

C_i ⊕ C_j = C_i ’ ⊕ C_j ’ = 0 или C_i ⊕ C_j ’ = C_i ’ ⊕ C_j = 0.

Схема такой коллизии приведена на рис. 2 (на рисунке не показаны ключевые элементы, разности показаны прерывистыми линиями).

Рис. 2 Коллизия для квартета одноблочных сообщений

В части криптоанализа алгоритмов HMAC-MD4 и NMAC-MD4 в работе [1] были достигнуты следующие результаты:

• для атаки на HMAC-MD4, позволяющей без знания секретного ключа найти корректную пару «сообщение – код аутентификации данного сообщения» с вероятностью успеха 93 %, необходимо наличие 258 выбранных сообщений и результатов их обработки алгоритмом HMAC-MD4;
• полностью аналогичным образом можно атаковать и алгоритм NMAC-MD4.

Анализ HMAC и NMAC был независимо выполнен в работе [2], вышедшей в том же 2006 г., в которой также было показано, что слабая функция хэширования может скомпрометировать HMAC и NMAC, построенные на ее основе, а также любые другие вышележащие конструкции при их недостаточной криптостойкости.

Авторы [2] использовали найденные ранее коллизии для алгоритма MD4 при построении коллизии для внутренней функции хэширования HMAC- или NMAC-MD4, т. е. для функции hash(k 1, m) при использовании NMAC. Схема такой внутренней коллизии двух многоблочных сообщений M 1 и M 2 для HMAC-варианта приведена на рис. 3. Как отмечено в [2], внешняя функция хэширования скрывает результат выполнения внутренней функции, но не может скрыть факт возникновения такой внутренней коллизии (поскольку в случае внутренней коллизии совпадут выходные значения HMAC или NMAC).

Рис. 3 Внутренняя коллизия алгоритма HMAC

Следующий шаг атаки – создание набора специально выбранных сообщений, внутренние коллизии на которых позволят полностью определить значение внутреннего секретного ключа (т. е. h(k ⊕ C 1) в HMAC или k 1 в NMAC). В результате авторы [2] предложили следующие атаки на HMAC-MD4 и NMAC-MD4:

• 2⁵⁸ операций достаточно для нахождения корректной пары «сообщение – код аутентификации данного сообщения» без знания секретного ключа;
• 2⁶³ операций достаточно для вычисления внутреннего секретного ключа.

Отметим, что относительно невысокая трудоемкость данных атак делает возможной их практическую реализацию. Поэтому (это указано и в [2]) алгоритмы HMAC-MD4 и NMAC-MD4 после публикации данных результатов следовало как можно быстрее перестать использовать.

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

Еще одна универсальная методика атак на HMAC и NMAC была предложена в работе [3] (2007 г.). Суть методики в использовании коллизий алгоритма хэширования, лежащего в основе HMAC/NMAC, для нахождения вектора инициализации данного алгоритма. Поскольку в HMAC/NMAC в качестве вектора инициализации используется секретный ключ (в NMAC) либо результат его обработки функцией сжатия алгоритма хэширования (в HMAC), данная атака позволяет:

• для NMAC – определить значения секретных ключей k 1 и k 2;
• для HMAC – определить значения h(k ⊕ C 1) и h(k ⊕ C 2), знания которых (без знания значения k) достаточно для последующей подделки кодов аутентификации сообщений, т. е. данный случай можно считать эквивалентным полному раскрытию секретного ключа алгоритма HMAC.

В частности, в [3] описана атака на алгоритмы HMAC-MD4 и NMAC-MD4, позволяющая вычислить описанные выше ключевые элементы данных алгоритмов. Для успешной реализации атаки необходимы значения HMAC/NMAC 288 выбранных сообщений; вычислительная трудоемкость атаки составляет 295 операций.

Результаты предыдущей работы были усилены авторами вышедшей в следующем году работы [4], в которой было предложено для вычисления ключа использовать не коллизии, а near-коллизии, которые существенно проще получить. В результате количество данных, необходимых для успешной атаки, было снижено с 2⁸⁸ до 2⁷² сообщений и результатов их обработки алгоритмом HMAC/NMAC, а трудоемкость атаки была снижена с 2⁹⁵ до 2⁷⁷ операций.

Какие-либо последующие работы, посвященные анализу HMAC-MD4 и NMAC-MD4, не получили широкой известности. Последние достижения в криптоанализе данных алгоритмов показывают явную зависимость криптостойкости HMAC и NMAC от криптостойкости нижележащих алгоритмов хэширования. Поскольку активный криптоанализ HMAC и NMAC продолжается, в ближайшие годы возможно дальнейшее усиление результатов работы [4], которые пока находятся за гранью практической применимости.

 

Литература:

1. Kim J., Biryukov A., Preneel B., Hong S. On the Security of HMAC and NMAC Based on HAVAL, MD4, MD5, SHA-0, and SHA-1. // http://eprint.iacr.org – 2006.
2. Contini S., Yin Y. L. Forgery and Partial Key-Recovery Attacks on HMAC and NMAC Using Hash Collisions. // http://www.iacr.org – 2006.
3. Fouque P.-A., Leurent G., Nguyen P. Q. Full Key-Recovery Attacks on HMAC/NMAC-MD4 and NMAC-MD5. // http://C_iteseerx.ist.psu.edu – Ecole Normale Superieure, Paris, France – 2007.
4. 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 – 2008.

 

Алгоритм хэширования MD6: обзор криптоаналитических исследований

 

Сергей Панасенко,
зам. директора Фирмы «АНКАД»
по науке и системной интеграции,
кандидат технических наук

 

В отличие от широко распространенного алгоритма MD5, криптоанализу которого было посвящено множество работ, алгоритм MD6 распространения, практически, не получил, в результате чего он привлек несравнимо меньшее внимание криптоаналитиков. Широкую известность получило относительно немного работ по криптоанализу данного алгоритма.

 

Начало исследованиям алгоритма MD6 положила магистерская диссертация [1] одного из авторов алгоритма – Кристофера Кратчфилда (Christopher Crutchfield). Данная работа вышла еще до опубликования самого алгоритма – в июне 2008 г. Она была целиком посвящена обоснованию достаточной криптостойкости алгоритма MD6; основные положения данной работы вошли в опубликованную в октябре 2008 г. спецификацию алгоритма [2].

В начале 2009 г. вышли две работы Дмитрия Ховратовича (Dmitry Khovratovich) и его коллег из университета Люксембурга [3-5]. Авторы данных работ смогли представить внутреннее состояние функции сжатия алгоритма MD6 в виде системы линейных уравнений и применить впоследствии для ее решения метод Гаусса. В результате криптоанализа было доказано, что выполнением до 33 раундов внутреннего преобразования функции сжатия (напомним, что алгоритм MD6-160 выполняет 80 раундов – см. подробное описание MD6 в [6]) вырабатывается последовательность, не обладающая характеристиками псевдослучайной. Теоретически, данный метод можно использовать для последующего нахождения коллизий усеченной функции сжатия алгоритма.

В феврале 2009 г. вышла также работа [7], авторами которой были несколько криптологов из числа авторов алгоритма MD6. В данной работе они доказали, что полнораундовая функция сжатия алгоритма MD6, как и алгоритм целиком, вырабатывают последовательности, не отличимые от псевдослучайных. Авторы [7] сделали вывод об отсутствии в алгоритме MD6 структурных слабостей, из-за которых, в частности, были бы необходимы какие-либо ограничения на использование алгоритма.

Тогда же, в феврале 2009 г., Шахрам Хазей (Shahram Khazaei) и Уилли Мейер (Willi Meier) опубликовали коллизию функции сжатия алгоритма MD6, усеченной до 16 раундов, приводящую также к near-коллизии функции сжатия, усеченной до 19 раундов включительно. Трудоемкость вычисления коллизии составляла 2³⁰ операций при незначительных требованиях к памяти [5, 8] (детали атаки подробно описаны в [9] и [10]). В июле 2009 г. результаты Хазея и Мейера были усилены Томасом Ходанеком (Thomas Hodanek), который ускорил атаку на 16-раундовую функцию сжатия до 2¹⁷ операций [11].

1 июля 2009 г. авторы алгоритма MD6 направили в NIST комментарий [12], содержащий список их собственных замечаний относительно алгоритма MD6 и конкурса SHA-3, в котором данный алгоритм участвовал. Несмотря на то, что в документе [12] (см. также [13]) было сказано, что «NIST вправе выбрать алгоритм MD6 в следующий раунд конкурса при желании», документ, фактически, представлял собой отзыв данного алгоритма с конкурса SHA-3, как минимум, по следующим причинам:

• по мнению авторов MD6, алгоритм SHA-3 должен быть не медленнее, чем аналогичный алгоритм семейства SHA-2; для того, чтобы удовлетворить данному условию, количество раундов функции сжатия алгоритма MD6 необходимо было бы уменьшить до порядка 30-40 вместо текущих 80-168 (в зависимости от параметров алгоритма – см. [6]);
• авторы алгоритма нашли незначительную ошибку в собственном доказательстве стойкости MD6 против дифференциального криптоанализа, которое было ранее опубликовано в [1] и [2]; в результате, появилась необходимость нового доказательства данного свойства алгоритма MD6, в том числе, с учетом требуемого уменьшения количества раундов функции сжатия алгоритма;
• наконец, как написали авторы MD6 в [13], им неизвестны какие-либо успешные результаты атак на данный алгоритм, но «в настоящий момент MD6 не соответствует нашим собственным стандартам, соответствие которым мы считаем обязательным для SHA-3, поэтому лучше, если NIST поищет среди других алгоритмов».

После этого не выглядит удивительным тот факт, что алгоритм MD6 не был выбран во второй раунд конкурса SHA-3 [14].

В том же 2009 вышла работа [15], в которой были предложены следующие атаки на усеченные версии алгоритма MD6:

• авторы работы применили предложенную годом ранее в [16] «кубическую атаку» (cube attack, один из вариантов алгебраического криптоанализа) к ключевой версии алгоритма MD6, усеченной до 14 раундов; данная атака позволила вычислить 128-битный ключ алгоритма с трудоемкостью около 2²² операций;
• путем модификации кубической атаки, авторы работы получили технологию «кубического тестирования» (cube tester), позволившую им создать различитель (алгоритм, позволяющий отличить атакуемую функцию от случайно и равновероятно выбранной функции) для 18-раундового алгоритма MD6 (трудоемкость – 2¹⁷ операций); различитель предложен также для незначительно модифицированного (с нулевыми раундовыми константами S_j – см. [6]) алгоритма MD6 с 66 раундами (2²⁴ операций).

Последней из получивших широкую известность работ, посвященных криптоанализу алгоритма MD6, была вышедшая в 2011 г. работа Этана Хейлмана (Ethan Heilman) [17]. Автор данной работы предложил новые доказательства достаточной криптостойкости алгоритма MD6 против дифференциального криптоанализа; доказанный запас криптостойкости алгоритма MD6 по сравнению с доказанным ранее авторами алгоритма был увеличен в два раза. Таким образом, выводы авторов алгоритма оего недостаточной криптостойкости, изложенные в [12], были опровергнуты. Тем не менее, вернуть алгоритм MD6 в список участников второго раунда конкурса SHA-3 было уже поздно: алгоритм MD6 выбыл из конкурса и, как одно из следствий, не получил широкого распространения.

 

Данная статья завершает серию публикаций, посвященных алгоритмам хэширования семейства MD. Автор выражает благодарность коллективу портала по безопасности Sec.ru за предоставленную возможность опубликования данной серии статей и активное в этом содействие, а также благодарность экспертам за время, потраченное на анализ статей цикла, и предоставленные экспертные оценки, отзывы и замечания.

 

Литература

1. Crutchfield C. Y. Security Proofs for the MD6 Hash Function Mode of Operation. // http://csrc.nist.gov – Massachusetts Institute of Technology – June 2008.
2. Rivest R. L., Agre B., Bailey D. V., Crutchfield C., Dodis Y., Fleming K. E., Khan A., Krishnamurthy J., Lin Y., Reyzin L., Shen E., Sukha J., Sutherland D., Tromer E., Yin Y. L. The MD6 hash function. A proposal to NIST for SHA-3. // http://csrc.nist.gov – Massachusetts Institute of Technology, Cambridge, MA – October 27, 2008.
3. Khovratovich D., Biryukov A., Nikolic I. Gaussian Cryptanalysis of Hash Functions: Collisions and Distinguishers. // http://www.dagstuhl.de – University of Luxembourg – 16 January 2009.
4. Khovratovich D. Nonrandomness of the 33-round MD6. // http://fse2009rump.cr.yp.to – University of Luxembourg – 2009.
5. The ECRYPT Hash Function Website. MD6. // http://ehash.iaik.tugraz.at.
6. Панасенко С. Алгоритм хэширования MD6. // Sec.ru. – http://daily.sec.ru/publication.cfm?pid=43766 – 22.11.2013 г.
7. Dodis Y., Reyzin L., Rivest R. L., Shen E. Indifferentiability of Permutation-Based Compression Functions and Tree-Based Modes of Operation, with Applications to MD6. // http://groups.csail.mit.edu.
8. Khazaei S. Сообщение в NIST от 24 февраля 2009 г. // http://ehash.iaik.tugraz.at.
9. Brier E., Khazaei S., Meier W., Peyrin T. Linearization Framework for Collision Attacks: Application to CubeHash and MD6 (Extended Version). // http://eprint.iacr.org.
10. Khazaei S. Neutrality-Based Symmetric Cryptanalysis. // http://infoscience.epfl.ch – Ecole Polytechnique Federale de Lausanne, Suisse, 2010.
11. Hodanek T. Analysis of Reduced MD6 – Abstract. // http://events.iaik.tugraz.at – Graz University of Technology, Austria.
12. Rivest R. L. OFFICIAL COMMENT: MD6. // http://groups.csail.mit.edu – 01 Jul 2009.
13. The MD6 Hash Algorithm. // http://groups.csail.mit.edu.
14. Regenscheid A., Perlner R., Chang S., Kelsey J., Nandi M., Paul S. Status Report on the First Round of the SHA-3 Cryptographic Hash Algorithm Competition. // http://csrc.nist.gov – National Institute of Standards and Technology, Gaithersburg, MD – September 2009.
15. Aumasson J.-P., Dinur I., Meier W., Shamir A. Cube Testers and Key Recovery Attacks on Reduced-Round MD6 and Trivium. // http://iacr.org – 2009.
16. Dinur I., Shamir A. Cube Attacks on Tweakable Black Box Polynomials. // http://eprint.iacr.org – 2008.
17. Heilman E. Restoring the Differential Resistance of MD6. // http://eprint.iacr.org – September 21, 2011.