Безопасность криптографических хеш-функций

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

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

Типы устойчивости хеш-функций

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

• Сопротивление поиску первого прообраза: при наличии хеша $h$ должно быть трудно найти какое-либо сообщение $m$, такое что $h=hash(m)$, Это свойство связано с понятием односторонней функции. Функции, у которых отсутствует это свойство, уязвимы для атак нахождения первого прообраза.
• Сопротивление поиску второго прообраза: при наличии сообщения $m_{1}$, должно быть трудно найти другое сообщение $m_{2}$ (не равное $m_{1}$) такое, что $hash(m_{1})=hash(m_{2})$. Это свойство иногда называют слабым сопротивлением поиску коллизий. Функции, у которых отсутствует это свойство, уязвимы для атак поиска второго прообраза.
• Сопротивление поиску коллизий: должно быть трудно найти два разных сообщения $m_{1}$ и $m_{2}$, таких что $hash(m_{1})=hash(m_{2})$. Такая пара называется (криптографической) хеш-коллизией. Это свойство иногда называют сильным сопротивлением поиску коллизий. Требуется хеш-значение, по крайней мере, вдвое длиннее, чем требуемое для сопротивления поиску первого прообраза, в противном случае столкновения могут быть обнаружены атакой "дней рождения".
• Псевдослучайность: должно быть трудно отличить генератор псевдослучайных чисел на основе хеш-функции от генератора случайных чисел, например, он проходит обычные тесты на случайность.

Значение понятия "трудно"

Основной вопрос - значение понятия "трудно". Есть два подхода к ответу на этот вопрос. Во-первых, это интуитивно-практический подход: «трудно означает, почти наверняка недосягаемо для любого противника, которому должно быть позволено взломать систему до тех пор, пока безопасность системы считается важной».

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

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

Доказуемо безопасные хеш-функции

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

Криптографическая хеш-функция является доказуемо защищённой от коллизий, если задача нахождения коллизий может быть средуцирована за полиномиальное время от задачи $P$, которая считается неразрешимой за полиномиальное время. Иначе говоря, если алгоритм $A$ позволял бы за полиномиальное время решить задачу нахождения коллизий при существовании редуцирующего алгоритма $R$, работающего также за полиномиальное время, то последний позволил бы алгоритму $A$ решить задачу $P$ за полиномиальное время, что противоречит её сложности, а значит задача нахождения коллизий не легче задачи $P$.

Аналогично определяется доказуемая защищённость от поиска первого и второго прообраза.

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

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

• Дискретное логарифмирование
• Нахождение квадратичного вычета
• Факторизация целых чисел
• Задача о сумме подмножеств

Недостатки доказательного подхода

При наличии теоретических гарантий сложности, у доказательного подхода имеются и существенные недостатки:

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

SWIFFT является примером хеш-функции, которая несколько обходит описанную проблему безопасности. Может быть показано, что для любого алгоритма, который взламывает SWIFFT с вероятностью $P$ за время $T$ найдётся алгоритм, который решает определённую математическую задачу в худшем случае за время $T'$ в зависимости от $P$ и $T$.

Примеры доказуемо безопасных хеш-функции

• 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 - семейство хеш-функций, основанное на задаче о рюкзаке.