Основы криптографии Учебное пособие - Алферов А.П.
ISBN 5-85438-025-0
Скачать (прямая ссылка):
В заключение отметим, что существуют ключевые хэш-функции, не использующие какую-либо основу типа блочного шифрования или вычисления бесключевой хэш-функции, а разработанные независимо с учетом эффективной реализации на современных ЭВМ. Примером служит ключевая хэш-функция, используемая в алгоритме MAA (.Message Authenticator Algorithm), утвержденном стандартом ISO 8731-2.
§ 13.3. Бесключевые функции хэширования
Обычно требуется, чтобы бесключевые хэш-функции обладали следующими свойствами:
1) однонаправленность,
2) устойчивость к коллизиям,
3) устойчивость к нахождению второго прообраза, означающими соответственно высокую сложность нахождения сообщения с заданным значением свертки; пары сообщений с одинаковыми значениями свертки; второго сообщения с тем же значением свертки для заданного сообщения с известным значением свертки.
Например, хэш-функция CRC-32, представляющая собой контрольную сумму, является линейным отображением и поэтому не удовлетворяет ни одному из этих трех свойств.
Использование в качестве бесключевой хэш-функции рассмотренной выше функции (2), построенной на основе алгоритма блочного шифрования в режиме выработки имитов-ставки, также нецелесообразно, так как обратимость блочного шифрования позволяет подбирать входное сообщение для любого значения свертки при фиксированном и общеизвестном ключе.
Для построения примера хэш-функции, удовлетворяющей свойству 1), рассмотрим функцию, заданную формулой
354
Хэш-функции
gk(x) = Ek(x)®x 9 где Ek — алгоритм блочного шифрования. Такая функция является однонаправленной по обоим аргументам. Поэтому на ее основе можно построить хэш-функцию по правилу (1), определив одношаговую сжимающую функцию одной из следующих формул:
f(x,H) = Ен(х)@х
или
/(X9H) = Ex(H)QH.
Первая из этих функций лежит в основе российского стандарта хэш-функции, а вторая — в основе американского стандарта SHA.
Справедливо следующее
Утверждение 1. Если функция хэширования h построена на основе одношаговой сжимающей функции/ по правшу (1), то из устойчивости к коллизиям функции / следует устойчивость к коллизиям функции h.
Действительно, если у функции h имеется коллизия, то на некотором шаге і должна существовать коллизия у функции / (при определении коллизий функцию /(х]9х2) следует рассматривать как функцию от одного переменного, полученного конкатенацией переменных X19X2 в один входной вектор).
Укажем взаимозависимость между свойствами 1) и 2).
Утверждение 2. Если хэш-функция устойчива к коллизиям, то она устойчива к нахождению второго прообраза.
Действительно, если для заданной пары сообщение-свертка можно подобрать второй прообраз, то полученная пара сообщений будет составлять коллизию.
Утверждение 3. Устойчивая к коллизиям хэш-функция не обязана быть однонаправленной.
В качестве примера несжимающей функции приведем функцию h(x) = х, которая, очевидно, является устойчивой
355
І лава U
к коллизиям и к нахождению второго прообраза, но не является однонаправленной.
В качестве примера сжимающей хэш-функции рассмотрим функцию Л, определенную условиями
h(x) = (I, X) , если битовая длина х равна я, h(x) = (0,g(x)), если битовая длина х больше п,
где g(x) — сжимающая я-битовая функция, устойчивая к коллизиям. Функция h также является устойчивой к коллизиям и к нахождению второго прообраза, но, очевидно, не является однонаправленной.
Утверждение 4. Пусть h : X —» F — хэш-функция и IXI > 21Y |. Тогда если существует эффективный алгоритм обращения функции h, то существует вероятностный алгоритм нахождения коллизии функции h с вероятностью успеха,, большей 1/2.
Доказательство. Будем случайно и равновероятно выбирать сообщение jc, вычислять у = h(x), x' = h~x(y) и сравнивать х с JCf. Покажем, что данный алгоритм имеет вероятность успеха р > 1 / 2 . Под успехом мы понимаем построение х', отличного от X.
Пусть X = Xx U... U Xm — разбиение X на классы, состоящие из сообщений с одинаковыми значениями хэш-функции. Ясно, что т < \Y\. Легко заметить, что выполняются следующие соотношения:
!*! W 2 •
> - ' >
Утверждение доказано.
356
Хэш-функции
Заметим, что трудоемкость подбора прообраза для однонаправленной функции или трудоемкость поиска второго прообраза оцениваются величиной о(2W). В то же время трудоемкость поиска коллизии оценивается величиной o{ln/2), так как в данной ситуации применима атака, основанная на парадоксе “дней рождений”.
Рассмотрим конкретные примеры хэш-функций, построенных на основе некоторых алгоритмов преобразования блоков.
Пусть Ek — алгоритм блочного шифрования, п — размер блока, / — размер ключа и G — некоторое отображение, ставящее в соответствие вектору длины п вектор длины /. Рассмотрим следующие одношаговые сжимающие функции, построенные на основе алгоритма ?*:
а) /(*> Н) = Ex (H) ® H (Дэвис — Мейер);
б) /(*,Н) = Е0(Н)(х)® х (Матиас — Мейер — Осеас);
в) f(x,Н) = Ев{Н)(х) ® х © H (Миагучи — Принель).
Значением любой из хэш-функций, построенных по правилу (1) из приведенных одношаговых сжимающих функций, является вектор длины п, равной размеру блока. В случае если эта величина оказывается недостаточной, ее можно увеличить, заменив одношаговую функцию/на функцию/! с удвоенной размерностью значений. Это можно сделать, например, путем двукратного применения функции / с последующим перемешиванием полублоков согласно формуле:
