HAIFA

HAIFA (англ. HAsh Iterative FrAmework) — итеративный метод построения криптографичеких хеш-функций, являющийся усовершенствованием классической структуры Меркла — Дамгора.

Был предложен в 2007 году в целях повышения устойчивости ко многим атакам и поддержки возможности получать хеш-суммы различных длин. На основе алгоритма были разработаны такие хеш-функции, как BLAKE^[1] и SHAvite-3^[2].

История править

Создателями алгоритма являются Эли Бихам и Ор Дункельман — израильские криптографы из Хайфского университета. Бихам — ученик Ади Шамира, разработавшего большое количество новых криптографических алгоритмов, в том числе взлома существующих; Дункельман — коллега Шамира по одному из проектов, а в дальнейшем продолжил свои исследования самостоятельно^[3].

Структура Меркла — Дамгора долгое время считалась устойчивой к атаке на нахождение второго прообраза, пока в 1999 году профессор Принстонского университета Ричард Дин не доказал, что это предположение неверно для длинных сообщений, если при данной функции сжатия возможно легко находить фиксированные точки последовательности. Также на структуру Меркла — Дамгора могла быть успешно произведена атака множественный коллизий и хэрдинг-атака (атака по известному префиксу)^[4]^[5].

Алгоритм править

Структура Меркла — Дамгора представляет собой следующий алгоритм:

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

Есть сообщение $M$ , разбитое на несколько частей: $M_{1},M_{2}...M_{k}$ . Есть некоторое начальное значение — $IV$ и некоторая функция $C$ , которая подсчитывает промежуточное представление хеш-функции $H$ определённым образом^[5]:

h_{0}=IV

Далее итеративно:

h_{i}=C(h_{i-1},M_{i})

H(M)=h_{k}

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

\{0,1\}^{m_{c}}\times \{0,1\}^{n}\rightarrow \{0,1\}^{m_{c}}

, где

m_{c}

— размер

h

,

n

— размер блока,

m=m_{c}

(чаще всего выходной размер совпадает с размером h)

используется:

\{0,1\}^{m_{c}}\times \{0,1\}^{n}\times \{0,1\}^{b}\times \{0,1\}^{s}\rightarrow \{0,1\}^{m_{c}}

, где

b,s

— длины количества бит и соли,

внутреннее же представление подсчитывается (в соответствии с введенными выше обозначениями):

h_{i}=C(h_{i-1},M_{i},bits,salt)

, где

bits

— количество бит, захешированных к этому времени.

Чтобы захешировать сообщение, нужно выполнить следующие шаги:

Дополнить сообщение $M$ в соответствии с нижеописанной схемой.
Подсчитать начальное значение $IV_{m}$ для внутренней ячейки размера m в соответствии с алгоритмом, описанным ниже.
Пройти по всем блокам дополненного сообщения, вычисляя на каждом шаге значение функции сжатия $h_{i}$ от текущего блока $M_{i}$ , $h_{i-1}$ и теперь уже добавляя соль и $bits$ в качестве аргументов. Если к сообщению добавляется дополнительный блок (в самый конец), то для этого блока выставляем значение $bits$ равное нулю.
Обрезать последнее, выходное, значение функции, если необходимо^[4].

Дополнение сообщения править

