Курс "Защита информации", кафедра радиотехники, Московский физико-технический институт (МФТИ)

2010: Главная Экзамен Лекции Семинары Проекты Эссе | Преподаватели Литература | Архив: 2009 2008-fall 2008 2007 2006 2005 2004 2003 | English
HTML-версия эссе "2003 CLIQUES Group Key Agreement", 2003_CLIQUES_Group_Key_Agreement, 2003, сгенерированная из pdf/rtf.
Конвертация не вcегда корректна. Смотрите исходный pdf.
Проект CLIQUES распределения ключей для групп с динамическим составом участников.
Введение
В настоящее время организация безопасной связи внутри групп абонентов с динамически меняющимся составом участников является достаточно сложной задачей, отличающейся по своему качественному составу от классических задач криптографии. Она включает в себя множество сопутствующих задач, начиная от создания основных алгоритмов и заканчивая созданием конечных приложений и коммуникационных систем. Выделяют два основных аспекта безопасности при работе в группах - секретность (т. е. все взаимодействия внутри группы остаются секретными для лиц, не являющихся участниками группы) и аутентификация.
Стандартным подходом к обеспечению безопасности для групп является получение некоторой секретной величины, известной только участникам группы. Криптографические протоколы, в которых происходят выработка и распространение этой величины внутри группы известны как распределение ключа группы (group key establishment). В случае, когда это значение не вырабатывается в протоколе, а приобретается заранее кем-либо из участников, протокол носит название протокола распространения ключей в группе(group key distribution). В случае, когда каждый участник группы участвует в генерации этого секретного значения, мы получаем протокол обмена ключами (group key agreement). В обоих случаях только действующие участники группы имеют доступ к этому групповому секрету (действующие потому, что предполагается высокая динамичность группы). При любом присоединении нового участника или выходе участника из группы секретное значение меняется для предотвращения НСД со стороны лиц, не входящих в группу.
1 Используемые в протоколах термины и обозначения
Определим некоторые обозначения: п - число участников протокола; i, j - индексы для участников групп; Mi - i-ый участник группы;
G - циклическая группа G порядка q, где q — простое; α,g - образующие элементы в группе G; xi - долговременный секретный ключ Mi; ri - случайное (секретное) число ∈ Zq, вырабатываемое Mi; Sn - групповой ключ n участников; Sn(Mi) - вклад Mi -го участника в групповой ключ; Ку - долговременная секретная величина, выработанная Mi и Mj,, Щ.
Все вычисления проводятся в циклической группе G простого порядка q, причем p=kq+1 для некоторого k∈Ν.
2 Протоколы аутентичного обмена ключами
Простейшей схемой получения общего ключа является схема с доверенным сервером, в котором кто-либо посылает ему запрос на связь с другими абонентами, и сервер рассылает каждому абоненту общий ключ для связи внутри группы и список участников группы, зашифрованные ключом абонента. Но при такой схеме возникают сложности при высокой динамичности группы, обусловленные невозможностью одновременной обработки сервером большого числа запросов. Поэтому рассмотрим некоторые специально созданные протоколы для получения общего ключа участниками группы.
В рамках предварительного знакомства приведем аутентичный обмен для выработки ключа для двух сторон. Затем приведем расширение этого протокола для n сторон. Приводимые протоколы базируются на схеме Диффи-Хеллмана.
2.1 Протоколы A-DH, GDH.2 и A-GDH.2
Прежде чем привести описание протокола аутентичного обмена для двух сторон A-DH, важно подчеркнуть, что существует множество разнообразных протоколов аутентичного обмена для выработки ключа, но одни из них не поддерживают двусторонний вклад в общий ключ (как в El Gamal), другие требуют большого числа сообщений или предполагают априорный доступ к сертифицированным долговременным ключам. Необходимо также отметить, что протокол предполагает наличие у участников аутентичных открытых ключей друг друга.
Очевидно, что в полученном в результате ключе имеется вклад обоих сторон (т.к. r1 и r2 случайны и вырабатываются разными сторонами), т.е. протокол обладает контрибутивностью. В то же время обеспечивается
аутентификация ключа, поскольку при его формировании участвуют открытые ключи обоих абонентов, которые переданы по аутентичному каналу.
Рассмотрим теперь протокол Диффи-Хеллмана для групп .
Данный протокол можно модифицировать для обеспечения аутентификации ключа. Такая модификация отличается от выше приведенного только последним этапом. Предполагается, что Mn имеет с каждым Mi общий секрет
где xi-секретное долговременное значение долговременный открытый ключ Mi.
В этом протоколе каждый участник группы вырабатывает общий аутентичный ключ с Mn. Более того, если мы доверяем Mn , то каждый участник группы может быть уверен, что такой же ключ имеют и все участники группы, т.е. они выработали общий групповой ключ.
Очевидно, что протокол обладает свойством контрибутивности, поскольку в результирующем ключе Sn есть вклад i-го участника группы в виде степени ri.
3 Проект CLIQUES
Целью данного проекта являлась разработка протокола обмена для выработки ключа для групп. Такой протокол должен поддерживать все групповые операции по удалению, включению новых участников в группу. На основе этого протокола необходимо было создать специальный прикладной программный интерфейс (CLQ-API), позволяющий работать приложениям в неких абстрактных группах. Протокол во многом основывается на вышеописанных протоколах аутентичного обмена. Ограничимся рассмотрением только математических принципов проекта.
В качестве базового протокола обмена для выработки общего ключа был выбран протокол A-GDH.2 . Предполагается, что участники группы уже сформировали общий ключ.
Рассмотрим основные операции, которые позволяет выполнять разработанный протокол.
1. Операции для одного участника группы: включают в себя добавление или удаление одного участника группы. Данные ситуации появляются, когда кто-то хочет присоединиться к группе или покинуть ее. Эти операции могут проводится контролером группы или по согласию каждого участника группы (в зависимости от используемой политики безопасности).
2. Операции для нескольких участников: также включают в себя добавление и удаление. Однако есть отличия, обусловленные желанием проводить операции с несколькими участниками сразу, а не с каждым в отдельности:
•    массовое присоединение: несколько участников хотят присоединиться к существующей группе;
•    слияние групп: две или более групп желают соединиться в одну;
•    массовый выход из группы: несколько участников хотят покинуть группу;
•    разделение групп: группа распадается на две или более частей.
Итак, список операций, выполняемых протоколом, выглядит следующим образом:
•   присоединение (JOIN): новый участник добавляется в группу;
•   слияние (MERGE): один или более участников добавляются в группу;
•   выход из группы (LEAVE): один или более участников покидают группу;
•   обновление ключа (KEY REFRESH): генерация нового ключа для группы.
Для простоты, считается, что последний участник группы является контролирующим группы (это может быть легко исправлено и не является критическим требованием).
Присоединение
Операция добавляет нового участника Mn+1 к группе из n участников. Во время операции вычисляется новый групповой ключ Sn+1, и Mn+1 становится новым контролирующим группы. Предполагая, что Mn является текущим контролирующим группы, протокол выглядит следующим образом:
1.   Mn вырабатывает новое значение гп и получает множество1 чисел
Затем M посылаетсяMn+1.
2.   После получения сообщения Mn+1 вырабатывает число rn+1 и вычисляет значениедля всех i из [1,п]. Затем это множество рассылается всей группе.
3.При получении каждый Mi вычисляет групповой ключ как
вычисляет ключ, используя
сообщение из шага (1).
Шаги (1) и (2) требуют n экспоненцирований, шаг (3) требует одно
экспоненцирование для каждого участника группы. Общее число
экспоненцирований для получения ключа равно 2n+1 (считается, что на третьем
шаге экспоненцирования происходят одновременно и по времени равны
одному).
Слияние
Операция используется для добавления k>0 участников к существующей группе из n>1 участников. Пусть m=n+k. Во время операции вырабатывается новый групповой ключ Sm, и Mm становится новым контролирующим группы. Предполагая, что Mn является текущим контролирующим группы, протокол выглядит следующим образом:
1.   Mn вырабатывает новое значение гп и вычисляет2. Затем это сообщение отправляется к Mn+1.
2.Каждый участник Mj ,j=n+1,…,m-1 вырабатывает число rj и вычисляет
. Это сообщение посылается Mj+1.
3.   После получения сообщения, Mm рассылает полученное значение всей группе
4.   После получения сообщения каждый участникMi, i=1,2,…,m-1 группы вычисляети посылает его Мт.
5.Mm вырабатывает rm и получает множество
Затем оно посылается группе.
1 Необходимые данные для вычисления множества Mn берет из последнего этапа протокола A-GDH.2 и возводя затем нужные элементы в степеньполучает необходимые значения.
2 Значениеможет получить из предыдущего ключа путем возведения в степень
6. При получении сообщения шага (5) каждыйвычисляет
групповой ключ какАналогично,
вычисляет ключ, используя сообщение из шага (3). Если k=2, то шаг (2) не нужен, в остальном протокол выглядит также. Шаги требуют всего k модульных экспоненцирований. Также, как и ранее, шаги (4) и (6) требуют по одному для каждого участника. Шаг (5) требует n+k-1 экспоненцирований. Число экспоненцирований для присоединения k участников равно n+2k+1.
Операция присоединения также может быть использована для добавления k участников к группе. Это потребует повторить операцию присоединения k раз -соответственно возрастает трудоемкость операции. Таким образом для массового добавления участников группы лучше использовать операцию слияния. Если использовать операцию слияния для добавления одного участника к группе, то получается на два экспоненцирования больше, чем для операции присоединения. Итак, присоединение используется для добавления одного участника к группе, а слияние - нескольких.
Выход из группы
Операция выхода из группы удаляет k участников из n участников текущей группы. Во время операции вычисляется новый групповой ключ становится новым контролирующим группы, если Mn покидает группу. Для простоты предположим, что только один участник Md выходит из состава группы. Протокол выглядит следующим образом:
1.Mn вырабатывает новое г„ и получает множество
Затем М рассылается всем.
2.При получении сообщения.вычисляет
вычисляет новый групповой ключ используя старое значение.
Участникне может вычислить новый групповой ключ, т.к. контролирующий группы не вычислил вспомогательный ключЕсли несколько
участников покидают группу, то контролирующий группы не вычисляет нужные значения для выходящих из группы участников на шаге (1). Если из группы выходит контролирующий, то вышеописанные операции выполняет предпоследний участник группыБолее того, поскольку новый контролирующий группы не может удалить из ключа долговременные ключи (они были у прошлого контролирующего группы), каждый участник Mi должен заново вычислить свой случайный сеансовый ключ какперед
выполнением шага (2). Шаг (1) требует n-k экспоненцирований. Шаг (2) требует одно экспоненцирование от каждого участника группы. Таким образом, операция выхода из группы требует n-k+1 модульных экспоненцирований.
Обновление ключа
Операция обновления ключа выполняет замену группового ключа на новый. Использование этой операции зависит от используемой политики приложения, использующего CLIQUES или политики работы с ключами для предприятия. Эта операция выглядит также, как и операция выхода из группы с k=0, т.е. на первомшаге Mn вырабатывает множество
для всех участников группы.
Приведенный протокол является протоколом аутентичного обмена и обладает свойством контрибутивности, что гарантирует независимость ключа (так как в его формировании участвуют все участники группы), может обеспечивать подтверждение ключа (как это было описано выше), устойчив к атакам по известному ключу (многие свойства следуют из рассмотренного ранее протокола A-GDH.2).
Таким образом, с использованием приведенных выше операций достигается полноценная работы группы. На основе приведенного протокола был разработан интерфейс прикладного программирования (Application Programming Interface - API). Он принят как проект стандарта для Internet. Программные реализации математических принципов, используемых в протоколах, можно найти в крипто-библиотеках Crypto++[3] и RSAREF[4]. Между тем, приведенная схема работы не лишена недостатков. Во-первых - и это, наверное, самый главный из них - приходится менять ключ для всей группы при изменении ее состояния. Это может подходить для небольших групп, но при большом числе участников становится серьезной трудностью. В этом случае все будет зависеть от динамики группы. Также решающую роль играет пропускная способность каналов связи между участниками, поскольку в случае появления участника со слабым каналом (тем более, если это контролирующий группы) встает вопрос о временных факторах формирования ключа. Возможна ситуация непроизвольного «выкидывания» (в случае отсутствия необходимых механизмов) участника, использующего канал с низкой пропускной способностью в случае высокой динамики группы. Он просто не будет успевать получать новые данные для формирования ключа. Во-вторых - довольно высокое число экспоненцирований в операциях протокола.
Используемые работы:
[1] G. Ateniese, M. Steiner, G. Tsudik "Authenticated Group Key Agreement and Friends",
[2] M. Steiner, G. Tsudik, M. Waidner "Diffie-Hellman key distribution extended to groups", in ACM
Conference on Computer and Communications Security, pp.31-37, ACM Press, Mar. 1996. [3] W. Dai "Crypto++", 05.1999, http://www.eskimo.com/~wedai/cryptolib.html [4] RSA Laboratories, http://www.rsalab.com


Page last update: Fri Jun 10 10:11:24 2005 MSD.
Website last update:
Rambler's Top100 Рейтинг@Mail.ru