HAIFA

HAIFA (англ. HAsh Iterative FrAmework)— режим итераций для хэш-функций: к функции сжатия добавляется информация о количестве уже захэшированных бит сообщения. Режим был предложен в 2006 году и использовался в нескольких хэш-функциях, например BLAKE, SHAvite-3. Три из 14 кандидатов на конкурс SHA-3 были основаны на HAIFA, один из них стал финалистом.

В отличие от кардинально новой конструкции Sponge (губка), использованной в победителе конкурса SHA-3, хэше Keccak, HAIFA близка по своей структуре к классическому широко используемому методу Merkle Damgård (MD). Однако по сравнению с MD улучшена стойкость к атакам фиксированной точки и поиска второго прообраза.

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

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

Создатели алгоритма

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

Предпосылки к созданию HAIFA

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

Как известно, структура Меркла-Дамгарда представляет собой следующее: у нас есть сообщение M, разбитое на несколько частей: M₁, M₂...M_n. Есть некоторое начальное значение - IV и некоторая функция C, которая подсчитывает промежуточное представление нашей хэш-функции H определенным образом:

<math>h_0=IV</math>

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

<math>h_i=C(h_{i-1}, M_i)</math>

<math>H(M)=h_k</math>

В атаке на второй прообраз можно было бы искать такое значение M' , для которого <math>H(M')=h_i=H(M_i)</math>, т.е. хэш от M' равен какому-либо промежуточному значению в итерациях, и далее соединить часть оставшегося сообщения M(находящуюся справа от M') с нашим угаданным M'. В итоге <math>H(M)=H(M')</math>. Однако алгоритм был признан устойчивым к этой атаке, так как в усовершенствованном варианте в конец сообщения дописывался его размер. В силу того , что размеры для M и M' различались, невозможно (или достаточно сложно) было подобрать такое M'. Дин же в своей работе указал совершенно новый способ атаки, основанный на предположении, что для данной функции C легко найти фиксированные точки ( по определению фиксированная точка - та, для которой выполняется соотношение <math>h=C(h, M_i)</math>). В его алгоритме недостающая длина сообщения восполнялась добавлением множества фиксированных точек, т.е. мы могли достаточным количеством повторений значения h дополнить нашу длину до нужной. В дальнейшем Кэлси и Шнайер усовершенствовали его атаку, отказавшись от предположения, что для данной C легко находить фиксированные точки, и находили множественные коллизии в блоках. При этом длина сообщения уже контролировалась расширяющимся префиксом.

Также в качестве одной из причин для создания нового алгоритма стоит упомянуть труды Джоукса, в которых он описал возможность нахождения <math>2^t</math> сообщений, имеющих один и тот же хэш. Его работа базируется на факте, что возможно найти t таких одноблочных коллизий, в которых <math>C(h_{i-1},M_i)=C(h_{i-1},M_i^*)</math>, и далее конструировать различные сообщения, всего <math>2^t</math> вариантов,выбирая на каждом из t шагов либо сообщение <math>M_i</math>, либо <math>M_i^*</math> . Немаловажную роль в желании разработать новый режим итерации хэш-функции сыграла возможность осуществления хэрдинг атаки на алгоритм Меркла-Дамгарда. Хэрдинг атака основана на том, что атакующий пытается найти такой суффикс по заданному префиксу, который будет давать нужное значение хэша

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

Алгоритм HAIFA

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

<math>\{0,1\}^{m_c}\times\{0,1\}^{n} \rightarrow\{0,1\}^{m_c}</math>

мы используем:

<math>\{0,1\}^{m_c}\times\{0,1\}^{n}\times\{0,1\}^{b}\times\{0,1\}^{s} \rightarrow\{0,1\}^{m_c}</math>

а внутреннее представление подсчитывается:

<math>h_i=C(h_{i-1}, M_i, bits, salt)</math> , где

<math>bits</math> - количество бит, захэшированных к этому времени.

Поэтому алгоритм может быть описан следующими шагами:

1. Дополнить сообщение <math>M</math> в соответствии с нижеописанной схемой.
2. Подсчитать начальное значение <math>IV_m</math> для внутренней ячейки размера m в соответствии с с алгоритмом, описанным ниже.
3. Итеративно пройти по дополненному сообщению (соответственно разбитому на части) , добавляя соль на каждом шаге. Стоит отметить, что если к сообщению добавляется дополнительный блок ( в самый конец), то для этого блока выставляем значение <math>bits</math> равное нулю.
4. Обрезать последнее, выходное, значение функции,если необходимо.

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

