HAVAL

Криптографическая</br>хеш-функция
Название	HAVAL
Создан	1992
Опубликован	1992
Размер хеша	128, 160, 192, 224, 256 бит
Число раундов	96, 128, 160
Тип	хеш-функция

HAVAL — криптографическая хеш-функция, разработанная Yuliang Zheng (англ.) , Josef Pieprzyk (англ.) и Jennifer Seberry (англ.) в 1992 году. Для произвольного входного сообщения функция генерирует хеш-значение, называемое дайджестом сообщения, которое может иметь длину 128, 160, 192, 224 или 256 бит. Количество итераций — переменное, от 3 до 5. Количество раундов на каждой итерации — 32. Является модификацией MD5.

Алгоритм

Определим булевы функции, которые используются для выполнения побитовых операций над словами.
1-я итерация <math>F_1(x_6,x_5,x_4,x_3,x_2,x_1,x_0)=x_1 x_4\oplus x_2 x_5\oplus x_3 x_6\oplus x_0 x_1\oplus x_0</math>
2-я итерация <math>F_2(x_6,x_5,x_4,x_3,x_2,x_1,x_0)=x_1 x_2 x_3\oplus x_2 x_4 x_5\oplus x_1 x_2\oplus x_1 x_4\oplus x_2 x_6 \oplus x_3 x_5\oplus x_4 x_5\oplus x_0 x_2\oplus x_0</math>
3-я итерация <math>F_3(x_6,x_5,x_4,x_3,x_2,x_1,x_0)=x_1 x_2 x_3\oplus x_1 x_4\oplus x_2 x_5\oplus x_3 x_6\oplus x_0 x_3\oplus x_0</math>
4-я итерация <math>F_4(x_6,x_5,x_4,x_3,x_2,x_1,x_0)=x_1 x_2 x_3\oplus x_2 x_4 x_5\oplus x_3 x_4 x_6\oplus x_1 x_4\oplus x_2 x_6 \oplus x_3 x_4\oplus x_3 x_5\oplus x_3 x_6\oplus x_4 x_5 \oplus x_4 x_6\oplus x_0 x_4\oplus x_0</math>
5-я итерация <math>F_5(x_6,x_5,x_4,x_3,x_2,x_1,x_0)=x_1 x_4\oplus x_2 x_5\oplus x_3 x_6\oplus x_0 x_1 x_2 x_3\oplus x_0 x_5\oplus x_0</math>
На вход алгоритма поступает входной поток данных, хеш которого необходимо найти. Этот поток делится на блоки, каждый длиной в 1024 бита. Ниже приведены 3 шага алгоритма.

Шаг 1. Расширение сообщения

Сначала сообщение расширяется так, чтобы его длина в битах стала равной 944 по модулю 1024. Для этого в конец сообщения записывается единичный бит, а затем необходимое число нулевых бит. В оставшиеся 80 бит дописывают 64-битное представление количества бит в сообщении до выравнивания(поле MSGLENG), 10-битное представление длины дайджеста сообщения(поле DGSTLENG),3-битное представление числа итераций(поле PASS) и 3-битное представление версии HAVAL(поле VERSION).

Шаг 2. Обработка сообщения блоками по 1024 бит

Запишем расширенное сообщение в виде: <math>B_{n-1} B_{n-2} \ldots B_0</math>, где <math>B_{i}</math> — 1024-битный блок и n — количество блоков в расширенном сообщении.
Далее, для i от 0 до n-1 проводим следующее вычисление:
<math>D_{i+1} = H(D_i,B_i)</math> , где H — функция сжатия, описанная ниже, и <math>D_0</math> — 256-битная константа.

Функция сжатия H

H обрабатывает блок сообщения в течение 3, 4 или 5 итераций(в зависимости от значения поля PASS). Обозначим функции сжатия, использующиеся в итерациях, через <math>H_1, H_2, H_3, H_4 </math> и <math>H_5 </math>. Пусть <math>D_{in}</math> — некоторая 256-битная константа, а <math>D_{out}</math> — 256-битный выход функции H. Тогда H может быть описана следующим образом(см. рисунок):

