Структура Меркла — Дамгора

Структура Меркла — Дамгора (MD, Merkle—Damgård) — метод построения криптографических хеш-функций, предусматривающий разбиение входных сообщений произвольной длины на блоки фиксированной длины и работающий с ними по очереди с помощью функции сжатия, каждый раз принимая входной блок с выходным от предыдущего прохода.

Впервые описана в 1979 году в докторской диссертации Ральфа Меркла[1]. Меркл и Дамгор независимо показали: если функция сжатия устойчива к коллизиям, то и хеш-функция будет также устойчива[2][3] — чтобы доказать устойчивость структуры, сообщение дополняется блоком, который кодирует длину первоначального сообщения (упрочнение Меркла — Дамгора).

Односторонняя функция сжатия

f

, преобразует два входных блока фиксированной длины в выходной блок того же размера, что и входные; алгоритм начинает с вектора инициализации IV, функция

f

выполняется последовательно над результатом каждого предыдущего прохода.

Структура предусматривает вектор инициализации — фиксированное значение, которое зависит от реализации алгоритма, и которое применяется к первому проходу — применению функции сжатия $f$ к нему и первому блоку сообщения. Результат каждого прохода передаётся на следующий вход $f$ и очередному блоку сообщения; последний блок дополняется нулями, если необходимо, также, добавляется блок с информацией о длине целого сообщения. Для упрочнения хеша последний результат иногда пропускают через функцию финализации (англ. finalisation function), которая может использоваться также для уменьшения размера выходного хеша сжатием результата последнего применения $f$ в хеш более маленького размера, или чтобы гарантировать лучшее смешивание битов и усилить влияние небольшого изменения входного сообщения на хеш (обеспечить лавинный эффект). Функция финализации часто строится с использованием функции сжатия.

Основные алгоритмы, реализующие структуру Меркла — Дамгора — MD5, SHA-1, семейство SHA-2.

Характеристики безопасности

Популярность структуры Меркла — Дамгора обусловлена следующим результатом: если односторонняя функция сжатия $f$ устойчива к коллизиям, то и хеш-функция, построенная на её основе, будет также устойчива к коллизиям. При этом структура имеет несколько нежелательных свойств:

атака нахождения второго прообраза для длинных сообщений всегда намного более эффективна, чем полный перебор. Атака для сообщения из $2^{k}$ блоков может быть выполнена за время $k\times 2^{n/2+1}+2^{n-k+1}$ ; важно, что сложность атаки находится между $2^{n/2}$ и $2^{n}$ , когда сообщения длинные, а когда длина сообщения становится меньше — сложность приближается к $2^{n}$ [4];
множественные коллизии (много сообщений имеют одинаковый хеш) могут быть найдены лишь незначительно бо́льшими усилиями, чем коллизии[5];
атаки дополнением сообщения: при данном хеше $H(X)$ неизвестного входного сообщения $X$ легко найти значение $H(\mathrm {pad} (X)||Y)$ , где $\mathrm {pad}$ — функция дополнения; это значит, что возможно найти хеши входных сообщений, связанных с $X$ , даже когда $X$ остаётся неизвестным[6]; случайный оракул не имеет такой возможности, и это может привести к простым атакам даже на схемы, безопасность которых была доказана для модели случайного оракула[7].

Пример

Для того, чтобы передать сообщение в функцию сжатия, необходимо дополнить последний блок до полного определёнными данными (обычно нулями). Например, для сообщения «HashInput» и размера блока для функции сжатия 8 байт (64 бит), получится 2 блока:

HashInpu t0000000

Но этого недостаточно, так как это будет означать, что различные сообщения, начинающиеся одними и теми же символами, и заканчивающимися нулями или другими байтами из заполнителя, будут поступать в функцию сжатия совершенно одинаковыми блоками, и будет получаться одинаковая хеш-сумма. В этом примере сообщение «HashInput00» будет разделено на такие же блоки, что и первоначальное сообщение «HashInput». Чтобы этого избежать, первый бит добавляемых данных, должен быть изменён. Так как заполнитель обычно состоит из нулей, первый бит заполнителя должен быть заменён на «1»:

HashInpu t1000000

