Исследования после конкурса AES

 

Как и предполагали эксперты, после принятия алгоритма Rijndael в качестве стандарта AES попытки вскрытия данного алгоритма существенно усилились.

Можно сказать, что криптоанализ алгоритма AES стал развиваться, в основном, в следующих четырех направлениях:

Во-первых, попытки усиления «классических» атак или применения других известных атак к данному алгоритму. Например, работа [6] описывает атаку методом бумеранга на 6-раундовую версию алгоритма со 128-битным ключом, для выполнения которой требуется 2³⁹ выбранных открытых текстов, 2⁷¹ шифртекстов с адаптивным выбором и 2⁷¹ операций шифрования.

Во-вторых, применение различных методов криптоанализа на связанных ключах, в частности:

· В работе [33] предложено несколько вариантов атак на связанных ключах на 7- и 8-раундовый AES-192 с использованием невозможных дифференциалов.

· Комбинация метода бумеранга и связанных ключей предложена в работе [3]: 9-раундовый AES-192 атакуется при наличии 2⁷⁹ выбранных открытых текстов, каждый из которых шифруется на 256 связанных ключах, выполнением 2¹²⁵ операций шифрования; для атаки на 10-раундовый AES-256 требуется 2^114,9 выбранных открытых текстов (включая зашифрование на 256 связанных ключах) и 2^171,8 операций. Данная атака использует слабость процедуры расширения ключа, состоящую в ее недостаточной нелинейности.

· Эта атака была усилена в работе [17], в которой, в частности, предлагается атака на 10-раундовый алгоритм AES-192, для которой требуется 2¹²⁵ выбранных открытых текстов (на 256 связанных ключах) и 2^146,7 операций.

Несмотря на то, что предложенные атаки на связанных ключах являются весьма непрактичными, настораживает тот факт, что атаке подвержены уже 10 из 12 раундов алгоритма AES-192 (и это после всего 5 лет после принятия стандарта AES!) – возникает опасение, что эксперты (указывающие на недостаточность раундов в алгоритме Rijndael) были правы и полнораундовый алгоритм AES будет вскрыт существенно раньше, чем предполагали эксперты институтаNIST.

В-третьих, многие исследования посвящены алгебраической структуре алгоритма Rijndael, например:

· В работе [16] найдены линейные соотношения в таблице замен Rijndael (т.е. в единственном нелинейном элементе алгоритма). Однако, как и в других аналогичных работах, каких-либо практических возможностей использования данного свойства не предложено.

· Как показано в работе [15], зашифрование с помощью Rijndael можно выразить относительно (особенно по сравнению с другими «серьезными» алгоритмами шифрования) простой формулой. Авторы не нашли практического применения данной формулы, но предположили, что она будет использована в реальных атаках в течение ближайших примерно 20 лет.

· В работе [21] показано, что вскрытие алгоритма AES эквивалентно решению системы квадратичных уравнений в конечном поле GF(2⁸).

Попытки использования алгебраических свойств алгоритма для его вскрытия были названы «алгебраическими атаками» [9]. Стоит отметить, что были и работы с попытками доказательства того факта, что простая структура алгоритма AES не ухудшает его криптостойкости, например, [30].

В-четвертых, больше всего исследований посвящено атакам, использующим информацию, полученную по побочным каналам:

· Много работ содержат примеры успешного вскрытия различных реализаций полнораундового алгоритма AES с помощью атак по времени исполнения (например, [1]), потребляемой мощности (например, [20]) и атак на основе сбоев (например, [26]). Автор [1] (данная работа описывает успешное вскрытие сервера OpenSLL, использующего для шифрования алгоритм AES), в частности, считает, что эксперты NIST при выборе Rijndael в качестве AES допустили весьма серьезную ошибку, посчитав, что время выбора значения из таблицы замен является константной величиной в конкретной реализации; вывод автора таков: выбор Rijndael, скорее всего, был ошибочным.

· Не меньше исследований (например, [10, 28]) посвящено безопасным (т.е. защищенным от утечек данных по побочным каналам) программным или аппаратным реализациям AES.

Весьма большой список работ, посвященных side-channel-атакам на AES и методам защиты от них, можно найти, например, на ресурсе [32], посвященном криптоанализу AES.

 

Заключение

 

Итак, на май 2007 г., по прошествии всего 6 лет после принятия алгоритма Rijndael в качестве стандарта AES, криптоаналитики весьма серьезно продвинулись во вскрытии данного алгоритма:

· Предложена теоретическая атака уже на 10 раундов (из 12) алгоритма AES-192.

· Существует множество примеров вскрытия реализаций алгоритма AES с помощью side-channel-атак.

Не правда ли, все это производит впечатление, что эксперты NIST могли ошибиться в выборе алгоритма-победителя конкурса AES?

 

 

1. Bernstein D.J. Cache-timing attacks on AES. // http://cr.yp.to – 2005.04.14 – The University of Illinois at Chicago.

2. Biham E. Comment on Selecting the Cipher for the AES Second Round. // http://csrc.nist.gov – Technion – Israel Institute of Technology, Haifa, Israel.

3. Biham E., Dunkelman O., Keller N. Related-Key Boomerang and Rectangle Attacks. // http://vipe.technion.ac.il – 2005.

4. Biham E., Keller N. Cryptanalysis of Reduced Variants of Rijndael. // http://csrc.nist.gov – Technion – Israel Institute of Technology, Haifa, Israel.

5. Biham E., Shamir A. Power Analysis of the Key Scheduling of the AES Candidates. // http://csrc.nist.gov.

6. Biryukov A., The Boomerang Attack on 5 and 6-round Reduced AES. // http://www.cosic.esat.kuleuven.be – 2004 – Katholieke Universiteit Leuven, Heverlee, Belgium.

7. Chari S., Jutla C., Rao J.R., Rohatgi P. A Cautionary Note Regarding Evaluation of AES Candidates on Smart-Cards. // http://csrc.nist.gov – I.B.M. J.T.Watson Research Center, Yorktown Heights, USA.

8. Cheon J.H., Kim M., Kim K., Lee J.-Y., Kang S. Improved Impossible Differential Cryptanalysis of Rijndael and Crypton. // http://citeseer.ist.psu.edu – 2001.

9. Courtois N.T. Is AES a Secure Cipher. // http://www.cryptosystem.net.

10. Courtois N.T., Goubin L. An Algebraic Masking Method to Protect AES Against Power Attacks. // http://eprint.iacr.org.

11. Daemen J., Knudsen L., Rijmen V. The Block Cipher Square. // http://www.esat.kuleuven.ac.be.

12. Daemen J., Rijmen V. Answer to “new observations on Rijndael”. // http://www.esat.kuleuven.ac.be – August 11, 2000.

13. Daemen J., Rijmen V. AES Proposal: Rijndael. // http://csrc.nist.gov – Document version 2 – 03/09/99.

14. Ferguson N., Kelsey J., Lucks S., Schneier B., Stay M., Wagner D., Whiting D. Improved Cryptanalysis of Rijndael. // http://www.schneier.com.

15. Ferguson N., Schroeppel R., Whiting D. A simple algebraic representation of Rijndael. // http://citeseer.ist.psu.edu – Draft 2001/05/16.

16. Fuller J., Millan W. On Linear Redundancy in the AES S-box. // http://eprint.iacr.org – 2002 – Queensland University of Technology, Brisbane, Australia.

17. Kim J. Combined Differential, Linear and Related-Key Attacks on Block Ciphers and MAC Algorithms. // http://www.cosic.esat.kuleuven.be – November 2006 – Katholieke Universiteit Leuven.

18. Knudsen L.R. Some thoughts on the AES process. // http://csrc.nist.gov – April 15, 1999.

19. Lucks S. Attacking Seven Rounds of Rijndael under 192-bit and 256-bit Keys. // http://citeseer.ist.psu.edu – University of Mannheim, Germany.

20. Mangard S., Pramstaller N., Oswald E. Successfully Attacking Masked AES Hardware Implementations. // http://www.iaik.tu-graz.ac.at – 2005 – Graz University of Technology, Austria.