В HAIFA сообщение $M$ дополняется единицей, необходимым количеством нулей, длиной сообщения в битах и размером выходного блока $h$ . Т.е добавляем последовательность (количество нулей в данном случае должно быть таким, чтобы $N_{1}+N_{0}\equiv N-(M_{length}+H_{size})modN$ ^[4] , где $N_{1}$ , $N_{0}$ — количество единиц и нулей, $N$ — размер блока:

$1+{0..0}+bits+m_{c}$

Хеширование сообщения, дополненного размером выходного блока, избавляет от проблемы нахождения коллизий, так как если два сообщения $M_{1}$ и $M_{2}$ хешируются с размерами блока $l_{1}$ и $l_{2}$ , то от коллизий спасает именно последний блок. В свою очередь, добавлением $bits$ = 0 в самом последнем блоке, создаётся сигнал для обозначения последнего и дополняющего блока^[4].

Возможность дополнения исходного сообщения в данном алгоритме позволяет обрезать захешированное, тем самым изменяя размер конечного хеша^[4].

Длина хеша править

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

$IV$ — начальное значение
$m$ — желательная длина выхода
Считаем преобразованное начальное значение : $IV_{m}=C(IV,m,0,0)$
Таким образом получаем $m$ «зашитое» в первые $r$ бит, за которыми следуют 1 и нули.
После того, как посчитался последний блок, итоговым значением являются $m$ бит последнего значения функции сжатия цепочки^[4].

Стойкость алгоритма править

Доказательство того, что HAIFA устойчив к коллизиям, если функция сжатия устойчива к коллизиям, проводится аналогично доказательству для Меркла — Дамгора^[4].

Количество захешированных бит значительно затрудняет поиск и использование фиксированных точек. Даже найдя такие $h_{i}$ и $M_{i}$ , для которых выполняется $h_{i}=C(h_{i},M_{i},bits,salt)$ , нельзя бесконечно размножать эти значения в данном алгоритме, потому что количество битов будет все время меняться^[4].

Соль ( $salt$ ), как и $bits$ , тоже вносит свой вклад в стойкость алгоритма^[4]:

Дает возможность устанавливать безопасность хеш-функций в теоретической модели.
Заставляет атаки, базирующиеся на предварительных расчетах, переносить все свои вычисления в онлайн-режим, так как значение соли неизвестно заранее.
Повышает безопасность электронных подписей (так как каждый раз приходится учитывать то, что есть некоторое случайное значение).

Ниже приведены оценки стойкости HAIFA к различным типам атак.

Атаки, основанные на фиксированных точках править

В атаке на второй прообраз ищется такое значение $M^{'}$ , для которого $H(M')=h_{i}=H(M_{i})$ , то есть хеш от $M^{'}$ равен какому-либо промежуточному значению в итерациях, и далее соединить часть оставшегося сообщения $M$ (находящуюся справа от $M_{i}$ ) с нашим угаданным $M^{'}$ . Однако алгоритм был признан устойчивым к этой атаке, так как в усовершенствованном варианте в конец сообщения дописывался его размер. Ричард Дин же в своей работе указал совершенно новый способ атаки, основанный на предположении о том, что для данной функции $C$ легко найти фиксированные точки (по определению фиксированная точка — та, для которой выполняется соотношение $h=C(h,M_{i})$ ). В его алгоритме недостающая длина сообщения восполнялась добавлением множества фиксированных точек, то есть мы могли достаточным количеством повторений значения $h$ дополнить нашу длину до нужной.

В данном случае HAIFA защищает от атаки, основанной на фиксированных точках, так как наличие соли и поля, содержащего количество захешированных бит сводит к минимуму вероятность появления повторения значений сжимающей функции^[4].

Атака множественных коллизий править

Для множественных коллизий французский криптограф Антуан Жу^[en] описал возможность нахождения $2^{t}$ сообщений, имеющих один и тот же хеш. Его работа базируется на факте, что возможно найти $t$ таких одноблочных коллизий, в которых $C(h_{i-1},M_{i})=C(h_{i-1},M_{i}^{*})$ , и далее конструировать различные сообщения, всего $2^{t}$ вариантов, выбирая на каждом из $t$ шагов либо сообщение $M_{i}$ , либо $M_{i}^{*}$ .

Составление сообщения с помощью множественных коллизий

HAIFA, несмотря на сложную структуру, не гарантирует нулевой вероятности удачного прохождения атаки на множественные коллизии. После вышеописанных модификаций, сделанных над алгоритмом Меркла — Дамгора, сложность нахождения коллизий для каждого блока не изменилась, но так как появилось случайное подмешанное значение, атакующий не может заранее перебирать варианты этих коллизий, не зная случайного значения. Расчеты переходят в онлайн-режим^[4].

Хэрдинг-атака править

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

Изначально строится дерево из различных $2^{t}$ внутренних значений, ищутся сообщения Mj, которые приводят к коллизиям среди этих состояний. То есть в узлах дерева находятся различные значения $h$ , на ребрах — значения $M_{j}$ .
Строим коллизии по вновь полученным значениям $h$ (с предыдущего уровня дерева) до тех пор, пока не дойдем до конечного значения $H$ .
Затем атакующий получает информацию о префиксе.
Получив эту информацию, он пытается подобрать связующее сообщение между эти префиксом и желаемым суффиксом. Связующее сообщение должно удовлетворять условию, что значение сжимающей функции от него равен одному из внутренних значений $h$ на первом уровне дерева. Далее суффикс строится обычным проходом по дереву (так как на его ребрах уже находятся сообщения, которые приведут к необходимому результату). Ключевым моментом является возможность производить предварительные вычисления, в онлайн-режиме останется подобрать только нужное промежуточное значение $h$ и $M$ .

Доказано, что на HAIFA невозможно провести первую фазу хэрдинг-атаки (построение дерева решений), пока неизвестно значение соли. То есть тот brute-force, который излагался выше, уже провести нельзя. Условие успешного отражения атаки — длина подмешиваемого сообщения, если желаемая сложность атаки ставится на уровне $O(2^{m})$ , должна быть не менее ${\frac {m_{c}}{2}}$ символов. Если этого правила не придерживаться, то возможны некоторые предварительные расчеты, приводящие к взлому алгоритма. Если значение соли все же было найдено, то потребуется некоторое время для поиска нужного места в сообщении в силу наличия поля $bits$ ^[4].

Сложность атак на алгоритмы Меркла — Дамгора и HAIFA править

Тип атаки	Идеальная хеш-функция	MD	HAIFA (фиксированное значение соли)	HAIFA (с различными значениями соли)
Атака на первый прообраз^[en] ( $k^{'}<2^{s}$ целей)	$2^{m_{c}}$	$2^{m_{c}}$	$2^{m_{c}}$	$2^{m_{c}}$
Атака на один из первых прообразов	${\displaystyle 2^{m_{c}}}/k'$	${\displaystyle 2^{m_{c}}}/k'$	${\displaystyle 2^{m_{c}}}/k'$	$2^{m_{c}}$
Атака на второй прообраз ( $k$ блоков)^[9]^[10]	$2^{m_{c}}$	$2^{m_{c}}/k$	$2^{m_{c}}$	$2^{m_{c}}$
Атака на один из вторых прообразов ( $k$ блоков, $k^{'}<2^{s}$ сообщений)	${\displaystyle 2^{m_{c}}}/k'$	$2^{m_{c}}/k$	${\displaystyle 2^{m_{c}}}/k'$	$2^{m_{c}}$
Коллизии	$2^{m_{c}/2}$	$2^{m_{c}/2}$	$2^{m_{c}/2}$	$2^{m_{c}/2}$
Множественные коллизии ( $k$ — количество коллизий)^[9]	$2^{m_{c}(k-1)/k}$	$\left\lceil {log_{2}k}\right\rceil 2^{m_{c}/2}$	$\left\lceil {log_{2}k}\right\rceil 2^{m_{c}/2}$	$\left\lceil {log_{2}k}\right\rceil 2^{m_{c}/2}$
Herding^[11]^[12]	-	Offline: $2^{m_{c}/2+t/2}$ Online: $2^{m_{c}-t}$	Offline: $2^{m_{c}/2+t/2}$ Online: $2^{m_{c}-t}$	Offline: $2^{m_{c}/2+t/2+s}$ Online: $2^{m_{c}-t}$

Приложения править

HAIFA, по мнению разработчиков, может являться основой для множества криптографических алгоритмов, так как представляет cобой новую усовершенствованную базовую конструкцию. Доказано, что с её использованием могут быть разработаны функции рандомизированного хеширования^[13], обёрнутая функция Меркла — Дамгора (англ. Enveloped Merkle-Damgard, RMC^[14]^[15], ширококонвейрного хеша^[16].

Ширококонвейерный хеш править

Получить конструкцию ширококонвейерного (англ. wild-pipe) хеша с помощью HAIFA достаточно легко; в самом алгоритме для повышения сложности длина внутренних блоков была сделана в два раза больше, чем длина конечного блока (поэтому есть две функции сжатия $C^{'}$ и $C^{''}$ ). Можно непосредственно вывести формулу для широконвейерного хеша, с учётом того, что находить в HAIFA последний блок тривиально, так как $bits$ там выставлены ноль^[4].

Пример ширококонвейерного

Формула для перевода из HAIFA в ширококонвейрный хеш:

$C_{HAIFA}(h_{i-1},M_{i},bits,s)={\begin{cases}C''(C'(IV_{2},h_{i-1}||fixpad(M_{i}))),&{\text{if }}{\text{ last block}}\\C'(h_{i-1},M_{i}),&{\text{ }}{\text{otherwise}}\end{cases}}$

где $C':\{0,1\}^{m_{c}}\times \{0,1\}^{n}\rightarrow \{0,1\}^{m_{c}}$

$C'':\{0,1\}^{m_{c}}\rightarrow \{0,1\}^{m}$

$IV_{2}$ — второй вектор инициализации^[16].

Прикладное значение править

Способ, предложенный учёными в HAIFA, имеет важное прикладное значение для реализации алгоритмов электронной подписи: с введением количества бит и соли стало сложнее добавлять префиксы и суффиксы к сообщению (herd attack), а следовательно подменять сообщения для подписи^[8].

Примечания править

↑ Jean-Philippe Aumasson, Luca Henzen, Willi Meier, Raphael C.-W. Phan. SHA-3 proposal BLAKE (англ.) // SHA-3 Conference. — 2010. — 16 декабря. — С. 8—15. Архивировано 16 апреля 2016 года.
↑ Eli Biham, Orr Dunkelman. The SHAvite-3 Hash Function (англ.) // Encrypt II. — 2009. — С. 8—17. Архивировано 25 декабря 2016 года.
↑ Eli Biham. Publications (неопр.). The list of authors' publications (since 1991). Дата обращения: 17 ноября 2016. Архивировано 31 марта 2016 года.
↑ ¹ ² ³ ⁴ ⁵ ⁶ ⁷ ⁸ ⁹ ¹⁰ ¹¹ ¹² ¹³ ¹⁴ ¹⁵ Eli Biham, Orr Dunkelman. A Framework for Iterative Hash Functions —HAIFA (англ.) // ePrint. — 2007. — С. 6—12. Архивировано 17 августа 2016 года.
↑ ¹ ² Jean-Sebastien Coron, Yevgeniy Dodis, Cecile Malinaud, Prashant Puniya. Merkle Damgard Revisited: how to Construct a hash Function (A new Design Criteria for Hash-Functions) (англ.) // NIST. — С. 3—6. Архивировано 7 ноября 2016 года.
↑ Gregory Bard. The Fixed-Point Attack (неопр.). The explanation of fixed-point attack. ResearchGate (январь 2009). Дата обращения: 3 ноября 2016. Архивировано 4 ноября 2016 года.
↑ Antoine Joux. Multicollisions in iterated hash functions. Application to cascaded constructions (англ.) // Iacr. — 2004. — Август. Архивировано 13 мая 2016 года.
↑ ¹ ² Orr Dunkelman, Bart Preneel. Generalizing the Herding Attack to Concatenated Hashing Schemes (англ.) // IAIK. — 2007. — С. 6—7. Архивировано 4 ноября 2016 года.
↑ ¹ ² 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
↑ Charles Bouillaguet, Pierre-Alain Fouque. Practical Hash Functions Constructions Resistant to Generic Second Preimage Attacks Beyond the Birthday Bound (англ.) // PSL. — 2011. — С. 2. Архивировано 30 августа 2017 года.
↑ Simon R. Blackburn. On the Complexity of the Herding Attack and Some Related Attacks on Hash Functions (англ.) // ePrint. — 2010. — С. 3. Архивировано 26 августа 2016 года.
↑ Elena Andreeva, Charles Bouillaguet, Orr Dunkelman, and John Kelsey. Herding, Second Preimage and Trojan Message Attacks Beyond Merkle-Damgard (англ.) // NIST. — С. 5, 10, 14. Архивировано 21 ноября 2016 года.
↑ Halevi S., Krawczyk H. Strengthening Digital Signatures Via Randomized Hashing (англ.) // Advances in Cryptology — CRYPTO 2006: 26th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 2006, Proceedings / C. Dwork — Berlin, Heidelberg, New York City, London: Springer Science+Business Media, 2006. — P. 41—59. — 622 p. — (Lecture Notes in Computer Science; Vol. 4117) — ISBN 978-3-540-37432-9 — ISSN 0302-9743; 1611-3349 — doi:10.1007/11818175_3
↑ Itai Dinur. New Attacks on the Concatenation and XOR Hash Combiners // ePrint. — 2016. Архивировано 9 сентября 2016 года.
↑ Elena Andreeva, Gregory Neven, Bart Preneel, Thomas Shrimpton. Seven-Properties-Preserving Iterated Hashing: The RMC Construction (англ.) // ePrint. — 2007. — С. 10—14. Архивировано 25 августа 2016 года.
↑ ¹ ² Dustin Moody. Indifferentiability Security of the Fast Wide Pipe Hash: Breaking the Birthday Barrier (англ.) // ePrint. — 2011. Архивировано 6 августа 2016 года.

Литература править

Eli Biham and Orr Dunkelman. A framework for iterative hash functions - HAIFA. — ePrint, 2007. — С. 3—12, 15. — 20 с.
Orr Dunkelman. Re-visiting HAIFA. Talk at the workshop Hash functions in cryptology: theory and practice. — 2008. — 207 с.
B. Denton and R. Adhami. Modern Hash Function Construction. — 5 с.
John Kelsey, Tadayoshi Kohno. Herding Hash Functions and the Nostradamus Attack. — ePrint, 2005. — С. 4—8. — 17 с.
Marjan Skrobot. Provable Security Analysis of SHA-3 Candidates. — 2012. — С. 31—33. — 72 с.

Ссылки править

Mihir Bellare, Thomas Ristenpart. Multi-Property-Preserving Hash Domain Extension and the EMD Transform (Enveloped Merkle-Damgard) : [англ.] // ePrint : presentation. — University of California at San Diego Security and Cryptography Lab, 2006.
Сайт конкурса SHA-3 (англ.) (июль 2012). — Описание предложенных на конкурсе хеш-функций, результаты раундов.
Eli Biham. Страница Эли Бихама (англ.). — Основная информация, перечень публикаций.

[1] Jean-Philippe Aumasson, Luca Henzen, Willi Meier, Raphael C.-W. Phan. SHA-3 proposal BLAKE (англ.) // SHA-3 Conference. — 2010. — 16 декабря. — С. 8—15. Архивировано 16 апреля 2016 года.

[2] Eli Biham, Orr Dunkelman. The SHAvite-3 Hash Function (англ.) // Encrypt II. — 2009. — С. 8—17. Архивировано 25 декабря 2016 года.

[3] Eli Biham. Publications (неопр.). The list of authors' publications (since 1991). Дата обращения: 17 ноября 2016. Архивировано 31 марта 2016 года.

[:2-4] ¹ ² ³ ⁴ ⁵ ⁶ ⁷ ⁸ ⁹ ¹⁰ ¹¹ ¹² ¹³ ¹⁴ ¹⁵ Eli Biham, Orr Dunkelman. A Framework for Iterative Hash Functions —HAIFA (англ.) // ePrint. — 2007. — С. 6—12. Архивировано 17 августа 2016 года.

[:3-5] ¹ ² Jean-Sebastien Coron, Yevgeniy Dodis, Cecile Malinaud, Prashant Puniya. Merkle Damgard Revisited: how to Construct a hash Function (A new Design Criteria for Hash-Functions) (англ.) // NIST. — С. 3—6. Архивировано 7 ноября 2016 года.

[6] Gregory Bard. The Fixed-Point Attack (неопр.). The explanation of fixed-point attack. ResearchGate (январь 2009). Дата обращения: 3 ноября 2016. Архивировано 4 ноября 2016 года.

[7] Antoine Joux. Multicollisions in iterated hash functions. Application to cascaded constructions (англ.) // Iacr. — 2004. — Август. Архивировано 13 мая 2016 года.

[:0-8] ¹ ² Orr Dunkelman, Bart Preneel. Generalizing the Herding Attack to Concatenated Hashing Schemes (англ.) // IAIK. — 2007. — С. 6—7. Архивировано 4 ноября 2016 года.

[:4-9] ¹ ² 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

[10] Charles Bouillaguet, Pierre-Alain Fouque. Practical Hash Functions Constructions Resistant to Generic Second Preimage Attacks Beyond the Birthday Bound (англ.) // PSL. — 2011. — С. 2. Архивировано 30 августа 2017 года.

[11] Simon R. Blackburn. On the Complexity of the Herding Attack and Some Related Attacks on Hash Functions (англ.) // ePrint. — 2010. — С. 3. Архивировано 26 августа 2016 года.

[12] Elena Andreeva, Charles Bouillaguet, Orr Dunkelman, and John Kelsey. Herding, Second Preimage and Trojan Message Attacks Beyond Merkle-Damgard (англ.) // NIST. — С. 5, 10, 14. Архивировано 21 ноября 2016 года.

[13] Halevi S., Krawczyk H. Strengthening Digital Signatures Via Randomized Hashing (англ.) // Advances in Cryptology — CRYPTO 2006: 26th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 2006, Proceedings / C. Dwork — Berlin, Heidelberg, New York City, London: Springer Science+Business Media, 2006. — P. 41—59. — 622 p. — (Lecture Notes in Computer Science; Vol. 4117) — ISBN 978-3-540-37432-9 — ISSN 0302-9743; 1611-3349 — doi:10.1007/11818175_3

[14] Itai Dinur. New Attacks on the Concatenation and XOR Hash Combiners // ePrint. — 2016. Архивировано 9 сентября 2016 года.

[15] Elena Andreeva, Gregory Neven, Bart Preneel, Thomas Shrimpton. Seven-Properties-Preserving Iterated Hashing: The RMC Construction (англ.) // ePrint. — 2007. — С. 10—14. Архивировано 25 августа 2016 года.

[:1-16] ¹ ² Dustin Moody. Indifferentiability Security of the Fast Wide Pipe Hash: Breaking the Birthday Barrier (англ.) // ePrint. — 2011. Архивировано 6 августа 2016 года.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]