<math>E_0 = D_{in};</math>
<math>E_1 = H_1(E_0,B);</math>
<math>E_2 = H_2(E_1,B);</math>
<math>E_3 = H_3(E_2,B);</math>
<math>E_4 = H_4(E_3,B);\qquad \mbox{if PASS=4, 5}</math>
<math>E_5 = H_5(E_4,B);\qquad \mbox{if PASS=5}</math>
<math>D_{out} = \begin{cases} E_3 \boxplus E_0, & \mbox{if PASS=3} \\ E_4 \boxplus E_0, & \mbox{if PASS=4} \\ E_5 \boxplus E_0, & \mbox{if PASS=5} \end{cases}</math>
(Примечание: под операцией вида <math>D_{out} = E_x \boxplus E_y;</math> понимается операция вида: <math>D_{out, n-1} = E_{x, n-1} \boxplus E_{y,n-1}; D_{out,n-2} = E_{x,n-2} \boxplus E_{y,n-2}; \dots D_{out,0} = E_{x,0} \boxplus E_{y,0};</math>, где <math>D_{out, i}, E_{x, i}, E_{y, i}, 0 \leqslant i\leqslant n-1</math> 32-битные слова.

Обозначим номер итерации через j (j =1,…,5). Итерации под номером j соответствует функция сжатия <math>H_j </math>. На вход каждой функции <math>H_j </math>подаётся <math>B</math> и <math>E_{j-1}</math>, где <math>B</math> — это 1024-битный блок сообщения, состоящий из 32 слов <math>W_{31}W_{30} \dots W_0</math>, a <math>E_{j-1}</math> состоит из 8 слов <math>E_{j-1,7}E_{j-1,6} \dots E_{j-1,0}</math>. Тогда <math>H_j</math> может быть записана следующим образом:

1. Пусть <math>T_{0,i} = E_{j-1,i} , 0\leqslant i\leqslant 7</math>

2. Повторяем следующие действия для i от 0 до 31:

<math> P = \begin{cases}

F_j \circ \phi_{3,j}(T_{i,6}, T_{i,5}, T_{i,4}, T_{i,3}, T_{i,2}, T_{i,1}, T_{i,0}), & \mbox{if PASS=3} \\ F_j \circ \phi_{4,j}(T_{i,6}, T_{i,5}, T_{i,4}, T_{i,3}, T_{i,2}, T_{i,1}, T_{i,0}), & \mbox{if PASS=4} \\ F_j \circ \phi_{5,j}(T_{i,6}, T_{i,5}, T_{i,4}, T_{i,3}, T_{i,2}, T_{i,1}, T_{i,0}), & \mbox{if PASS=5} \end{cases}</math>

<math>R = (P \gggtr 7)\boxplus (T_{i,7} \gggtr 11)\boxplus W_{ord_j(i)} \boxplus K_{j,i}</math>, где <math>K_{j,i}</math> — 32-битные константы

<math>T_{i+1,7} = T_{i,6} ;\ T_{i+1,6} = T_{i,5} ;\ T_{i+1,5} = T_{i,4} ;\ T_{i+1,4} = T_{i,3};</math>

<math>T_{i+1,3} = T_{i,2} ;\ T_{i+1,2} = T_{i,1} ;\ T_{i+1,1} = T_{i,0} ;\ T_{i+1,0} = R.</math>

3. Пусть <math>E_{j,i} = T_{32,i} , 0\leqslant i\leqslant 7</math> и <math>E_j = E_{j,7}E_{j,6} \dots E_{j,0}</math> является 256-битным выходом <math>H_j</math>.

Обозначения: <math>f \circ g </math> — композиция двух функций(первой выполняется <math>g</math>),

<math>\boxplus</math> — сложение по модулю <math>2^{32}</math>,

<math>\phi_{3,j}, \phi_{4,j}, \phi_{5,j} </math> — перестановки, описанные в Таблице 2.

Замечания: на 1-й итерации константы не используются (то есть <math>K_{j,i} = 0 , 0\leqslant i\leqslant 31</math>).

В отличие от итерации 1, во 2-й и в последующих итерациях <math>B</math> обрабатывается не в пословном порядке, а в порядке, определённом Таблицей 1.

Таблица 1. Порядок обработки слов

<math>ord_1 </math> (<math>H_1</math>)	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
<math>ord_2 </math> (<math>H_2</math>)	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
<math>ord_3 </math> (<math>H_3</math>)	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
<math>ord_4 </math> (<math>H_4</math>)	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
<math>ord_5 </math> (<math>H_5</math>)	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. Перестановки

	<math>x_6</math> <math>\downarrow</math>	<math>x_5</math> <math>\downarrow</math>	<math>x_4</math> <math>\downarrow</math>	<math>x_3</math> <math>\downarrow</math>	<math>x_2</math> <math>\downarrow</math>	<math>x_1</math> <math>\downarrow</math>	<math>x_0</math> <math>\downarrow</math>
<math>\phi_{3,1}</math>	<math>x_1</math>	<math>x_0</math>	<math>x_3</math>	<math>x_5</math>	<math>x_6</math>	<math>x_2</math>	<math>x_4</math>
<math>\phi_{3,2}</math>	<math>x_4</math>	<math>x_2</math>	<math>x_1</math>	<math>x_0</math>	<math>x_5</math>	<math>x_3</math>	<math>x_6</math>
<math>\phi_{3,3}</math>	<math>x_6</math>	<math>x_1</math>	<math>x_2</math>	<math>x_3</math>	<math>x_4</math>	<math>x_5</math>	<math>x_0</math>
<math>\phi_{4,1}</math>	<math>x_2</math>	<math>x_6</math>	<math>x_1</math>	<math>x_4</math>	<math>x_5</math>	<math>x_3</math>	<math>x_0</math>
<math>\phi_{4,2}</math>	<math>x_3</math>	<math>x_5</math>	<math>x_2</math>	<math>x_0</math>	<math>x_1</math>	<math>x_6</math>	<math>x_4</math>
<math>\phi_{4,3}</math>	<math>x_1</math>	<math>x_4</math>	<math>x_3</math>	<math>x_6</math>	<math>x_0</math>	<math>x_2</math>	<math>x_5</math>
<math>\phi_{4,4}</math>	<math>x_6</math>	<math>x_4</math>	<math>x_0</math>	<math>x_5</math>	<math>x_2</math>	<math>x_1</math>	<math>x_3</math>
<math>\phi_{5,1}</math>	<math>x_3</math>	<math>x_4</math>	<math>x_1</math>	<math>x_0</math>	<math>x_5</math>	<math>x_2</math>	<math>x_6</math>
<math>\phi_{5,2}</math>	<math>x_6</math>	<math>x_2</math>	<math>x_1</math>	<math>x_0</math>	<math>x_3</math>	<math>x_4</math>	<math>x_5</math>
<math>\phi_{5,3}</math>	<math>x_2</math>	<math>x_6</math>	<math>x_0</math>	<math>x_4</math>	<math>x_3</math>	<math>x_1</math>	<math>x_5</math>
<math>\phi_{5,4}</math>	<math>x_1</math>	<math>x_5</math>	<math>x_3</math>	<math>x_2</math>	<math>x_0</math>	<math>x_4</math>	<math>x_6</math>
<math>\phi_{5,5}</math>	<math>x_2</math>	<math>x_5</math>	<math>x_0</math>	<math>x_6</math>	<math>x_4</math>	<math>x_3</math>	<math>x_1</math>

Шаг 3. Формирование дайджеста сообщения

На этом шаге используется <math>D_n = D_{n,7}D_{n,6}\dots D_{n,0} </math> длиной в 256 бит, полученный на шаге 2. Если требуемый размер хэша — 256 бит, то <math>D_n</math> и есть дайджест сообщения. Рассмотрим остальные 4 случая.

1. Размер хеша — 128 бит

Представим <math>D_{n,7}, D_{n,6},D_{n,5}</math> и <math>D_{n,4}</math> в следующем виде:

<math>D_{n,7} = X_{7,3}^{[8]}X_{7,2}^{[8]}X_{7,1}^{[8]}X_{7,0}^{[8]}</math>

<math>D_{n,6} = X_{6,3}^{[8]}X_{6,2}^{[8]}X_{6,1}^{[8]}X_{6,0}^{[8]}</math>

<math>D_{n,5} = X_{5,3}^{[8]}X_{5,2}^{[8]}X_{5,1}^{[8]}X_{5,0}^{[8]}</math>

<math>D_{n,4} = X_{4,3}^{[8]}X_{4,2}^{[8]}X_{4,1}^{[8]}X_{4,0}^{[8]}</math> (верхний индекс указывает на длину X в битах)

Тогда дайджестом сообщения является 128-битовое <math>Y_3Y_2Y_1Y_0</math>, где

<math>Y_3 = D_{n,3}\boxplus (X_{7,3}^{[8]}X_{6,2}^{[8]}X_{5,1}^{[8]}X_{4,0}^{[8]})</math>

<math>Y_2 = D_{n,2}\boxplus (X_{7,2}^{[8]}X_{6,1}^{[8]}X_{5,0}^{[8]}X_{4,3}^{[8]})</math>

<math>Y_1 = D_{n,1}\boxplus (X_{7,1}^{[8]}X_{6,0}^{[8]}X_{5,3}^{[8]}X_{4,2}^{[8]})</math>

<math>Y_0 = D_{n,0}\boxplus (X_{7,0}^{[8]}X_{6,3}^{[8]}X_{5,2}^{[8]}X_{4,1}^{[8]})</math>

2. Размер хеша — 160 бит

Представим <math>D_{n,7}, D_{n,6}</math> и <math>D_{n,5}</math> в следующем виде:

<math>D_{n,7} = X_{7,4}^{[7]}X_{7,3}^{[6]}X_{7,2}^{[7]}X_{7,1}^{[6]}X_{7,0}^{[6]}</math>

<math>D_{n,6} = X_{6,4}^{[7]}X_{6,3}^{[6]}X_{6,2}^{[7]}X_{6,1}^{[6]}X_{6,0}^{[6]}</math>

<math>D_{n,5} = X_{5,4}^{[7]}X_{5,3}^{[6]}X_{5,2}^{[7]}X_{5,1}^{[6]}X_{5,0}^{[6]}</math>

Тогда дайджестом сообщения является 160-битовое <math>Y_4Y_3Y_2Y_1Y_0</math>, где

<math>Y_4 = D_{n,4}\boxplus (X_{7,4}^{[7]}X_{6,3}^{[6]}X_{5,2}^{[7]})</math>

<math>Y_3 = D_{n,3}\boxplus (X_{7,3}^{[6]}X_{6,2}^{[7]}X_{5,1}^{[6]})</math>

<math>Y_2 = D_{n,2}\boxplus (X_{7,2}^{[7]}X_{6,1}^{[6]}X_{5,0}^{[6]})</math>

<math>Y_1 = D_{n,1}\boxplus (X_{7,1}^{[6]}X_{6,0}^{[6]}X_{5,4}^{[7]})</math>

<math>Y_0 = D_{n,0}\boxplus (X_{7,0}^{[6]}X_{6,4}^{[7]}X_{5,3}^{[6]})</math>

3. Размер хеша — 192 бит

Представим <math>D_{n,7}</math> и <math>D_{n,6}</math> в следующем виде:

<math>D_{n,7} = X_{7,5}^{[6]}X_{7,4}^{[5]}X_{7,3}^{[5]}X_{7,2}^{[6]}X_{7,1}^{[5]}X_{7,0}^{[5]}</math>

<math>D_{n,6} = X_{6,5}^{[6]}X_{6,4}^{[5]}X_{6,3}^{[5]}X_{6,2}^{[6]}X_{6,1}^{[5]}X_{6,0}^{[5]}</math>

Пусть

<math>Y_5 = D_{n,5}\boxplus (X_{7,5}^{[6]}X_{6,4}^{[5]})</math>

<math>Y_4 = D_{n,4}\boxplus (X_{7,4}^{[5]}X_{6,3}^{[5]})</math>

<math>Y_3 = D_{n,3}\boxplus (X_{7,3}^{[5]}X_{6,2}^{[6]})</math>

<math>Y_2 = D_{n,2}\boxplus (X_{7,2}^{[6]}X_{6,1}^{[5]})</math>

<math>Y_1 = D_{n,1}\boxplus (X_{7,1}^{[5]}X_{6,0}^{[5]})</math>

<math>Y_0 = D_{n,0}\boxplus (X_{7,0}^{[5]}X_{6,5}^{[6]})</math>

<math>Y_5Y_4Y_3Y_2Y_1Y_0</math> — дайджест сообщения.

4. Размер хеша — 224 бит

Представим <math>D_{n,7}</math> в следующем виде:

<math>D_{n,7} = X_{7,6}^{[5]}X_{7,5}^{[5]}X_{7,4}^{[4]}X_{7,3}^{[5]}X_{7,2}^{[4]}X_{7,1}^{[5]}X_{7,0}^{[4]}</math>

Тогда дайджестом сообщения является 224-битовое <math>Y_6Y_5Y_4Y_3Y_2Y_1Y_0</math>, где

<math>Y_6 = D_{n,6}\boxplus (X_{7,0}^{[4]})</math>

<math>Y_5 = D_{n,5}\boxplus (X_{7,1}^{[5]})</math>

<math>Y_4 = D_{n,4}\boxplus (X_{7,2}^{[4]})</math>

<math>Y_3 = D_{n,3}\boxplus (X_{7,3}^{[5]})</math>

<math>Y_2 = D_{n,2}\boxplus (X_{7,4}^{[4]})</math>

<math>Y_1 = D_{n,1}\boxplus (X_{7,5}^{[5]})</math>

<math>Y_0 = D_{n,0}\boxplus (X_{7,6}^{[4]})</math>

Константы, использующиеся в алгоритме

В данном алгоритме используются 136 32-битовых константы. Запишем их в следующем порядке:

1.<math>D_{0,7},D_{0,6},\dots,D_{0,0}</math>

2.<math>K_{2,31},K_{2,30},\dots,K_{2,0}</math>

3.<math>K_{3,31},K_{3,30},\dots,K_{3,0}</math>

4.<math>K_{4,31},K_{4,30},\dots,K_{4,0}</math>

5.<math>K_{5,31},K_{5,30},\dots,K_{5,0}</math>

243F6A88 85A308D3 13198A2E 03707344 A4093822 299F31D0 082EFA98 EC4E6C89

452821E6 38D01377 BE5466CF 34E90C6C C0AC29B7 C97C50DD 3F84D5B5 B5470917
9216D5D9 8979FB1B D1310BA6 98DFB5AC 2FFD72DB D01ADFB7 B8E1AFED 6A267E96
BA7C9045 F12C7F99 24A19947 B3916CF7 0801F2E2 858EFC16 636920D8 71574E69
A458FEA3 F4933D7E 0D95748F 728EB658 718BCD58 82154AEE 7B54A41D C25A59B5

9C30D539 2AF26013 C5D1B023 286085F0 CA417918 B8DB38EF 8E79DCB0 603A180E
6C9E0E8B B01E8A3E D71577C1 BD314B27 78AF2FDA 55605C60 E65525F3 AA55AB94
57489862 63E81440 55CA396A 2AAB10B6 B4CC5C34 1141E8CE A15486AF 7C72E993
B3EE1411 636FBC2A 2BA9C55D 741831F6 CE5C3E16 9B87931E AFD6BA33 6C24CF5C

7A325381 28958677 3B8F4898 6B4BB9AF C4BFE81B 66282193 61D809CC FB21A991
487CAC60 5DEC8032 EF845D5D E98575B1 DC262302 EB651B88 23893E81 D396ACC5
0F6D6FF3 83F44239 2E0B4482 A4842004 69C8F04A 9E1F9B5E 21C66842 F6E96C9A
670C9C61 ABD388F0 6A51A0D2 D8542F68 960FA728 AB5133A3 6EEF0B6C 137A3BE4

BA3BF050 7EFB2A98 A1F1651D 39AF0176 66CA593E 82430E88 8CEE8619 456F9FB4
7D84A5C3 3B8B5EBE E06F75D8 85C12073 401A449F 56C16AA6 4ED3AA62 363F7706
1BFEDF72 429B023D 37D0D724 D00A1248 DB0FEAD3 49F1C09B 075372C9 80991B7B
25D479D8 F6E8DEF7 E3FE501A B6794C3B 976CE0BD 04C006BA C1A94FB6 409F60C4

Первые 8 констант <math>D_{0,0},D_{0,1},\dots,D_{0,7}</math> представляют собой первые 256 бита дробной части числа <math>\pi</math>. Константы <math>K_{2,0},K_{2,1},\dots,K_{2,31}</math> соответствуют следующим 1024 битам дробной части <math>\pi</math> и т. д.

Функции <math>F_1</math>, <math>F_2</math>, <math>F_3</math>, <math>F_4</math> и <math>F_5</math>

Булевы функции <math>F_1</math>, <math>F_2</math>, <math>F_3</math>, <math>F_4</math> и <math>F_5</math>, использующиеся в алгоритме, обладают рядом полезных свойств в случае предварительной перестановки их аргументов :

1) Они сбалансированы по 0 и 1. Это значит, что выходом функции при произвольном наборе входных данных с равной вероятностью(1/2) может быть либо 0, либо 1.

