Требования к качественной хеш-функции

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

Хеш-функцией называется преобразование h, превращающее информационную последовательность (строку) М произвольной длины в информационную последовательность (строку) фиксированной длины h(M). На рисунке 2 показана упрощенная схема хеш-функции.

Рис. 2. Хеш-функция: а) - наложение ПСП на входную информационную последовательность, б) - упрощенный принцип действия хеш-функции

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

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

К функции h(x) предъявляются следующие основные требования:

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

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

Для качественной хеш-функции следующие три задачи являются вычислительно неразрешимыми.

· Нахождение прообраза. Задача нахождения последовательности М по заданному хеш-образу h(M), т.е. хеш-функция должна быть стойкой в смысле обращения. Или другими словами хеш-функция должна быть односторонней, т.е. функцией, по значению которой вычислительно трудно найти ее аргумент.

· Нахождение коллизии. Задача нахождения последовательностей М и М’ причем М' ≠ М таких, что h(M') = h(M), т.е. хеш-функция должна быть стойкой в смысле нахождения коллизий.

· Нахождение второго прообраза. 3адача нахождения для заданной последовательности М другой последовательности М’, М' ≠ М, такой, что h(M') = h(M) (рис. 3).

Рис. 3. Атаки на хеш-функцию: а) - нахождение прообраза, б) - нахождение второго прообраза

Если n - разрядность хеш-образа, сложность первой и третьей атаки (рис. 3) на идеальную хеш-функцию пропорциональна 2ⁿ. Сложность задачи нахождения коллизии пропорциональна 2^n/2.

Дата добавления: 2014-01-07