21. Murphy S., Robshaw M.J.B. Essential Algebraic Structure Within the AES. // http://citeseer.ist.psu.edu – University of London, Egham, U.K.

22. Murphy S., Robshaw M. Further Comments on the Structure of Rijndael. // http://www.isg.rhul.ac.uk – University of London, Egham, U.K. – 17 August, 2000.

23. Murphy S., Robshaw M. New Observations on Rijndael.Preliminary Draft. // http://www.isg.rhul.ac.uk – University of London, Egham, U.K. – 7 August, 2000.

24. Nechvatal J., Barker E., Bassham L., Burr W., Dworkin M., Foti J., Roback E. Report on the Development of the Advanced Encryption Standard (AES). // http://csrc.nist.gov – National Institute of Standards and Technology.

25. Nechvatal J., Barker E., Dodson D., Dworkin M., Foti J., Roback E. Status report on the first round of the development of the advanced encryption standard. // http://csrc.nist.gov – National Institute of Standards and Technology.

26. Peacham D., Thomas B. A DFA attack against the AES key schedule. // http://www.siventure.com – 26 October 2006 – SiVenture.

27. Schneier B., Kelsey J., Whiting D., Wagner D., Hall C., Ferguson N., Kohno T., Stay M. The Twofish Team’s Final Comments on AES Selection. // http://csrc.nist.gov – May 15, 2000.

28. Schramm K., Paar C. Higher Order Masking of the AES. // http://www.crypto.ruhr-uni-bochum.de – 2006 – Ruhr University Bochum, Germany.

29. Schroeppel R. AES Comments. // Public Comments Regarding The Advanced Encryption Standard (AES) Development Effort. Round 2 Comments – http://csrc.nist.gov – University of Arizona – May 15, 2000.

30. Song B., Seberry J. Further Observations on the Structure of the AES Algorithm. // http://citeseer.ist.psu.edu – University of Wollongong, Australia.

31. Tang J. A Survey of Cryptanalysis of Rijndael. // http://www.cs.auckland.ac.nz – The University of Auckland.

32. The AES Lounge. // http://iaik.tu-graz.ac.at.

33. Wentao Z., Wenling W., Lei Z., Dengguo F. Improved Related-Key Impossible Differential Attacks on Reduced-Round AES-192. // http://www.lois.cn – 2006 – Chinese Academy of Science, Beijing, China.

 

 

Об авторе:

Панасенко Сергей Петрович, нач. отдела разработки программного обеспечения фирмы АНКАД, кандидат технических наук.

С автором можно связаться: по телефонам (495)532-1313, (495)531-0000

или по E-mail [email protected]

http://www.panasenko.ru

 

Алгоритм хэширования MD2
Часть 1

Данная статья начинает цикл статей, посвященных алгоритмам хэширования семейства MD (Message Digest). Алгоритмы MD2, MD4, MD5 и MD6 широко известны; первые три из них широко использовались и продолжают широко использоваться, несмотря на то, что существуют известные криптоаналитические атаки против каждого из них.
Алгоритмы MD обладают различными характеристиками; они разработаны в разные годы известным криптологом Рональдом Ривестом (Ronald Rivest) с участием некоторых других специалистов RSA Laboratories – научного подразделения компании RSA Data Security Inc.
Первая из статей данного цикла посвящена алгоритму MD2 и описывает его структуру. MD2 (который изначально назывался RSA-MD2) является первым из широко известных алгоритмов семейства MD. Существует и алгоритм MD1 (он же RSA-MD1), который, однако, является закрытым, его спецификация не опубликована. Алгоритм MD1 упоминается, в частности, в известной работе [1], а в [2] сказано, что RSA-MD1 – «закрытый алгоритм, практически идентичный алгоритму RSA-MD2».

Алгоритм хэширования MD2 был разработан в 1988 г. для использования в качестве одного из криптографических алгоритмов, входящих в стандарт защищенной электронной почты PEM (Privacy-Enhanced Mail); его реализация на языке Си была приведена в RFC 1115 [3]. Впоследствии спецификация и обновленная реализация MD2 были опубликованы в RFC 1319 [4].

