WikiSort.ru - Не сортированное

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 к различным типам атак.

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

Основной источник: ^[7]

Для множественных коллизий французский криптограф Антуан Жу^[en] описал возможность нахождения ${\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].

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

Тип атаки	Идеальная хеш-функция	MD	HAIFA (фиксированное значение соли)	HAIFA (с различными значениями соли)
Атака на первый прообраз[en] (${\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 (англ.) (2007-2012). — Описание предложенных на конкурсе хеш-функций, результаты раундов.
• Eli Biham. Страница Эли Бихама (англ.). — Основная информация, перечень публикаций.

Эта статья входит в число добротных статей русскоязычного раздела Википедии.