2) Они сильно нелинейные.

3) Они удовлетворяют критерию строгого лавинного эффекта (Strict Avalanche Criterion), т.е при изменении значения любой из входных переменных значение функции меняется с вероятностью 1/2.

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

5) Этот набор функций — взаимно некоррелирующий по выходу, то есть любая пара функций взаимно не коррелирует по выходу(функции <math>f</math> и <math>g</math> взаимно не коррелируют по выходу, если <math>f</math>, <math>g</math> и <math>f \oplus g</math> — сбалансированные по 0 и 1, нелинейные функции)

HAVAL — хеши

HAVAL-хеши обычно представляются в виде последовательности, состоящей из 32, 40, 48, 56 или 64 шестнадцатеричных чисел.
Несколько примеров хеша(размер — 256 бит, число итераций — 5):

HAVAL("The quick brown fox jumps over the lazy dog") =
b89c551cdfe2e06dbd4cea2be1bc7d557416c58ebb4d07cbc94e49f710c55be4

Даже небольшое изменение входного сообщения (в нашем случае, на один символ: символ «d» заменяется на символ «c») приводит к полному изменению хеша.

HAVAL("The quick brown fox jumps over the lazy cog") = 
60983bb8c8f49ad3bea29899b78cd741f4c96e911bbc272e5550a4f195a4077e