В HAIFA сообщение M дополняется единицей, необходимым количеством нулей, длиной сообщения в битах и размером внутреннего блока h. Т.е добавляем последовательность ( количество единиц в данном случае должно быть таким, чтобы <math>N_1+N_0\equiv N- (M_{length}+D_{size}) mod N</math> :

<math>0+{1..1}+bits+m_c</math>

Хэшируя сообщение , дополненное размером внутреннего блока, мы избавляемся от проблемы нахождения коллизий, так как если два сообщения M1 и M2 хэшируются с размерами блока l1 и l2 , то от коллизий спасает именно последний блок.

В свою очередь, добавляя bits = 0 в самом последнем блоке, мы создаем сигнал для обозначения последнего и дополняющего блока.

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

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

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

Можно с уверенностью сказать, что количество захэшированных бит значительно затрудняет поиск и использование фиксированных точек. Даже найдя такое h и M , для которых выполняется <math>h_i=C(h_{i}, M_i, bits, salt)</math>, мы не сможем бесконечно размножать эти значения в нашем алгоритме,потому что количество битов будет все время меняться.

Соль (salt), как и bits, тоже вносит свой вклад в стойкость нового алгоритма. Она обладает тройкой очень неплохих свойств:

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

Но гораздо нагляднее будет показать , как HAIFA справляется с вышеупомянутыми атаками:

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

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

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

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

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

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

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

Тип атаки	Идеальная хэш-функция	MD	HAIFA (фиксированное значение соли)	HAIFA (с различными значениями соли)
Атака на первый прообраз	<math>2^{m_c}</math>	<math>2^{m_c}</math>	<math>2^{m_c}</math>	<math>2^{m_c}</math>
Атака на один из первых прообразов	<math>{\displaystyle 2^{m_{c}}}/k'</math>	<math>{\displaystyle 2^{m_{c}}}/k'</math>	<math>{\displaystyle 2^{m_{c}}}/k'</math>	<math>2^{m_c}</math>
Атака на второй прообраз	<math>2^{m_c}</math>	<math>2^{m_c}/k</math>	<math>2^{m_c}</math>	<math>2^{m_c}</math>
Атака на один из вторых прообразов	<math>{\displaystyle 2^{m_{c}}}/k'</math>	<math>2^{m_c}/k</math>	<math>{\displaystyle 2^{m_{c}}}/k'</math>	<math>2^{m_c}</math>
Коллизии	<math>2^{m_c/2}</math>	<math>2^{m_c/2}</math>	<math>2^{m_c/2}</math>	<math>2^{m_c/2}</math>
Множественные коллизии	<math>2^{m_c(k-1)/k}</math>	<math>\left \lceil {log_2k} \right \rceil2^{m_c/2}</math>	<math>\left \lceil {log_2k} \right \rceil2^{m_c/2}</math>	<math>\left \lceil {log_2k} \right \rceil2^{m_c/2}</math>
Herding	-	Offline:<math>2^{m_c/2+t/2}</math> Online:<math>2^{m_c-t}</math>	Offline:<math>2^{m_c/2+t/2}</math> Online:<math>2^{m_c-t}</math>	Offline:<math>2^{m_c/2+t/2+s}</math> Online:<math>2^{m_c-t}</math>

Некоторые приложения HAIFA

HAIFA может являться основой множества алгоритмов, так как представляет cобой новую, усовершенствованную базовую конструкцию. На ней могут быть основаны Randomized Hashing, Enveloped Merkle-Damgard, RMC, ROX, Wide-Pipe Hash.

Пример : Wide-Pipe хэш

Один из наиболее интуитивных способов конструкции хэш-функции, который можно получить из HAIFA. Желая повысить сложность, делаем длину внутренних блоков в два раза больше, чем длину конечного блока. Можно непосредственно вывести формулу для Wide-Pipe, помня о том, что находить в HAIFA последний блок очень легко, так как bits там выставлены ноль). Формула для перевода из HAIPA в Wide-Pipe:

<math>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}</math>

где <math>C':\{0,1\}^{m_c}\times\{0,1\}^n\rightarrow\{0,1\}^{m_c}</math>

<math> C:\{0,1\}^{m_{c}}\rightarrow\{0,1\}^{m}</math>

<math>IV_2</math> - второй вектор инициализации.

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

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

См. также

• Wide pipe
• Sponge
• Merkle Damgård
• Эли Бихам

Литература

• Eli Biham and Orr Dunkelman. [eprint.iacr.org/2007/278 A framework for iterative hash functions - HAIFA]. — ePrint, 2007.
• Orr Dunkelman. [www.cs.haifa.ac.il/~orrd/crypt/Lorentz-Haifa.pdf Re-visiting HAIFA. Talk at the workshop Hash functions in cryptology: theory and practice]. — 2008. — 207 с.
• [citeseerx.ist.psu.edu/viewdoc/download?rep=rep1&type=pdf&doi=10.1.1.218.1717 Modern Hash Function Construction], 2011
• eprint.iacr.org/2005/281.pdf
• [www.cosic.esat.kuleuven.be/publications/thesis-209.pdf#page=31]
• Enveloped Merkle-Damgard. pages.cs.wisc.edu/~rist/papers/ac06pres.pdf