MD2 хэширует данные переменного размера с получением 128-битного выходного значения. Прежде всего, выполняется дополнение входных данных до размера, кратного 16 байтам (дополнение выполняется и в том случае, когда исходный размер сообщения кратен 16 байтам), следующим образом: в конец сообщения добавляется определенное количество (n) байтов (от 1 до 16); значение каждого дополняемого байта равно n (например, дополнение 27-байтного сообщения состоит из 5 байтов, каждый из которых содержит значение 5).
Затем вычисляется 16-байтная контрольная сумма сообщения, которая также дополняет сообщение перед его дальнейшей обработкой. Контрольная сумма вычисляется следующим образом: для каждого 16-байтного блока дополненного сообщения 16 раз выполняются следующие действия:

c = M [ i * 16 + j ],

C [ j ] = S [ c L ] C [ j ],

L = C[ j ],

где:
i – номер 16-байтного блока данных;
j – номер текущего шага цикла;
M [ x ] – x -й байт сообщения, т. е. M [ i * 16 + j ] – это j -й байт текущего блока данных;
с и L – временные переменные, L изначально содержит значение 0;
C [ j ] – j -й байт массива контрольной суммы; перед вычислением контрольной суммы массив содержит нулевые байты;
S – табличная замена, определенная следующим образом:

41

Псевдослучайное заполнение таблицы сформировано значениями дробной части числа?. Каждая n -я ячейка таблицы содержит значение S [ n ], 0? n? 255. Данная таблица используется и в функции сжатия алгоритма MD2.
Функция сжатия использует 48-байтное внутреннее состояние X [0]… X [47], которое обнуляется перед началом вычислений. Каждый 16-байтный i -й блок дополненного сообщения, включая блок контрольной суммы, накладывается на внутреннее состояние следующим образом:

1. Блок данных копируется в состояние следующим образом:

X [16 + j ] = M [ i * 16 + j ], j = 0…15,

X [32 + j ] = (X [16 + j ] X [ j ]), j = 0…15.

Таким образом, если представить внутреннее состояние как 3 фрагмента по 16 байт, то после копирования блока данных второй из фрагментов состояния содержит обрабатываемый блок данных, а третий – результат применения побитовой операции «исключающее или» (XOR) к текущему содержимому первого фрагмента и блока данных (см. рис. 1).

Рис. 1 Копирование блока данных в состояние

1. Выполняется обработка состояния, которая состоит из 18 раундов преобразований, в рамках каждого из которых выполняется обновление каждого байта состояния следующим образом:

X [ k ] = (X [ k ] S [ t ]), k = 0…47,

t = X [ k ],

где t – временная переменная, которая изначально имеет нулевое значение, а после выполнения каждого j -го раунда (j = 0…17) t модифицируется:
t = t + j mod 256.
После обработки всех блоков сообщения в первом 16-байтном фрагменте состояния X [0]… X [15] находится результирующее хэш-значение алгоритма.

Отметим, что алгоритм MD2 является крайне простым в реализации.

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

Литература

1. Preneel B. Analysis and Design of Cryptographic Hash Functions. // http://homes.esat.kuleuven.be – February 2003.
2. Dusse S. R., Kaliski B. S. Jr. A Cryptographic Library for the Motorola DSP56000. // http://ftp.zedz.net – 1998 – RSA Data Security Inc.
3. Linn J. RFC 1115. Privacy Enhancement for Internet Electronic Mail: Part III -- Algorithms, Modes, and Identifiers. // http://tools.ietf.org – August 1989 – DEC.
4. Kaliski B. RFC 1319. The MD2 Message-Digest Algorithm. // http://tools.ietf.org – April 1992 – RSA Laboratories.

 

 

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

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

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

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

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

Из таблицы видно, что по быстродействию алгоритм 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	295	238
Поиск псевдо-прообраза3	273	278

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

Цель атаки	Трудоемкость
Поиск псевдо-коллизии4	216
Поиск псевдо-прообраза	295
Поиск прообраза	от 297,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 использовался во многих из них в качестве основного или одного из основных алгоритмов хэширования. Приведем несколько примеров.

