Криптографические хэш-функции

From CryptoWiki
Jump to: navigation, search

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

Contents

Постановка задачи

Хэш-функции, долгое время использующиеся в компьютерных науках, представляют собой функции, математические или иные, которые получают на вход строку переменной длины (называемую прообразом) и преобразуют ее в строку фиксированной, обычно меньшей, дли- ны (называемую значением хэш-функции). В качестве простой хэшфункции можно рассматривать функцию, которая получает прообраз и возвращает байт, представляющий собой XOR всех входных байтов. Смысл хэш-функции состоит в получении характерного признака, прообраза-значения, по которому анализируются различные прообразы при решении обратной задачи. Так как обычно хэш-функция представляет собой соотношение "многие к одному", невозможно со всей деленностью сказать, что две строки совпадают, но их можно использовать, получая приемлемую оценку точности. Однонаправленная хэш-функция – это хэш-функция, которая работает только в одном направлении. Легко вычислить значение хэш-функции по прообразу, но трудно создать прообраз, значение хэш-функции которого равно заданной величине. Упоминавшиеся ранее хэш-функции, вообще говоря, не являются однонаправленными: задав конкретный байт, не представляет труда создать строку байтов, XOR которых дает заданное значение. С однонаправленной хэш-функцией такой вариант невозможен. Хэш-функция является открытой, тайны ее расчета не существует. Безопасность однонаправленной хэш-функции заключается именно в ее однонаправленности. У выхода нет видимой зависимости от входа. Изменение одного бита прообраза приводит к изменению (в среднем) половины битов значения хэш-функции, что известно также как лавинный эффект. Вычислительно невозможно найти прообраз, соответствующий заданному значению хэш-функции

Требования

