Во втором подходе для определения того, может ли протокол перейти в нежелательное состояние (например, потеря ключа), используются экспертные системы. Хотя этот подход дает лучшие результаты при поиске "дыр", он не гарантирует безопасности и не предоставляет методик разработки вскрытий . Он хорош для проверки того, содержит ли протокол конкретную "дыру", но вряд ли способен обнаружить неизвестные "дыры" в протоколе . Примеры такого подхода можно найти в [987,1521], а в [1092] обсуждается экспертная система, разработанная армией США и названная Следователем (Interrogator).

Третий подход гораздо популярнее. Он б1л впервые введен Майклом Бэрроузом ( Michael Burrows), Мартином Абэди (Martin Abadi) и Роджером Неедхэмом. Они разработали формальную логическую модель для ан а-лиза знания и доверия, названную БАН-логикой [283, 284]. БАН-логика является наиболее широко распространена при анализе протоколов проверки подлинности . Она рассматривает подлинность как функцию от ц е-лостности и новизны, используя логические правила для отслеживания состояния этих атрибутов на протяжении всего протокола. Хотя были предложены различные варианты и расширения, большинство разработчиков пр о-токолов до сих пор обращаются к оригинальной работе.

БАН-логика не предоставляет доказательство безопасности , она может только рассуждать о проверке подлинности. Она является простой, прямолинейной логикой, легкой в применении и полезной при поиске "дыр" . Вот некоторые предложения БАН-логики:

Алиса считает X. (Алиса действует, как если бы X являлось истиной.)

Алиса видит X. (Кто-то послал сообщение, содержащее X, Алисе, которая может прочитать и снова передать X - возможно после дешифрирования.)

Алиса сказала X. (В некоторый момент времени Алиса послала сообщение, которое содержит предложение X. Не известно, как давно было послано сообщение, и было ли оно послано в течении текущего выполнения протокола . Известно, что Алиса считала X, когда говорила X.)

X ново. (X никогда не было послано в сообщении до текущего выполнения протокола .)

И так далее. БАН-логика также предоставляет правила для рассуждения о доверии протоколу . Для доказательства чего-либо в протоколе или для ответа на какие-то вопросы к логическим предложениям о протоколе можно применить эти правила. Например, одним из правил является правило о значении сообщения :

ЕСЛИ Алиса считает, что у Алисы и Боба общий секретный ключ, К, и Алиса видит X, шифрованное К, и Алиса не шифровала X с помощью K, ТО Алиса считает, что Боб сказал X.

Другим является правило подтверждения метки времени :

ЕСЛИ Алиса считает, что X могло быть сказано только недавно, и, что Боб X когда-то сказал X, ТО Алиса считает, что Боб считает X.

БАН-анализ делится на четыре этапа:

(1) Преобразуйте протокол к идеальной форме, используя описанные выше предложения.

(2) Добавьте все предположения о начальном состоянии протокола.

(3) Присоедините логические формулы к предложениям, получая утверждения о состоянии системы после каждого предложения.

(4) Примените логические постулаты к утверждениям и предположениям, чтобы раскрыть состояние доверия участников протокола.

Авторы БАН-логики "рассматривают идеализированные протоколы как более ясные и полные описания, чем традиционные, найденные в литературе..." [283, 284]. Другие исследователи не так оптимистичны и подвергают это действие критике, так как при этом реальный протокол может быть искажен [1161, 1612]. Дальнейшие споры отражены в [221, 1557]. Ряд критиков пытается показать, что БАН-логика может и получить очевидно н е-правильные характеристики протоколов [1161] - см. контрдоводы в [285, 1509] - и что БАН-логика занимается только доверием, а не безопасностью [1509]. Подробное обсуждение приведено в [1488, 706, 1002].

Несмотря на эту критику БАН-логика достигла определенных успехов . Ей удалось обнаружить "дыры" в нескольких протоколах, включая Needham-Schroeder и раннюю черновую версию протокола CCITT X.509 [303]. Она обнаружила избыточность во многих протоколах, включая Yahalom, Needham-Schroeder и Kerberos. Во многих опубликованных работах БАН-логика используется для заявления претензии о безопасности описыва е-мых протоколов [40, 1162, 73].

