Иванов М.А. КМЗИ сети

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

Рис. 3.2. Атаки на хеш-функцию:

а – нахождение прообраза; б – нахождение второго прообраза

Наиболее известные алгоритмы хеширования – MD5, SHA, Tiger, Whirlpool.

MD5 – представитель семейства хеш-функций MD (Message Digest Algorithm), предложенного Р. Ривестом; разработан в 1991 г.; преобразует информационную последовательность произвольной длины в хеш-образ разрядностью 128 бит.

Tiger разработан Р. Андерсоном и Э. Бихэмом; предназначен для реализации на 64-разрядных компьютерах; преобразует информационную последовательность произвольной длины в хеш-образ разрядностью 192 бит.

121

3.2. Итеративная хеш-функция

На рис. 3.3 показана схема итеративной хеш-функции, которая является стойкой в смысле нахождения коллизий, если аналогичным свойством обладает используемая функция сжатия. Обозначения: M1, M2 , ..., Mt – блоки дополненного сообщения; t – число

блоков дополненного сообщение; h0 – фиксированное значение, называемое стартовым вектором или вектором инициализации IV; h1, h2 , ..., ht – промежуточные результаты вычисления итераций,

число которых равно числу блоков t . Оригинальное сообщение дополняется до длины, кратной n , где n – разрядность блока данных, обрабатываемого функцией сжатия. На i -м итерационном шаге функция сжатия f принимает результат предыдущего шага hi-1

структура дополнения показана на рис. 3.4.

3.3. Secure Hash Algorithm (SHA)

Алгоритм SHA является частью стандарта SHS (Secure Hash Standard), разработанного в 1993 г. Национальным институтом стандартов и технологий США (FIPS 180) и Агенством национальной безопасности США. SHA использует принципы, предложенные ранее Р. Ривестом при разработке своих алгоритмов семейства MD. В 1995 г. стандарт был пересмотрен (FIPS 180-1) в пользу версии

122

SHA-1. Позднее стандарт пересмотрен вновь, и были определены четыре новые версии: SHA-224, SHA-256, SHA-384, SHA-512. Все версии имеют одинаковую структуру, поэтому часто их называют общим именем SHA-2. В табл. 3.3 приведены характеристики этих версий.

Рассмотрим версию SHA-1, в которой осуществляется преобразование информационной последовательности произвольной длины в хеш-образ разрядностью 160 бит. На первом этапе информационная последовательность дополняется до длины, кратной 512 бит. Сначала информационная последовательность дополняется до длины на 64 двоичных разряда меньшей числа, кратного 512: к концу последовательности (сообщения) приписывается 1, а затем необходимое количество нулей. После этого

123

приписывается 64-разрядный код длины сообщения. Если дли-

на исходного сообщения больше 264, используются только 64 младших разряда этого кода. Пусть после дополнения получена информационная последовательность

i-й блок информационной последовательности и результат работы предыдущего цикла SHAi-1, т.е.

SHAi h Mi , SHAi-1 .

Перед началом каждого цикла соответствующий блок расширяется до 80 слов по 32 разряда в каждом. Расширение происходит следующим образом. Пусть

где Rol операция циклического сдвига на один разряд влево. Перед началом первого цикла инициализируются пять

32-разрядных переменных:

A = 67452301h, B = EFCDAB89h, C = 98BADCFEh, D = 10325476h, E = C3D2E1F0h,

при этом стартовый вектор хеширования (синхропосылка) есть результат конкатенации этих переменных, т.е.

A, B, C, D, E .

Конкатенация новых значений этих переменных, полученных

вконце i-го цикла, объявляется результатом работы цикла SHAi .

Вначале каждого цикла создаются копии входных перемен-

ных

AA = A, BB = B, CC = C, DD = D, EE = E.

124

Затем выполняются 80 шагов алгоритма, на каждом из которых происходит выполнение следующих операций:

Temp Rol5 A f j B, C, D E Mij c j ; E D;

D C ;

C Rol30B;

A Temp,

где Roln операция циклического сдвига на n разрядов влево;

и константа

cj CA62C1D6h.

Цикл завершается сложением по модулю 232 полученных значений A, B, C, D и E соответственно с AA, BB, CC, DD и EE:

125

A A AA,

BB BB,

CC CC, D D DD,

EE EE ,

конкатенация полученных значений A, B, C, D и E является результатом работы основного цикла.

Алгоритмы семейства SHA-2 значительно отличаются от более ранних версий SHA. Опишем алгоритм SHA-256.

Перед хешированием сообщению дополняется до длины, кратной 512 бит, аналогично SHA-1. После этого полученная последовательность разделяется на блоки по 512 бит (16 32-разрядных слов), каждый из которых поступает на вход функции сжатия SHA256. В этом смысле мы имеем обычную итеративную хешфункцию.