Пример HAVAL-хеша для «нулевой» строки:

HAVAL("") =
be417bb4dd5cfb76c7126f4f8eeb1553a449039307b1a3cd451dbfdc0fbbe330

Сравнение HAVAL и MD5

В отличие от хеш-функции MD5, у которой дайджест и число итераций имеют фиксированные размеры, HAVAL предоставляет 15 различных вариантов алгоритма за счёт комбинирования длины дайджеста и числа итераций. Это обеспечивает большую гибкость и, следовательно, делает хеш-функцию более подходящей для приложений, в которых требуется различная длина хеша сообщения и различный уровень безопасности.
Эксперименты показали, что HAVAL на 60 % быстрее MD5 при 3-х итерациях, на 15 % — при 4-х итерациях и столь же быстр при пяти итерациях.

Криптоанализ

Коллизии HAVAL

Коллизия хеш-функции — это получение одинакового значения функции для разных сообщений.
В 2003 году Bart Van Rompay, Alex Biryukov (англ.) и др. обнаружили коллизию для 3-итерационного HAVAL. Для нахождения этой коллизии потребовалось приблизительно <math>2^{29}</math> выполнений функции сжатия H.
В 2004 году китайские исследователи Wang Xiaoyun (англ.), Feng Dengguo, Lai Xuejia (англ.) и Yu Hongbo объявили об обнаруженной ими уязвимости в 3-итерационном HAVAL-128, позволяющей за <math>2^7</math> HAVAL-вычислений находить коллизии.
В 2006 году группа китайских учёных во главе с Wang Xiaoyun и Yu Hongbo провели две атаки на 4-итерационный HAVAL, потребовавшие <math>2^{43}</math> и <math>2^{36}</math> операций хеширования соответственно. Они же предложили первую теоретическую атаку на 5-итерационный HAVAL с числом операций хеширования, приблизительно равным <math>2^{123}</math>.

