2.20. Профили сообщений

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

Эта схема основана на идее необратимой хэш-функции, которая принимает на входе участок открытого текста произвольной длины и по нему вычисляет строку битов фиксированной длины. У этой хэш-функции, часто называемой профилем сообщения (message digest, MD), есть четыре следующих важных свойства:

1. По заданному открытому тексту Р легко сосчитать значение хэш-функции MD(P).

2. По цифровой подписи MD(P) практически невозможно определить значение открытого текста Р.

3. Для данного Р практически невозможно подобрать такой Р', чтобы выполнялось равенство MD(P') = MD(P).

4. Изменение даже одного бита входной последовательности приводит к очень непохожему результату.

Чтобы удовлетворять требованию 3, результат хэш-функции должен быть длиной, по крайней мере, в 128 бит, желательно даже больше. Чтобы удовлетворять требованию 4, хэш-функция должна искажать входные значения очень сильно. Этим данный метод напоминает алгоритмы с симметричными ключами, которые мы рассматривали ранее.

Профиль сообщения по части открытого текста вычисляется значительно быстрее, чем шифруется все сообщение с помощью алгоритма с открытым ключом. Поэтому профили сообщений могут использоваться для ускорения работы алгоритмов цифровых подписей. Вместо того чтобы посылать открытый текст Р вместе с К_АО(А, t, P), АО теперь вычисляет профиль сообщения MD(P), применяя функцию хэширования MD к открытому тексту Р. Затем он помещает К_АО(А, t, MD(P)) как пятый элемент в список, который зашифровывает ключом К_В, и отправляет его Бобу вместо К_АО(А, t, P).

В случае возникновения спора Боб может предъявить на суде как открытый текст Р, так и К_АО(А, t, MD(P)) По просьбе судьи АО расшифровывает К_АО(А, t, MD(P)), в результате чего суду предъявляются также цифровая подпись MD(P), подлинность которой гарантируется АО, и сам открытый текст Р, подлинность которого суд должен выяснить. Поскольку практически невозможно создать другой открытый текст, соответствующий данной цифровой подписи, суд убеждается в том, что Боб говорит правду. Использование профиля сообщения экономит время шифрования и затраты на транспортировку и хранение.

Профиль сообщения может также применяться для гарантии сохранности сообщения при передаче его по сети в системах шифрования с открытым ключом. При этом, Алиса сначала вычисляет профиль сообщения для своего открытого текста. Затем она подписывает профиль сообщения и посылает зашифрованный профиль сообщения и открытый текст Бобу. Если злоумышленник попытается подменить по дороге открытый текст Р, Боб обнаружит это, сосчитав значение профиля сообщения MD(P).

2.21. MD5

Было предложено несколько вариантов функций, вычисляющих профиль сообщения. Самое широкое распространение получили алгоритмы MD5 и SHA. Алгоритм MD5 (Message Digest 5 - профиль сообщения 5) представляет собой пятую версию хэш-функций, разработанных Рональдом Ривестом. Он перемешивает входные биты достаточно сложным образом, так что каждый выходной бит зависит от каждого входного бита. Сначала сообщение дополняется до длины 448 бит по модулю 512. Затем к нему добавляется исходная длина сообщения, рассматриваемая как 64-разрядное число, в результате чего получается блок битов, длина которого кратна 512. Последний шаг подготовки к вычислениям инициализирует 128-разрядный буфер, задавая его содержимое равным некоему фиксированному значению.

Затем начинаются вычисления. На каждом этапе берется 512-разрядный блок входного текста и тщательно перемешивается со 128-разрядным буфером. Также используется содержимое таблицы синусов. Именно синусы используются не потому, что их результат более случаен, чем результат других генераторов случайных чисел (в которых часто также применяются тригонометрические функции), а чтобы избежать каких бы то ни было подозрений в создании потайной лазейки, через которую потом разработчик (или заказчик) мог бы войти. Отказ корпорации IBM раскрыть принципы устройства S-блоков, применяемых в стандарте шифрования DES, привел к появлению большого количества слухов и домыслов о потайных ходах. Каждый входной блок обрабатывается за четыре итерации. Процесс продолжается, пока не будут обработаны все входные блоки. Содержимое 128-разрядного буфера и образует профиль сообщения.