Для того, чтобы хэш-функция H считалась криптографически стойкой, она должна удовлетворять трем основным требованиям, на которых основано большинство применений хэш-функций в криптографии:

  • Необратимость или стойкость к восстановлению прообраза: для заданного значения хэш-функции m должно быть вычислительно невозможно найти блок данных X, для которого H(X)=m.
  • Стойкость к коллизиям первого рода или восстановлению вторых прообразов: для заданного сообщения M должно быть вычислительно невозможно подобрать другое сообщение N, для которого H(N)=H(M).
  • Стойкость к коллизиям второго рода: должно быть вычислительно невозможно подобрать пару сообщений (M, M'), имеющих одинаковый хэш.

Данные требования не являются независимыми:

  • Обратимая функция нестойка к коллизиям первого и второго рода.
  • Функция, нестойкая к коллизиям первого рода, нестойка к коллизиям второго рода; обратное неверно.

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

Атака «дней рождения» позволяет находить коллизии для хэш-функции с длиной значений n битов в среднем за примерно 2 n/2 вычислений хэш-функции. Поэтому n – битная хэш-функция считается криптостойкой, если вычислительная сложность нахождения коллизий для неё близка к 2 n/2.

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

Принципы построения

Итеративная последовательная схема.jpg

Итеративная последовательная схема

В общем случае, в основе построения хэш-функции лежит итеративная последовательная схема (Структура Меркля-Дамгарда). Ядром алгоритма является сжимающая функция — преобразование k входных в n выходных бит, где n — разрядность хэш-функции, а k — произвольное число большее n. При этом сжимающая функция должна удовлетворять всем условиям криптостойкости.

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

При проектировании хэш-функций на основе итеративной схемы возникает проблема с размером входного потока данных. Размер входного потока данных должен быть кратен (k-n). Как правило, перед началом алгоритма данные расширяются неким, заранее известным, способом.

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

Сжимающая функция на основе симметричного блочного алгоритма

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

A, B и C могут принимать значения Mj , Hj-1 , MjHj-1 или быть константой, где Mj — j – ый блок входного потока,  — сложение по модулю 2, Hj — результат j – ой итерации.

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

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

Схемы безопасного хэширования.jpg

Основным недостатком хэш-функций, спроектированных на основе блочных алгоритмов, является низкая скорость работы. Необходимую криптостойкость можно обеспечить и за меньшее количество операций над входными данными. Существуют более быстрые алгоритмы хэширования, спроектированных самостоятельно, с нуля, исходя из требований криптостойкости (наиболее распространенные из них — MD5, SHA-1, SHA-2 и ГОСТ Р 34.11-94).

Применения

Электронная цифровая подпись

Электронная цифровая подпись (ЭЦП) - по сути шифрование сообщения алгоритмом с открытым ключом. Текст, зашифрованный секретным ключом, объединяется с исходным сообщением. Тогда проверка подписи — расшифрование открытым ключом, если получившийся текст аналогичен исходному тексту — подпись верна.

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

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

Проверка пароля

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

Примером в данном случае могут служить ОС GNU/Linux и Microsoft Windows. В них хранятся лишь хэш-значения парольных фраз из учётных записей пользователей.

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

Пусть некий клиент, с именем name, производит аутентификацию по парольной фразе, pass, на некоем сервере. На сервере хранится значение хэш-функции H(pass,R2), где R2 — псевдослучайное, заранее выбранное, число. Клиент посылает запрос (name, R1), где R1 — псевдослучайное, каждый раз новое, число. В ответ сервер посылает значение R2. Клиент вычисляет значение хэш-функции H(R1,H(pass,R2)) и посылает его на сервер. Сервер также вычисляет значение H(R1,H(pass,R2)) и сверяет его с полученным. Если значения совпадают — аутентификация верна.

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

Случайный оракул

Напомним свойство перемешивания, которое присуще функции хэширования: при любом аргументе хэширование неотличимо с вычислительной точки зрения от строки битов, равномерно распределенных в области значений функции. Если заменить последнее выражение фразой "принадлежит генеральной совокупности равномерно распределенных величин", мы получим весьма мощную гипотетическую функцию, называемую случайный оракул (randome oracle). Он обладает тремя свойствами: детерминированность, эффективность, равномерность распределения результирующих значений. Однако,все известные вычислительные модели в той или иной степени не соответствуют модели случайного оракула. Равномерность и детерминированность величин, вычисляемых случайным оракулом, означает, что энтропия его результатов выше, чем энтропия чисел, поступающих на вход. Поскольку свойства перемешивания, которым обладает хэш-функция является лишь предположением вычислительного характера, реальная хэш-функция должна обеспечивать лишь вычислительную неразличимость, то есть результаты должны иметь некое распределение вероятностей в области значений, которое невозможно определить за полиномиальное время. Итак, реальные функции хэширования лишь имитируют поведение случайного оракула, хоть и с высокой точностью.

Атака на основе парадокса дней рождений

Предположим, что функция хэширования h действительно является случайным оракулом. В атаке по методу квадратного корня (атака на основе парадокса дней раждения) предполагается, что для обнаружения коллизий с ненулевой вероятностью достаточно выполнить 2 в степени |h|/2 случайных вычислений значения функции хэширования. Для организации атаки на основе парадокса дней рождений атакующий должен сгенерировать пары "сообщение-хэшированное значение", пока не обнаружаться два сообщения m и m`, удовлетворяющие условиям m не равно m`, h(m)=h(m`). Такая пара сообщений называется коллизией(collision) функции хэширования h. Например, для функции хэшироания SHA-1 выполняется условие |h|=160, а значит его стойкость на основе парадокса дней рождения оценивается величиной 280.

Сравнительная характеристика наиболее известных функций

Существует длинный перечень криптографических хеш-функций, хотя многие из них были признаны уязвимыми и не должны быть использованы. Даже если хэш-функция никогда не была взломана, успешная атака против ослабленного варианта может подорвать доверие экспертов и привести к отказу от хэш-функции. Например, в августе 2004 года были найдены слаюости в ряде хэш-функций , которые были популярны в то время, в том числе SHA-0, RIPEMD и MD5. Это поставило под сомнение долгосрочную безопасность более поздних алгоритмов, которые являются производными от этих хеш-функций - в частности, SHA-1 ( усиленный вариант SHA-0 ), RIPEMD- 128 , и RIPEMD-160 (оба усиленные версии RIPEMD ). Ни SHA-0 , ни RIPEMD широко не используются, так как они были заменены на более усиленные версии. По состоянию на 2009, двумя наиболее часто используемыми криптографическими хэш-функциями являются MD5 и SHA-1. Тем не менее, MD5 была взломана, атака против него была также использована для взлома SSL в 2008. Функции SHA-0 и SHA-1 были разработаны в АНБ. В феврале 2005 года сообщалось, что проведена успешная атака на SHA-1, найдены коллизии за, примерно, 269 операций хэширования, а не в 280, которые ожидаются для 160-битной хэш-функции. В августе 2005 года сообщалось, об еще одном успешном нападении на SHA-1: нахождение коллизии за 263 операций. Новые приложения могут избежать этих проблем с безопасностью функции SHA-1 с помощью более продвинутых членов семьи SHA , например, SHA-2. Тем не менее, для обеспечения долгосрочной надежности приложений, использующих хэш-функций, был устроен конкурс на лучший проект - замену SHA-2. 2 октября 2012 года, Keccak был выбран в победителем в конкурсе, устроенном NIST. Версия этого алгоритма как ожидается, станет стандартным FIPS в 2014 году под названием SHA-3. Некоторые из следующих алгоритмов часто используется в приложениях криптографии.Обратите внимание, что этот список не включает кандидатов в текущем конкурсе NIST.

Алгоритм Размер выхода Размер внутреннего состояния Размер блока Длина Размер слова Количество раундов Атаки
(сложность:раунды)
Атака «дней рождения» Нахождение
второго прообраза
Нахождение прообраза
ГОСТ 34.11-45 256 256 256 256 32 256 Yes (2105) Yes (2192]) Yes (2192)
HAVAL 256/224/192/160/128 256 1,024 64 32 160/128/96 Да Нет Нет
MD2 128 384 128 - 32 864 Да (263.3]) Да (273]) Да (2sup>73</sup>])
MD4 128 128 512 64 32 48 Да (3) Да (264) Да (278.4)
MD5 128 128 512 64 32 64 Да (220.96) Да (2123.4) Да (2123.4)
PANAMA 256 8,736 256 - 32 - Да Нет Нет
RIPEMD 128 128 512 64 32 48 Да (218) Нет Нет
RIPEMD-128/256 128/256 128/256 512 64 32 64 Нет Нет Нет
RIPEMD-160 160 160 512 64 32 80 Да (251) Нет Нет
RIPEMD-320 320 320 512 64 32 80 Нет Нет Нет
SHA-0 160 160 512 64 32 80 Да (233.6) Нет Нет
SHA-1 160 160 512 64 32 80 Да (251) Нет Нет
SHA-256/224 256/224 256 512 64 32 64 Теоретически (28.5</sup>) Теоретически (2248.4) Теоретически (2248.4)
SHA-512/384 512/384 512 1,024 128 64 80 Теоретически (232.5) Теоретически (2494.6) Теоретически (2494.6)
SHA-3 (Keccak) 224/256/384/512 1600 1600-2*bits - 64 24 Нет Нет Нет
SHA-3-224 224 1600 1152 - 64 24 Нет Нет Нет
SHA-3-256 256 1600 1088 - 64 24 Нет Нет Нет
SHA-3-384 384 1600 832 - 64 24 Нет Нет Нет
SHA-3-512 512 1600 576 - 64 24 Нет Нет Нет
Tiger-192/160/128 192/160/128 192 512 64 64 24 Да (262) Да (2184.3) Да (2184.3)
WHIRLPOOL 512 512 512 256 8 10 Да (2120:4.5]) Нет Нет

Демонстрационная программа, показывающая работу алгоритма SHA-1:
Исходный код на C#: File:SHA1 src.zip
Исполняемый файл: File:SHA1.zip

Демонстрационная программа, показывающая работу алгоритма MD2:
Исходный код на ЯП Python: File:Md2 src.zip
Исполняемый файл: File:Md2.zip

Md2screenshot.jpg

Глоссарий

Литература

Перейти к списку литературы.

Составители


Комаров А.И. / Митцель А.С.


Назад к оглавлению </p>