ГЛАВА 3. ХЕШ-ФУНКЦИИ
3.1. Требование к качественной хеш-функции
Хеширование – вид криптографического преобразования, не менее важный, чем шифрование. При этом существует мнение, что задача проектирования качественной хеш-функции более сложная, чем задача проектирования качественного симметричного шифра.
Хеш-функцией называется преобразование h, превращающее информационную последовательность (строку) M произвольной длины в информационную последовательность (строку) фиксиро- ванной длины
M
h
На рис. 3.1 показана упрощенная схема хеш- функции.
n
n
N
n
Функция обратной связи FB
Память
Q
Исходная информация
M
h(M)
m
M
3
...
M
t
M
2
M
1
M
h(x)
хеш-образ
h(M)
F
а
б
Генератор
ПСЧ
h
0
Рис. 3.1. Хеш-функция: а – наложение ПСП на входную информационную последовательность; б – упрощенный принцип действия хеш-функции
Процесс получения хеш-функции можно рассматривать как на- ложение псевдослучайной последовательности (ПСП) на входную
119 преобразуемую последовательность. По этой причине часто спе- цификация синхронного поточного шифра описывает и родствен- ную хеш-функцию.
К криптографической функции x
h
предъявляются следующие основные требования: результат действия хеш-функции должен зависеть от всех дво- ичных символов исходного сообщения, а также от их взаимно- го расположения;
x
h
должна быть чувствительна к любым изменениям вход- ной информационной последовательности, при любых изме- нениях на входе результат действия хеш-функции должен быть непредсказуем – в среднем должна измениться половина бит хеш-образа.
Рассмотрим четыре проблемы дней рождения, которые могут быть применены для анализа безопасности хеш-функций.
Имеем равномерно распределенную случайную переменную, принимающую N возможных значений (между 0 и N – 1).
1) Определить минимальное число реализаций k, при котором с вероятностью
2
/
1
P
хотя бы одна выборка оказалась равной пре- допределенной величине.
2) Определить минимальное число реализаций k, при котором с вероятностью
2
/
1
P
хотя бы одна выборка оказалась равной вы- бранной величине.
3) Определить минимальное число реализаций k, при котором с вероятностью
2
/
1
P
хотя бы две выборки оказались равными.
Формируем два набора случайных значений по k выборок в ка- ждом.
4) Определить минимальное число реализаций k, при котором с вероятностью
2
/
1
P
хотя бы одна выборка из первого набора оказалась равной одной выборке из второго набора.
Решения проблем дней рождения приведены в табл. 3.1.
Для качественной криптографической хеш-функции три сле- дующие задачи вычислительно неразрешимы:
1)
нахождение прообраза
– задача нахождения последова- тельности M по заданному хеш-образу M
h
(рис. 3.2,а);
120 2)
нахождение коллизии
– задача нахождения последователь- ностей M и
,
M'
причем
,
M
M'
таких, что
M
h
M'
h
;
3)
нахождение второго прообраза
– задача нахождения для заданной последовательности M другой последовательно- сти
,
M'
,
M
M'
такой, что
M
h
M'
h
(рис. 3.2,б).
Таблица 3.1
Решения проблем дней рождения
Проб- лема
Вероят- ность
Значение k
Значение k при
2
/
1
P
Значение
k при
2
/
1
P
и
365
N
1
N
k
e
P
/
N
P
k
1
/
1
ln
N
k
69
,
0 253 2
N
k
e
P
/
1 1
1
/
1
N
P
n
k
1 69
,
0
N
k
254 3
N
k
k
e
P
/2 1
2
/
1 2
/
1 1
/
1
ln
2
N
P
k
2
/
1 18
,
1
N
k
23 4
N
k
e
P
/2 2
2
/
1 2
/
1 1
/
1
ln
N
P
k
2
/
1 83
,
0
N
k
16
Примечание. Последняя ячейка в строке 3 представляет собой классический пара-
докс дней рождения.
Если n – разрядность хеш-образа, сложность первой и третьей атаки (рис. 3.2) на идеальную хеш-функцию пропорциональна
n
2 .
Сложность задачи нахождении коллизии пропорциональна
2
/
2
n
. В табл. 3.2 приведены оценки сложности атак на идеальную хеш- функцию, где k – размер списков сообщений, создаваемых ата- кующим. Рассмотрим отличия поиска коллизии в случаях 1 и 2. В первом случае речь идет о поиске двух произвольных сообщений, имеющих одинаковое значение хеш-образа. Есть точка зрения, что эта атака бесполезна для атакующего. Однако существуют атаки на конкретные протоколы с использованием известных коллизий
MD5. Во втором случае предполагается, что одно сообщение ре- альное, а другое – фальсифицированное, при этом оба сообщения должны быть осмысленными. Решение состоит в создании двух списков осмысленных сообщений путем внесения избыточности или модификации содержимого (например, добавление пробелов,
121 перестановка слов сообщения, добавление дополнительных избы- точных слов и т.п.) без изменения смысла сообщений.
Mh(
x)
y =
h(
M)
К субъекту
ВСубъект
АПротивник
WЗадача нахождения прообраза
Дано:
h(
x),
yНайти: любое
М’ такое,
что
у =
h(
M’)
M’Нахождение прообраза
Mh(x)
y =
h(
M)
К субъекту
ВСубъект
АПротивник
WЗадача нахождения второго прообраза
Дано:
h(
x),
y,
MНайти:
М’ ≠
M такое,
что
h(
M’) =
h(
M)
Нахождение второго прообраза
Mh(
M)
M’абРис. 3.2. Атаки на хеш-функцию:
а –
нахождение прообраза;
б – нахождение второго прообраза
Наиболее известные алгоритмы хеширования – MD5, SHA,
Tiger, Whirlpool.
MD5 – представитель семейства хеш-функций MD (Message
Digest Algorithm), предложенного Р. Ривестом; разработан в 1991 г.; преобразует информационную последовательность произвольной длины в хеш-образ разрядностью 128 бит.
Tiger разработан Р. Андерсоном и Э. Бихэмом; предназна- чен для реализации на 64-разрядных компьютерах; преобразует информационную последовательность произвольной длины в хеш-образ разрядностью 192 бит.
122
Таблица 3.2
Оценка сложности атак на хеш-функцию
Атака
Значение
k при
2
/
1
PСложность
Нахождение прообраза
nk2 69
,
0
n2
Нахождение второго прообраза
1 2
69
nkn2
Нахождение коллизии 1 2
/
2 18
,
1
nk2
/
2
nНахождение коллизии 2 2
/
2 83
,
0
nk2
/
2
n3.2. Итеративная хеш-функция На рис. 3.3 показана схема итеративной хеш-функции, которая является стойкой в смысле нахождения коллизий, если аналогич- ным свойством обладает используемая функция сжатия. Обозначе- ния:
tMMM...,
,
,
2 1
– блоки дополненного сообщения;
t – число блоков дополненного сообщение;
0
h – фиксированное значение, называемое стартовым вектором или вектором инициализации
IV;
thhh...,
,
,
2 1
– промежуточные результаты вычисления итераций, число которых равно числу блоков
t . Оригинальное сообщение дополняется до длины, кратной
n, где
n –
разрядность блока дан- ных, обрабатываемого функцией сжатия. На
i -м итерационном ша- ге функция сжатия
f принимает результат предыдущего шага
1
-
ih и
i -й блок данных
iM , а затем формирует результат
iiiMhfh,
1
-
. На шаге
t полученное значение
th объявляется хеш-образом исходного сообщения, т.е.
Mhht. Типичная структура дополнения показана на рис. 3.4.
3.3. Secure Hash Algorithm (SHA) Алгоритм SHAявляется частью стандарта SHS (Secure Hash
Standard), разработанного в 1993 г. Национальным институтом стандартов и технологий США (FIPS 180) и Агенством националь- ной безопасности США. SHA использует принципы, предложенные ранее Р. Ривестом при разработке своих алгоритмов семейства MD.
В 1995 г. стандарт был пересмотрен (FIPS 180-1) в пользу версии
123
SHA-1. Позднее стандарт пересмотрен вновь, и были определены четыре новые версии: SHA-224, SHA-256, SHA-384, SHA-512. Все версии имеют одинаковую структуру, поэтому часто их называют общим именем SHA-2. В табл. 3.3 приведены характеристики этих версий.
Функция сжатия
h
0
Оригинальное сообщение М
М
1
М
2
М
t
Функция сжатия
Функция сжатия
h
t
h
1
h
2
h
t - 1
m
n
n
n
m
m
m
m
IV - вектор инициализации
Хеш-образ
Дополнение
Рис. 3.3. Схема итеративной хеш-функции
Дополнение
Padding 1000...000
Длина M
Рис. 3.4. Структура дополнения при итеративном хешировании
Таблица 3.3
Характеристики SHA
Характеристика
SHA-1
SHA-224
SHA-256
SHA-384
SHA-512
Максимальная длина сообщения
1 2
64 1
2 64 1
2 64 1
2 128 1
2 128
Длина блока
512 512 512 1024 1024
Длина хеш-образа
160 224 256 384 512
Число раундов
80 64 64 80 80
Длина слова
32 32 32 64 64
Рассмотрим версию SHA-1, в которой осуществляется пре- образование информационной последовательности произволь- ной длины в хеш-образ разрядностью 160 бит. На первом этапе информационная последовательность дополняется до длины, кратной 512 бит. Сначала информационная последовательность дополняется до длины на 64 двоичных разряда меньшей числа, кратного 512: к концу последовательности (сообщения) припи- сывается 1, а затем необходимое количество нулей. После этого
124 приписывается 64-разрядный код длины сообщения. Если дли- на исходного сообщения больше
,
2 64
используются только 64 младших разряда этого кода. Пусть после дополнения получена информационная последовательность
512
,
,
1
,
2 1
i
t
i
M
t
i
M
M
M
M
M
На вход i-го основного цикла
i
SHA преобразования поступает
i-й блок информационной последовательности и результат раб о- ты предыдущего цикла
,
1
-
i
SHA
т.е.
,
1
-
i
i
i
SHA
M
h
SHA
Перед началом каждого цикла соответствующий блок расши- ряется до 80 слов по 32 разряда в каждом. Расширение происхо- дит следующим образом. Пусть
16 2
1
...w
w
w
исходный блок,
80 2
1
w
w
w
расширенный блок, при этом
j
j
w
w
для
,
16
,
1
j
16
-
14
-
8
-
3
-
j
j
j
j
j
w
w
w
w
Rol
w
для
,
80
,
17
j
где Rol операция циклического сдвига на один разряд влево.
Перед началом первого цикла инициализируются пять
32-разрядных переменных:
A = 67452301h, B = EFCDAB89h, C = 98BADCFEh,
D = 10325476h, E = C3D2E1F0h, при этом стартовый вектор хеширования (синхропосылка) есть результат конкатенации этих переменных, т.е.
,
,
,
,
0
E
D
C
B
A
SHA
Конкатенация новых значений этих переменных, полученных в конце i-го цикла, объявляется результатом работы цикла
i
SHA
В начале каждого цикла создаются копии входных перемен- ных
AA = A, BB = B, CC = C, DD = D, EE = E.
125
Затем выполняются 80 шагов алгоритма, на каждом из которых происходит выполнение следующих операций:
,
;
;
;
;
,
,
30 5
Tem p
A
B
Rol
C
C
D
D
E
c
M
E
D
C
B
f
A
Rol
Tem p
j
ij
j
где
n
Rol операция циклического сдвига на n разрядов влево;
j
f шаговая функция;
ij
M
j-е слово i-го блока
;
i
M
j
c
ша- говая константа;
,
1
,
80
,
1
t
i
j
В первом раунде (при
20
,
1
j
) используются функция
Z
X
XY
Z
Y
X
f
j
,
,
и константа
;
5A827999h
j
c
во втором раунде (при
40
,
21
j
) функция
Z
Y
X
Z
Y
X
f
j
,
,
и константа
;
h
1
ED9EBA
6
j
c
в третьем раунде (при
60
,
41
j
) функция
ZY
XY
XZ
Z
Y
X
f
j
,
,
и константа
;
8F1BBCDCh
j
c
в четвертом раунде (при
80
,
61
j
) функция
Z
Y
X
Z
Y
X
f
j
,
,
и константа
CA62C1D6h
j
c
Цикл завершается сложением по модулю
32 2
полученных значений A, B, C, D и E соответственно с AA, BB, CC, DD и EE:
126
,
,
,
,
,
EE
E
E
DD
D
D
CC
C
C
BB
B
B
AA
A
A
конкатенация полученных значений A, B, C, D и E является ре- зультатом работы основного цикла.
Алгоритмы семейства SHA-2 значительно отличаются от бо- лее ранних версий SHA. Опишем алгоритм SHA-256.
Перед хешированием сообщению дополняется до длины, крат- ной 512 бит, аналогично SHA-1. После этого полученная последо- вательность разделяется на блоки по 512 бит (16 32-разрядных слов), каждый из которых поступает на вход функции сжатия SHA-
256. В этом смысле мы имеем обычную итеративную хеш- функцию.
Функция сжатия обладает похожей итеративной структурой.
Функция «расширения» блока на основе 16 слов исходного со- общения формирует расширенное сообщение 64 слова, по- ступающие на вход 64 раундов функции сжатия, как показано на рис. 3.5, где РФ – раундовая функция.
Функция расширения блока MS описывается следующим об- разом. Первые 16 слов расширенного сообщения соответствуют исходным 16 словам блока, дальнейшие слова формируются по рекуррентной формуле:
}
256
{
0
(x)= ROTR
7
(x) ROTR
18
(x) SHR
3
(x);
}
256
{
1
(x)= ROTR
17
(x) ROTR
19
(x) SHR
10
(x);
w
t
=
}
256
{
1
(w
t - 2
) + w
t - 7
+
}
256
{
0
(w
t - 15
) + w
t - 16
,
где w
i
– i-е слово расширенного сообщения. Здесь и далее
ROTR
a
(x) обозначает слово x, циклически сдвинутое вправо на a разрядов.
127
w1w64
w2wiSSmiMS......РФ
РФ
РФ
РФ
256 256 256 256 256 256 256 32 32 32 32
Рис. 3.5. Функция сжатия SHA-256:
mi–
блок сообщения;
wj – слова расширенного блока сообщения;
S – состояние определяемое регистрами
a,
b,
c,
d,
e,
f,
g,
h Структура раунда изображена на рис. 3.6.
adcbhgfe∑
0
∑
1
Maj(
a,
b,
c)
Ch(
e,
f,
g)
KtwtРис. 3.6. Структура раунда SHA-2
На рисунке приняты следующие обозначения:
Ch (
X,
Y,
Z)
= ;
ZXXYMaj (
X,
Y,
Z)
= XY XZ YZ;
}
256
{
0
(
x)
= ROTR2
(
x)
ROTR13
(
x)
ROTR22
(
x);
}
256
{
1
(
x)
= ROTR6
(
x)
ROTR11
(
x)
ROTR25
(
x).
Используется фиксированную последовательность из 64 32-разрядных констант (по количеству раундов). На каждом раунде применяется одна константа из этого массива, обозна- ченная на рис. 3.6 как
KtSHA-224 представляет собой SHA-256 с «обрезанным» до
224 бит хеш-образом и изменённым начальным состоянием.
128
SHA-384 получается аналогичным образом из SHA-512. Инте- ресно, что по стандарту разрешается сокращать хеш-образ до любой длины, если это по каким-либо причинам необходимо.
3.4. Хеш-функции на основе симметричных
блочных криптоалгоритмов
При использовании для построения
x
h
симметричных блоч- ных криптоалгоритмов стойкость хеш-функции гарантируется стойкостью применяемого блочного шифра. Пусть
)
,
1
(
2 1
t
i
M
M
M
M
M
t
i
– последовательность, состоящая из блоков, размер которых равен размеру ключа блочного шифра. Блоки
i
M суть результат расши- рения блоков исходного сообщения меньшей длины (см, например, схему получения кода MDC в гл. 4). Наиболее надежные схемы получаются при использовании для вычисления текущего хеш- значения
i
h функции зашифрования
,
k
E где ключ k – предыдущее хеш-значение
,
1
-
i
h
хотя известны схемы, в которых в качестве k используется либо очередной блок сообщения
i
M , либо
1
-
i
i
M
h
Наиболее известны следующие схемы формирования хеш-образа
t
h
M
h
=
:
;
1
-
i
i
h
i
M
M
E
h
i
;
1
-
1
-
1
-
i
i
i
i
h
i
h
M
h
M
E
h
i
;
1
-
1
-
i
i
i
h
i
h
M
M
E
h
i
1
-
1
-
i
i
i
h
i
M
h
M
E
h
i
На рис. 3.7 показаны три варианта построения хеш-функции на основе функции зашифрования
M
E
k
Структура, показанная на рис. 3.7,в, использована при проек- тировании хеш-функции Whirlpool, представленной в рамках ев- ропейского конкурса New European Schemes for Signatures, Integri- ty and Encryption (NESSIE). В качестве симметричного блочного шифра для реализации функции сжатия авторами (V. Rijmen,
P. Barreto) использован модифицированный алгоритм AES.
129
E
AB
h
0
М
Дополнение
М
1
М
2
М
t
h
t
E
AB
E
AB
E
AB
М
Дополнение
М
1
М
2
М
t
...
h
t
E
AB
E
AB
h
0
...
E
AB
h
0
М
Дополнение
М
1
М
2
М
t
h
t
E
AB
E
AB
...
m
m
m
m
m
m
m
m
n
n
n
а
б
в
Рис. 3.7. Варианты построения хеш-функций на основе преобразования
M
E
k
Контрольные вопросы
1.
Что такое парадокс дней рождения?
2.
Какие три задачи являются вычислительно неразрешимыми для качественной криптографической хеш-функции?
3.
Перечислите необходимые свойства качественной хеш- функции (не менее пяти).
4.
Нарисуйте схему итеративной хеш-функции.
Скачать 3.04 Mb.