В криптографии криптографические хеш-функции можно разделить на две основные категории. В первую категорию входят те функции, конструкции которых основаны на математических задачах, и безопасность которых, таким образом, следует из строгих математических доказательств, теории сложности и формальной редукции . Эти функции называются доказуемо безопасными криптографическими хеш-функциями . Построить их очень сложно, и было приведено мало примеров. Их практическое использование ограничено.
Во второй категории находятся функции, которые основаны не на математических задачах, а на ad-hoc конструкциях, в которых биты сообщения смешиваются для получения хеша. Затем считается, что их трудно взломать, но никаких формальных доказательств не приводится. Почти все широко используемые хеш-функции находятся в этой категории. Некоторые из этих функций уже взломаны и больше не используются. См. Сводка по безопасности хеш-функций .
Как правило, базовую безопасность криптографических хеш-функций можно рассматривать с разных точек зрения: устойчивость к прообразу, устойчивость ко второму прообразу, устойчивость к коллизиям и псевдослучайность.
Основной вопрос заключается в значении слова hard . Существует два подхода к ответу на этот вопрос. Первый — интуитивно-практический подход: « hard означает, что он почти наверняка находится вне досягаемости любого злоумышленника, которому необходимо помешать взломать систему до тех пор, пока безопасность системы считается важной». Второй подход — теоретический и основан на теории вычислительной сложности : если задача A является hard, то существует формальное снижение безопасности из задачи, которая широко считается неразрешимой за полиномиальное время , такой как целочисленная факторизация или задача дискретного логарифма .
Однако отсутствие алгоритма полиномиального времени не гарантирует автоматически, что система безопасна. Сложность проблемы также зависит от ее размера. Например, криптография с открытым ключом RSA (которая опирается на сложность факторизации целых чисел ) считается безопасной только с ключами длиной не менее 2048 бит, тогда как ключи для криптосистемы Эль-Гамаля (которая опирается на сложность задачи дискретного логарифма ) обычно находятся в диапазоне 256–512 бит.
Если набор входных данных для хеша относительно невелик или упорядочен по правдоподобию каким-либо образом, то поиск методом перебора может быть практичным, независимо от теоретической безопасности. Вероятность восстановления прообраза зависит от размера входного набора и скорости или стоимости вычисления хеш-функции. Распространенным примером является использование хэшей для хранения данных проверки паролей . Вместо того чтобы хранить открытый текст паролей пользователей, система контроля доступа обычно хранит хэш пароля. Когда человек запрашивает доступ, отправляемый им пароль хэшируется и сравнивается с сохраненным значением. Если сохраненные данные проверки украдены, то у вора будут только значения хэша, а не пароли. Однако большинство пользователей выбирают пароли предсказуемыми способами, и пароли часто достаточно короткие, чтобы можно было проверить все возможные комбинации, если используются быстрые хэши. [1] Для замедления поиска были созданы специальные хэши, называемые функциями вывода ключей . См. Взлом паролей .
Большинство хэш-функций построены на основе ad-hoc, где биты сообщения аккуратно перемешиваются для создания хеша. Различные побитовые операции (например, вращения), модульные сложения и функции сжатия используются в итеративном режиме для обеспечения высокой сложности и псевдослучайности вывода. Таким образом, безопасность очень трудно доказать, и доказательство обычно не делается. Всего несколько лет назад [ когда? ] было показано , что одна из самых популярных хэш-функций, SHA-1 , менее безопасна, чем предполагала ее длина: коллизии можно было найти всего за 2 51 [2] тестов, а не за число 2 80 методом грубой силы .
Другими словами, большинство используемых в настоящее время хэш-функций не являются доказуемо устойчивыми к коллизиям. Эти хэши не основаны на чисто математических функциях. Такой подход обычно приводит к более эффективным хэш-функциям, но с риском того, что слабость такой функции в конечном итоге будет использована для поиска коллизий. Одним из известных случаев является MD5 .
В этом подходе безопасность хэш-функции основана на некоторой сложной математической задаче, и доказано, что нахождение коллизий хэш-функции так же сложно, как и взлом базовой проблемы. Это дает несколько более сильное представление о безопасности, чем простое полагание на сложное смешивание битов, как в классическом подходе.
Криптографическая хэш-функция имеет доказуемую безопасность от атак коллизий , если поиск коллизий доказуемо сводится к полиномиальному времени из задачи P, которая, как предполагается, неразрешима за полиномиальное время. Тогда функция называется доказуемо безопасной или просто доказуемой.
Это означает, что если бы поиск коллизий был возможен за полиномиальное время с помощью алгоритма A , то можно было бы найти и использовать полиномиальный алгоритм R (алгоритм редукции), который использовал бы алгоритм A для решения задачи P , которая , как широко предполагается, неразрешима за полиномиальное время. Это противоречие. Это означает, что поиск коллизий не может быть проще, чем решение P.
Однако это лишь указывает на то, что в некоторых случаях поиск столкновений затруднен , поскольку не все примеры вычислительно сложных задач обычно являются сложными. Действительно, очень большие примеры NP-сложных задач решаются регулярно, в то время как только самые сложные практически не поддаются решению.
Примеры задач, которые, как предполагается, не могут быть решены за полиномиальное время, включают:
SWIFFT — пример хэш-функции, которая обходит эти проблемы безопасности. Можно показать, что для любого алгоритма, который может взломать SWIFFT с вероятностью p в течение предполагаемого времени t , можно найти алгоритм, который решает наихудший сценарий определенной сложной математической задачи в течение времени t ′ в зависимости от t и p . [ требуется цитата ]
Пусть hash( m ) = x m mod n , где n — сложно разлагаемое составное число, а x — некоторое заранее заданное базовое значение. Коллизия x m 1 ≡ x m 2 (mod n ) выявляет кратное m 1 − m 2 мультипликативного порядка x по модулю n . Эту информацию можно использовать для разложения n за полиномиальное время, предполагая определенные свойства x .
Однако алгоритм совершенно неэффективен, поскольку требует в среднем 1,5 умножения по модулю n на бит сообщения.
{{citation}}: Отсутствует или пусто |title=( помощь )