HAIFA

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

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

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

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

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

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

${\displaystyle h_{0}=IV}$

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

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

${\displaystyle H(M)=h_{k}}$

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

${\displaystyle \{0,1\}^{m_{c}}\times \{0,1\}^{n}\rightarrow \{0,1\}^{m_{c}}}$, где ${\displaystyle m_{c}}$ — размер ${\displaystyle h}$, ${\displaystyle n}$ — размер блока, ${\displaystyle m=m_{c}}$ (чаще всего выходной размер совпадает с размером h)

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

${\displaystyle \{0,1\}^{m_{c}}\times \{0,1\}^{n}\times \{0,1\}^{b}\times \{0,1\}^{s}\rightarrow \{0,1\}^{m_{c}}}$, где ${\displaystyle b,s}$ — длины количества бит и соли,

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

${\displaystyle h_{i}=C(h_{i-1},M_{i},bits,salt)}$ , где

${\displaystyle bits}$ — количество бит, захешированных к этому времени.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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}}}$

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

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

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

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

• 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. Страница Эли Бихама (англ.). — Основная информация, перечень публикаций.