Функция сжатия обладает похожей итеративной структурой. Функция «расширения» блока на основе 16 слов исходного сообщения формирует расширенное сообщение 64 слова, поступающие на вход 64 раундов функции сжатия, как показано на рис. 3.5, где РФ – раундовая функция.

Функция расширения блока MS описывается следующим образом. Первые 16 слов расширенного сообщения соответствуют исходным 16 словам блока, дальнейшие слова формируются по рекуррентной формуле:

ς{0256} (x)= ROTR7(x) ROTR18(x) SHR3(x);

ς1{256} (x)= ROTR17(x) ROTR19(x) SHR10(x);

wt=ς1{256} (wt - 2) + wt - 7 + ς0{256} (wt - 15) + wt - 16,

где wi – i-е слово расширенного сообщения. Здесь и далее ROTRa(x) обозначает слово x, циклически сдвинутое вправо на a разрядов.

126

mi

MS

mi – блок сообщения; wj – слова расширенного блока сообщения; S – состояние определяемое регистрами a, b, c, d, e, f, g, h

Структура раунда изображена на рис. 3.6.

Рис. 3.6. Структура раунда SHA-2

На рисунке приняты следующие обозначения:

Ch (X, Y, Z) = XY XZ;

Maj (X, Y, Z) = XY XZ YZ;

¦{256} (x)= ROTR2(x) ROTR13(x) ROTR22(x);

0

¦{256} (x)= ROTR6(x) ROTR11(x) ROTR25(x).

1

Используется фиксированную последовательность из 64 32-разрядных констант (по количеству раундов). На каждом раунде применяется одна константа из этого массива, обозначенная на рис. 3.6 как Kt.

SHA-224 представляет собой SHA-256 с «обрезанным» до 224 бит хеш-образом и изменённым начальным состоянием.

127

SHA-384 получается аналогичным образом из SHA-512. Интересно, что по стандарту разрешается сокращать хеш-образ до любой длины, если это по каким-либо причинам необходимо.

3.4. Хеш-функции на основе симметричных блочных криптоалгоритмов

При использовании для построения h x симметричных блоч-

ных криптоалгоритмов стойкость хеш-функции гарантируется стойкостью применяемого блочного шифра. Пусть

M M1 M2 ... Mi ... Mt (i 1, t) –

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

рения блоков исходного сообщения меньшей длины (см, например, схему получения кода MDC в гл. 4). Наиболее надежные схемы получаются при использовании для вычисления текущего хешзначения hi функции зашифрования Ek , где ключ k – предыдущее

хеш-значение hi-1, хотя известны схемы, в которых в качестве k используется либо очередной блок сообщения Mi , либо hi-1 Mi .

На рис. 3.7 показаны три варианта построения хеш-функции на основе функции зашифрования Ek M .

Структура, показанная на рис. 3.7,в, использована при проектировании хеш-функции Whirlpool, представленной в рамках ев-

ропейского конкурса New European Schemes for Signatures, Integrity and Encryption (NESSIE). В качестве симметричного блочного шифра для реализации функции сжатия авторами (V. Rijmen, P. Barreto) использован модифицированный алгоритм AES.

128

МДополнение

Рис. 3.7. Варианты построения хеш-функций на основе преобразования Ek M

Контрольные вопросы

1.Что такое парадокс дней рождения?

2.Какие три задачи являются вычислительно неразрешимыми для качественной криптографической хеш-функции?

3.Перечислите необходимые свойства качественной хешфункции (не менее пяти).

4.Нарисуйте схему итеративной хеш-функции.

129

ГЛАВА 4. МЕТОДЫ АУТЕНТИФИКАЦИИ ИНФОРМАЦИИ

4.1.Аутентичность. Задача аутентификации информации

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

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

На самом деле приведенные рассуждения ошибочны. Искажения, внесенные в зашифрованные данные, становятся очевидными после расшифрования только в случае большой избыточности исходных данных. Эта избыточность имеет место лишь в некоторых частных случаях (например, когда исходная информация является текстом на естественном или искусственном языке). В общем случае требование избыточности данных может не выполняться, а это означает, что после расшифрования модифицированных данных они по-прежнему могут поддаваться интерпретации. Кроме того, при использовании симметричной криптосистемы факт успешного расшифрования данных, зашифрованных на секретном ключе, может подтвердить их авторство лишь для самого получателя. Третий участник информационного обмена (арбитр) при возникновении споров не сможет сделать однозначного вывода об авторстве информационного массива, так как его автором может быть каждый из обладателей секрет-

130