1. Протокол защищенной электронной почты PEM (Privacy-Enhanced Mail), изначально определенный в [14] (подробное описание можно найти также в [4]). Спецификация криптоалгоритмов, используемых в PEM, была определена в [6], где в качестве единственного алгоритма хэширования (но не единственного алгоритма контроля целостности) предполагалось использовать MD2. В последующих версиях протокола PEM [15] наряду с MD2 предполагалось использовать также алгоритм хэширования MD5.
2. Алгоритм MD2 использовался наряду с алгоритмами MD5 и SHA-1 в инфраструктуре открытых ключей (Public Keys Infrastructure, PKI); однако, уже в спецификации PKI 1999 года [16], в частности, сказано, что MD2 должен использоваться только в целях совместимости со старыми приложениями, в новых же следует применять алгоритмы SHA-1 и MD5.
3. Широко используемый стандарт асимметричных криптоопераций 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].

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

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

Литература

1. Bakhtiari S., Safavi-Naini R., Pieprzyk J. Practical and Secure Message Authentication. // http://citeseerx.ist.psu.edu – April 27, 1995 – University of Wollongong.
2. eBASH: ECRYPT Benchmarking of All Submitted Hashes. // http://bench.cr.yp.to.
3. eBACS: ECRYPT Benchmarking of Cryptographic Systems. // http://bench.cr.yp.to.
4. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. – Пер. с англ.: М.: Издательство ТРИУМФ, 2002 – 816 с.
5. Preneel B. Analysis and Design of Cryptographic Hash Functions. // http://homes.esat.kuleuven.be – February 2003.
6. Linn J. RFC 1115. Privacy Enhancement for Internet Electronic Mail: Part III -- Algorithms, Modes, and Identifiers. // http://tools.ietf.org – August 1989 – DEC.
7. Kaliski B. RFC 1319. The MD2 Message-Digest Algorithm. // http://tools.ietf.org – April 1992 – RSA Laboratories.
8. Rogier N., Chauvaud P. MD2 is not Secure without the Checksum Byte. Abstract. // http://ehash.iaik.tugraz.at – 1995.
9. Muller F. The MD2 Hash Function is Not One-Way. // http://www.ssi.gouv.fr – DCSSI Crypto Lab.
10. Robshaw M. J. B. On Recent Results for MD2, MD4 and MD5. // ftp://ftp.rsa.com – RSA Laboratories’ Bulletin. – Number 4 – November 12, 1996.
11. Knudsen L. R., Mathiassen J. E. Preimage and Collision Attacks on MD2. // http://www.ii.uib.no.
12. Thomsen S. S. An improved preimage attack on MD2. // http://eprint.iacr.org – 2008 – Technical University of Denmark.
13. 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.
14. 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.
15. Balenson D. RFC 1423. Privacy Enhancement for Internet Electronic Mail: Part III: Algorithms, Modes, and Identifiers. // http://tools.ietf.org – February 1993.
16. 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.
17. 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.
18. Turner S., Chen L. MD2 to Historic Status. // http://tools.ietf.org – March 2011.
19. FIPS PUB 180-2. Secure Hash Standard. // http://www.securitytechnet.com – 2002 August 1 – National Institute of Standards and Technology.

 

Алгоритм хэширования MD4

Данная статья является продолжением цикла статей про алгоритмы хэширования семейства MD. Она описывает структуру широко распространенного алгоритма хэширования MD4. Данный алгоритм активно использовался до начала 2000 гг. – до тех пор, когда была предложена эффективная атака на MD4, позволяющая практически мгновенно найти коллизию (обзору результатов криптоанализа MD4 будет посвящена следующая статья цикла).
MD4 интересен не только тем, что он был одним из наиболее широко применяемых алгоритмов хэширования в мире, но и тем, что на основе заложенных в MD4 идей были разработаны многие другие известные алгоритмы хэширования – прежде всего, алгоритмы семейства SHA [1, 2].

