Хеш-функции

Определение 3.1. Хеш-функцией называется преобразование , превращающее последовательность произвольной длины в информационную последовательность фиксированной длины [1,2,6,7,9].

В общем случае гораздо меньше, чем , например, может быть 128 или 256 бит, тогда как может быть размером в мегабайты и более.

Хеширование иногда считают видом криптографического преобразования. Вместе с тем, криптографическое преобразование, по определению, является обратимым, а хеширование представляет собой необратимое преобразование.

3.1.Требования к хеш-функции

Для того чтобы хеш-функция могла быть использована в криптографических алгоритмах она должна обладать следующими свойствами [2,9]:

- преобразование может быть применено к любого размера;

- выходное значение должно иметь фиксированный размер;

- значение достаточно просто вычисляется для любого ;

- для любого значения с вычислительной точки зрения невозможно найти ;

- для любого значения с вычислительной точки зрения невозможно найти , такое, что ;

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

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

1. Задача нахождения прообраза – это задача нахождения входной последовательности по заданному хеш-образу . Хеш-функция должна быть стойкой в смысле обращения.

2. Задача нахождения коллизий – это задача нахождения последовательностей и , причем , для которых . Хеш-функция должна быть стойкой в смысле нахождения коллизий.

3. Задача нахождения второго прообраза – это задача нахождения для заданной входной последовательности другой входной последовательности , причем , такой, что . Эта задача является разновидностью задачи нахождения коллизий.

В табл.3.1 представлены атаки на хеш-функции и приведена оценка их вычислительной сложности.

Таблица 3.1. Оценка сложности атак на хеш-функцию

Атака	Вычислительная сложность
Нахождение прообраза
Нахождение второго прообраза
Нахождение коллизии

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

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

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

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

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

Рис. 3.1. Схема итерационной хеш-функции

Итерационная хеш-функция является стойкой в смысле нахождения коллизий, если аналогичным свойством обладает функция сжатия .

Рассмотрим, в качестве примера, итерационный алгоритм хеширования SHA (Secure Hash Algorithm) являющегося частью стандарта SHS (Secure Hash Standard), разработанный Национальным институтом стандартов и технологий США в 1993 году. Алгоритм был предложен Р. Ривестом и в своем первоначальном виде обозначался как SHA-1. В 1995 году стандарт был пересмотрен и определены четыре версии алгоритма: SHA-224, SHA-256, SHA-384, SHA-512. Все версии имеют одинаковую структуру, поэтому их называют общим именем SHA-2. В табл. 3.2 представлены характеристики SHA.

Рассмотрим версию SHA-1 (см. рис. 3.2). На первом этапе входная информационная последовательность дополняется до длины 512 бит.

Таблица 3.2. Характеристики SHA

Характеристика	SHA-1	SHA-224	SHA-256	SHA-384	SHA-512
Максимальная длина сообщения	-1	-1	-1	-1	-1
Длина блока
Длина хеш-образа
Число раундов

Рис. 3.2. Схема одного шага алгоритма SHA

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

, 512.

На вход -го основного цикла SHA преобразования поступает -й блок информационной последовательности и результат работы предыдущего цикла SHA, т.е.

.

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

для ,

для ,

где - операция циклического сдвига на один разряд влево.

Перед началом первого цикла инициализируются пять 32-разрядных переменных: 67452301h, EFCDAB89h, 98BADCFEh, 10325476h, C3D2E1F0h, при этом вектор инициализации является результатом конкатенации этих переменных

,

где - символ операции конкатенации.

Конкатенация новых значений этих переменных, полученных в конце -го цикла, объявляется результатом работы цикла .

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

, , ,

, ,

, ,

где - операция циклического сдвига на разрядов влево, - шаговая функция, - -е слово -го блока , - шаговая константа.

В первом раунде (при ) используются функции и константа:

, 5А827999h,

во втором раунде (при ) -

, 6ED9EBA1h,

в третьем раунде (при ) -

, 8F1BBCDCh,

в четвертом раунде (при ) -

, CA62C1D6h.

Цикл завершается сложением по модулю :

, , , , ,

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

Алгоритмы семейства SHA-2 значительно отличаются от версии SHA-1. Рассмотрим алгоритм SHA-256 [9].

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

Функция сжатия имеет похожую итерационную структуру. Функция расширения блока на основе 16 слов исходного сообщения формирует расширенное сообщение - 64 слова, поступающие на вход 64 раундов функции сжатия (РФС) (см. рис. 3.3).

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

,

,

.

где - -е слово расширенного сообщения, - циклический сдвиг слова вправо на позиций, - сдвиг слова вправо на позиций.

Рис. 3.3. Функция сжатия SHA-256

Структура раунда представлена на рис. 3.4., где приняты следующие обозначения:

,

,

,

.

Используется фиксированная последовательность из 64 32-разрядных констант (по количеству раундов). На каждом раунде используется одна константа из этого массива . Более подробно семейство SHA-2 описано в [2,9].

Рис. 3.4. Один раунд функции сжатия SHA-256

К итерационным алгоритмам хеширования относятся ГОСТ Р 34.11-94, MD5 и др.

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

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

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

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

,

;

;

.

Здесь в качестве ключа используется хеш-значение, вычисленное на предыдущем шаге . Третья формула реализует схему хеширования, которая используется в алгоритме Whirlpool. В качестве симметричной блочной криптосистемы используется алгоритм AES.

В заключение этой главы необходимо сказать, что в настоящее время в РФ принят стандарт хеширования ГОСТ Р 34.11-2012, проектное название представленного стандартом семейства хеш-функций носит название «Стрибог». Основными отличиями ГОСТ Р 34.11-2012 («Стрибог») и ГОСТ Р 34.11-94 являются:

- размер блоков сообщения и внутреннего состояния в ГОСТ Р 34.11-2012 составляет 512 бит, а в ГОСТ Р 34.11-94 – 256 бит;

- ГОСТ Р 34.11-2012 состоит из двух хеш-функций, с длинами результирующего значения хеш-образа 256 и 512 бит;

- В ГОСТ Р 34.11-94 в качестве функции сжатия используется блочный симметричный криптоалгоритм ГОСТ 28147-89, а в ГОСТ Р 34.11-2012 функция сжатия другая и это - главное отличие. В ГОСТ Р 34.11-2012 функция сжатия состоит из трех основных преобразований: подстановки на байтах, транспонирования матрицы байт, умножения 64-битных векторов на матрицу 64×64.

Результаты тестирования хеш-функций показали, что ГОСТ Р 34.11-2012 практические в два раза быстрее, чем ГОСТ Р 34.11-94. К тому же ГОСТ Р 34.11-2012 проще в реализации и оптимизации как алгоритмически, так и для конкретной платформы.

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

1. Дайте определение хеш-функции.

2. Назовите свойства, которыми должна обладать хеш-функция.

3. В чем суть задач: нахождения прообраза, нахождения коллизий, нахождения второго прообраза.

4. Что такое итерационная хеш-функция. Приведете примеры.

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

Дата добавления: 2014-12-26