Чтобы усилить хеш, можно добавить длину сообщения в дополнительном блоке:

HashInpu t1000000 00000009

Чтобы избежать двусмысленности, значение длины сообщения должно быть само по себе устойчиво к добавлению заполнителя в блок. Наиболее распространенные реализации используют фиксированный размер (обычно 64 или 128 бит в современных алгоритмах) и фиксированную позицию в конце последнего блока для кодирования значения длины сообщения.

Однако, немного расточительно кодировать один дополнительный блок для длины сообщения, поэтому, существует небольшая оптимизация алгоритма, которая часто используется: если в последнем блоке сообщения достаточно места значение длины сообщения может быть добавлено к нему. Например, если кодировать длину сообщения в 5 байт, то достаточно двух блоков для примера:

HashInpu t1000009

Модификации

В 2006 году был предложен подход HAIFA, при котором структура Меркла — Дамгора немного модифицируется: в каждую функцию сжатия дополнительно к блоку сообщения подаётся текущее смещение во входном файле и, опционально, некоторая соль.

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

Из-за некоторых слабых мест структуры, особенно проблемы, связанной с дополнением сообщения до необходимой длины, в 2004 году Штефаном Люксом предложено применять широконвейерный хеш (англ. wilde pipe hash)[8], похожий на структуру Меркла — Дамгора, но имеющий больше внутренних состояний, то есть битовая длина, использующаяся внутри алгоритма больше, чем выходная. Таким образом, последний этап — вторая функция сжатия, которая сжимает последнее внутреннее значение хеша в окончательное значение. SHA-224 и SHA-384 были получены из SHA-256 и SHA-512 соответственно путём применения этого алгоритма.

Примечания

R.C. Merkle. Secrecy, authentication, and public key systems. Stanford Ph.D. thesis 1979, pages 13-15.
Merkle R. A Certified Digital Signature (англ.) // Advances in Cryptology — CRYPTO ’89: 9th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 1989, Proceedings / G. Brassard — Berlin, Heidelberg, New York, NY, London [etc.]: Springer New York, 1990. — P. 218—238. — (Lecture Notes in Computer Science; Vol. 435) — ISBN 978-0-387-97317-3 — ISSN 0302-9743; 1611-3349 — doi:10.1007/0-387-34805-0_21
Damgård I. A Design Principle for Hash Functions (англ.) // Advances in Cryptology — CRYPTO ’89: 9th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 1989, Proceedings / G. Brassard — Berlin, Heidelberg, New York, NY, London [etc.]: Springer New York, 1990. — P. 416—427. — (Lecture Notes in Computer Science; Vol. 435) — ISBN 978-0-387-97317-3 — ISSN 0302-9743; 1611-3349 — doi:10.1007/0-387-34805-0_39
Kelsey J., Schneier B. Second Preimages on n-Bit Hash Functions for Much Less than 2ⁿ Work (англ.) // Advances in Cryptology — EUROCRYPT 2005: 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Aarhus, Denmark, May 22-26, 2005. Proceedings / R. Cramer — Springer Science+Business Media, 2005. — P. 474—490. — 578 p. — ISBN 978-3-540-25910-7 — doi:10.1007/11426639_28
Joux A. Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions (англ.) // Advances in Cryptology — CRYPTO 2004: 24th Annual International Cryptology Conference, Santa Barbara, California, USA, August 15-19, 2004, Proceedings / M. Franklin — Berlin, Heidelberg, New York, NY, London [etc.]: Springer Science+Business Media, 2004. — P. 306—316. — 579 p. — (Lecture Notes in Computer Science; Vol. 3152) — ISBN 978-3-540-22668-0 — ISSN 0302-9743; 1611-3349 — doi:10.1007/978-3-540-28628-8_19
Yevgeniy Dodis, Thomas Ristenpart, Thomas Shrimpton. Salvaging Merkle-Damgård for Practical Applications. Preliminary version in Advances in Cryptology — EUROCRYPT '09 Proceedings, Lecture Notes in Computer Science Vol. 5479, A. Joux, ed, Springer-Verlag, 2009, pp. 371—388.
Coron J., Dodis Y., Malinaud C., Puniya P. Merkle-Damgård Revisited: How to Construct a Hash Function (англ.) // Advances in Cryptology — CRYPTO 2005: 25th Annual International Cryptology Conference, Santa Barbara, California, USA, August 14-18, 2005, Proceedings / V. Shoup — Berlin, Heidelberg, New York, NY, London [etc.]: Springer Science+Business Media, 2005. — P. 430—448. — 572 p. — (Lecture Notes in Computer Science; Vol. 3621) — ISBN 978-3-540-28114-6 — ISSN 0302-9743; 1611-3349 — doi:10.1007/11535218_26
S. Lucks, Design Principles for Iterated Hash Functions, In: Cryptology ePrint Archive, Report 2004/253, 2004.