Как и другие алгоритмы семейства MD, MD4 разработан Рональдом Ривестом; данный алгоритм был предложен в 1990 г. Алгоритм MD4 подробно описан в документах RFC 1186 [3] и RFC 1320 [4].

Структура алгоритма MD4 полностью соответствует схеме Меркля-Дамгаарда. Данная схема была предложена в 1988-1989 гг. независимо двумя известными криптологами: Ральфом Мерклем (Ralph Merkle) и Айвеном Дамгаардом (Ivan Damgard) [5]. Суть схемы состоит в следующем (см. рис. 1).

• Хэшируемое сообщение M разбивается на блоки определенной длины M ₀… M_N. Выполняется (по-разному в различных алгоритмах) дополнение сообщения M до размера, кратного данной длине блока (при этом количество блоков может увеличиться).
• Каждый i -й блок сообщения обрабатывается функцией fb (), являющейся криптографическим ядром алгоритма хэширования, причем данная функция накладывает результат этой обработки на текущее хэш-значение H_i-1 (т. е. на результат обработки предыдущих блоков сообщения):

H_i = fb (H_i-1, M_i).

• Результатом работы алгоритма хэширования hash () (т. е. хэш-значением сообщения M) является значение H_N:

hash (M) = H_N.

• Начальное значение H -1 обычно является константным и различным в различных алгоритмах хэширования; оно часто обозначается как IV (от Initialization Vector – вектор инициализации).

 

Рис. 1 Схема Меркля-Дамгаарда

Алгоритм MD4 вычисляет 128-битовое хэш-значение от входного блока данных переменного и неограниченного размера.
Прежде всего, входное сообщение разбивается на блоки размером по 512 битов. Последний блок всегда дополняется до 512-битового размера следующим образом:

• сначала добавляется единичный бит;
• затем – нулевые биты до размера 448 битов (т. е. 512 - 64); нулевые биты не добавляются, если после добавления единичного бита блок имеет 448-битовый размер;
• к последовательности добавляется 64-битовое значение, равное размеру в битах исходной последовательности входных данных до дополнения.

В [4] Ривест отметил, что если размер сообщения в битах L превышает 2⁶⁴ - 1 (что можно считать крайне маловероятным), то значение размера становится невозможно записать в 64 бита. Поэтому в качестве размера записывается не L, а значение L mod 2⁶⁴.
Если изначально размер последнего блока равен 448 битам (или больше), дополнение выполняется все равно, при этом количество блоков увеличивается на один.
Для хранения промежуточных значений алгоритм использует 4 регистра по 32 бита, которые обозначаются как A, B, C и D. Они инициализируются перед началом вычислений согласно следующей таблице (указаны шестнадцатеричные значения):

Регистр	Исходное значение
A
B	89ABCDEF
C	FEDCBA98
D

Согласно описанной выше схеме Меркля-Дамгаарда, совокупность регистров A … D содержит значение H_i после обработки i -го блока сообщения, а указанное в таблице начальное заполнение регистров является вектором инициализации алгоритма.
Каждый из 512-битовых блоков входных данных M_i поочередно обрабатывается следующим образом:

• Блок входных данных представляется в виде 16 слов M [0]… M [15], каждое из которых является 32-битовым.
• Содержимое регистров A … D копируется во временные переменные a … d.

 

Рис. 2 Итерация алгоритма MD4

• Выполняются 48 итераций преобразований (см. рис. 2), в каждой из которых модифицируются переменные a … d с участием одного из слов блока сообщения M [0]… M [15]:

t = (a + f_j (b, c, d) + M [ x_j ] + K_j mod 2³²) <<< s_j ;
a = d;
d = c;
c = b;
b = t,
где:

• j – номер итерации, j = 0…47;
• t – временная 32-битовая переменная;
• f_j () – одна из следующих раундовых функций (в таблице символами & и | обозначены, соответственно, побитовые логические операции «и» и «или»; ~ x обозначает побитовый комплемент к x):

Номер итерации j	fj ()
0…15	fj (x, y, z) = (x & y) | (~ x & z)
16…31	fj (x, y, z) = (x & y) | (x & z) | (y & z)
32…47	fj (x, y, z) = x A y A z

• индекс используемого слова блока сообщения xj определяется следующим образом:

Номер итерации j	xj
0, 16, 32
1, 20, 40
2, 24, 36
3, 28, 44
4, 17, 34
5, 21, 42
6, 25, 38
7, 29, 46
8, 18, 33
9, 22, 41
10, 26, 37
11, 30, 45
12, 19, 35
13, 23, 43
14, 27, 39
15, 31, 47

• Kj – модифицирующие константы (указаны шестнадцатеричные значения):

Номер итерации j	Kj
0…15
16…31	5A827999
32…47	6ED9EBA1

Происхождение второй и третьей констант – округленный результат умножения, соответственно, значений и на 2³² [6]. Отметим, что в [4] в качестве источника данных констант ошибочно указаны значения и вместо и.

• <<< – операция побитового циклического сдвига влево; количество битов сдвига sj определяется в зависимости от номера итерации согласно следующей таблице:

Номер итерации j	sj
0, 4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44
17, 21, 25, 29
1, 5, 9, 13
18, 22, 26, 30, 33, 37, 41, 45
2, 6, 10, 14, 34, 38, 42, 46
19, 23, 27, 31
35, 39, 43, 47
3, 7, 11, 15

• Значения регистров A … D складываются по модулю 2³² с полученными значениями переменных a … d соответственно.

Выходное значение алгоритма, т. е. 128-битовое хэш-значение сообщения – результат конкатенации регистров A … D после обработки последнего блока расширенного сообщения.

Алгоритм MD4 выглядит не более сложным в реализации, чем алгоритм MD2. В отличие от MD2, MD4 не содержит таблиц замен и может быть весьма компактно реализован аппаратно [4].

В [3] описан также расширенный вариант алгоритма MD4, который позволяет вычислить 256-битовое хэш-значение. Расширенный вариант основан на параллельном применении двух копий обычного алгоритма MD4. Вычисления выполняются следующим образом:

• Первая копия алгоритма выполняется обычным образом, за исключением описанного далее обмена значениями регистров A.
• Во второй копии применяются другие начальные значения регистров A … D согласно таблице (в этой и следующей таблицах указаны шестнадцатеричные значения):

Регистр	Исходное значение
A
B
C	8899AABB
D	CCDDEEFF

• В итерациях 16…47 используются другие значения модифицирующих констант K_j:

Номер итерации j	Kj
16…31	50A28BE6
32…47	5C4DD124

• После обработки каждого из 512-битовых блоков входных данных (в т. ч., после обработки последнего блока) значения регистров A двух копий алгоритма MD4 меняются местами.

Результирующим 256-битовым хэш-значением алгоритма является конкатенация регистров A … D первой копии MD4 и регистров A … D второй копии после обработки всех блоков входных данных. Отметим, что расширенный вариант алгоритма MD4 продолжает соответствовать схеме Меркля-Дамгаарда.
Из более поздней спецификации алгоритма MD4 ([4]) расширенный вариант исключен.

Литература

1. FIPS PUB 180-1. Secure Hash Standard. // http://www.itl.nist.gov – National Institute of Standards and Technology – 1995 April 17.
2. FIPS PUB 180-2. Secure Hash Standard. // http://www.securitytechnet.com – National Institute of Standards and Technology – 2002 August 1.
3. Rivest R. RFC 1186: The MD4 Message Digest Algorithm. // http://www.ietf.org – MIT Laboratory for Computer Science – October 1990.
4. Rivest R. RFC 1320: The MD4 Message Digest Algorithm. // http://www.ietf.org – April 1992.
5. Merkle-Damgard construction. From Wikipedia, the free encyclopedia // http://en.wikipedia.org.
6. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. – Пер. с англ.: М.: Издательство ТРИУМФ, 2002 – 816 с.

 

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

Алгоритм хэширования MD4 был подробно описан в предыдущей статье. Данная и последующая статьи посвящены криптоаналитическим исследованиям этого алгоритма; они предлагают обзор основных работ по криптоанализу MD4.
В этой