См. также

• MD5
• SHA-1

Ссылки

• 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.
• [www.webutils.pl/index.php?idx=haval Онлайн-вычисление HAVAL-хешей]

Отрывок, характеризующий HAVAL

Наташа удивленно, любопытными глазами смотрела на Соню и молчала. Она чувствовала, что то, что говорила Соня, была правда, что была такая любовь, про которую говорила Соня; но Наташа ничего подобного еще не испытывала. Она верила, что это могло быть, но не понимала.
– Ты напишешь ему? – спросила она.
Соня задумалась. Вопрос о том, как писать к Nicolas и нужно ли писать и как писать, был вопрос, мучивший ее. Теперь, когда он был уже офицер и раненый герой, хорошо ли было с ее стороны напомнить ему о себе и как будто о том обязательстве, которое он взял на себя в отношении ее.
– Не знаю; я думаю, коли он пишет, – и я напишу, – краснея, сказала она.
– И тебе не стыдно будет писать ему?
Соня улыбнулась.
– Нет.
– А мне стыдно будет писать Борису, я не буду писать.
– Да отчего же стыдно?Да так, я не знаю. Неловко, стыдно.
– А я знаю, отчего ей стыдно будет, – сказал Петя, обиженный первым замечанием Наташи, – оттого, что она была влюблена в этого толстого с очками (так называл Петя своего тезку, нового графа Безухого); теперь влюблена в певца этого (Петя говорил об итальянце, Наташином учителе пенья): вот ей и стыдно.
– Петя, ты глуп, – сказала Наташа.
– Не глупее тебя, матушка, – сказал девятилетний Петя, точно как будто он был старый бригадир.
Графиня была приготовлена намеками Анны Михайловны во время обеда. Уйдя к себе, она, сидя на кресле, не спускала глаз с миниатюрного портрета сына, вделанного в табакерке, и слезы навертывались ей на глаза. Анна Михайловна с письмом на цыпочках подошла к комнате графини и остановилась.
– Не входите, – сказала она старому графу, шедшему за ней, – после, – и затворила за собой дверь.
Граф приложил ухо к замку и стал слушать.
Сначала он слышал звуки равнодушных речей, потом один звук голоса Анны Михайловны, говорившей длинную речь, потом вскрик, потом молчание, потом опять оба голоса вместе говорили с радостными интонациями, и потом шаги, и Анна Михайловна отворила ему дверь. На лице Анны Михайловны было гордое выражение оператора, окончившего трудную ампутацию и вводящего публику для того, чтоб она могла оценить его искусство.
– C'est fait! [Дело сделано!] – сказала она графу, торжественным жестом указывая на графиню, которая держала в одной руке табакерку с портретом, в другой – письмо и прижимала губы то к тому, то к другому.
Увидав графа, она протянула к нему руки, обняла его лысую голову и через лысую голову опять посмотрела на письмо и портрет и опять для того, чтобы прижать их к губам, слегка оттолкнула лысую голову. Вера, Наташа, Соня и Петя вошли в комнату, и началось чтение. В письме был кратко описан поход и два сражения, в которых участвовал Николушка, производство в офицеры и сказано, что он целует руки maman и papa, прося их благословения, и целует Веру, Наташу, Петю. Кроме того он кланяется m r Шелингу, и m mе Шос и няне, и, кроме того, просит поцеловать дорогую Соню, которую он всё так же любит и о которой всё так же вспоминает. Услыхав это, Соня покраснела так, что слезы выступили ей на глаза. И, не в силах выдержать обратившиеся на нее взгляды, она побежала в залу, разбежалась, закружилась и, раздув баллоном платье свое, раскрасневшаяся и улыбающаяся, села на пол. Графиня плакала.
– О чем же вы плачете, maman? – сказала Вера. – По всему, что он пишет, надо радоваться, а не плакать.
Это было совершенно справедливо, но и граф, и графиня, и Наташа – все с упреком посмотрели на нее. «И в кого она такая вышла!» подумала графиня.
Письмо Николушки было прочитано сотни раз, и те, которые считались достойными его слушать, должны были приходить к графине, которая не выпускала его из рук. Приходили гувернеры, няни, Митенька, некоторые знакомые, и графиня перечитывала письмо всякий раз с новым наслаждением и всякий раз открывала по этому письму новые добродетели в своем Николушке. Как странно, необычайно, радостно ей было, что сын ее – тот сын, который чуть заметно крошечными членами шевелился в ней самой 20 лет тому назад, тот сын, за которого она ссорилась с баловником графом, тот сын, который выучился говорить прежде: «груша», а потом «баба», что этот сын теперь там, в чужой земле, в чужой среде, мужественный воин, один, без помощи и руководства, делает там какое то свое мужское дело. Весь всемирный вековой опыт, указывающий на то, что дети незаметным путем от колыбели делаются мужами, не существовал для графини. Возмужание ее сына в каждой поре возмужания было для нее так же необычайно, как бы и не было никогда миллионов миллионов людей, точно так же возмужавших. Как не верилось 20 лет тому назад, чтобы то маленькое существо, которое жило где то там у ней под сердцем, закричало бы и стало сосать грудь и стало бы говорить, так и теперь не верилось ей, что это же существо могло быть тем сильным, храбрым мужчиной, образцом сыновей и людей, которым он был теперь, судя по этому письму.
– Что за штиль, как он описывает мило! – говорила она, читая описательную часть письма. – И что за душа! Об себе ничего… ничего! О каком то Денисове, а сам, верно, храбрее их всех. Ничего не пишет о своих страданиях. Что за сердце! Как я узнаю его! И как вспомнил всех! Никого не забыл. Я всегда, всегда говорила, еще когда он вот какой был, я всегда говорила…
Более недели готовились, писались брульоны и переписывались набело письма к Николушке от всего дома; под наблюдением графини и заботливостью графа собирались нужные вещицы и деньги для обмундирования и обзаведения вновь произведенного офицера. Анна Михайловна, практическая женщина, сумела устроить себе и своему сыну протекцию в армии даже и для переписки. Она имела случай посылать свои письма к великому князю Константину Павловичу, который командовал гвардией. Ростовы предполагали, что русская гвардия за границей , есть совершенно определительный адрес, и что ежели письмо дойдет до великого князя, командовавшего гвардией, то нет причины, чтобы оно не дошло до Павлоградского полка, который должен быть там же поблизости; и потому решено было отослать письма и деньги через курьера великого князя к Борису, и Борис уже должен был доставить их к Николушке. Письма были от старого графа, от графини, от Пети, от Веры, от Наташи, от Сони и, наконец, 6 000 денег на обмундировку и различные вещи, которые граф посылал сыну.


