Криптографические хеш-функции — это выделенный класс хеш-функций, который имеет определённые свойства, делающие его пригодным для использования в криптографии.
Принципы построения
Итеративная последовательная схема
В общем случае в основе построения хеш-функции лежит итеративная последовательная схема. Ядром алгоритма является сжимающая функция — преобразование входных в выходных бит, где n — разрядность хеш-функции, а — произвольное число, большее . При этом сжимающая функция должна удовлетворять всем условиям криптостойкости.
Входной поток разбивается на блоки по бит. Алгоритм использует вре́менную переменную размером в бит, в качестве начального значения которой берётся некое общеизвестное число. Каждый следующий блок данных объединяется с выходным значением сжимающей функции на предыдущей итерации. Значением хеш-функции являются выходные бит последней итерации. Каждый бит выходного значения хеш-функции зависит от всего входного потока данных и начального значения. Таким образом достигается лавинный эффект.
При проектировании хеш-функций на основе итеративной схемы возникает проблема с размером входного потока данных. Размер входного потока данных должен быть кратен . Как правило, перед началом алгоритма данные расширяются неким, заранее известным, способом.
Помимо однопроходных алгоритмов, существуют многопроходные алгоритмы, в которых ещё больше усиливается лавинный эффект. В этом случае данные сначала повторяются, а потом расширяются до необходимых размеров.
Сжимающая функция на основе симметричного блочного алгоритма В качестве сжимающей функции можно использовать симметричный блочный алгоритм шифрования. Для обеспечения большей безопасности можно использовать в качестве ключа блок данных, предназначенный к хешированию на данной итерации, а результат предыдущей сжимающей функции — в качестве входа. Тогда результатом последней итерации будет выход алгоритма. В таком случае безопасность хеш-функции базируется на безопасности используемого алгоритма.
Обычно при построении хеш-функции используют более сложную систему. Обобщённая схема симметричного блочного алгоритма шифрования изображена на рис. 2.
Таким образом, мы получаем 64 варианта построения сжимающей функции. Большинство из них являются либо тривиальными, либо небезопасными. Ниже изображены четыре наиболее безопасные схемы при всех видах атак.
Основным недостатком хеш-функций, спроектированных на основе блочных алгоритмов, является низкая скорость работы. Необходимую криптостойкость можно обеспечить и за меньшее количество операций над входными данными. Существуют более быстрые алгоритмы хеширования, спроектированных самостоятельно, с нуля, исходя из требований криптостойкости. Наиболее распространённые из них — MD5, SHA-1, SHA-2.
Требования К криптографическим хеш-функциям предъявляются следующие требования:
1. Сопротивление поиску прообраза: при наличии хеша должно быть трудно найти какое-либо сообщение , такое что , Это свойство связано с понятием односторонней функции. Функции, у которых отсутствует это свойство, уязвимы для атак нахождения первого прообраза.
2. Сопротивление поиску второго прообраза: при наличии сообщения , должно быть трудно найти другое сообщение (не равное ) такое, что . Это свойство иногда называют слабым сопротивлением поиску коллизий. Функции, у которых отсутствует это свойство, уязвимы для атак поиска второго прообраза.
3. Стойкость к коллизиям
Коллизией для хеш-функции называется такая пара значений и ′, ′, для которой . Так как количество возможных открытых текстов больше числа возможных значений свёртки, то для некоторой свёртки найдётся много прообразов, а следовательно, коллизии для хеш-функций обязательно существуют. Например, пусть длина хеш-прообраза 6 битов, длина свёртки 4 бита. Тогда число различных свёрток — , а число хеш-прообразов — , то есть в 4 раза больше, значит хотя бы одна свёртка из всех соответствует 4 прообразам.
Стойкость хеш-функции к коллизиям означает, что нет эффективного полиномиального алгоритма, позволяющего находить коллизии.
Данные свойства не являются независимыми: Обратимая функция неустойчива к восстановлению второго прообраза и коллизиям. Функция, нестойкая к восстановлению второго прообраза, нестойка к коллизиям; обратное неверно. Функция устойчивая к коллизиям, устойчива к нахождению второго прообраза. Устойчивая к коллизиям хеш-функция не обязательно является односторонней. Для криптографии важно, чтобы значения хеш-функции сильно изменялись при малейшем изменении аргумента (лавинный эффект). Значение хеша не должно давать утечки информации даже об отдельных битах аргумента.
При разработке современного российского стандарта ГОСТ Р 34.11-2012 (Стрибог) к криптографическим хеш-функциям были сформулированы следующие требования: Стойкость к вычислению прообраза: если известно значение функции, тогда должно быть сложно найти такое сообщение, хеш-функция от которого равна известному; Стойкость к вычислению второго прообраза: пусть есть одно значение, и известен хеш-код этого значения. Тогда злоумышленнику должно быть сложно найти ещё одно такое значение, чтобы его хеш-функция совпадала с хеш-функцией первого значения; Стойкость к поиску коллизий: должно быть сложно найти два таких сообщения, которые не равны, но у них равны хеш-коды; Стойкость к удлинению прообраза: если злоумышленник не знает сообщение, но знает его длину и хеш-код от него, то ему должно быть сложно подобрать такое сообщение, которое, будучи дописанным к оригинальному, даст какую-нибудь известную хеш-функцию. Другими словами, не должно быть возможно злоумышленнику что-то менять путём дополнения в сообщении, получая известны выход. Это можно сформулировать по-другому: хеш-функция не должна быть хорошо «дополняема».
4. Псевдослучайность: должно быть трудно отличить генератор псевдослучайных чисел на основе хеш-функции от генератора случайных чисел, например, он проходит обычные тесты на случайность.
Доказуемо безопасные хеш-функции Безопасность хеш-функции может обеспечиваться сложностью некоторой математической задачи при наличии доказательства, что атаки, направленные на нарушение требований к ней, настолько же сложны, насколько и решение этой задачи.
Криптографическая хеш-функция является доказуемо защищённой от коллизий, если задача нахождения коллизий может быть средуцирована за полиномиальное время от задачи , которая считается неразрешимой за полиномиальное время. Иначе говоря, если алгоритм позволял бы за полиномиальное время решить задачу нахождения коллизий при существовании редуцирующего алгоритма , работающего также за полиномиальное время, то последний позволил бы алгоритму решить задачу за полиномиальное время, что противоречит её сложности, а значит задача нахождения коллизий не легче задачи .
Аналогично определяется доказуемая защищённость от поиска первого и второго прообраза.
Стойкость к поиску второго прообраза вытекает из доказанной стойкости к коллизиям, поэтому на практике иногда теоретически доказывается только стойкость к нахождению первого прообраза и стойкость к коллизиям.
Некоторые задачи, полагающиеся неразрешимыми за полиномиальное время, которые могут быть использованы для построения таких функций: Дискретное логарифмирование Нахождение квадратичного вычета Факторизация целых чисел Задача о сумме подмножеств
Недостатки доказательного подхода При наличии теоретических гарантий сложности, у доказательного подхода имеются и существенные недостатки: Текущие доказуемо безопасные алгоритмы хеширования слишком вычислительно сложны для того, чтобы использоваться на практике. По сравнению с обычными хеш функциями они достаточно медленные. Создание доказуемо безопасных хеш функций значительно более трудоёмко, чем классические подходы. Само доказательство безопасности часто основывается на задаче, имеющей требуемую сложность в среднем или в худшем случае. Сложность в худшем случае чаще всего описывает патологические ситуации, а не типичные для этой задачи. Даже редукция к задаче со сложностью в среднем обеспечивает ограниченную защищённость, так как может быть найден алгоритм, который легко решает проблему для определённого подмножества данных задачи. Так, например, было показано, что для двух из трёх предложенных в оригинальной статье для функции Fast Syndrome-Based hash параметров существуют более оптимальные атаки, чем предложенные создателями для доказательства безопасности.
SWIFFT является примером хеш функции, которая несколько обходит описанную проблему безопасности. Может быть показано, что для любого алгоритма, который взламывает SWIFFT с вероятностью за время найдётся алгоритм, который решает определённую математическую задачу в худшем случае за время в зависимости от и .
Примеры доказуемо безопасных хеш-функции VSH — Very Smooth Hash function — доказуемо безопасная устойчивая к коллизиям функция, опирающаяся на сложность нахождения нетривиальных квадратных корней по модулю составного числа n (что является настолько же сложным, насколько разложение n на множители). MuHASH ECOH - Elliptic curve only hash — основанная на идее эллиптических кривых, задаче о сумме подмножеств и суммировании полиномов хеш функция. Доказательство безопасности опиралось на предположение о NP-полноте лежащей в основе математической задачи, однако была найдена уязвимость для обобщённой атаки «дней рождения» Вагнера, связанной с поиском второго прообраза. FSB — Fast Syndrome-Based hash function — может быть показано, что взломать FSB по меньшей мере настолько же трудно, насколько решить NP-полную задачу, известную как регулярное синдромное декодирование. SWIFFT — SWIFFT основан на БПФ и доказуемо безопасен при довольно слабом предположении о сложности нахождения коротких векторов в циклической/идеальной решётке в худшем случае. Chaum, van Heijst, Pfitzmann hash function — функция, в которой нахождение коллизий так же трудоёмко, как и при нахождении дискретного логарифма в конечной группе . Knapsack-based hash functions — семейство хеш-функций, основанное на задаче о рюкзаке. Существует общий подход к построению доказуемо безопасных алгоритмов хеширования на основе любого подходящего . Более быстрая версия VSH (называющаяся VSH*) может быть получена таким способом.
Идеальная криптографическая хеш-функция Идеальной криптографической хеш-функцияей является такая криптографическая хеш-функция, к которой можно отнести пять основных свойств: Детерминированность. При одинаковых входных данных результат выполнения хеш-функции будет одинаковым (одно и то же сообщение всегда приводит к одному и тому же хешу); Высокая скорость вычисления значения хеш-функции для любого заданного сообщения; Невозможность сгенерировать сообщение из его хеш-значения, за исключением попыток создания всех возможных сообщений; Наличие лавинного эффекта. Небольшое изменение в сообщениях должно изменить хеш-значения, так широко, что новые хеш-значения не совпадают со старыми хеш-значениями; Невозможность найти два разных сообщения с одинаковыми хеш-значениями. Таким образом, идеальная криптографическая хеш-функция, у которой длина n (то есть на выходе n бит), для вычисления прообраза должна требовать как минимум операций.
Злоумышленник будет искать прообраз для идеальной хеш-функции следующим образом: у него есть число h, и ему надо найти такое m, что H(m) = h. Если это идеальная хеш-функция, то злоумышленнику остаётся лишь перебирать все возможные M и проверять, чему равна хеш-функция от этого сообщения. Результат вычисления, если m перебирается полностью, есть фактически случайное число. Если число h лежит в диапазоне от 0 до , то тогда в среднем на поиски нужного h злоумышленник будет тратить итераций. Таким образом, вычисление прообраза займёт в два раза меньше итераций, чем в идеальном случае.
Вычисление второго прообраза останется . В поиске коллизий оценка даст , причём это не совсем точный результат. Данная оценка идёт из оценки так называемого «Парадокса дней рождения».