Предназначением ключевых итерационных схем хеширования является выработка образа хешируемого сообщения (текста) для определения и доказательства его подлинности и принадлежности истинному владельцу (объекту). Ключевые хеш-функции также принято называть методами безопасного хеширования. Суть безопасного хеширования состоит в формировании сжатого образа открытой последовательности, параметризированного секретным ключом. Длина хеш-кода и длина ключа влияет на стойкость схемы хеширования к навязыванию ложных данных.
Ключевая хеш-функция представляет семейство итерационных хеш-функций Fk, параметризированных с помощью секретного ключа k
Рис. 2. Общая схема итерационной хеш-функции
Информация представляется в виде последовательности блоков Mi определенной длины Lm, если необходимо, то дополняется до размера кратного длине блока.
Совокупность блоков {Mi} последовательно обрабатывается в цикловой функции (рис. 3). Результат последней итерации поступает на выход хеш-функции в виде образа: h = H(Мi), где h є R, R – множество значений хеш-функции.
Рис. 3. Структура хеш-функции CBC-MAC ISO/IEC 6796
Хеш-функция называется стойкой по 2-му прообразу тогда и только тогда, когда вычислительно неосуществимо для фиксированного М1 найти такое М2? М1, что Н(М1) = Н(М2).
Хеш-функция называется стойкой к коллизиям тогда и только тогда, когда вычислительно неосуществимо нахождение любых двух входных сообщений (прообразов) М2? М1, имеющих одинаковое значение хеш-функции, h1 = Н(М1) = Н(М2) = h2.
Коллизии хеш-функции MD5
В 2004 году китайские исследователи Ван Сяоюнь (Wang Xiaoyun), Фен Дэнгуо (Feng Dengguo), Лай Сюэцзя (Lai Xuejia) и Юй Хунбо (Yu Hongbo) объявили об обнаруженной ими уязвимости в алгоритме, позволяющей за небольшое время (1 час на кластере en:IBM_p690) находить коллизии.
В 2005 году исследователи Ван Сяоюнь и Юй Хунбо из университета Шаньдун в Китае, опубликовали алгоритм для поиска коллизий в хеш-функции MD5, причём их метод работает для любого инициализирующего вектора, а не только для вектора, используемого по стандарту. Применение этого метода к MD4 позволяет найти коллизию меньше чем за секунду. Он также применим и к другим хеш-функциям, таким как RIPEMD и HAVAL.
В 2008 году Сотиров Александр, Марк Стивенс (Marc Stevens), Якоб Аппельбаум (Jacob Appelbaum) опубликовали на конференции 25th Chaos Communication Congress статью, в которой показали возможность генерирования поддельных цифровых сертификатов, на основе использования коллизий MD5.
Хэш-функции
Требования к хэш-функциям
Хэш-функцией называется односторонняя функция, предназначенная для получения дайджеста или "отпечатков пальцев" файла, сообщения или некоторого блока данных.
Хэш-код создается функцией Н:
h = H (M)
Где М является сообщением произвольной длины и h является хэш-кодом фиксированной длины.
Рассмотрим требования, которым должна соответствовать хэш-функция для того, чтобы она могла использоваться в качестве аутентификатора сообщения. Рассмотрим очень простой пример хэш-функции. Затем проанализируем несколько подходов к построению хэш-функции.
Хэш-функция Н, которая используется для аутентификации сообщений, должна обладать следующими свойствами:
1. Хэш-функция Н должна применяться к блоку данных любой длины.
2. Хэш-функция Н создает выход фиксированной длины.
3. Н (М) относительно легко (за полиномиальное время) вычисляется для любого значения М.
4. Для любого данного значения хэш-кода h вычислительно невозможно найти M такое, что Н (M) = h.
5. Для любого данного х вычислительно невозможно найти 
, что H (y) = H (x).
6. Вычислительно невозможно найти произвольную пару (х, y) такую, что H (y) = H (x).
Первые три свойства требуют, чтобы хэш-функция создавала хэш-код для любого сообщения.
Четвертое свойство определяет требование односторонности хэш-функции: легко создать хэш-код по данному сообщению, но невозможно восстановить сообщение по данному хэш-коду. Это свойство важно, если аутентификация с использованием хэш-функции включает секретное значение. Само секретное значение может не посылаться, тем не менее, если хэш-функция не является односторонней, противник может легко раскрыть секретное значение следующим образом. При перехвате передачи атакующий получает сообщение М и хэш-код С = Н (SAB || M). Если атакующий может инвертировать хэш-функцию, то, следовательно, он может получить SAB || M = H-1 (C). Так как атакующий теперь знает и М и SAB || M, получить SAB совсем просто.
Пятое свойство гарантирует, что невозможно найти другое сообщение, чье значение хэш-функции совпадало бы со значением хэш-функции данного сообщения. Это предотвращает подделку аутентификатора при использовании зашифрованного хэш-кода. В данном случае противник может читать сообщение и, следовательно, создать его хэш-код. Но так как противник не владеет секретным ключом, он не имеет возможности изменить сообщение так, чтобы получатель этого не обнаружил. Если данное свойство не выполняется, атакующий имеет возможность выполнить следующую последовательность действий: перехватить сообщение и его зашифрованный хэш-код, вычислить хэш-код сообщения, создать альтернативное сообщение с тем же самым хэш-кодом, заменить исходное сообщение на поддельное. Поскольку хэш-коды этих сообщений совпадают, получатель не обнаружит подмены. Хэш-функция, которая удовлетворяет первым пяти свойствам, называется простой или слабой хэш-функцией. Если кроме того выполняется шестое свойство, то такая функция называется сильной хэш-функцией. Шестое свойство защищает против класса атак, известных как атака " день рождения ".
