Криптографические хэш-функции

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

▪ Необратимость: для заданного значения хэш-функции m должно быть вычислительно неосуществимо найти блок данных X, для которого H(X) = m.

▪ Стойкость к коллизиям первого рода: для заданного сообщения M должно быть вычислительно неосуществимо подобрать другое сообщение N, для которого H(N) = H(M).

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

Данные требования не являются независимыми:

▪ Обратимая функция нестойка к коллизиям первого и второго рода.

▪ Функция, нестойкая к коллизиям первого рода, нестойка к коллизиям второго рода; обратное неверно.

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

Атака «дней рождения» позволяет находить коллизии для хеш-функции с длиной значений n битов в среднем за примерно 2n / 2 вычислений хэш-функции. Поэтому n-битная хеш-функция считается криптостойкой, если вычислительная сложность нахождения коллизий для неё близка к 2n / 2.

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

Хэширование (иногда хеширование, англ. hashing) — преобразование входного массива данных произвольной длины в выходную битовую строку фиксированной длины. Такие преобразования также называются хэш-функциями или функциями свёртки, а их результаты называют хэшем, хэш-кодом или дайджестом сообщения (англ. message digest).

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

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