|
Криптографические протоколы
Введение В настоящее время
организация безопасной связи внутри групп абонентов с динамически меняющимся
составом участников является достаточно сложной задачей,отличающейся по своему
качественному составу от классических задач криптографии. Она включает в себя
множество сопутствующих задач, начиная отсоздания основных алгоритмов и
заканчивая созданием конечных приложений и коммуникационных систем. Выделяют два
основных аспекта безопасности при работе в группах – секретность (т. е. все
взаимодействия внутри группы остаютсясекретными для лиц, не являющихся
участниками группы) и аутентификация. Стандартным подходом к обеспечению
безопасности для групп является получение некоторой секретнойвеличины, известной
только участникам группы. Криптографические протоколы, в которых происходят
выработка и распространение этой величины внутри группыизвестны как
. В случае,
когда это значение невырабатывается в протоколе, а приобретается заранее кем-
либо из участников, протокол носит название В
случае, когда каждый участник группы участвует в генерации этого секретного
значения,мы получаем В обоих случаях только действующие участники группыимеют доступ
к этому групповому секрету (действующие потому, что предполагается высокая
динамичность группы). При любом присоединении нового участника иливыходе
участника из группы секретное значение меняется для предотвращения НСД со
стороны лиц, не входящих в группу. Данная работа представляет собой обзор
существующих материалов по криптографическимпротоколам для динамических групп.
Построена она по следующей схеме: В разделе 1.2
приводятся используемые обозначения В разделе рассмотрены протоколы получения общего ключа
для группы лиц. Приведеноописание протокола Диффи-Хеллмана с аутентификацией,
устойчивость его к различным атакам, протокол Диффи-Хеллмана выработки общего
ключа для групп иего расширение до протокола с аутентификацией. В разделе рассмотрена
конкретная реализация протоколов для групп. Приведены математические основы.
Тестовые величины, сравнения различных реализаций иформаты данных не
рассматривались. Эту информацию можно получить из работ [3,4,5]. Протокол обмена для выработки общего ключа ( – протокол распределения ключей, в котором общий
ключвырабатывается двумя или более участниками как функция от информации,
вносимой каждым из них, причем таким образом, что никакая другая сторона не
можетпредопределить получаемый в результате общий секрет. Perfect forward secrecy – PFS аутентификации ключа ( Key
confirmation & key integrity Протокол
обеспечивает Протокол обладает
свойством , если сформированный
ключ зависит от секретных данных, внесенныхкаждым из участников. –
множество участников, а неявную аутентификацию
ключа M не
могла получить доступ к
– протокол обмена, в смысле опр.
1.1.4, обеспечивающийнеявную аутентификацию ключа. , если участник протокола
уверен, чтодругой участник (или группа) действительно обладает ключом,
полученным в результате протокола. , если участник уверен, что
полученный им секретный ключ представляет собой функцию
отиндивидуальных вкладов всех других участников. Таким образом, любое
вмешательство в сформированный ключ (или формируемый) нарушает данное
свойство,если ключ получается отличным от предполагаемого. 1.2 Используемые в протоколахтермины и
обозначения i, j -
образующие элементы в группе
, вырабатываемое
(M - долговременная секретная величина,
выработанная Все
вычисления проводятся в циклической группе , где Для того, чтобы
предотвратить атаки методами подмены или утечки секретных величин, каждый
участник протокола должен иметьвозможность проверить, что те значения, которые
он получает, являются элементами подгруппы. – общие для всех пользователей. Поскольку онивырабатываются один раз,
необходимо качественно проработать процесс генерации, чтобы исключить (возможно
умышленное) получение слабых или каких-тоспецифических простых чисел. В
частности, рекомендуется использовать метод из стандарта США, описанный в FIPS
186 или же наоснове метода, изложенного в стандарте ГОСТ Р34.10-94. В
таком контексте, возможности активного противника довольно сильно
ограничены.Действительно, любое сообщение может быть представлено как
порядка упирается в проблему дискретного
логарифмирования. Простейшей схемой получения общего ключа является схема с
доверенным сервером, в которомкто-либо посылает ему запрос на связь с другими
абонентами, и сервер рассылает каждому абоненту общий ключ для связи внутри
группы и список участников группы,зашифрованные ключом абонента. Но при такой
схеме возникают сложности при высокой динамичности группы, обусловленные
невозможностью одновременнойобработки сервером большого числа запросов. Поэтому
рассмотрим некоторые специально созданные протоколы для получения общего ключа
участниками группы. В рамках предварительного знакомства приведем
аутентичный обмен для выработкиключа для двух сторон. Затем приведем расширение
этого протокола для 2.1 Протоколы A-DH, GDH.2 и A-GDH.2 Прежде
чем привести описание протокола аутентичного обмена для двух сторон A-DH, важно
подчеркнуть, что существует множестворазнообразных протоколов аутентичного
обмена для выработки ключа, но одни из них не поддерживают двусторонний вклад в
общий ключ (как в El Gamal), другие требуют большого числа сообщений
илипредполагают априорный доступ к сертифицированным долговременным ключам.
Многие не обладают свойством . Поэтому, наиболее подходящим протоколом
для групп всоответствии с [1] считают A-DH. Необходимо также отметить, что
протокол предполагает наличие у участников аутентичных открытых ключей друг
друга. , Предварительный этап. x M x1 2 q
получает r r2r1 .
Очевидно, что в полученном в результате ключе имеется вклад
обоих сторон (т.к. r1 и r2 случайны ивырабатываются разными сторонами), т.е.
протокол обладает . В то же время обеспечивается
аутентификация ключа, поскольку при егоформировании участвуют открытые ключи
обоих абонентов, которые переданы по аутентичному каналу. Док-во: ) скомпрометирован.Противник знает
эквива-лентно решению проблемы DH(Диффи-Хеллмана) для групп простого
порядка. # 2 этапе) идет сбор информации от отдельных
участников группы, а на второй стадии ( –
простое и порядка q
r [1 M
Z
(r [1 Данный протокол
можно модифицировать для обеспечения аутентификации ключа.Такая модификация
отличается от выше приведенного только последним этапом. Предполагается,что
x , Этапы i i a n В этом протоколе каждый
участник группы вырабатывает общий аутентичный ключ с
, то
каждый участник группы может быть уверен, чтотакой же ключ имеют и все участники
группы, т.е. они выработали общий групповой ключ. Пример протокола для четырех
участников приведен на рис. 1. n
Предположим, что долговременные ключи ] скомпрометированы, тогда противник в
состояниивычислить подмножество Ì не возможно восстановить сеансовый
ключ Пусть
< K-
1 C }}.В
данных условиях нахождение in Однако, некоторые из атак возможны. Если на последнем этапе протокола (где
( 1 , обнаружит проблему и
просто заново запустит протоколобмена. Допустим, что противник каким-то образом
получил этот неверный ключ (заметим, что на практике это маловероятно). При
повторномвыполнении протокола K . n 1 K r в последнем этапе протокола. В
результате . Но (хотя в работе [1]
это и не отмечается), общий групповойключ опять не совпадет, и через некоторое
время протокол придется повторить снова. Все дело во времени определения
конфликта ключей. Однако, в такого типаатаке очень много условностей, и поэтому
ее можно отнести к разряду теоретических, а не к реально осуществимым атакам.
Кроме того, как указано в [1], простым средством предотвращения таких атак
являетсявычисление в качестве ключа
Необходимо заметить, что вышеупомянутый
протокол A-GDH.2 выполняет , причем в
довольно слабой форме, поскольку ключ неаутентифицируется непосредственно между
каждыми любыми двумя ). Последний участник ,поскольку через
него проводятся ключевые операции протокола) отвечает за использование
аутентичных ключей n n сможет
разбить группу на две части без обнаруженияэтого (поскольку он может
перехватывать все сообщения и таким образом получить необходимую информацию в
виде i 2.2 Протокол
SA-GDH.2 – протокол обмена для
протоколом, обеспечивающим
полную( M был получен при участии каждого
Другими
словами, полная аутентификация группового ключа есть аутентичный обмен
длявыработки ключа между всеми парами (
Для выполнения этого
определения можно модифицировать протокол A-GDH.2 в следующий: SA-GDH.2 получает множество
промежуточных величин { }. (в данном контексте можно
сказать, что =
k
на первом этапе M k = обратных элементов, -1
В протоколе SA-GDH.2 требуется, чтобы каждый участник группы имел
некоторый общий ключ с любым другимучастником (это значение
не требуется нахождение обратного . Таким образом, достаточно получить такие ключи передначалом работы
в группе и затем эти ключи могут оставаться постоянными, не добавляя лишних
действий в протокол. Протокол основан на кольцевой схеме взаимодействия,
т.е. данные проходят по кругу и лишь на последнем этапе идет
широковещательнаярассылка. Данные, которые передаются, представляют собой
множество из -го участника. Во время обновления ключа каждый
изучастников вносит свой вклад в формирование ключа. Только пройдя полный круг,
-м абонентом (рис. 1). Это позволяет избежать явной
замены противником одного из значений на какое-тодругое, выгодное ему (возможное
вмешательство противника рассмотрим далее) Однако SA-GDH.2 имеет более
высокую «вычислительную стоимость» по сравнению с A-GDH.2. Прежде всего, он
требует ( экспоненцирований в A-GDH.2. К этому еще
добавляется работа по формированию общихключей для каждой пары абонентов (если
они не вычислены заранее): на последнем этапе проводится одно экспоненцирование
– как и в A-GDH.2. На рис. 1 приведены примеры протоколов A-GDH.2 и SA-
GDH.2. Как показано в [1],
протокол SA-GDH.2 обеспечивает полную аутентификацию группового ключа вычислили одинаковый
ключ в результате выполнения протокола. Пусть
), и предположим, что некто j обозначают величины, полученные
на последнем этапе протокола.
Напомним, что в соответствии с
протоколом n Поскольку
все участники группы сделали вклад в ключ, то можно записать, что
n 1i являются
секретными, то получаем противоречие. # В работе [1] также отмечается, что
обсуждаемый протокол обладает устойчивостью к атакам по известному ключу
( ), однако строгого формального доказательства
неприведено, авторы лишь отмечают, что это легко пронаблюдать на приведенной
выше атаке на A-GDH.2. подтверждение
ключа . Не для каждого протокола этосвойство является необходимым: например,
оно не нужно, если взаимодействие с полученным ключом происходит немедленно. Но
тем не менее свойство подтвержденияключа является желательным для протоколов
обмена по следующим причинам: 2. Исключается возможность вычисления
неправильного ключа без обнаружения этого (в случаеперерыва между выработкой
общего ключа и непосредственно передачей данных). С другой стороны, пока
еще нет точного определения, что же такое подтверждение ключа для групп. Если
братьполное подтверждение ключа, то это достигается путем получения каждым
участником ключа и затем доказательства всем, что он знает этот ключ. как . Это может быть легко
достигнуто в обоих протоколах путем добавления )) M –хэш-функцию, как это было
определено выше. ) и проверяет
равенство: )) . В [2,5] замечено, что в A-GDH.2 и SA-GDH.2
подтверждение и неявная аутентификация ключа образуют полезный в некоторых
случаях побочныйэффект –
для всех участников группы. Это еще раз доказываетнеобходимость выделения
Включение подтверждения ключа в протокол SA-GDH.2 приводит к
интересному результату, а именно: знает, что ключ, выработанный им,
содержит вкладкаждого участника группы. подтверждения
ключа . Если бы отсутствовало подтверждение ключа, то участники группы не
могли бы убедиться в истинности своего ключа. целостность
группы (неформ.) Групповой протокол
обмена для выработки общего ключа является , если каждый участник протокола уверен, что каждый
другой участник сделал вклад в групповой ключ. Свойство проверямой
контрибутивности включает в себя свойство целостности группы.
Обратноеутверждение неверно, поскольку целостность группы может быть обеспечена,
если участник группы будет простоподписывать сообщение
отсылать его дальше. Проверяемой контрибутивности в данном случае нет. В то же
время проверяемая контрибутивность можетвыполняться, если в формировании ключа
участвовало лицо, стороннее по отношению к группе. Таким образом противник может
влиять на протокол. Однако следует заметить, что даже если выполняются
свойства (неявной, полной) аутентификации и подтвержденияключа, свойство
целостности ключа в вышеприведенном протоколе SA-GDH.2 не
достигается. Предположим, что имеется активный противник, который может
вмешиваться в передачу, подменять имодифицировать данные. Он может провести
какое-либо экспоненцирование данных на этапе (1) и/или (2) и это
останетсянезамеченным. Пусть он просто возводит в квадрат все величины на этапе
(2). Тогда вычислит , т.е. квадрат предполагавшегося ключа. Все
остальныеучастники группы получат то же самое. Подтверждение ключа здесь не
помогает, поскольку злоумышленник вторгается в протоколперед тем, как
Как было справедливо
замечено в [1], протокол SA-GDH.2 подвержен (пока) только мультипликативному
(экспоненциальному) влиянию противника наключ, т.е. можно получить ключ
-ключ,
предполагаемый впротоколе. Авторы задаются вопросом: так ли важна целостнось
ключа в протоколе обмена с проверяемой контрибутивностью? Для обеспечения
целостности можно воспользоваться сторонними средствами обеспечения целостности
данных вовремя передачи – например, проверять целостность пакетов при отправке
по сети. На последнем же широковещательном этапе никаких сторонних средств не
требуется,т.к любое вмешательство будет обнаружено из-за свойства подтверждения
ключа для контролирующего группы. Приведем таблицу сравнения протоколов (по вычислительным
требованиям). Понятно, что различные реализациибудут различаться по скорости
выполнения и объему кода, а также типа используемых процессоров – это отдельная
тема и с математической точки зренияне представляет интереса, нужные таблицы
приведены в [2,3,4,5]. Поэтому ограничимся приведением лишь
вычислительныххарактеристик в таблице 1. Экспоненцирований для
Всего экспоненцирований Вычисления обр. элементов для
Вычисления обр. элементов
для Всего
вычислений обр. элементов
Умножений для -1
n Полученные в результате приведенных протоколов общие ключи
могут использоваться как ключи для секретнойсвязи внутри группы, служить для
аутентификации участников группы, выполнять роль секретного ключа при
формировании групповой подписи и т.д. Целью
данного проекта являлась разработка протокола обмена для выработки ключа
длягрупп. Такой протокол должен поддерживать все групповые операции по удалению,
включению новых участников в группу. На основе этого протокола необходимо
былосоздать специальный прикладной программный интерфейс (CLQ-API) , позволяющий
работать приложениям в неких абстрактныхгруппах. Протокол во многом основывается
на вышеописанных протоколах аутентичного обмена. Ограничимся рассмотрением
только математических принциповпроекта. Не будем рассматривать полученные
результаты (по эффективности), программные реализации. В качестве
базового протокола обмена для выработки общего ключа был выбран протокол A-GDH.2
(однако возможноиспользование и SA-GDH.2). Предполагается, что участники группы
уже сформировали общий ключ. Операции для одного
участника группы: включают в себя добавление илиудаление одного участника
группы. Данные ситуации появляются, когда кто-то хочет присоединиться к группе
или покинуть ее. Эти операции могут проводитсяконтролером группы или по согласию
каждого участника группы (в зависимости от используемой политики
безопасности). также
включают в себя добавление иудаление. Однако есть отличия, обусловленные
желанием проводить операции с несколькими участниками сразу, а не с каждым в
отдельности: слияние групп: две или
более групп желают соединиться в одну; разделение групп:
группа распадается на две или более частей. ограничением
шифртекста, получаемого на одном ключе для ограничения возможности получения пар
открытыйтекст/шифртекст для проведения криптоанализа (время жизни ключа
определяется выбранной политикой); Итак,
список операций, выполняемых протоколом, выглядит следующим образом:
слияние (MERGE): один или более участников добавляются в
группу; обновление ключа (KEY REFRESH): генерация нового
ключа для группы. Для простоты, считается, что последний
участник группы является контролирующим группы (это может быть легкоисправлено и
не является критическим
требованием). к группе из является текущим
контролирующим группы, протокол выглядит следующим образом: и получает множество n È и вычисляет
значение 3. При
получении каждый 1
= Шаги (1) и (2) требуют экспоненцирований,
шаг (3) требует одно экспоненцирование для каждого участника группы. Общее число
экспоненцированийдля получения ключа равно 2 >0 участников к существующей группе из S
являетсятекущим контролирующим группы, протокол выглядит следующим
образом: и вычисляет r 2. Каждый участник 3. После получения
сообщения, M вырабатывает
1 Î i g .Аналогично, =2, то шаг (2) не нужен, в остальном
протокол выглядит также. модульных
экспоненцирований. Также, как и ранее, шаги (4) и (6) требуют по одному для
каждого участника. Шаг (5)требует +2 участниковк группе. Это потребует повторить
операцию присоединения раз – соответственно возрастает трудоемкость
операции. Таким образомдля массового добавления участников группы лучше
использовать операцию слияния. Если использовать операцию слияния для добавления
одного участника к группе, тополучается на два экспоненцирования больше, чем для
операции присоединения. Итак, присоединение используется для добавления одного
участника к группе, аслияние – нескольких.
участников текущейгруппы. Во время операции вычисляется новый групповой ключ
покидает группу. Для простоты предположим, что
только один участник вырабатывает новое
r [1, 2. При получении сообщения n = не может вычислить новый
групповой ключ, т.к. контролирующий группы не вычислил вспомогательный ключ
. Если несколько участников покидают группу, то
контролирующий группы невычисляет нужные значения для выходящих из группы
участников на шаге (1). n-
1 . Более того, поскольку новый контролирующий группы не может удалить
из ключадолговременные ключи (они были у прошлого контролирующего группы),
каждый участник Шаг (1) требует
экспоненцирований. Шаг (2) требует одно экспоненцирование от каждого участника
группы. Таким образом,операция выхода из группы требует Операция
обновления ключа выполняет замену группового ключа на новый. Использование этой
операции зависит отиспользуемой политики приложения, использующего CLIQUES или
политики работы с ключами для предприятия. Эта операция выглядит также, как и
операция выхода из группы с Приведенный протокол является
протоколом аутентичного обмена и обладает свойством контрибутивности, что
гарантирует независимость ключа (таккак в его формировании участвуют все
участники группы), может обеспечивать подтверждение ключа (как это было описано
выше), обладает свойством и устойчив к атакам по известному
ключу(многие свойства следуют из рассмотренного ранее протокола A-
GDH.2). Таким образом, с использованием приведенных выше операций
достигается полноценная работы группы.На основе приведенного протокола был
разработан интерфейс прикладного программирования ( ). В работах [3,5] приводятся форматы заголовков сообщений и
принципы построения приложений наоснове CLIQUES-API. Он принят как проект
стандарта для Internet. Программные реализации математических принципов,
используемых в протоколах,можно найти в крипто-библиотеках Crypto++[6] и
RSAREF[7]. Между тем, приведенная схема работы не лишена недостатков. Во-
первых – и это, наверное, самый главный из них– приходится менять ключ для всей
группы при изменении ее состояния. Это может подходить для небольших групп, но
при большом числе участников становитсясерьезной трудностью. В этом случае все
будет зависеть от динамики группы. На решение этой задачи были направлены усилия
разработчиков. Также решающую рольиграет пропускная способность каналов связи
между участниками, поскольку в случае появления участника со слабым каналом (тем
более, если этоконтролирующий группы) встает вопрос о временных факторах
формирования ключа. Возможна ситуация непроизвольного «выкидывания» (в случае
отсутствия необходимыхмеханизмов) участника, использующего канал с низкой
пропускной способностью в случае высокой динамики группы. Он просто не будет
успевать получать новыеданные для формирования ключа. Рассмотренные протоколы обмена для выработки общего
ключа предоставляют большие возможности дляразвития безопасных протоколов
коммуникаций для динамических групп. На основе них можно строить сложные
протоколы аутентификации, цифровой подписи,доказательства знания. 1. Цифровые подписи – данный раздел
довольно велик по своему объему. Существует большое число проблем,
связанных с подписями для групп. Прежде всего этопроблемы устойчивости к атакам
объединенных пользователей и проблемы удаления участников группы и их ключей. В
сфере предлагаемой анонимности для участниковгруппы это является серьезной
проблемой. Также до конца не определено межгрупповые взаимодействия и случаи с
одновременным членством в несколькихгруппах (использование нескольких ключей
признается нерациональными) и образование подгрупп. Существующие схемы имеют
предварительный характер. 2. Взаимодействие протоколов с сетевыми
технологиями. Ввиду сугубо практических аспектов данные материалы не
учитывались В настоящее время задачам безопасной связи внутри групп с
динамическим составом участников уделяетсяповышенное внимание благодаря
повсеместному использованию технологий сети Internet. Возможно, в скором времени
появятся новые протоколыраспределения ключей, не содержащие недостатков
описанных протоколов. [1] G.
Ateniese, M. Steiner, G. Tsudik "Authenticated Group Key Agreement and Friends",
in [2] M. Steiner, G. Tsudik, M. Waidner "Diffie-Hellman key
distribution extended to groups", in [3] G.
Ateniese, D. Hasse, O. Chevassut, Y. Kim, G. Tsudik "The Design of a Group
KeyAgreement API", IBM Research Division, Zurich Research Laboratiry. [4]
Y. Amir, G. Ateniese, D. Hasse, Y. Kim, C. Nita-Rotaru, T. Sclossnagle,
J.Schultz, J. Stanton, G. Tsudik "Secure Group Communications in Asynchronous
Networks with Failures: Integration and Experiments", 1999. [5] G.
Caronni, M. Waldvoget, D. Sun, B. Plattner "Efficient Security for Large
andDynamic Multicast Groups", Computer Engineering and Networks Laboratory.
[7] RSA Laboratories, можетбыть вычислен посредством
выбора случайного элемента = n ' n-1 n
| |
