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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• VSH - Very Smooth Hash function - доказуемо безопасная устойчивая к коллизиям функция, опирающаяся на сложность нахождения нетривиальных квадратных корней по модулю составного числа n (что является настолько же сложным, насколько разложение n на множители).
• MuHASH
• - основанная на идее эллиптических кривых, задаче о сумме подмножеств и суммировании полиномов хеш-функция. Доказательство безопасности опиралось на предположение о NP-полноте лежащей в основе математической задачи, однако была найдена уязвимость для обобщённой атаки "дней рождения" Вагнера, связанной с поиском второго прообраза.
• FSB - Fast Syndrome-Based hash function - может быть показано, что взломать FSB по меньшей мере настолько же трудно, насколько решить NP-полную задачу, известную как регулярное синдромное декодирование.
• SWIFFT - SWIFFT основан на БПФ и доказуемо безопасен при довольно слабом предположении о сложности нахождения коротких векторов в циклической/идеальной решетке в худшем случае.
• - функция, в которой нахождение коллизий так же трудоёмко, как и при нахождении дискретного логарифма в конечной группе .
• - семейство хеш-функций, основанное на задаче о рюкзаке .

Ссылки