Введение в современную криптографию

125
сообщений (то есть когда Mac — детерминистский алгоритм), канонический метод 
верификаци и заключается в том, чтобы просто заново вычислить тэг и проверить 
равенство двух тэгов. Иными словами, Vrfyk (m, t) сначала вычисляет t˜ := Mack(m), 
а потом выдает 1 тогда и только тогда, когда t˜ = t. Однако, даже для детерминист-
ских КАСов, полезно определить отдельный алгоритм Vrfy , чтобы четко различать 
семантику аутентификации сообщения и проверку его подлинности. 
Безопасность кодов аутентификации сообщений 
Определим теперь исходное понятие безопасности для кодов аутентификации 
сообщений. Интуитивная идея, лежащая в основе этого определения, следую-
щая: ни один эффективный противник не может сгенерировать действительный 
тэг для любого «нового» сообщения, которое ранее не посылалось (и не было 
аутентифицировано) никем из участников коммуникации.
Как в любом определении безопасности, для формализации этого понятия нам 
нужно определить как силу противника, так и что именно будет пониматься под 
«взломом». Как обычно , мы рассматриваем только вероятностных противников, 
работающих в полиномиальном времени² и настоящий вопрос заключается в 
том, как создать модель взаимодействия противника с участниками коммуника-
ции. При аутентификации сообщения противник, следящий за коммуникацией 
между честными участниками, может видеть все сообщения, посылаемые участ-
никами, вместе с их соответствующими тэгами КАС. Противник также может по-
влиять на содержание этих сообщений, напрямую или косвенно (если, например, 
внешние действия противника влияют на сообщения участников). Это примени-
мо, например, к примеру сетевых куки, где действия самого пользователя влияют 
на содержание куки, сохраняемого на его компьютере.
Для создания соответствующей модели мы позволяем противнику запросить 
тэги КАС для любых выбранных им сообщений. Формально, мы даем про-
тивнику доступ к оракулу КАСа Mack (•). Противник может повторно послать 
любое сообщение m этому оракулу, и взамен получает тэг t ← Mack (m). (Для 
всех КАСов фиксированной длины могут посылаться только сообщения соот-
вествующей длины.)
Мы будем считать «взломом» схемы, если противник может выдать любое 
сообщение m вместе с тэгом t , такое что: (1) t — действующий тэг для сообще-
ния m (т.е., Vrfyk (m, t) = 1), и (2) противник ранее не запрашивал тэг КАС для 
сообщения m (т.е. из его оракула). Первое условие означает, что если бы про-
тивник хотел послать (m, t) одному из честны х участников, то этот участник бы 
___________________________________________________________
²См. Раздел 4.6, где обсуждается информационно-теоретическая аутентификация сообщений, 
где на противника не накладывается никаких вычислительных ограничений.

126
ложно подумал, что m послано легитимным участником, так как Vrfyk (m, t) = 1. Вто-
рое условие требуется, потому что противник всегда может просто скопировать сооб-
щение и тэг КАС, посланные ранее одним из легитимных участников (и, конечно, они 
будут приняты как действующие). Такая повторная атака не считается «взломом» 
кода аутентификации сообщения. Это не означает, что повторные атаки не представ-
ляют проблему для безопасности. Они представляют, и мы вернемся к этому позже.
КАС, соответствующий уровню безопасности, описанному выше, называют 
экзистенциально не поддающийся подделке при адаптивной атаке с выбором со-
общения. «Невозможность пооделки» означает, что противник не должен иметь 
возможность подделать действующий тэг для любого сообщения, а «адаптивная 
атаки с выбором сообщения» означает, что противник может получить тэги КАС 
для произвольных сообщений, выбранных адаптивно во время атаки.
Для формального определения, рассмотрим следющий эксперимент для кода 
унтентификации сообщений Π = (Gen, Mac, Vrfy), противника A, и значение n 
для параметра безопасности:

жүктеу/скачать 6.4 Mb.

Достарыңызбен бөлісу: