Структура ключевых итерационных схем хеширования.

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

Ключевая хеш-функция представляет семейство итерационных хеш-функций 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 совсем просто.

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

Статьи к прочтению:

Информатика. Структуры данных: Разрешение коллизий хеширования. Центр онлайн-обучения «Фоксфорд»

Похожие статьи: