Стандарты Хеш-функций. Основные определения и требования безопасности к функциям хеширования, страница 6

Функция сжатия SHA-1.

Пусть  есть блок сообщения в 512 бит, и  – 32 битные слова. SHA-1 использует процедуру расширения, которая определена как

.

Используются следующие константы

,

,

,

,

и булевые функции

,

,

.

Предположим, что начальные значения  заданы. Функция сжатия выполняет вычисления за  шагов (со сложением по ):

,

,

,

,

.

Наконец выход функции сжатия определяется как

.

Анализ безопасности алгоритма SHA-1.

Требования коллизионной стойкости к алгоритму SHA-1 являются следующими. При длине хеш кода 160 бит порядок образования коллизии должен составлять  попыток, а нахождение второго прообраза - порядок . На данный момент не известны атаки, которые опровергали бы эти предположения.

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

Слайд атака SHA-1. Сложность слайд атаки на алгоритм SHA-1 составляет , как установил Saarinen [17]. Хотя трудно представить каким образом эта атака может быть практически реализована. Анализ функции сжатия показывает неожиданную особенность. Рассмотрим два сообщения:  и . Основное наблюдение состоит в том, что процедуру для расширения сообщения можно двигать. Мы просто выбираем  для  и . После расширения сообщения справедливо следующее:  для . Второе наблюдение состоит в том, что для 20 шагов в каждом цикле функции сжатия, булевая функция  и аддитивные константы  является неизменными. Следовательно, любые два последовательных шага (шаг  и шаг ) функция сжатия является подобной, если бы не три преобразования между различными циклами (это происходит когда ).

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

, , , .

Цель атаки состоит в том, чтобы найти сообщения и начальные значения для которых то же самое отношение (между цепочечными переменными) сохранится в конце функции сжатия. Такая пара из сообщения и связанного с ним начального значения называется слайд парой. Метод обнаружения слайд пары технически непростой, но общая стратегия состоит в том, чтобы выбрать подходящие значения для цепочечных переменных на шагах  и , и выполнить атаку "встреча посредине". Эта процедура повторяется до преобразования на шаге  c вероятностью успеха . Затраты времени и  сложность атаки имеет порядок .

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

Для SHA-1 существует дифференциальная характеристика с 5 шагами по любым 5 шагам в функции сжатия с вероятностью 1. Handschuh и Naccache [18] показали, что при более чем 80 шагах в функции сжатия лучшая дифференциальная характеристика имеет вероятность около . Подчеркнем, что эта оценка является "благоприятной" для криптоанализа, поскольку должно быть не возможно связать все установленные характеристики, так чтобы достичь этих смещений. Bogaert и Rijmen [19] нашли оптимальные дифференциальные характеристики удовлетворяющие требованию, чтобы вес Хэмминга каждого входного слова с 32 битами был ограничен с верху 2. Было обнаружено, что имеются две 10 шаговые характеристики для  с вероятностью  (это в 2 раза лучше чем в [18]), 10 шаговая характеристика для  в лучшем случае с вероятностью , и 20 шаговая характеристика для  и  с вероятностями  и , соответственно (эти значения представлены в [237]). Ким и др. [20] нашли дифференциальную 28 шаговую характеристику с вероятностью , и дифференциальную 30 шаговую характеристику с вероятностью . Это показывает, что, когда число шагов увеличивается, вероятность дифференциальных характеристик уменьшается быстро (так как вес Хэмминга в различных словах увеличивается). Граница безопасности SHA-1 против дифференциального анализа кажется очень большой.