- •Введение
- •1.2 Пример хеш-функции.
- •Ключевые функции хеширования
- •Бесключевые функции хеширования
- •Обзор блочного шифрования.
- •Логика выполнения sha-1
- •Сравнение sha-1 и md5
- •Краткое описание алгоритма гост 28147-89
- •Алгоритм вычисления шаговой функции хэширования
- •Генерация ключей
- •Шифрующее преобразование
- •Перемешивающее преобразование
- •Различные атаки на хеш-функции.
-
Хеш-функции.
-
Введение
-
Функцией хеширования (в широком смысле) называется функция , удовлетворяющая минимум двум требованиям:
1. Сжатие – функция отображает входное сообщениепроизвольной конечной длины в хеш-значение небольшой фиксированной длины, при этом входное сообщение будем называть прообразом.
2. Простота вычисления – для заданной функции и сообщения , вычисляется не выше, чем с полиномиальной сложностью.
Хеш-функции имеют разнообразные применения при проведении статистических экспериментов, при тестировании логических устройств, при построении алгоритмов быстрого поиска и проверки целостности записей в базах. Например, для осуществления быстрого поиска нужного сообщения в большом списке сообщений различной длины удобнее сравнивать друг с другом не сами сообщения, а короткие значения их сверток, играющих одновременно роль контрольных сумм. Основным требованием к таким хеш-функциям является равномерность распределения их значений при случайном выборе значений аргументов.
Простейшим примером хэш-функций являются контрольные суммы. Это несложные, крайне быстрые и легко реализуемые аппаратные алгоритмы, используемые для защиты от непреднамеренных искажений, в том числе ошибок аппаратуры. По скорости вычисления в десятки и сотни раз быстрее, чем криптографические хеш-функции, и значительно проще в аппаратной реализации. Примером такого алгоритма является деление сообщения на 32- или 16- битные слова и их суммирование.
Платой за столь высокую скорость является отсутствие криптостойкости — лёгкая возможность подогнать сообщение под заранее известную сумму. Также обычно разрядность контрольных сумм (типичное число: 32 бита) ниже, чем криптографических хешей (типичные числа: 128, 160 и 256 бит), что означает возможность возникновения непреднамеренных коллизий.
Поэтому в криптографии используют более сложные функции.
Рассмотрим основные задачи криптографии в которых используются хэш-функции:
-
построения систем контроля целостности данных при их передаче или хранении,
-
аутентификации источника данных.
При решении первой задачи для каждого набора данных вычисляется значение хеш-функции (называемое кодом аутентификации сообщения или имитовставкой), которое передается или хранится вместе с самими данными. При получении данных пользователь вычисляет значение свертки и сравнивает его с имеющимся контрольным значением. Несовпадение говорит о том, что данные были изменены.
Хеш-функция, служащая для выработки имитовставки, должна позволять (в отличие от обычной контрольной суммы) осуществлять обнаружение не только случайных ошибок в наборах данных, возникающих при их хранении и передаче, но и сигнализировать об активных атаках злоумышленника, пытающегося осуществить навязывание ложной информации. Для того чтобы злоумышленник не смог самостоятельно вычислить контрольное значение свертки и тем самым осуществить успешную имитацию или подмену данных, хеш-функция должна зависеть от секретного, не известного злоумышленнику, параметра — ключа пользователя. Этот ключ должен быть известен передающей и проверяющей сторонам. Такие хеш-функции будем называть ключевыми.
Имитовставки, формируемые с помощью ключевых хеш-функций, не должны позволять противнику создавать поддельные (сфабрикованные) и модифицировать передаваемые сообщения.
При решении второй задачи — аутентификации источника данных — мы имеем дело с не доверяющими друг другу сторонами. В связи с этим подход, при котором обе стороны обладают одним и тем же секретным ключом, уже неприменим. В такой ситуации применяют схемы цифровой подписи, позволяющие осуществлять аутентификацию источника данных. Как правило, при этом сообщение, прежде чем быть подписано личной подписью, основанной на секретном ключе пользователя, "сжимается" с помощью хеш-функции, выполняющей функцию кода обнаружения ошибок. В данном случае хеш-функция не зависит от секретного ключа и может быть фиксирована и известна всем. Основными требованиями к ней являются гарантии невозможности подмены подписанного документа, а также подбора двух различных сообщений с одинаковым значением хеш-функции (в этом случае говорят, что такая пара сообщений образует коллизию).
Формализуя сказанное, введем следующее определение. Обозначим через X множество, элементы которого будем называть сообщениями. Обычно сообщения представляют собой последовательности символов некоторого алфавита, как правило, двоичного. Пусть Y — множество двоичных векторов фиксированной длины.
Хеш-функцией называется всякая функция удовлетворяющая следующим требованиям:
-
для данного легко вычислить
-
для данного трудно вычислить такое, что
-
для данного трудно вычислить , , такое, что .
Отображение , удовлетворяющее требованиям 1) и 2), является однонаправленным. Иногда вместо 3) требуют выполнения более сильного свойства.
трудно вычислить пару , для которой .
Пара элементов множества (пара сообщений), о которой идет речь в называется коллизией для отображения . Т.к. мощность больше мощности , то допускает коллизии.
Покажем теперь, что при выполнении нескольких естественных предположений условие влечет выполнение условия 2).
Лемма 1.1.1 Пусть - конечные множества, и . Задано произвольное отображение . Пусть для любого имеется эффективный алгоритм вычисления такого, что (если существует), при этом алгоритм задает равномерное распределение на множестве таких при всех . Тогда имеется эффективный алгоритм вычисления коллизии для функции .
Доказательство. Обозначим через алгоритм обращения , о котором идет речь в формулировке леммы. Т.е. для некоторого такого, что . Сформулируем алгоритм вычисления коллизии.
Входные данные алгоритма: хеш-функция , алгоритм .
ыходные данные алгоритма: коллизия для .
Шаг 1. Выбрать случайное , вычислить .
Шаг 2. Вычислить .
Шаг 3. Если , то перейти к шагу 1; в противном случае - коллизия для . Алгоритм заканчивает работу.
Оценим среднее число прохождений алгоритма через шаг 1. Имеем вероятностную схему, исходами которой являются пары , где . Обозначим через множество , для которых . Заметим, что число классов не больше . Тогда вероятность исхода равна . Благоприятными являются исходы , где . Найдем вероятность неблагоприятного исхода. Она равна
.
Отсюда вероятность благоприятного исхода не меньше . Т.о. среднее число прохождений алгоритма через шаг 1 не превосходит 2. Т.е. этот алгоритм эффективен. Лемма доказана.
Т.о. свойство влечет 2). Очевидно, что влечет также 3).
Лемма 1.1.2. В общем случае устойчивая к коллизиям хеш-функция не обязана быть однонаправленной.
В качестве примера несжимающей функции приведем функцию , которая, очевидно, является устойчивой к коллизиям и к нахождению второго прообраза, но не является однонаправленной.
В качестве примера сжимающей хеш-функции рассмотрим функцию h, определенную условиями:
если битовая длина x равна n,
если битовая длина x больше n.
где — сжимающая n-битовая функция, устойчивая к коллизиям. Функция h также является устойчивой к коллизиям и к нахождению второго прообраза, но, очевидно, не является однонаправленной.