HAIFA

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

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

История

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

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

Алгоритм

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

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

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

$h_{0}=IV$

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

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

$H(M)=h_{k}$

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

$\{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$ — количество бит, захешированных к этому времени.

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

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

Дополнение сообщения

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

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

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

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

Длина хеша

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

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

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

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

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

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

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

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

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

Основной источник:

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

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

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

Основной источник:

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

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

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

Хэрдинг-атака

Основной источник:

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

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

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

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

Основной источник:

Тип атаки	Идеальная хеш-функция	MD	HAIFA (фиксированное значение соли)	HAIFA (с различными значениями соли)
Атака на первый прообраз ($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$ блоков)	$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$ — количество коллизий)	$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	-	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обой новую усовершенствованную базовую конструкцию. Доказано, что с её использованием могут быть разработаны функции рандомизированного хеширования, обёрнутая функция Меркла — Дамгора (англ. Enveloped Merkle-Damgard, RMC, ширококонвейрного хеша.

Ширококонвейерный хеш

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

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

Формула для перевода из 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}$ — второй вектор инициализации.

Прикладное значение

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

Литература

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