HAVAL — криптографическая хеш-функция , разработанная Yuliang Zheng [англ.] Josef Pieprzyk [англ.] Jennifer Seberry [англ.] 1992 году .
Для произвольного входного сообщения функция генерирует хеш-значение, называемое дайджестом сообщения , которое может иметь длину 128, 160, 192, 224 или 256 бит. Количество итераций — переменное, от 3 до 5. Количество раундов на каждой итерации — 32. Является модификацией MD5 .
Определим булевы функции , которые используются для выполнения побитовых операций над словами.
F
1
(
x
6
,
x
5
,
x
4
,
x
3
,
x
2
,
x
1
,
x
0
)
=
x
1
x
4
⊕
x
2
x
5
⊕
x
3
x
6
⊕
x
0
x
1
⊕
x
0
{\displaystyle 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}}
F
2
(
x
6
,
x
5
,
x
4
,
x
3
,
x
2
,
x
1
,
x
0
)
=
x
1
x
2
x
3
⊕
x
2
x
4
x
5
⊕
x
1
x
2
⊕
x
1
x
4
⊕
x
2
x
6
⊕
x
3
x
5
⊕
x
4
x
5
⊕
x
0
x
2
⊕
x
0
{\displaystyle 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}}
F
3
(
x
6
,
x
5
,
x
4
,
x
3
,
x
2
,
x
1
,
x
0
)
=
x
1
x
2
x
3
⊕
x
1
x
4
⊕
x
2
x
5
⊕
x
3
x
6
⊕
x
0
x
3
⊕
x
0
{\displaystyle 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}}
F
4
(
x
6
,
x
5
,
x
4
,
x
3
,
x
2
,
x
1
,
x
0
)
=
x
1
x
2
x
3
⊕
x
2
x
4
x
5
⊕
x
3
x
4
x
6
⊕
x
1
x
4
⊕
x
2
x
6
⊕
x
3
x
4
⊕
x
3
x
5
⊕
x
3
x
6
⊕
x
4
x
5
⊕
x
4
x
6
⊕
x
0
x
4
⊕
x
0
{\displaystyle 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}}
F
5
(
x
6
,
x
5
,
x
4
,
x
3
,
x
2
,
x
1
,
x
0
)
=
x
1
x
4
⊕
x
2
x
5
⊕
x
3
x
6
⊕
x
0
x
1
x
2
x
3
⊕
x
0
x
5
⊕
x
0
{\displaystyle 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}}
Сначала сообщение расширяется так, чтобы его длина в битах стала равной 944 по модулю 1024. Для этого в конец сообщения записывается единичный бит, а затем необходимое число нулевых бит. В оставшиеся 80 бит дописывают 64-битное представление количества бит в сообщении до выравнивания(поле MSGLENG), 10-битное представление длины дайджеста сообщения(поле DGSTLENG),3-битное представление числа итераций(поле PASS) и 3-битное представление версии HAVAL(поле VERSION).
Запишем расширенное сообщение в виде:
B
n
−
1
B
n
−
2
…
B
0
{\displaystyle B_{n-1}B_{n-2}\ldots B_{0}}
B
i
{\displaystyle B_{i}}
D
i
+
1
=
H
(
D
i
,
B
i
)
{\displaystyle D_{i+1}=H(D_{i},B_{i})}
H — функция сжатия, описанная ниже, и
D
0
{\displaystyle D_{0}}
Функция сжатия H H обрабатывает блок сообщения в течение 3, 4 или 5 итераций(в зависимости от значения поля PASS).
Обозначим функции сжатия, использующиеся в итерациях, через
H
1
,
H
2
,
H
3
,
H
4
{\displaystyle H_{1},H_{2},H_{3},H_{4}}
H
5
{\displaystyle H_{5}}
D
i
n
{\displaystyle D_{in}}
D
o
u
t
{\displaystyle D_{out}}
H . Тогда H может быть описана следующим образом(см. рисунок):
E
0
=
D
i
n
;
{\displaystyle E_{0}=D_{in};}
E
1
=
H
1
(
E
0
,
B
)
;
{\displaystyle E_{1}=H_{1}(E_{0},B);}
E
2
=
H
2
(
E
1
,
B
)
;
{\displaystyle E_{2}=H_{2}(E_{1},B);}
E
3
=
H
3
(
E
2
,
B
)
;
{\displaystyle E_{3}=H_{3}(E_{2},B);}
E
4
=
H
4
(
E
3
,
B
)
;
if PASS=4, 5
{\displaystyle E_{4}=H_{4}(E_{3},B);\qquad {\mbox{if PASS=4, 5}}}
E
5
=
H
5
(
E
4
,
B
)
;
if PASS=5
{\displaystyle E_{5}=H_{5}(E_{4},B);\qquad {\mbox{if PASS=5}}}
D
o
u
t
=
{
E
3
⊞
E
0
,
if PASS=3
E
4
⊞
E
0
,
if PASS=4
E
5
⊞
E
0
,
if PASS=5
{\displaystyle 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}}}
D
o
u
t
=
E
x
⊞
E
y
;
{\displaystyle D_{out}=E_{x}\boxplus E_{y};}
D
o
u
t
,
n
−
1
=
E
x
,
n
−
1
⊞
E
y
,
n
−
1
;
D
o
u
t
,
n
−
2
=
E
x
,
n
−
2
⊞
E
y
,
n
−
2
;
…
D
o
u
t
,
0
=
E
x
,
0
⊞
E
y
,
0
;
{\displaystyle 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};}
D
o
u
t
,
i
,
E
x
,
i
,
E
y
,
i
,
0
⩽
i
⩽
n
−
1
{\displaystyle D_{out,i},E_{x,i},E_{y,i},0\leqslant i\leqslant n-1}
Обозначим номер итерации через j (j =1,…,5). Итерации под номером j соответствует функция сжатия
H
j
{\displaystyle H_{j}}
H
j
{\displaystyle H_{j}}
B
{\displaystyle B}
E
j
−
1
{\displaystyle E_{j-1}}
B
{\displaystyle B}
W
31
W
30
…
W
0
{\displaystyle W_{31}W_{30}\dots W_{0}}
E
j
−
1
{\displaystyle E_{j-1}}
E
j
−
1
,
7
E
j
−
1
,
6
…
E
j
−
1
,
0
{\displaystyle E_{j-1,7}E_{j-1,6}\dots E_{j-1,0}}
H
j
{\displaystyle H_{j}}
1 . Пусть
T
0
,
i
=
E
j
−
1
,
i
,
0
⩽
i
⩽
7
{\displaystyle T_{0,i}=E_{j-1,i},0\leqslant i\leqslant 7}
2 . Повторяем следующие действия для i от 0 до 31:
P
=
{
F
j
∘
ϕ
3
,
j
(
T
i
,
6
,
T
i
,
5
,
T
i
,
4
,
T
i
,
3
,
T
i
,
2
,
T
i
,
1
,
T
i
,
0
)
,
if PASS=3
F
j
∘
ϕ
4
,
j
(
T
i
,
6
,
T
i
,
5
,
T
i
,
4
,
T
i
,
3
,
T
i
,
2
,
T
i
,
1
,
T
i
,
0
)
,
if PASS=4
F
j
∘
ϕ
5
,
j
(
T
i
,
6
,
T
i
,
5
,
T
i
,
4
,
T
i
,
3
,
T
i
,
2
,
T
i
,
1
,
T
i
,
0
)
,
if PASS=5
{\displaystyle 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}}}
R
=
(
P
⋙
7
)
⊞
(
T
i
,
7
⋙
11
)
⊞
W
o
r
d
j
(
i
)
⊞
K
j
,
i
{\displaystyle R=(P\ggg 7)\boxplus (T_{i,7}\ggg 11)\boxplus W_{ord_{j}(i)}\boxplus K_{j,i}}
K
j
,
i
{\displaystyle K_{j,i}}
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
;
{\displaystyle 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};}
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
.
{\displaystyle 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.}
3 . Пусть
E
j
,
i
=
T
32
,
i
,
0
⩽
i
⩽
7
{\displaystyle E_{j,i}=T_{32,i},0\leqslant i\leqslant 7}
E
j
=
E
j
,
7
E
j
,
6
…
E
j
,
0
{\displaystyle E_{j}=E_{j,7}E_{j,6}\dots E_{j,0}}
H
j
{\displaystyle H_{j}}
Обозначения:
f
∘
g
{\displaystyle f\circ g}
g
{\displaystyle g}
⊞
{\displaystyle \boxplus }
2
32
{\displaystyle 2^{32}}
ϕ
3
,
j
,
ϕ
4
,
j
,
ϕ
5
,
j
{\displaystyle \phi _{3,j},\phi _{4,j},\phi _{5,j}}
Замечания: на 1-й итерации константы не используются (то есть
K
j
,
i
=
0
,
0
⩽
i
⩽
31
{\displaystyle K_{j,i}=0,0\leqslant i\leqslant 31}
В отличие от итерации 1, во 2-й и в последующих итерациях
B
{\displaystyle B}
Таблица 1. Порядок обработки слов
o
r
d
1
{\displaystyle ord_{1}}
H
1
{\displaystyle H_{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
o
r
d
2
{\displaystyle ord_{2}}
H
2
{\displaystyle H_{2}}
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
o
r
d
3
{\displaystyle ord_{3}}
H
3
{\displaystyle H_{3}}
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
o
r
d
4
{\displaystyle ord_{4}}
H
4
{\displaystyle H_{4}}
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
o
r
d
5
{\displaystyle ord_{5}}
H
5
{\displaystyle H_{5}}
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. Перестановки
x
6
{\displaystyle x_{6}}
↓
{\displaystyle \downarrow }
x
5
{\displaystyle x_{5}}
↓
{\displaystyle \downarrow }
x
4
{\displaystyle x_{4}}
↓
{\displaystyle \downarrow }
x
3
{\displaystyle x_{3}}
↓
{\displaystyle \downarrow }
x
2
{\displaystyle x_{2}}
↓
{\displaystyle \downarrow }
x
1
{\displaystyle x_{1}}
↓
{\displaystyle \downarrow }
x
0
{\displaystyle x_{0}}
↓
{\displaystyle \downarrow }
ϕ
3
,
1
{\displaystyle \phi _{3,1}}
x
1
{\displaystyle x_{1}}
x
0
{\displaystyle x_{0}}
x
3
{\displaystyle x_{3}}
x
5
{\displaystyle x_{5}}
x
6
{\displaystyle x_{6}}
x
2
{\displaystyle x_{2}}
x
4
{\displaystyle x_{4}}
ϕ
3
,
2
{\displaystyle \phi _{3,2}}
x
4
{\displaystyle x_{4}}
x
2
{\displaystyle x_{2}}
x
1
{\displaystyle x_{1}}
x
0
{\displaystyle x_{0}}
x
5
{\displaystyle x_{5}}
x
3
{\displaystyle x_{3}}
x
6
{\displaystyle x_{6}}
ϕ
3
,
3
{\displaystyle \phi _{3,3}}
x
6
{\displaystyle x_{6}}
x
1
{\displaystyle x_{1}}
x
2
{\displaystyle x_{2}}
x
3
{\displaystyle x_{3}}
x
4
{\displaystyle x_{4}}
x
5
{\displaystyle x_{5}}
x
0
{\displaystyle x_{0}}
ϕ
4
,
1
{\displaystyle \phi _{4,1}}
x
2
{\displaystyle x_{2}}
x
6
{\displaystyle x_{6}}
x
1
{\displaystyle x_{1}}
x
4
{\displaystyle x_{4}}
x
5
{\displaystyle x_{5}}
x
3
{\displaystyle x_{3}}
x
0
{\displaystyle x_{0}}
ϕ
4
,
2
{\displaystyle \phi _{4,2}}
x
3
{\displaystyle x_{3}}
x
5
{\displaystyle x_{5}}
x
2
{\displaystyle x_{2}}
x
0
{\displaystyle x_{0}}
x
1
{\displaystyle x_{1}}
x
6
{\displaystyle x_{6}}
x
4
{\displaystyle x_{4}}
ϕ
4
,
3
{\displaystyle \phi _{4,3}}
x
1
{\displaystyle x_{1}}
x
4
{\displaystyle x_{4}}
x
3
{\displaystyle x_{3}}
x
6
{\displaystyle x_{6}}
x
0
{\displaystyle x_{0}}
x
2
{\displaystyle x_{2}}
x
5
{\displaystyle x_{5}}
ϕ
4
,
4
{\displaystyle \phi _{4,4}}
x
6
{\displaystyle x_{6}}
x
4
{\displaystyle x_{4}}
x
0
{\displaystyle x_{0}}
x
5
{\displaystyle x_{5}}
x
2
{\displaystyle x_{2}}
x
1
{\displaystyle x_{1}}
x
3
{\displaystyle x_{3}}
ϕ
5
,
1
{\displaystyle \phi _{5,1}}
x
3
{\displaystyle x_{3}}
x
4
{\displaystyle x_{4}}
x
1
{\displaystyle x_{1}}
x
0
{\displaystyle x_{0}}
x
5
{\displaystyle x_{5}}
x
2
{\displaystyle x_{2}}
x
6
{\displaystyle x_{6}}
ϕ
5
,
2
{\displaystyle \phi _{5,2}}
x
6
{\displaystyle x_{6}}
x
2
{\displaystyle x_{2}}
x
1
{\displaystyle x_{1}}
x
0
{\displaystyle x_{0}}
x
3
{\displaystyle x_{3}}
x
4
{\displaystyle x_{4}}
x
5
{\displaystyle x_{5}}
ϕ
5
,
3
{\displaystyle \phi _{5,3}}
x
2
{\displaystyle x_{2}}
x
6
{\displaystyle x_{6}}
x
0
{\displaystyle x_{0}}
x
4
{\displaystyle x_{4}}
x
3
{\displaystyle x_{3}}
x
1
{\displaystyle x_{1}}
x
5
{\displaystyle x_{5}}
ϕ
5
,
4
{\displaystyle \phi _{5,4}}
x
1
{\displaystyle x_{1}}
x
5
{\displaystyle x_{5}}
x
3
{\displaystyle x_{3}}
x
2
{\displaystyle x_{2}}
x
0
{\displaystyle x_{0}}
x
4
{\displaystyle x_{4}}
x
6
{\displaystyle x_{6}}
ϕ
5
,
5
{\displaystyle \phi _{5,5}}
x
2
{\displaystyle x_{2}}
x
5
{\displaystyle x_{5}}
x
0
{\displaystyle x_{0}}
x
6
{\displaystyle x_{6}}
x
4
{\displaystyle x_{4}}
x
3
{\displaystyle x_{3}}
x
1
{\displaystyle x_{1}}
На этом шаге используется
D
n
=
D
n
,
7
D
n
,
6
…
D
n
,
0
{\displaystyle D_{n}=D_{n,7}D_{n,6}\dots D_{n,0}}
D
n
{\displaystyle D_{n}}
1. Размер хеша — 128 бит
Представим
D
n
,
7
,
D
n
,
6
,
D
n
,
5
{\displaystyle D_{n,7},D_{n,6},D_{n,5}}
D
n
,
4
{\displaystyle D_{n,4}}
D
n
,
7
=
X
7
,
3
[
8
]
X
7
,
2
[
8
]
X
7
,
1
[
8
]
X
7
,
0
[
8
]
{\displaystyle D_{n,7}=X_{7,3}^{[8]}X_{7,2}^{[8]}X_{7,1}^{[8]}X_{7,0}^{[8]}}
D
n
,
6
=
X
6
,
3
[
8
]
X
6
,
2
[
8
]
X
6
,
1
[
8
]
X
6
,
0
[
8
]
{\displaystyle D_{n,6}=X_{6,3}^{[8]}X_{6,2}^{[8]}X_{6,1}^{[8]}X_{6,0}^{[8]}}
D
n
,
5
=
X
5
,
3
[
8
]
X
5
,
2
[
8
]
X
5
,
1
[
8
]
X
5
,
0
[
8
]
{\displaystyle D_{n,5}=X_{5,3}^{[8]}X_{5,2}^{[8]}X_{5,1}^{[8]}X_{5,0}^{[8]}}
D
n
,
4
=
X
4
,
3
[
8
]
X
4
,
2
[
8
]
X
4
,
1
[
8
]
X
4
,
0
[
8
]
{\displaystyle D_{n,4}=X_{4,3}^{[8]}X_{4,2}^{[8]}X_{4,1}^{[8]}X_{4,0}^{[8]}}
Тогда дайджестом сообщения является 128-битовое
Y
3
Y
2
Y
1
Y
0
{\displaystyle Y_{3}Y_{2}Y_{1}Y_{0}}
Y
3
=
D
n
,
3
⊞
(
X
7
,
3
[
8
]
X
6
,
2
[
8
]
X
5
,
1
[
8
]
X
4
,
0
[
8
]
)
{\displaystyle Y_{3}=D_{n,3}\boxplus (X_{7,3}^{[8]}X_{6,2}^{[8]}X_{5,1}^{[8]}X_{4,0}^{[8]})}
Y
2
=
D
n
,
2
⊞
(
X
7
,
2
[
8
]
X
6
,
1
[
8
]
X
5
,
0
[
8
]
X
4
,
3
[
8
]
)
{\displaystyle Y_{2}=D_{n,2}\boxplus (X_{7,2}^{[8]}X_{6,1}^{[8]}X_{5,0}^{[8]}X_{4,3}^{[8]})}
Y
1
=
D
n
,
1
⊞
(
X
7
,
1
[
8
]
X
6
,
0
[
8
]
X
5
,
3
[
8
]
X
4
,
2
[
8
]
)
{\displaystyle Y_{1}=D_{n,1}\boxplus (X_{7,1}^{[8]}X_{6,0}^{[8]}X_{5,3}^{[8]}X_{4,2}^{[8]})}
Y
0
=
D
n
,
0
⊞
(
X
7
,
0
[
8
]
X
6
,
3
[
8
]
X
5
,
2
[
8
]
X
4
,
1
[
8
]
)
{\displaystyle Y_{0}=D_{n,0}\boxplus (X_{7,0}^{[8]}X_{6,3}^{[8]}X_{5,2}^{[8]}X_{4,1}^{[8]})}
2. Размер хеша — 160 бит
Представим
D
n
,
7
,
D
n
,
6
{\displaystyle D_{n,7},D_{n,6}}
D
n
,
5
{\displaystyle D_{n,5}}
D
n
,
7
=
X
7
,
4
[
7
]
X
7
,
3
[
6
]
X
7
,
2
[
7
]
X
7
,
1
[
6
]
X
7
,
0
[
6
]
{\displaystyle D_{n,7}=X_{7,4}^{[7]}X_{7,3}^{[6]}X_{7,2}^{[7]}X_{7,1}^{[6]}X_{7,0}^{[6]}}
D
n
,
6
=
X
6
,
4
[
7
]
X
6
,
3
[
6
]
X
6
,
2
[
7
]
X
6
,
1
[
6
]
X
6
,
0
[
6
]
{\displaystyle D_{n,6}=X_{6,4}^{[7]}X_{6,3}^{[6]}X_{6,2}^{[7]}X_{6,1}^{[6]}X_{6,0}^{[6]}}
D
n
,
5
=
X
5
,
4
[
7
]
X
5
,
3
[
6
]
X
5
,
2
[
7
]
X
5
,
1
[
6
]
X
5
,
0
[
6
]
{\displaystyle D_{n,5}=X_{5,4}^{[7]}X_{5,3}^{[6]}X_{5,2}^{[7]}X_{5,1}^{[6]}X_{5,0}^{[6]}}
Тогда дайджестом сообщения является 160-битовое
Y
4
Y
3
Y
2
Y
1
Y
0
{\displaystyle Y_{4}Y_{3}Y_{2}Y_{1}Y_{0}}
Y
4
=
D
n
,
4
⊞
(
X
7
,
4
[
7
]
X
6
,
3
[
6
]
X
5
,
2
[
7
]
)
{\displaystyle Y_{4}=D_{n,4}\boxplus (X_{7,4}^{[7]}X_{6,3}^{[6]}X_{5,2}^{[7]})}
Y
3
=
D
n
,
3
⊞
(
X
7
,
3
[
6
]
X
6
,
2
[
7
]
X
5
,
1
[
6
]
)
{\displaystyle Y_{3}=D_{n,3}\boxplus (X_{7,3}^{[6]}X_{6,2}^{[7]}X_{5,1}^{[6]})}
Y
2
=
D
n
,
2
⊞
(
X
7
,
2
[
7
]
X
6
,
1
[
6
]
X
5
,
0
[
6
]
)
{\displaystyle Y_{2}=D_{n,2}\boxplus (X_{7,2}^{[7]}X_{6,1}^{[6]}X_{5,0}^{[6]})}
Y
1
=
D
n
,
1
⊞
(
X
7
,
1
[
6
]
X
6
,
0
[
6
]
X
5
,
4
[
7
]
)
{\displaystyle Y_{1}=D_{n,1}\boxplus (X_{7,1}^{[6]}X_{6,0}^{[6]}X_{5,4}^{[7]})}
Y
0
=
D
n
,
0
⊞
(
X
7
,
0
[
6
]
X
6
,
4
[
7
]
X
5
,
3
[
6
]
)
{\displaystyle Y_{0}=D_{n,0}\boxplus (X_{7,0}^{[6]}X_{6,4}^{[7]}X_{5,3}^{[6]})}
3. Размер хеша — 192 бит
Представим
D
n
,
7
{\displaystyle D_{n,7}}
D
n
,
6
{\displaystyle D_{n,6}}
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
]
{\displaystyle 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]}}
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
]
{\displaystyle 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]}}
Пусть
Y
5
=
D
n
,
5
⊞
(
X
7
,
5
[
6
]
X
6
,
4
[
5
]
)
{\displaystyle Y_{5}=D_{n,5}\boxplus (X_{7,5}^{[6]}X_{6,4}^{[5]})}
Y
4
=
D
n
,
4
⊞
(
X
7
,
4
[
5
]
X
6
,
3
[
5
]
)
{\displaystyle Y_{4}=D_{n,4}\boxplus (X_{7,4}^{[5]}X_{6,3}^{[5]})}
Y
3
=
D
n
,
3
⊞
(
X
7
,
3
[
5
]
X
6
,
2
[
6
]
)
{\displaystyle Y_{3}=D_{n,3}\boxplus (X_{7,3}^{[5]}X_{6,2}^{[6]})}
Y
2
=
D
n
,
2
⊞
(
X
7
,
2
[
6
]
X
6
,
1
[
5
]
)
{\displaystyle Y_{2}=D_{n,2}\boxplus (X_{7,2}^{[6]}X_{6,1}^{[5]})}
Y
1
=
D
n
,
1
⊞
(
X
7
,
1
[
5
]
X
6
,
0
[
5
]
)
{\displaystyle Y_{1}=D_{n,1}\boxplus (X_{7,1}^{[5]}X_{6,0}^{[5]})}
Y
0
=
D
n
,
0
⊞
(
X
7
,
0
[
5
]
X
6
,
5
[
6
]
)
{\displaystyle Y_{0}=D_{n,0}\boxplus (X_{7,0}^{[5]}X_{6,5}^{[6]})}
Y
5
Y
4
Y
3
Y
2
Y
1
Y
0
{\displaystyle Y_{5}Y_{4}Y_{3}Y_{2}Y_{1}Y_{0}}
4. Размер хеша — 224 бит
Представим
D
n
,
7
{\displaystyle D_{n,7}}
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
]
{\displaystyle 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]}}
Тогда дайджестом сообщения является 224-битовое
Y
6
Y
5
Y
4
Y
3
Y
2
Y
1
Y
0
{\displaystyle Y_{6}Y_{5}Y_{4}Y_{3}Y_{2}Y_{1}Y_{0}}
Y
6
=
D
n
,
6
⊞
(
X
7
,
0
[
4
]
)
{\displaystyle Y_{6}=D_{n,6}\boxplus (X_{7,0}^{[4]})}
Y
5
=
D
n
,
5
⊞
(
X
7
,
1
[
5
]
)
{\displaystyle Y_{5}=D_{n,5}\boxplus (X_{7,1}^{[5]})}
Y
4
=
D
n
,
4
⊞
(
X
7
,
2
[
4
]
)
{\displaystyle Y_{4}=D_{n,4}\boxplus (X_{7,2}^{[4]})}
Y
3
=
D
n
,
3
⊞
(
X
7
,
3
[
5
]
)
{\displaystyle Y_{3}=D_{n,3}\boxplus (X_{7,3}^{[5]})}
Y
2
=
D
n
,
2
⊞
(
X
7
,
4
[
4
]
)
{\displaystyle Y_{2}=D_{n,2}\boxplus (X_{7,4}^{[4]})}
Y
1
=
D
n
,
1
⊞
(
X
7
,
5
[
5
]
)
{\displaystyle Y_{1}=D_{n,1}\boxplus (X_{7,5}^{[5]})}
Y
0
=
D
n
,
0
⊞
(
X
7
,
6
[
5
]
)
{\displaystyle Y_{0}=D_{n,0}\boxplus (X_{7,6}^{[5]})}
В данном алгоритме используются 136 32-битовых константы. Запишем их в следующем порядке:
1.
D
0
,
0
,
D
0
,
1
,
…
,
D
0
,
7
{\displaystyle D_{0,0},D_{0,1},\dots ,D_{0,7}}
2.
K
2
,
0
,
K
2
,
1
,
…
,
K
2
,
31
{\displaystyle K_{2,0},K_{2,1},\dots ,K_{2,31}}
3.
K
3
,
0
,
K
3
,
1
,
…
,
K
3
,
31
{\displaystyle K_{3,0},K_{3,1},\dots ,K_{3,31}}
4.
K
4
,
0
,
K
4
,
1
,
…
,
K
4
,
31
{\displaystyle K_{4,0},K_{4,1},\dots ,K_{4,31}}
5.
K
5
,
0
,
K
5
,
1
,
…
,
K
5
,
31
{\displaystyle K_{5,0},K_{5,1},\dots ,K_{5,31}}
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 констант
D
0
,
0
,
D
0
,
1
,
…
,
D
0
,
7
{\displaystyle D_{0,0},D_{0,1},\dots ,D_{0,7}}
π
{\displaystyle \pi }
K
2
,
0
,
K
2
,
1
,
…
,
K
2
,
31
{\displaystyle K_{2,0},K_{2,1},\dots ,K_{2,31}}
π
{\displaystyle \pi }
F
1
{\displaystyle F_{1}}
F
2
{\displaystyle F_{2}}
F
3
{\displaystyle F_{3}}
F
4
{\displaystyle F_{4}}
F
5
{\displaystyle F_{5}}
[ править | править код ] Булевы функции
F
1
{\displaystyle F_{1}}
F
2
{\displaystyle F_{2}}
F
3
{\displaystyle F_{3}}
F
4
{\displaystyle F_{4}}
F
5
{\displaystyle F_{5}}
1) Они сбалансированы по 0 и 1. Это значит, что выходом функции при произвольном наборе входных данных с равной вероятностью(1/2) может быть либо 0, либо 1. 2) Они сильно нелинейные.[ 1]
3) Они удовлетворяют критерию строгого лавинного эффекта (Strict Avalanche Criterion), т.е при изменении значения любой из входных переменных значение функции меняется с вероятностью 1/2.
4) Они не могут быть получены одна из другой посредством применения линейных преобразований к входным переменным.
5) Этот набор функций — взаимно некоррелирующий по выходу, то есть любая пара функций взаимно не коррелирует по выходу(функции
f
{\displaystyle f}
g
{\displaystyle g}
f
{\displaystyle f}
g
{\displaystyle g}
f
⊕
g
{\displaystyle f\oplus g}
HAVAL-хеши обычно представляются в виде последовательности, состоящей из 32, 40, 48, 56 или 64 шестнадцатеричных чисел.
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
В отличие от хеш-функции MD5, у которой дайджест и число итераций имеют фиксированные размеры, HAVAL предоставляет 15 различных вариантов алгоритма за счёт комбинирования длины дайджеста и числа итераций. Это обеспечивает большую гибкость и, следовательно, делает хеш-функцию более подходящей для приложений, в которых требуется различная длина хеша сообщения и различный уровень безопасности.
Коллизия хеш-функции — это получение одинакового значения функции для разных сообщений.
В 2003 году Bart Van Rompay, Алекс Бирюков , Барт Пренель и Joos Vandewalle обнаружили коллизию для 3-итерационного HAVAL.
[ 2]
2
29
{\displaystyle 2^{29}}
H .
В 2004 году китайские исследователи Wang Xiaoyun [англ.] Feng Dengguo , Лай Сюэцзя и Yu Hongbo объявили об обнаруженной ими уязвимости в 3-итерационном HAVAL-128, позволяющей за
2
7
{\displaystyle 2^{7}}
[ 3]
В 2006 году группа китайских учёных во главе с Wang Xiaoyun и Yu Hongbo провели две атаки на 4-итерационный HAVAL, потребовавшие
2
43
{\displaystyle 2^{43}}
2
36
{\displaystyle 2^{36}}
2
123
{\displaystyle 2^{123}}
[ 4]
↑ Токарева Н. Н. Сильно нелинейные булевы функции: бент-функции и их обобщения (рус.) (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).(недоступная ссылка)
![{\displaystyle D_{n,7}=X_{7,3}^{[8]}X_{7,2}^{[8]}X_{7,1}^{[8]}X_{7,0}^{[8]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4ea86f26a03f820d27b350c63445283773323aa7)
![{\displaystyle D_{n,6}=X_{6,3}^{[8]}X_{6,2}^{[8]}X_{6,1}^{[8]}X_{6,0}^{[8]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0903331c8f62f38f902ab92265daa6c9e682279f)
![{\displaystyle D_{n,5}=X_{5,3}^{[8]}X_{5,2}^{[8]}X_{5,1}^{[8]}X_{5,0}^{[8]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9f9940e1d0d1b1e9a07cf129860239e4e4b07753)
![{\displaystyle D_{n,4}=X_{4,3}^{[8]}X_{4,2}^{[8]}X_{4,1}^{[8]}X_{4,0}^{[8]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c2abb79bcc91b3bf78261b7be112aa2169f76ac4)
![{\displaystyle Y_{3}=D_{n,3}\boxplus (X_{7,3}^{[8]}X_{6,2}^{[8]}X_{5,1}^{[8]}X_{4,0}^{[8]})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9962626f31b1f01025e6c6b07568f5cca661acfc)
![{\displaystyle Y_{2}=D_{n,2}\boxplus (X_{7,2}^{[8]}X_{6,1}^{[8]}X_{5,0}^{[8]}X_{4,3}^{[8]})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4a3e78e21b38ddbc2dd2070c14bd01906a23c12c)
![{\displaystyle Y_{1}=D_{n,1}\boxplus (X_{7,1}^{[8]}X_{6,0}^{[8]}X_{5,3}^{[8]}X_{4,2}^{[8]})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/101607237a672b8ddf8491c808cc276da6700b03)
![{\displaystyle Y_{0}=D_{n,0}\boxplus (X_{7,0}^{[8]}X_{6,3}^{[8]}X_{5,2}^{[8]}X_{4,1}^{[8]})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a662cddf52130597fe9a88931de610a9a6a73c5b)
![{\displaystyle D_{n,7}=X_{7,4}^{[7]}X_{7,3}^{[6]}X_{7,2}^{[7]}X_{7,1}^{[6]}X_{7,0}^{[6]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a263d685ff86277d2aafe23faf7e232123412a1f)
![{\displaystyle D_{n,6}=X_{6,4}^{[7]}X_{6,3}^{[6]}X_{6,2}^{[7]}X_{6,1}^{[6]}X_{6,0}^{[6]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/567d21fe3a2885cfcf890e2f2e8bcaeafd1b9eeb)
![{\displaystyle D_{n,5}=X_{5,4}^{[7]}X_{5,3}^{[6]}X_{5,2}^{[7]}X_{5,1}^{[6]}X_{5,0}^{[6]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/34484aeb54ad2834835bd85042ec78e069563d59)
![{\displaystyle Y_{4}=D_{n,4}\boxplus (X_{7,4}^{[7]}X_{6,3}^{[6]}X_{5,2}^{[7]})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fede14ffdb64ebabc013ee6eeecb25c9d5d1d430)
![{\displaystyle Y_{3}=D_{n,3}\boxplus (X_{7,3}^{[6]}X_{6,2}^{[7]}X_{5,1}^{[6]})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6844b6db6308716b2eef8d03a99c8d333ddfe96b)
![{\displaystyle Y_{2}=D_{n,2}\boxplus (X_{7,2}^{[7]}X_{6,1}^{[6]}X_{5,0}^{[6]})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fe0c879e1acae03ee6c31fd4b9c45dfff6e1b428)
![{\displaystyle Y_{1}=D_{n,1}\boxplus (X_{7,1}^{[6]}X_{6,0}^{[6]}X_{5,4}^{[7]})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/62f3416c996dfb64b2d058b4dd93d04f8145d21a)
![{\displaystyle Y_{0}=D_{n,0}\boxplus (X_{7,0}^{[6]}X_{6,4}^{[7]}X_{5,3}^{[6]})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/12b423ddc02d08b306c1299197c56e22c71cc5d9)
![{\displaystyle 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]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e3f45b4f9e18573083e8f0ef1d2a127b73d96f45)
![{\displaystyle 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]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e21a37441023feda072609409449ae32bab61406)
![{\displaystyle Y_{5}=D_{n,5}\boxplus (X_{7,5}^{[6]}X_{6,4}^{[5]})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5ce22ae93b9b3a8aa76a927943f3fc918a997a63)
![{\displaystyle Y_{4}=D_{n,4}\boxplus (X_{7,4}^{[5]}X_{6,3}^{[5]})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0883f139e117606a8a576c22685e11bdfc31ffd0)
![{\displaystyle Y_{3}=D_{n,3}\boxplus (X_{7,3}^{[5]}X_{6,2}^{[6]})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/77edafd957320cc0020cca79d9c2e137128771a9)
![{\displaystyle Y_{2}=D_{n,2}\boxplus (X_{7,2}^{[6]}X_{6,1}^{[5]})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2e05d47f424e0aa7d0fff57c011b69edfe3c17c9)
![{\displaystyle Y_{1}=D_{n,1}\boxplus (X_{7,1}^{[5]}X_{6,0}^{[5]})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/716d0db4e701fb56047278899f5b356fd05e1260)
![{\displaystyle Y_{0}=D_{n,0}\boxplus (X_{7,0}^{[5]}X_{6,5}^{[6]})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/72bbc2ce5f321069d6aa67323319c2b45ceef4d0)
![{\displaystyle 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]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/95e8dbf6dfe9f37f7b21ddf4960cedc446f668ac)
![{\displaystyle Y_{6}=D_{n,6}\boxplus (X_{7,0}^{[4]})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c79803c256594da1df5f0ea4e82e308fafc71705)
![{\displaystyle Y_{5}=D_{n,5}\boxplus (X_{7,1}^{[5]})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7e11aff517e580534dbeae3fcc0388b105004086)
![{\displaystyle Y_{4}=D_{n,4}\boxplus (X_{7,2}^{[4]})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/879722e7f785cfb4bdff7e662b3c9450fcf9ebff)
![{\displaystyle Y_{3}=D_{n,3}\boxplus (X_{7,3}^{[5]})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2e011209d49a93cf5335e30472b403fcceea6d1f)
![{\displaystyle Y_{2}=D_{n,2}\boxplus (X_{7,4}^{[4]})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ce0d3087b1f8539efd0df2e52d749ce20997897a)
![{\displaystyle Y_{1}=D_{n,1}\boxplus (X_{7,5}^{[5]})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37adf730dc9f15abdf029904e4e47fd0b94adf14)
![{\displaystyle Y_{0}=D_{n,0}\boxplus (X_{7,6}^{[5]})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f7bbeb2499de7df146588e06dcf7d073a1deca30)
