Использование цепочки зашифрованных блоков
Существуют различные хэш-функции, основанные на создании цепочки зашифрованных блоков, но без использования секретного ключа. Одна из таких хэш-функций была предложена Рабином. Сообщение М разбивается на блоки фиксированной длины М1, М2, . . . , МN и используется алгоритм симметричного шифрования, например DES, для вычисления хэш-кода G следующим образом:
Н0 = начальное значение
Нi = EMi [Hi-1]
G = HN
Это аналогично использованию шифрования в режиме СВС, но в данном случае секретного ключа нет. Как и в случае любой простой хэш-функции, этот алгоритм подвержен "атаке дня рождения", и если шифрующим алгоритмом является DES и создается только 64-битный хэш-код, то система считается достаточно уязвимой.
Могут осуществляться другие атаки типа "дня рождения", которые возможны даже в том случае, если противник имеет доступ только к одному сообщению и соответствующему ему зашифрованному хэш-коду и не может получить несколько пар сообщений и зашифрованных хэш-кодов. Возможен следующий сценарий: предположим, что противник перехватил сообщение с аутентификатором в виде зашифрованного хэш-кода, и известно, что незашифрованный хэш-код имеет длину m битов. Далее противник должен выполнить следующие действия:
1. Используя описанный выше алгоритм, вычислить незашифрованный хэш-код G.
2. Создать поддельное сообщение в виде Q1, Q2, . . . , QN-2.
3. Вычислить Нi = EQi [Hi-1] для 1 ≤ i ≤ N-2.
4. Создать 2m/2 случайных блока Х и для каждого такого блока Х вычислить ЕХ [HN-2]. Создать дополнительно 2m/2 cлучайных блока Y и для каждого блока Y вычислить DY [G], где D - дешифрующая функция, соответствующая Е. Основываясь на "парадоксе дня рождения" можно сказать, что с высокой степенью вероятности эта последовательность будет содержать блоки Х и Y такие, что ЕХ [HN-2] = DY [Y].
5. Создать сообщение Q1, Q2, . . . ,QN-2, X, Y. Это сообщение имеет хэш-код G и, следовательно, может быть использовано вместе с зашифрованным аутентификатором.
Эта форма атаки известна как атака "встреча посередине". В различных исследованиях предлагаются более тонкие методы для усиления подхода, основанного на цепочке блоков. Например, Девис и Прайс описали следующий вариант:
Hi = EMi [Hi-1] Å Hi-1
Возможен другой вариант:
Hi = EHi-1 [Mi] Å Mi
Однако обе эти схемы также имеют уязвимости при различных атаках. В более общем случае, можно показать, что некоторая форма "атаки дня рождения" имеет успех при любом хэш-алгоритме, включающем использование цепочки шифрованных блоков без применения секретного ключа.
Дальнейшие исследования были направлены на поиск других подходов к созданию функций хэширования.
MD2
MD2 – 128-битовая однонаправленная хэш-функция, разработанная Роном Ривестом. Использовалась в протоколах PEM. Безопасность MD2 опирается на случайную перестановку байтов. Эта перестановка фиксирована и зависит от разрядов π. S0, S1, S2, …, S255 и являются перестановкой. Чтобы выполнить хэширование сообщения M нужно:
1. Дополнить сообщение нулями так, чтобы длина полученного сообщения была кратна 16 байтам.
2. Добавить к сообщению 16 байтов контрольной суммы.
3. Проинициализируйте 48-байтовый блок: X0, X1, X2, …, X47. Заполнить первые 16 байтов X нулями, во вторые 16 байтов X скопировать первые 16 байтов сообщения, а третьи 16 байтов X должны быть равны XOR первых и вторых 16 байтов X.
4. Вот как выглядит функция сжатия:
t=0
For j = 0 to 17
For k = 0 to 47
t = X[k] XOR S[t]
X[k] = t
t = (t+j) mod 256
5. Скопировать во вторые 16 байтов X вторые 16 байтов сообщения, а третьи 16 байтов X должны быть равны XOR первых и вторых 16 байтов X. Выполнить этап (4). Повторять этапы (5) и (4) по очереди для каждых 16 байтов сообщения.
6. Выходом являются первые 16 байтов X.