В. Р. Гинзбург Перевод с английского
жүктеу/скачать 2,74 Mb. Pdf көрінісі
|
практическая криптография
Глава 7. Коды аутентичности сообщений различия между функцией вычисления MAC и идеальной функцией вычис- ления MAC менее чем за 2 min( n,k ) шагов. Другими словами, функция вычисления MAC — это случайное отобра- жение, уровень безопасности которого ограничен k битами. Это совсем не то, что обычное случайное отображение. В обычном случайном отображении злоумышленник знает все; в нашем же случае у него есть некая неопределен- ность относительно значения K . (Если злоумышленник полностью уверен в значении K , тогда k = 0 , а значит, уровень безопасности равен нулю и нам нечего обсуждать.) Разумеется, заявленный уровень безопасности конкретной функции MAC может быть ниже, чем размер ее результата. В этом случае злоумышлен- ник ограничен 2 min( s,k ) шагами, где s — заявленный уровень безопасности. Неопределенность злоумышленника относительно значения K может быть использована для того, чтобы сделать функции вычисления MAC более эф- фективными, чем функции хэширования. Следует отметить, что никто другой, кроме нас, не определяет безопас- ность MAC подобным образом. Большинство исследователей подходят к опре- делению безопасности MAC с более ограниченной точки зрения. В частности, они используют модель атак, в которой злоумышленник по своему желанию выбирает n различных сообщений и получает значение MAC для каждого из этих сообщений. В результате у злоумышленника должно оказаться n +1 сооб- щение, каждое с правильным значением MAC. Данная модель не учитывает некоторых типов атак, например атак со связанным ключом и атак, кото- рые предполагают, что у злоумышленника имеется частичная информация о ключе. Вот почему мы предпочитаем наши определения безопасности, ко- торые оказываются корректными даже тогда, когда функция используется неправильно или в необычном для нее окружении. 7.4 CBC-MAC Это метод превращения блочного шифра в функцию вычисления MAC. Ключ K при этом используется в качестве ключа шифрования. Основная идея алгоритма CBC-MAC заключается в том, чтобы зашифровать сообще- ние m с помощью блочного шифра, используя режим CBC, и затем откинуть все блоки шифрованного текста кроме последнего. Для сообщения, состоя- щего из блоков P 1 , . . . , P k , значение MAC вычисляется следующим образом: H 0 := IV, H i := E K ( P i ⊕ H i − 1 ) , MAC := H k . 7.4. CBC-MAC 121 Иногда результатом функции CBC-MAC считают половину последнего блока, но это уже зависит от конкретной ситуации. Классическое определение алгоритма CBC-MAC требует, чтобы значение вектора инициализации было фиксированным и равнялось нулю. Именно та- кое определение часто встречается в учебниках. Вообще говоря, функцию CBC-MAC можно использовать и с любыми другими типами вектора иници- ализации, которые обсуждались при рассмотрении режима CBC, но очевид- ных преимуществ это не дает. Никогда не используйте один и тот же ключ для шифрования и аутен- тификации (разве что вы твердо уверены в необходимости этого шага). Осо- бенно опасно использовать шифрование в режиме CBC и аутентификацию CBC-MAC с одним и тем же ключом. В этом случае значение MAC будет просто равно последнему блоку шифрованного текста. Алгоритм CBC-MAC не слишком прост в применении. Тем не менее в об- щем случае он считается безопасным, если соответствующий блочный шифр также безопасен. Существует ряд атак на основе коллизий, которые сокра- щают уровень безопасности CBC-MAC до половины размера блока [12]. Вот простой пример одной из таких атак. Пусть M — это функция CBC-MAC. Если известно, что M ( a ) = M ( b ) , значит, M ( a k c ) = M ( b k c ) . Это объясня- ется спецификой алгоритма CBC-MAC. Проиллюстрируем данное свойство на простом примере, когда c состоит из одного блока текста. Мы знаем, что M ( a k c ) = E K ( c ⊕ M ( a )) , M ( b k c ) = E K ( c ⊕ M ( b )) . Поскольку M ( a ) = M ( b ) , правые части этих выражений равны. Такая атака выполняется в два этапа. На первом этапе злоумышленник собирает значения MAC для большого количества сообщений, пока не на- ткнется на коллизию. В этом случае у него появятся сообщения a и b , для которых M ( a ) = M ( b ) . Если теперь злоумышленнику удастся аутентифици- ровать у получателя сообщение a k c , он может заменить его сообщением b k c , причем значение MAC останется прежним. Получатель проверит зна- чение MAC и примет поддельное сообщение. (Напомним, что мы работаем с параноидальной моделью. Вполне возможно, что злоумышленник может создать сообщение и аутентифицировать его у получателя. В реальной жизни такие ситуации встречаются довольно часто.) Существует много усовершен- ствованных вариантов такой атаки, которые работают даже при добавлении поля с длиной сообщения и применении правил дополнения [12]. Эта атака не является тривиальной, поскольку она не срабатывает для идеальной функции вычисления MAC. Найти коллизию несложно и для иде- альной функции. Тем не менее, даже когда у вас появятся сообщения a и b , |