12 го ноября кутузовская боевая армия, стоявшая лагерем около Ольмюца, готовилась к следующему дню на смотр двух императоров – русского и австрийского. Гвардия, только что подошедшая из России, ночевала в 15 ти верстах от Ольмюца и на другой день прямо на смотр, к 10 ти часам утра, вступала на ольмюцкое поле.
Николай Ростов в этот день получил от Бориса записку, извещавшую его, что Измайловский полк ночует в 15 ти верстах не доходя Ольмюца, и что он ждет его, чтобы передать письмо и деньги. Деньги были особенно нужны Ростову теперь, когда, вернувшись из похода, войска остановились под Ольмюцом, и хорошо снабженные маркитанты и австрийские жиды, предлагая всякого рода соблазны, наполняли лагерь. У павлоградцев шли пиры за пирами, празднования полученных за поход наград и поездки в Ольмюц к вновь прибывшей туда Каролине Венгерке, открывшей там трактир с женской прислугой. Ростов недавно отпраздновал свое вышедшее производство в корнеты, купил Бедуина, лошадь Денисова, и был кругом должен товарищам и маркитантам. Получив записку Бориса, Ростов с товарищем поехал до Ольмюца, там пообедал, выпил бутылку вина и один поехал в гвардейский лагерь отыскивать своего товарища детства. Ростов еще не успел обмундироваться. На нем была затасканная юнкерская куртка с солдатским крестом, такие же, подбитые затертой кожей, рейтузы и офицерская с темляком сабля; лошадь, на которой он ехал, была донская, купленная походом у казака; гусарская измятая шапочка была ухарски надета назад и набок. Подъезжая к лагерю Измайловского полка, он думал о том, как он поразит Бориса и всех его товарищей гвардейцев своим обстреленным боевым гусарским видом.
Гвардия весь поход прошла, как на гуляньи, щеголяя своей чистотой и дисциплиной. Переходы были малые, ранцы везли на подводах, офицерам австрийское начальство готовило на всех переходах прекрасные обеды. Полки вступали и выступали из городов с музыкой, и весь поход (чем гордились гвардейцы), по приказанию великого князя, люди шли в ногу, а офицеры пешком на своих местах. Борис всё время похода шел и стоял с Бергом, теперь уже ротным командиром. Берг, во время похода получив роту, успел своей исполнительностью и аккуратностью заслужить доверие начальства и устроил весьма выгодно свои экономические дела; Борис во время похода сделал много знакомств с людьми, которые могли быть ему полезными, и через рекомендательное письмо, привезенное им от Пьера, познакомился с князем Андреем Болконским, через которого он надеялся получить место в штабе главнокомандующего. Берг и Борис, чисто и аккуратно одетые, отдохнув после последнего дневного перехода, сидели в чистой отведенной им квартире перед круглым столом и играли в шахматы. Берг держал между колен курящуюся трубочку. Борис, с свойственной ему аккуратностью, белыми тонкими руками пирамидкой уставлял шашки, ожидая хода Берга, и глядел на лицо своего партнера, видимо думая об игре, как он и всегда думал только о том, чем он был занят.
– Ну ка, как вы из этого выйдете? – сказал он.
– Будем стараться, – отвечал Берг, дотрогиваясь до пешки и опять опуская руку.
В это время дверь отворилась.
– Вот он, наконец, – закричал Ростов. – И Берг тут! Ах ты, петизанфан, але куше дормир , [Дети, идите ложиться спать,] – закричал он, повторяя слова няньки, над которыми они смеивались когда то вместе с Борисом.
– Батюшки! как ты переменился! – Борис встал навстречу Ростову, но, вставая, не забыл поддержать и поставить на место падавшие шахматы и хотел обнять своего друга, но Николай отсторонился от него. С тем особенным чувством молодости, которая боится битых дорог, хочет, не подражая другим, по новому, по своему выражать свои чувства, только бы не так, как выражают это, часто притворно, старшие, Николай хотел что нибудь особенное сделать при свидании с другом: он хотел как нибудь ущипнуть, толкнуть Бориса, но только никак не поцеловаться, как это делали все. Борис же, напротив, спокойно и дружелюбно обнял и три раза поцеловал Ростова.
Они полгода не видались почти; и в том возрасте, когда молодые люди делают первые шаги на пути жизни, оба нашли друг в друге огромные перемены, совершенно новые отражения тех обществ, в которых они сделали свои первые шаги жизни. Оба много переменились с своего последнего свидания и оба хотели поскорее выказать друг другу происшедшие в них перемены.
– Ах вы, полотеры проклятые! Чистенькие, свеженькие, точно с гулянья, не то, что мы грешные, армейщина, – говорил Ростов с новыми для Бориса баритонными звуками в голосе и армейскими ухватками, указывая на свои забрызганные грязью рейтузы.
Хозяйка немка высунулась из двери на громкий голос Ростова.
– Что, хорошенькая? – сказал он, подмигнув.
– Что ты так кричишь! Ты их напугаешь, – сказал Борис. – А я тебя не ждал нынче, – прибавил он. – Я вчера, только отдал тебе записку через одного знакомого адъютанта Кутузовского – Болконского. Я не думал, что он так скоро тебе доставит… Ну, что ты, как? Уже обстрелен? – спросил Борис.
Ростов, не отвечая, тряхнул по солдатскому Георгиевскому кресту, висевшему на снурках мундира, и, указывая на свою подвязанную руку, улыбаясь, взглянул на Берга.
– Как видишь, – сказал он.
– Вот как, да, да! – улыбаясь, сказал Борис, – а мы тоже славный поход сделали. Ведь ты знаешь, его высочество постоянно ехал при нашем полку, так что у нас были все удобства и все выгоды. В Польше что за приемы были, что за обеды, балы – я не могу тебе рассказать. И цесаревич очень милостив был ко всем нашим офицерам.
И оба приятеля рассказывали друг другу – один о своих гусарских кутежах и боевой жизни, другой о приятности и выгодах службы под командою высокопоставленных лиц и т. п.
– О гвардия! – сказал Ростов. – А вот что, пошли ка за вином.
Борис поморщился.
– Ежели непременно хочешь, – сказал он.
И, подойдя к кровати, из под чистых подушек достал кошелек и велел принести вина.
– Да, и тебе отдать деньги и письмо, – прибавил он.
Ростов взял письмо и, бросив на диван деньги, облокотился обеими руками на стол и стал читать. Он прочел несколько строк и злобно взглянул на Берга. Встретив его взгляд, Ростов закрыл лицо письмом.
– Однако денег вам порядочно прислали, – сказал Берг, глядя на тяжелый, вдавившийся в диван кошелек. – Вот мы так и жалованьем, граф, пробиваемся. Я вам скажу про себя…
– Вот что, Берг милый мой, – сказал Ростов, – когда вы получите из дома письмо и встретитесь с своим человеком, у которого вам захочется расспросить про всё, и я буду тут, я сейчас уйду, чтоб не мешать вам. Послушайте, уйдите, пожалуйста, куда нибудь, куда нибудь… к чорту! – крикнул он и тотчас же, схватив его за плечо и ласково глядя в его лицо, видимо, стараясь смягчить грубость своих слов, прибавил: – вы знаете, не сердитесь; милый, голубчик, я от души говорю, как нашему старому знакомому.