Однонаправленные хэш-функции на основе симметричных блочных алгоритмов

Однонаправленную хэш-функцию можно построить, используя симметричный блочный алгоритм. Наиболее очевидный подход состоит в том, чтобы шифровать сообщение М посредством блочного алгоритма в режиме СВСили СFВ с помощью фиксированного ключа и некоторого вектора инициализации IV. Последний блок шифртекста можно рассматривать в качестве хэш-значения сообщения М. При таком подходе не всегда возможно построить безопасную однонаправленную хэш-функцию, но всегда можно получить код аутентификации сообщения МАС (Message Authentication Code).

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

Поскольку большинство блочных алгоритмов являются 64-битовыми, некоторые схемы хэширования проектируют так, чтобы хэш-значение имело длину, равную двойной длине блока.

Если принять, что получаемая хэш-функция корректна, безопасность схемы хэширования базируется на безопасности лежащего в ее основе блочного алгоритма. Схема хэширования, у которой длина хэш-значения равна длине блока, показана на рис.3. Ее работа описывается выражениями:

Н₀ = I_н, Н_i = Е_A(В) Å С,

где Å - сложение по модулю 2 (исключающее ИЛИ); I_н - некоторое случайное начальное значение; А, В, С могут принимать значения М_i, Н_i-1, (М_i Å Н_i-1) или быть константами.

Рис.3. Обобщенная схема формирования хэш-функции

Сообщение М разбивается на блоки М_i принятой длины, которые обрабатываются поочередно.

Три различные переменные А, В, С могут принимать одно из четырех возможных значений, поэтому в принципе можно получить 64 варианта общей схемы этого типа. Из них 52 варианта являются либо тривиально слабыми, либо небезопасными. Остальные 12 схем безопасного хэширования, у которых длина хэш-значения равна длине блока перечислены в табл.1.

Таблица 1

Номер схемы Функция хэширования   Нi = ЕHi-1 (Мi ) Å Мi   Нi = ЕHi-1 (Мi Å Нi-1 ) Å Мi Å Нi-1   Нi = EHi-1 (Мi ) Å Мi Å Нi-1   Нi = ЕHi-1 (Мi Å Нi-1 ) Å Мi   Нi = ЕMi (Нi-1 ) Å Нi-1   Нi = ЕMi (Мi Å Нi-1 ) Å Мi Å Нi-1   Нi = ЕMi (Нi-1 ) Å Мi Å Нi-1   Нi = EMi (Мi Å Нi-1) Å Нi-1   Нi = ЕMi Å Hi-1 (Мi ) Å Мi   Нi = ЕMi Å Hi-1 (Нi-1) Å Нi-1   Нi = ЕMi ÅHi-1 (Mi ) Å Нi-1   Нi = ЕMi Å Hi-1 (Нi-1 ) Å Мi

Первые четыре схемы хэширования, являющиеся безопасными при всех атаках, приведены на рис.4.

Рис.4. Четыре схемы безопасного хэширования

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

Алгоритм MD5

Алгоритм MD5 (Message Digest №5) разработан Роналдом Риверсом. MD5 использует 4 многократно повторяющиеся преобразования над тремя 32-битными величинами U, V и W:

f(U,V,W)=(U AND V) OR ((NOT U) AND W) g(U,V,W)=(U AND W) OR (V AND (NOT W)) h(U,V,W)=U XOR V XOR W k(U,V,W)=V XOR (U OR (NOT W)).

В алгоритме используются следующие константы:

• начальные константы промежуточных величин -

H[0]=67452301₁₆, H[1]=EFCDAB89₁₆, H[2]=98BADCFE₁₆, H[3]=10325476₁₆;

• константы сложения в раундах -

y[j]=HIGHEST_32_BITS(ABS(SIN(j+1))) j=0...63,

где функция HIGHEST_32_BITS(X) отделяет 32 самых старших бита из двоичной записи дробного числа X, а операнд SIN(j+1) считается взятым в радианах;

• массив порядка выбора ячеек в раундах -

· z[0...63] = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,· 1, 6, 11, 0, 5, 10, 15, 4, 9, 14, 3, 8, 13, 2, 7, 12,· 5, 8, 11, 4, 1, 4, 7, 10, 13, 0, 3, 6, 9, 12, 15, 2, 0, 7, 14, 5, 12, 3, 10, 1, 8, 15, 6, 13, 4, 11, 2, 9);

• массив величины битовых циклических сдвигов влево -

· s[0...63] = (7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22,· 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20,· 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21).

На первоначальном этапе входной блок данных дополняется одним битом "1". Затем к нему добавляется такое количество битов "0", чтобы остаток от деления блока на 512 составлял 448. Наконец, к блоку добавляется 64-битная величина, хранящая первоначальную длину документа. Получившийся входной поток имеет длину кратную 512 битам.

Каждый 512-битный блок, представленный в виде 16 32-битных значений X[0]...X[15], проходит через сжимающую функцию, которая перемешивает его со вспомогательным блоком (H[0],H[1],H[2],H[3]):

(A,B,C,D) = (H[0],H[1],H[2],H[3])цикл по j от 0 до 15 T = (A + f(B,C,D) + x[z[j]] + y[j]) ROL s[j] (A,B,C,D) = (D,B+T,B,C)конец_циклацикл по j от 16 до 31 T = (A + g(B,C,D) + x[z[j]] + y[j]) ROL s[j] (A,B,C,D) = (D,B+T,B,C)конец_циклацикл по j от 32 до 47 T = (A + h(B,C,D) + x[z[j]] + y[j]) ROL s[j] (A,B,C,D) = (D,B+T,B,C)конец_циклацикл по j от 48 до 63 T = (A + k(B,C,D) + x[z[j]] + y[j]) ROL s[j] (A,B,C,D) = (D,B+T,B,C)конец_цикла(H[0],H[1],H[2],H[3]) = (H[0]+A,H[1]+B,H[2]+C,H[3]+D)

После того, как все 512-битные блоки прошли через процедуру перемешивания, временные переменные H[0],H[1],H[2],H[3], а 128-битное значение подается на выход хэш-функции.

Алгоритм MD5, основанный на предыдущей разработке Роналда Риверса MD4, был призван дать еще больший запас прочности к криптоатакам. MD5 очень похож на MD4. Отличие состоит в простейших изменениях в алгоритмах наложения и в том, что в MD4 48 проходов основного преобразования, а в MD5 - 64. Несмотря на большую популярность, MD4 "медленно, но верно" был взломан. Сначала появились публикации об атаках на упрощенный алгоритм. Затем было заявлено о возможности найти два входных блока сжимающей функции MD4, которые порождают одинаковый выход. Наконец, в 1995 году было показано, что найти коллизию, т.е. "хэш-двойник" к произвольному документу, можно менее чем за минуту, а добиться "осмысленности" фальшивого документа (т.е. наличия в нем только ASCII-символов с определенными "разумными" законами расположения) - всего лишь за несколько дней.