Ссылки

Handbook of Applied Cryptography by Menezes, van Oorschot and Vanstone (2001), chapter 9.
Introduction to Modern Cryptography, by Jonathan Katz and Yehuda Lindell. Chapman and Hall/CRC Press, August 2007, page 134 (construction 4.13).

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] R.C. Merkle. Secrecy, authentication, and public key systems. Stanford Ph.D. thesis 1979, pages 13-15.

[2] Merkle R. A Certified Digital Signature (англ.) // Advances in Cryptology — CRYPTO ’89: 9th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 1989, Proceedings / G. Brassard — Berlin, Heidelberg, New York, NY, London [etc.]: Springer New York, 1990. — P. 218—238. — (Lecture Notes in Computer Science; Vol. 435) — ISBN 978-0-387-97317-3 — ISSN 0302-9743; 1611-3349 — doi:10.1007/0-387-34805-0_21

[3] Damgård I. A Design Principle for Hash Functions (англ.) // Advances in Cryptology — CRYPTO ’89: 9th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 1989, Proceedings / G. Brassard — Berlin, Heidelberg, New York, NY, London [etc.]: Springer New York, 1990. — P. 416—427. — (Lecture Notes in Computer Science; Vol. 435) — ISBN 978-0-387-97317-3 — ISSN 0302-9743; 1611-3349 — doi:10.1007/0-387-34805-0_39

[4] Kelsey J., Schneier B. Second Preimages on n-Bit Hash Functions for Much Less than 2ⁿ Work (англ.) // Advances in Cryptology — EUROCRYPT 2005: 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Aarhus, Denmark, May 22-26, 2005. Proceedings / R. Cramer — Springer Science+Business Media, 2005. — P. 474—490. — 578 p. — ISBN 978-3-540-25910-7 — doi:10.1007/11426639_28

[5] Joux A. Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions (англ.) // Advances in Cryptology — CRYPTO 2004: 24th Annual International Cryptology Conference, Santa Barbara, California, USA, August 15-19, 2004, Proceedings / M. Franklin — Berlin, Heidelberg, New York, NY, London [etc.]: Springer Science+Business Media, 2004. — P. 306—316. — 579 p. — (Lecture Notes in Computer Science; Vol. 3152) — ISBN 978-3-540-22668-0 — ISSN 0302-9743; 1611-3349 — doi:10.1007/978-3-540-28628-8_19

[6] Yevgeniy Dodis, Thomas Ristenpart, Thomas Shrimpton. Salvaging Merkle-Damgård for Practical Applications. Preliminary version in Advances in Cryptology — EUROCRYPT '09 Proceedings, Lecture Notes in Computer Science Vol. 5479, A. Joux, ed, Springer-Verlag, 2009, pp. 371—388.

[7] Coron J., Dodis Y., Malinaud C., Puniya P. Merkle-Damgård Revisited: How to Construct a Hash Function (англ.) // Advances in Cryptology — CRYPTO 2005: 25th Annual International Cryptology Conference, Santa Barbara, California, USA, August 14-18, 2005, Proceedings / V. Shoup — Berlin, Heidelberg, New York, NY, London [etc.]: Springer Science+Business Media, 2005. — P. 430—448. — 572 p. — (Lecture Notes in Computer Science; Vol. 3621) — ISBN 978-3-540-28114-6 — ISSN 0302-9743; 1611-3349 — doi:10.1007/11535218_26

[8] S. Lucks, Design Principles for Iterated Hash Functions, In: Cryptology ePrint Archive, Report 2004/253, 2004.