Хеш-функция
Хеш-фу́нкция, алгоритм преобразования произвольной строки данных в значение фиксированной длины. Результат работы алгоритма называется хешем (хеш-кодом, хеш-суммой, дайджестом, сводкой сообщения). Смысл вычисления хеш-функции заключается в формировании цифрового идентификатора фиксированного размера для произвольного набора исходных данных (см. Хеширование).
Примером хеш-функции может служить алгоритм формирования штрих-кода или QR-кода, когда по наименованию товара или по другим произвольным параметрам формируется фиксированная числовая последовательность, однозначно идентифицирующая этот товар.
Хеш-функции широко применяются в области защиты информации, при построении баз данных (см. Хеш-таблица) и др.
В каждой области применения к хеш-функции предъявляются требования, специфичные для решаемых задач, например требования к длине хеш-кода, устойчивости к коллизиям, вычислительной сложности и др. Хеш-функция, как правило, содержит в себе множественные преобразования исходных данных для соблюдения этих требований.
Общие требования к хеш-функции:
Хеш-функция должна быть детерминированной. При преобразовании одного и того же исходного сообщения должен получаться одинаковый хеш-код.
Хеш-функция должна быстро вычисляться для любого объёма исходного сообщения.
Устойчивость к коллизиям. Зачастую длина исходного сообщения превышает длину хеш-кода. В этом случае область определения хеш-функции (общее число возможных исходных сообщений) превышает область значений (число возможных хеш-кодов). Следовательно, на один и тот же хеш-код может отображаться два и более различных исходных сообщения. Такая ситуация называется коллизией.
В области защиты информации используются криптографические хеш-функции, широко применяемые в криптовалютных протоколах, при создании и проверке электронной подписи, для идентификации файлов, при формировании информации о глобальном состоянии сети в блокчейне, при работе с пользовательскими паролями в информационных системах и др.
К криптографическим хеш-функциям предъявляются дополнительные требования:
Вычислительная необратимость (однонаправленность, односторонность). Хеш-функция должна быть такой, чтобы из хеш-кода нельзя было восстановить ни само сообщение, ни его отдельные элементы. Это свойство предусматривает возможность восстановления исходной информации только при полном переборе всех возможных значений из области определения хеш-функции.
Лавинный эффект. Незначительное изменение исходных данных должно приводить к значительному изменению хеш-кода. Это требование позволяет усложнить криптоанализ хешированных данных. Например, при невыполнении этого требования, при изменении в пароле пользователя одного символа, хеш-код этого пароля изменится незначительно, что повысит вероятность раскрытия пароля.
Высокая устойчивость к коллизиям. В отличие от других областей применения, в криптографических хеш-функциях это требование является крайне значимым и его нарушение приводит к возникновению уязвимостей. Как правило, именно факт нахождения коллизий является признаком устаревания хеш-функции и приводит к необходимости её замены. Например, широко используемая раньше для хранения паролей и проверки целостности данных хеш-функция MD5 на сегодняшний день считается крайне небезопасной ввиду наличия большого числа коллизий.
Необходимость совершенствования криптографических хеш-функций обусловлена ростом возможностей атакующих, связанным, в свою очередь, с прогрессом в области вычислительной техники. Основные направления развития криптографических хеш-функций фокусируются ныне на повышении сложности операций хеширования и увеличении длины хеш-кода.
Наиболее эффективные криптографические хеш-функции описываются в виде государственных и международных стандартов. Примерами «хороших», популярных хеш-функций, обладающих высокой устойчивостью к коллизиям, могут служить хеш-функции ГОСТ 34.11-2018, SHA-256 и SHA-3.