Были опубликованы и другие логические системы, некоторые из них разрабатывались как расширения БАН-логики [645, 586, 1556, 828], а другие основывались на БАН-логике для исправления ощутимых слабостей [1488, 1002]. Из них наиболее успешной оказалась CNY [645], хотя у нее есть ряд изъянов [40]. В [292,474] к БАН-логике с переменным успехом были добавлены вероятностные доверия . Другие формальные логики описаны в [156, 798,288]. [1514] пытается объединить черты нескольких логик. А в [1124, 1511] представлены логики, в которых доверия изменяются со временем .

Четвертый подход к анализу криптографических протоколов предлагает моделировать протокол как алге б-раическую систему, выразить состояние знания участников о протоколе и затем проанализировать достиж и-

мость определенных состояний. Этот подход пока не привлек столько внимания, как формальная логика, но состояние дел меняется. Он впервые был использован Майклом Мерриттом [1076], который показал, что для анализа криптографических протоколов можно использовать алгебраическую модель . Другие подходы рассмотрены в [473, 1508, 1530, 1531, 1532, 1510, 1612].

Анализатор протоколов Исследовательской лаборатория ВМС (Navy Research Laboratory, NRL), возможно, является наиболее успешным применением этих методов [1512, 823, 1046, 1513]. Он был использован для поиска как новых, так и известных "дыр" во множестве протоколов [1044, 1045, 1047]. Анализатор протоколов определяет следующие действия:

- Принять (Боб, Алиса, М, N). (Боб принимает сообщение Мкак пришедшее от Алисы в течение локального раунда Боба N.)

- Узнать (Ева, М). (Ева узнает М.)

- Послать (Алиса, Боб, Q, М). (Алиса посылает М Бобу в ответ на запрос, Q.)

- Запросить (Боб, Алиса, Q, N). (Боб посылает Q Алисе в течение локального раунда Боба N.) Используя эти действия, можно задать требования . Например:

- Если Боб принял сообщение М от Алисы в какой-то прошедший момент времени, то Ева не знает М в какой-то прошедший момент времени.

- Если Боб принял сообщение М от Алисы в течение локального раунда Боба N, то Алиса послала М Бобу в ответ на запрос Боба в локальном раунде Боба N.

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

Хотя формальные методы в основном применяются к уже существующим протоколам, сегодня есть тенде н-ция использовать их и при проектировании протоколов . Ряд предварительных шагов в этом направлении сделан в [711]. Это же пытается сделать и анализатор протоколов NRL [1512, 222, 1513].

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

3.5 Криптография с несколькими открытыми ключами

Обычная криптография с открытыми ключами использует два ключа. Сообщение, зашифрованное одним ключом, может быть расшифровано другим. Обычно один ключ является закрытым, а другой - открытым. Пусть, один ключ находится у Алисы, а другой - у Боба. Мы хотим реализовать следующую схему: Алиса м о-жет зашифровать сообщение так, что только Боб сможет расшифровать его, а Боб может зашифровать сообщ е-ние так, что только Алиса сможет прочитать его.

Эта концепция б1ла обобщены Конном Бойдом (Conn Boyd) [217]. Представьте себе вариант криптографии с открытыми ключами, использующий три ключа: КА, Кв и Кс, распределение которых показано в 1-й.

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

Табл. 3-2.

Распределение ключей в трехключевой системе.

Алиса КА Боб Кв

Такая схема может быть расширена на n ключей. Если для шифрования сообщения используется заданное подмножество ключей, то для дешифрирования сообщения потребуются оставшиеся ключи .

Широковещательная передача сообщения

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

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

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

Существуют и другие способы широковещательной передачи , ряд из них позволяет избежать описанной проблемы. Эти способы обсуждаются в разделе 22.7.

Табл. 3-3.

Шифрование сообщения в трехключевой системе.

Шифруется ключами Должно быть расшифровано ключами

Ка Кв и Kc

Кв Ка и Кс

Кс Ка и Кв

Ка и Кв Кс

Ка и Кс Кв Кв и КсКа

3.6 Разделение секрета

Вообразите, что вы изобрели новый, сверхлипкую, сверхсладкую сливочную тянучку или соус для гамбург еров, который еще безвкуснее, чем у ваших конкурентов. Это очень важно, и вы хотите сохранить изобретение в секрете. Только самым надежным работникам вы можете сообщить точный состав ингредиентов , но вдруг и кто-то из них подкуплен конкурентами? Секрет выкрадут, и немного погодя каждый в квартале будет делать гамбургеры с таким же безвкусным соусом, как ваш.

Предлагаемая схема называется разделением секрета. Есть способы взять сообщение и разделить его на части [551]. Каждая часть сама по себе ничего не значит, но сложите их - и вы получите сообщение . Если это