MD5 появился около десяти лет назад, и за это время было предпринято множество атак на этот алгоритм. Были обнаружены некоторые слабые места, однако существуют определенные внутренние процедуры, позволяющие защититься от взлома.

2.22. SHA-1

Второй широко применяемой функцией вычисления профиля сообщения является SHA (Secure Hash Algorithm — надежный алгоритм хэширования), разработанный Агентством национальной безопасности США (NSA)/ Как и MD5, алгоритм SHA обрабатывает входные данные 512-битовыми блоками, но, в отличие от MD5, он формирует 160-разрядный профиль сообщения. Типичный случай отправки Алисой несекретного, но подписанного сообщения Бобу. Открытый текст обрабатывается алгоритмом SHA-1, на выходе получается 160-битный хэш SHA-1. Он подписывается Алисой (закрытым ключом RSA) и отправляется вместе с открытым текстом Бобу.

При получении сообщения Боб сам вычисляет хэш-функцию с помощью алгоритма SHA-1 и применяет открытый ключ Алисы к подписанному хэшу для того, чтобы получить исходный хэш, Н. Если они совпадают, сообщение считается корректным. Так как Труди не может, перехватив сообщение, изменить его таким образом, чтобы значение Я совпадало с контрольным, Боб легко узнает обо всех подменах, которые совершила Труди. Для сообщений, чья неприкосновенность существенна, а секретность не имеет значения, часто применяется данная схема. При относительно небольших затратах на вычисления, она гарантирует, что любые изменения, внесенные на пути следования сообщения, будут с высокой вероятностью выявлены.

Давайте теперь вкратце рассмотрим, как работает SHA-1. Для начала алгоритм SHA-1 также дополняет сообщение единичным битом в конце, за которым следует такое количество нулевых бит, чтобы в итоге получилось общее число битов, кратное 512. Затем 64-разрядное число, содержащее длину сообщения (до битового дополнения), логически складывается (операция ИЛИ) с 64 младшими битами. Применительно к вычислительной технике такое расположение соответствует обратному порядку хранения байтов (сначала передается самый значимый, старший бит). Такая реализация присуща, например, SPARC. Однако вне зависимости от используемой техники SHA-1 вставляет битовое дополнение в конец сообщения.

Во время выполнения вычислений SHA-1 работает с пятью 32-битными переменными (H₀…H₄), в которых накапливается значение хэш-функции. Их начальные значения - это постоянные величины, определенные стандартом.

Затем поочередно обрабатываются блоки с М₀ по M_n-1 Для текущего блока 16 слов сначала копируются в начало вспомогательного массива W размером 80 слов, 64 оставшихся слова вычисляются с использованием следующей формулы:

W_i = S¹(W_i-3 XOR W_i-8XOR W_i-14 XOR W_i-16) (16<=i<=79)

где Sb(W) представляет собой поворот 32-разрядного слова W на b бит. Теперь по значениям H₀…H₄ инициализируются значения переменных от A до E.

Сами вычисления на псевдо-C можно записать таким образом

for (i=0;i<80;i++){

temp = S5(A) + fi(B,C,D) + E + Wi + Ki;

E=D;

D=C;

C=S30(B);

B=A;

A=temp;

}

где постоянные K_i определяются стандартом. Смешивающие функции f_i задаются следующим образом:

f_i (B, С, D) = (В AND С) OR (NOT В AND D) (О < i < 19),

f_i (B,C,D) = B XOR C XOR D (20<i<39),

f_i (B, С, D) = (В AND С) OR (В AND D) OR (C AND D) (40 < i < 59),

f_i (B, C,D) = B XOR С XOR D (60 < i < 79).

После 80 итераций цикла значения переменных А ... Е добавляются к H₀…H₄ соответственно.

После обработки первого 512-битного блока начинается обработка следующего. Массив W инициализируется заново с помощью нового блока, однако Н сохраняется неизменным. По окончании этого блока обрабатывается следующий, и так далее, пока все 512-разрядные блоки сообщения не попадут в эту кастрюлю. После обработки последнего блока пять 32-разрядных слов в массиве H выводятся в качестве 160-битного значения криптографической хэш-функции. Полный код SHA-1 приведен в RFC 3174.

В настоящее время идет работа над новыми версиями SHA-1 с 256-, 384-

и 512-разрядными значениями хэш-функций. Эти версии вместе называются SHA-2.