HAIFA

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

Был предложен в 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\to \{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\to \{0,1{\}}^{m_c}$, где $b,s$ — длины количества бит и соли,

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

$h_i=C(h_{i-1},M_i,bits,salt)$ , где

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

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

1. Дополнить сообщение $M$ в соответствии с нижеописанной схемой.
2. Подсчитать начальное значение $I{V}_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. Считаем преобразованное начальное значение : $I{V}_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 к различным типам атак.

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

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

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

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

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

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

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

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

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

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 (с различными значениями соли)
Шаблон:Iw ($k^{\text{'}}<2^s$ целей)	$2^{m_c}$	$2^{m_c}$	$2^{m_c}$	$2^{m_c}$
Атака на один из первых прообразов	$2^{m_c}/k^{\prime }$	$2^{m_c}/k^{\prime }$	$2^{m_c}/k^{\prime }$	$2^{m_c}$
Атака на второй прообраз ($k$ блоков)	$2^{m_c}$	$2^{m_c}/k$	$2^{m_c}$	$2^{m_c}$
Атака на один из вторых прообразов ($k$ блоков, $k^{\text{'}}<2^s$ сообщений)	$2^{m_c}/k^{\prime }$	$2^{m_c}/k$	$2^{m_c}/k^{\prime }$	$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}$	$\lceil lo{g}_{2}k\rceil 2^{m_c/2}$	$\lceil lo{g}_{2}k\rceil 2^{m_c/2}$	$\lceil lo{g}_{2}k\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обой новую усовершенствованную базовую конструкцию. Доказано, что с её использованием могут быть разработаны функции рандомизированного хеширования, обёрнутая функция Меркла — Дамгора (Шаблон:Lang-en, RMC, ширококонвейрного хеша.

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

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

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

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

$C_{HAIFA}(h_{i-1},M_i,bits,s)=\{\begin{array}{cc}{C}^{″}(C^{\prime }(I{V}_2,h_{i-1}||fixpad(M_i))),& \text{if }\text{ last block}\\ C^{\prime }(h_{i-1},M_i),& \text{otherwise}\end{array}$

где $C^{\prime }:\{0,1{\}}^{m_c}\times \{0,1{\}}^n\to \{0,1{\}}^{m_c}$

$C^{″}:\{0,1{\}}^{m_c}\to \{0,1{\}}^m$

$I{V}_2$ — второй вектор инициализации.

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

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

Литература

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга

Ссылки

• Шаблон:Публикация
• Шаблон:Cite web
• Шаблон:Cite web