C.J.Mitchell. Authenticating Multicast Internet Electronic Mail
Messages Using a Bidirectional MAC is Insecure// IEEE Trans. on
Computers, vol.41, Э4, 1992, pp.505-507.
Аннотация. Версия 1988 г. для
шифрования и аутентификации сообщений в электронной почте
"Интернет" использует "Двунаправленный КАС" (ДКАС). При
использовании в многоабонентской электронной почте важно, чтобы
этот ДКАС работал как односторонняя функция. Мы покажем, что он
не является такой функцией, и, следовательно, не может
использоваться для аутентификации многоабонентских сообщений.
Ключевые слова: Аутентификация, Криптография, Электронная почта,
Хэш-функция, КАС. I. Введение Электронная почта "Интернет" широко
используется в США и во всгм мире. Ввиду практической значимости
этой сети и чувствительности передаваемой по сети информации была
разработана программа обеспечения защиты системы. В результате
был разработан ряд отчгтов (RFC): RFC989 [10] в 1987, RFC1040
[11] в 1988 (пересмотренная версия RFC989) и совсем недавно в
1989 г. RFC1113 [12], 1114 [9] и 1115 [13]. В этих документах
описаны процедуры шифрования и аутентификации сообщений. К
сожалению, схема аутентификации, описанная в RFC989, содержит
существенный недостаток при использовании для многоабонентских
сообщений (т.е. сообщений, посылаемых более, чем одному
получателю). Наличие этого недостатка позволяет одному из
получателей сообщения послать фальшивое сообщение другому
получателю необнаружимым способом [15]. Коротко рассмотрим
сущность этого недостатка, более подробно рассмотренного
Митчеллом и Уокером [16]. Схема, описанная в RFC989, основана на
том, что отправитель сообщения рассчитывает "выжимку" из
сообщения при помощи предопределгнной хэш-функции h. Результат
хэширования поочергдно шифруется на ключе каждого получателя, и
полученные зашифрованные "выжимки" добавляются при передаче к
сообщению. Ключи получателя известны только отправителю и
соответствующим получателям. Эффективность схемы зависит от
хэш-функции h, которая должна удовлетворять ряду свойств, и
шифрования результатов хэширования (не рассматривается в статье).
Первое важное свойство h заключается в следующем: если сообщение
М является аргументом h, то результат h(М) (обычно 64 или 128
бит) должен зависеть от всего М. Другим свойством h должна быть
"односторонность": Н1: для некоторого предполагаемого результата
хэширования С должно быть вычислительно невозможным найти
сообщение М такое, что h(М)=С. В RFC989 [10] для выработки
64-битного КАС предполагалось использование DES [1,6] в режиме
сцепления блоков [2,7,8]. Этот способ стандартизован в США для
аутентификации финансовых сообщений [3,4]. (Отметим, что
приводимое в [15] описание режима сцепления блоков неправильно.)
Ключ, используемый для расчгта КАС, различен для каждого
сообщения. Он посылается (вместе с результатом хэширования)
зашифрованным на ключе каждого получателя. Это означает, что для
обеспечения безопасности системы многоабонентских сообщений КАС
на основе режима сцепления блоков DES должен отвечать Н1 даже при
- 2 - известном ключе. К сожалению, это не выполняется в [15] и
является источником слабости RFC989. В результате этого, в
RFC1040 [11, раздел А.2] появилось описание второй функции для
расчгта "выжимок", называемой "двунаправленный КАС" (ДКАС).
Предполагалось использование этой функции вместо обычного КАС для
многоабонентской почты. Авторы RFC1040 исходили из того, что
функция ДКАС удовлетворяет Н1 даже при известном ключе, на
котором вырабатывался ДКАС; к сожалению, это не так, что и
показано ниже в этой короткой статье. Ввиду описанной ниже атаки
алгоритм ДКАС был изъят из набора RFC 1989 года [9,12,13].
Алгоритм, описанный в RFC1115 [13], является более сильным. II.
ДКАС не является односторонней функцией А. Определение ДКАС
Сперва рассмотрим, как рассчитывается ДКАС. С этой целью
рассотрим порядок формирования КАС. Сообщение разбивается на
блоки по 64 бита (при необходимости последний блок дополняется
нулями): М1, М2,..., Мr. Затем вычисляется последовательность С1,
С2,..., Сr, где (1) Сi=Ек {Мi + Сi }, где по соглашению Со - это
блок нулей, "+" означает побитное сложение по модулю 2, а Ек{} -
шифрование при помощи DES на ключе К. КАС равен последнему блоку
Сr. Для расчгта ДКАС сообщение снова разбивается на
последовательность (Мi) . Последовательность рассчитывается как и
ранее, и кроме того, рассчитывается дополнительная
последовательность (Вi) (1 =< i <=r), где Вi=Ек {Мi + Вi }, где
по соглашению В - это блок нулей. ДКАС состоит из пары 64битных
блоков (Сr, В1). Другими словами, ДКАС состоит из пары КАС, один
из которых рассчитывается в прямом направлении, а другой в
обратном. В. Раскол ДКАС Теперь мы покажем, как при заданной паре
64-битных блоков и ключе К можно построить сообщение, для
которого эта пара блоков будет ДКАС. Это предполагает, что
функция ДКАС не является односторонней, и, следовательно, схема
RFC1040 небезопасна. Предлагаемый метод позволяет произвольно
выбрать сообщение, за исключением того, что в нгм должны быть два
действительно случайных 64-битных блока. Эти "мусорные" блоки
позволяют получить требуемый ДКАС. В описанном ниже способе эти
блоки находятся в начале и конце сообщения; однако метод легко
изменить, чтобы добиться их размещения в любом месте сообщения.
Предположим, что имеются два блока (С, В) и ключ К. Обозначим
также "подгоняемое" под ДКАС (С, В) сообщение как М. Сообщение М
разбивется на две части М1 и М2. Кроме того, выберем случайный
64-битный блок Х. Теперь выполним две группы очень простых
вычислений Сперва подготовим 2**32 вариантов М1, каждый из
которых состоит из целого числа 64-битных блоков (число блоков в
каждом варианте может быть различным). Дэвис и Прайс [5] показали
простой способ, при помощи которого можно добиться, чтобы каждый
вариант соответствовал нормам английского языка, и каждый вариант
был семантически одним и тем же. В общем случае, если в
сообщении, две - 3 - возможные редакции которого имеют одинаковое
значение, идентифицируется n точек, то можно получить 2**n
различных вариантов сообщения. Одна из простых возможностей - это
вставка одного или двух пробелов в конце каждого предложения. Для
каждого варианта проведите следующие вычисления (предполагаем,
что N2, N3,..., Ns - это декомпозиция варианта на 64-битные
блоки; отметим, что первый блок варианта на этом этапе не
определгн): - для каждого i (i=s, s-1,..., 2) пусть Fi=Ek {Ni +
Fi }, (3) где Fi =Х; - пусть N1=Dk {В} + F2, (4) где Dk{}
означает дешифрование по DES на ключе К. N1 образует первый блок
варианта М1; - для каждого i (i=1, 2,.., s) пусть Gi=Ek {Ni + G
}, (5) где Go - нулевой блок; - и наконец, пусть Y=Gs. (6) Затем
каждый вариант (N1,..., Ns) запоминается с соответствующим
значением Y. На втором этапе подготовим 2**32 вариантов М2,
каждый из которых состоит из целого числа 64-битных блоков (число
блоков в каждом варианте может быть различным). Для каждого
варианта (состоящего из 64-битных блоков Ps , Ps ,..., Pr )
выполните следующие вычисления: - для каждого i (i=s+2, s+3,...,
r) пусть Hi=Dk {Hi } + Pi , (7) где Hs =Х; - пусть Pr=Dk {Hr},
(8) где Pr образует последний блок варианта; - для каждого i
(i=r-1, r-2,..., s) пусть Li=Dk {Li } + Pi , (9) где Li=C; - и
наконец, пусть Z=Ls. (10) Это значение Z затем сравнивается со
всеми значениями Y, полученными для 2**32 вариантов М1. Очень
даже вероятно, что до окончания обработки всех 2**32 вариантов М2
найдгтся совпадение (т.е. пара значений Y и Z таких, что Y=Z);
ниже мы обоснуем это заявление. Теперь предположим, что
последовательности (Ni) (1 = 0.5, что подтверждает наше заявление
(в предположении, что DES-шифрование генерирует случайно
распределгнные 64-битные блоки). Предположение, что u=v=2**32,
было сделано чисто в иллюстративных целях и может быть
оптимизировано для получения более высокой вероятности успеха.
Можно оптимизировать ресурсы обработки и/или хранения. Например,
u (число вариантов М1) можно выбрать значительно меньшим, а v
соответственно большим, чтобы снизить требования по памяти (ценой
повышения требований к DES-обработке). - 5 - III. Рекомендации В
любой схеме аутентификации для многоабонентских сообщений,
исползующей метод, описанный в RFC для "Интернет", нельзя
использовать схему ДКАС. До разработки альтернативных способов
используется рекомендация Митчелла и Уокера [16]. Т.е. выбирается
функция h, удовлетворяющая свойству H1. Винтерниц [16-18]
предложил способ построения таких функций на основе блочных
шифров типа DES. Этот способ является хорошим кандидатом на
использование в электронной почте "Интернет". Другие способы на
основе DES обсуждались Мерклем [14]. Ряд способов предложил
Райвест, включая алгоритм из RFC1115 [13] и метод MD4.
Литература: 1. ANSI X3.92-1981. DEA. 2. ANSI X3.106-1983. DEA.
Режимы операций. 3. ANSI X9.9-1986. 4. ANSI X9.19. 5. Davies
D.W., Price W.L. Security for Computer Networks. 1984. 6. DES. 7.
DES. Режимы операций. 8. ISO 8372. Обработка информации - режимы
операций для алгоритма 64-битного блочного шифра. 1987. 9. RFC
1114 Безопасность электронной почты "Интернет". Управление
ключами на основе сертификации (проект). 1989 10. RFC 989
Безопасность электронной почты "Интернет". Процедуры шифрования и
аутентификации сообщений. 1987. 11. RFC 1040 Безопасность
электронной почты "Интернет". Процедуры шифрования и
аутентификации сообщений. 1988. 12. RFC 1113 Безопасность
электронной почты "Интернет". Процедуры шифрования и
аутентификации сообщений. 1989. 13. RFC 1113 Безопасность
электронной почты "Интернет". Алгоритмы, режимы и идентификаторы.
1989. 14. Merkle R.C. One-way hash-functions and DES, preprint,
1989. 15. Mitchell C.J. Multi-destination secure electronic mail/
Comput.J., v.32, pp.13-15, 1989. 16. Mitchell C.J., Walker M.
Solutions to the multi-destination secure electronic mail
problem/ C&S, v.7, pp.483-488, 1988. 17. Winternitz R.S.
Producing a one-way hash-functions from DES/ in Advances in
Cryptology: Proc. Crypto 83. N-Y: Plenum, 1984. 18. Winternitz
R.S. A Secure one-way hash-functions built from DES/in Proc. 1984
IEEE Sympo. Security & Privacy, IEEE, 1984, pp.88-90.
