Для произвольного входного сообщения функция генерирует хеш-значение, называемое дайджестом сообщения, которое может иметь длину 128, 160, 192, 224 или 256 бит. Количество итераций — переменное, от 3 до 5. Количество раундов на каждой итерации — 32. Является модификацией MD5.
Содержание
1Алгоритм
1.1Шаг 1. Расширение сообщения
1.2Шаг 2. Обработка сообщения блоками по 1024 бит
1.2.1Функция сжатия H
1.3Шаг 3. Формирование дайджеста сообщения
1.4Константы, использующиеся в алгоритме
1.5Функции '"`UNIQ--postMath-000000DF-QINU`"', '"`UNIQ--postMath-000000E0-QINU`"', '"`UNIQ--postMath-000000E1-QINU`"', '"`UNIQ--postMath-000000E2-QINU`"' и '"`UNIQ--postMath-000000E3-QINU`"'
2HAVAL — хеши
3Сравнение HAVAL и MD5
4Криптоанализ
4.1Коллизии HAVAL
5См. также
6Примечания
7Ссылки
Алгоритм
Определим булевы функции, которые используются для выполнения побитовых операций над словами. 1-я итерация 2-я итерация 3-я итерация 4-я итерация 5-я итерация На вход алгоритма поступает входной поток данных, хеш которого необходимо найти. Этот поток делится на блоки, каждый длиной в 1024 бита. Ниже приведены 3 шага алгоритма.
Шаг 1. Расширение сообщения
Сначала сообщение расширяется так, чтобы его длина в битах стала равной 944 по модулю 1024. Для этого в конец сообщения записывается единичный бит, а затем необходимое число нулевых бит. В оставшиеся 80 бит дописывают 64-битное представление количества бит в сообщении до выравнивания(поле MSGLENG), 10-битное представление длины дайджеста сообщения(поле DGSTLENG),3-битное представление числа итераций(поле PASS) и 3-битное представление версии HAVAL(поле VERSION).
Шаг 2. Обработка сообщения блоками по 1024 бит
Запишем расширенное сообщение в виде: , где — 1024-битный блок и n — количество блоков в расширенном сообщении. Далее, для i от 0 до n-1 проводим следующее вычисление: , где H — функция сжатия, описанная ниже, и — 256-битная константа.
Функция сжатия H
Функция сжатия H
H обрабатывает блок сообщения в течение 3, 4 или 5 итераций(в зависимости от значения поля PASS). Обозначим функции сжатия, использующиеся в итерациях, через и . Пусть — некоторая 256-битная константа, а — 256-битный выход функции H. Тогда H может быть описана следующим образом(см. рисунок):
(Примечание: под операцией вида понимается операция вида: , где 32-битные слова.
Обозначим номер итерации через j (j =1,…,5). Итерации под номером j соответствует функция сжатия . На вход каждой функции подаётся и , где — это 1024-битный блок сообщения, состоящий из 32 слов , a состоит из 8 слов . Тогда может быть записана следующим образом:
1. Пусть
2. Повторяем следующие действия для i от 0 до 31:
, где — 32-битные константы
3. Пусть и является 256-битным выходом .
Обозначения: — композиция двух функций(первой выполняется ),
— сложение по модулю ,
— перестановки, описанные в Таблице 2.
Замечания: на 1-й итерации константы не используются (то есть ).
В отличие от итерации 1, во 2-й и в последующих итерациях обрабатывается не в пословном порядке, а в порядке, определённом Таблицей 1.
Таблица 1. Порядок обработки слов
()
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
()
5
14
26
18
11
28
7
16
0
23
20
22
1
10
4
8
30
3
21
9
17
24
29
6
19
12
15
13
2
25
31
27
()
19
9
4
20
28
17
8
22
29
14
25
12
24
30
16
26
31
15
7
3
1
0
18
27
13
6
21
10
23
11
5
2
()
24
4
0
14
2
7
28
23
26
6
30
20
18
25
19
3
22
11
31
21
8
27
12
9
1
29
5
15
17
10
16
13
()
27
3
21
26
17
11
20
29
19
0
12
7
13
8
31
10
5
9
14
30
18
6
28
24
2
23
16
22
4
1
25
15
Таблица 2. Перестановки
Шаг 3. Формирование дайджеста сообщения
На этом шаге используется длиной в 256 бит, полученный на шаге 2. Если требуемый размер хэша — 256 бит, то и есть дайджест сообщения. Рассмотрим остальные 4 случая.
1. Размер хеша — 128 бит
Представим и в следующем виде:
(верхний индекс указывает на длину X в битах)
Тогда дайджестом сообщения является 128-битовое , где
2. Размер хеша — 160 бит
Представим и в следующем виде:
Тогда дайджестом сообщения является 160-битовое , где
3. Размер хеша — 192 бит
Представим и в следующем виде:
Пусть
— дайджест сообщения.
4. Размер хеша — 224 бит
Представим в следующем виде:
Тогда дайджестом сообщения является 224-битовое , где
Константы, использующиеся в алгоритме
В данном алгоритме используются 136 32-битовых константы. Запишем их в следующем порядке:
Первые 8 констант представляют собой первые 256 бита дробной части числа . Константы соответствуют следующим 1024 битам дробной части и т. д.
Функции , , , и
Булевы функции , , , и , использующиеся в алгоритме, обладают рядом полезных свойств в случае предварительной перестановки их аргументов :
1) Они сбалансированы по 0 и 1. Это значит, что выходом функции при произвольном наборе входных данных с равной вероятностью(1/2) может быть либо 0, либо 1.
3) Они удовлетворяют критерию строгого лавинного эффекта (Strict Avalanche Criterion), т.е при изменении значения любой из входных переменных значение функции меняется с вероятностью 1/2.
4) Они не могут быть получены одна из другой посредством применения линейных преобразований к входным переменным.
5) Этот набор функций — взаимно некоррелирующий по выходу, то есть любая пара функций взаимно не коррелирует по выходу(функции и взаимно не коррелируют по выходу, если , и — сбалансированные по 0 и 1, нелинейные функции)
HAVAL — хеши
HAVAL-хеши обычно представляются в виде последовательности, состоящей из 32, 40, 48, 56 или 64 шестнадцатеричных чисел. Несколько примеров хеша(размер — 256 бит, число итераций — 5):
В отличие от хеш-функции MD5, у которой дайджест и число итераций имеют фиксированные размеры, HAVAL предоставляет 15 различных вариантов алгоритма за счёт комбинирования длины дайджеста и числа итераций. Это обеспечивает большую гибкость и, следовательно, делает хеш-функцию более подходящей для приложений, в которых требуется различная длина хеша сообщения и различный уровень безопасности. Эксперименты показали, что HAVAL на 60 % быстрее MD5 при 3-х итерациях, на 15 % — при 4-х итерациях и столь же быстр при пяти итерациях.
Криптоанализ
Коллизии HAVAL
Коллизия хеш-функции — это получение одинакового значения функции для разных сообщений.
В 2003 году Bart Van Rompay, Алекс Бирюков, Барт Пренель и Joos Vandewalle обнаружили коллизию для 3-итерационного HAVAL. [2] Для нахождения этой коллизии потребовалось приблизительно выполнений функции сжатия H.
В 2004 году китайские исследователи Wang Xiaoyun[англ.], Feng Dengguo, Лай Сюэцзя и Yu Hongbo объявили об обнаруженной ими уязвимости в 3-итерационном HAVAL-128, позволяющей за HAVAL-вычислений находить коллизии.[3]
В 2006 году группа китайских учёных во главе с Wang Xiaoyun и Yu Hongbo провели две атаки на 4-итерационный HAVAL, потребовавшие и операций хеширования соответственно. Они же предложили первую теоретическую атаку на 5-итерационный HAVAL с числом операций хеширования, приблизительно равным .[4]
См. также
MD5
SHA-1
Примечания
↑Токарева Н. Н.Сильно нелинейные булевы функции: бент-функции и их обобщения(рус.) (2008). Архивировано из оригинала 15 февраля 2012 года.
↑Bart Van Rompay, Alex Biryukov, Bart Preneel and Joos Vandewalle.Cryptanalysis of 3-Pass HAVAL(англ.). (недоступная ссылка)
↑Xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu.Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD(англ.) (17 августа 2004). Архивировано из оригинала 23 августа 2011 года.
↑Xiaoyun Wang, Aaram Yun, Sangwoo Park, Hongbo Yu.Cryptanalysis of the Full HAVAL with 4 and 5 Passes(англ.) (2006). (недоступная ссылка)
Ссылки
https://web.archive.org/web/20080905132936/http://labs.calyptix.com/files/haval-paper.pdf — Yuliang Zheng, Josef Pieprzyk and Jennifer Seberry: «HAVAL — a one-way hashing algorithm with variable length of output», Advances in Cryptology — AUSCRYPT’92, Lecture Notes in Computer Science, Vol.718, pp. 83—104, Springer-Verlag, 1993.
https://www.researchgate.net/publication/225789941_HAVAL_-_A_one-way_hashing_algorithm_with_variable_length_of_output_extended_abstract (содержит исправленный порядок констант)