Новиков А. О.
Иркутский Национальный Исследовательский Технический Университет
Хеширование. Краткий обзор хеш-функций.
Хеширование – преобразование входного массива данных произвольной длины в выходную битовую строку фиксированной длины. Такие преобразования также называются хеш-функциями или функциями свёртки, а их результаты называют хешем, хеш-кодом или дайджестом сообщения.
Анализ при помощи хеш-функций часто используют для контроля целостности важных файлов операционной системы, важных программ, важных данных. Контроль может производиться как по необходимости, так и на регулярной основе.
Это осуществляется следующим образом. Вначале определяют, целостность каких файлов нужно контролировать. Для каждого файла производится вычисления значения его хеша по специальному алгоритму с сохранением результата. Через необходимое время производится аналогичный расчет и сравниваются результаты. Если значения отличаются, значит информация содержащаяся в файле была изменена.
Функция хеширования (хеш-функция) представляет собой преобразование, на вход которого подается сообщение переменной длины M, а выходом является строка фиксированной длины h(M). Иначе говоря, хеш-функция h() принимает в качестве аргумента сообщение (документ) M произвольной длины и возвращает хеш-значение (хеш) H = h(M) фиксированной длины.
Хеш-значение h(M) – это дайджест сообщения М, то есть сжатое двоичное представление основного сообщения М произвольной длины. Хеш-значение h(M) формируется функцией хеширования.
Функция хеширования позволяет сжать подписываемый документ M до 128 бит и более (в частности, 128 или 256 бит), тогда как M может быть размером в мегабайты или более. Следует отметить, что значение хеш-функции h(M) зависит сложным образом от документа M и не позволяет восстановить сам документ M.
Функция хеширования должна обладать следующими свойствами:
1. Хеш-функция может быть применена к аргументу любого размера.
2. Выходное значение хеш-функции имеет фиксированный размер.
3. Хеш-функцию h(x) достаточно просто вычислить для любого x. Скорость вычисления хэш-функции должна быть такой, чтобы скорость выработки и проверки электронной цифровой подписи (ЭЦП) при использовании хеш-функции была значительно больше, чем при использовании самого сообщения.
4. Хеш-функция должна быть чувствительна к всевозможным изменениям в тексте M, таким как вставки, выбросы, перестановки и т.п.
5. Хеш-функция должна быть однонаправленной, то есть обладать свойством необратимости. Иными словами, задача подбора документа M', который обладал бы требуемым значением хеш-функции, должна быть вычислительно неразрешима.
6. Вероятность того, что значения хеш-функций двух различных документов (вне зависимости от их длин) совпадут, должна быть ничтожно мала: то есть для любого фиксированного x с вычислительной точки зрения невозможно найти x' ≠ x, такое что h(x') = h(x).
Теоретически возможно, что два различных сообщения могут быть сжаты в одну и ту же свертку (так называемая коллизия, или столкновение). Поэтому для обеспечения стойкости функции хеширования необходимо предусмотреть способ избегать столкновений. Полностью столкновений избежать нельзя, поскольку в общем случае количество возможных сообщений превышает количество возможных выходных значений функции хеширования. Однако вероятность столкновения должна быть низкой.
Свойство 5 эквивалентно тому, что h() является односторонней функцией. Свойство 6 гарантирует, что не может быть найдено другое сообщение, дающее ту же свертку. Это предотвращает фальсификацию сообщения.
Таким образом, функция хеширования может использоваться для обнаружения изменений сообщения, то есть она может служить для формирования криптографической контрольной суммы (также называемой кодом обнаружения изменений или кодом аутентификации сообщения). В этом качестве хеш-функция используется для контроля целостности сообщения, при формировании и проверке электронной цифровой подписи. Хеш-функции широко используются также в целях аутентификации пользователей.
Некоторые функции хеширования:
MD (Message Digest) – ряд алгоритмов хеширования, наиболее
распространенных в мире. Каждый из них вырабатывает 128-битовый хеш-код.
Алгоритм MD2 – самый медленный из них, MD4 – самый быстрый. Алгоритм MD5
является модификацией MD4, при которой пожертвовали скоростью ради увеличения
безопасности. Алгоритм MD5 применяется в последних версиях Microsoft Windows
для преобразования пароля пользователя в 16-байтовое число. Новая
функция MD6 предполагается доказуемо устойчивой к дифференциальному
криптоанализу (с помощью которого была взломана MD5).
Разработчики использовали оригинальные идеи в дизайне хеш-функции. Так, размер
обрабатываемого за один раз блока данных будет 512 байт (а не бит), что
затрудняет проведение многих атак, даёт выигрыш в распараллеливании. MD6
поддерживает также хеширование с ключем 512-бит. Различные конструктивные
особенности (нумерация узлов деревьев, root и z-биты на входе в подфункции)
защищают функцию от атак вставок и расширения. Нелинейность функции достигается
использованием всего трёх простейших операций: XOR, сложение и сдвиг с
константами.
SHA (Secure Hash Algorithm) – это алгоритм вычисления дайджеста сообщений, вырабатывающий 160-битовый хеш-код входных данных. Широко распространен в мире, используется во многих сетевых протоколах защиты информации.
Российский стандарт ГОСТ Р34.11-94. который повсеместно используется многими производителями средств защиты информации. Одним из таких средств является программа фиксации и контроля исходного состояния программного комплекса «ФИКС». Эта программа является средством контроля эффективности применения СЗИ.Вычисляет хеш-функцию размером 32 байт.
RIPEMD-320 – хэш-функция разработана Хансом Доббертином, Антоном Боселаерсом и Бартом Принилом в 1996 году. Размер хэша — 320 бит. Размер блока входных данных – 512 бит. Уязвимостей на текущий момент не обнаружено.
Хеш-функции широко используются также для аутентификации пользователей. Существует множество криптографических протоколов, основанных на применении хеш-функций.
Литература
1. Петров А.А. «Компьютерная безопасность. Криптографические методы защиты.» - М.:ДМК, 2000. – 448 с.
2. ГОСТ Р 34.11-94. Информационная технология. Криптографическая защита информации. Функция хэширования. - М.: Госстандарт России, 1994.
3. Галатенко В.А. Основы информационной безопасности. Курс лекций. – М.: ИНТУИТ. РУ, 2006. – 205 с.
4. В.И. Глухих «Информационная безопасность и защита данных: учебное пособие» Иркутский технический университет. − Иркутск: Изд-во Иркутского технического университета, 2012. – 244 с.