Криптографические протоколы (стр. 2 из 5)

Теорема 2.1.1 Протокол A-DH обеспечивает свойство PFS.

Док-во: предположим, что долговременный ключ K=F( ^x1x2 mod p) скомпрометирован. Противник знает  ^r1 и  ^(r2K)K-1 mod p º ^r2 . При данных условиях вычисление сеансового ключа S₂= ^r2r1 mod p эквива-лентно решению проблемы DH (Диффи-Хеллмана) для групп простого порядка. #

Рассмотрим теперь протокол Диффи-Хеллмана для групп [2].

Протокол GDH.2. Пусть M = {M₁ , M₂ …M_n} – множество пользователей, которым необходимо выработать общий ключ S_n. GDH.2 протокол выполняется за n шагов. На первой стадии (n-1 этапе) идет сбор информации от отдельных участников группы, а на второй стадии (n шаге) всем рассылается материал для вычисления общего ключа. Предварительный этап. Пусть p – простое и q – простой делитель p-1. Пусть G-циклическая подгруппа Z_p^* порядка q и образующий элемент G. Этап i: M_i выбирает случайное r_i Î_R Z_q^* , M_i ® M_i+1 : { ^{r1…ri / rj} | jÎ[1,i]},  ^r1…ri . Этап n: M_n выбирает случайное r_n Î_R Z_q^* , M_n ®Каждому M_i : { ^{(r1…rn) / ri} | iÎ[1,n]}. Общим ключом будет значение  ^r1…rn .

Данный протокол можно модифицировать для обеспечения аутентификации ключа. Такая модификация отличается от выше приведенного только последним этапом. Предполагается, что M_n имеет с каждым M_i общий секрет K_in=F(^xixn mod p), где x_i-секретное долговременное значение M_i , ^xi mod p –долговременный открытый ключ M_i .

Протокол A-GDH.2. Этапы c 1 по n-1 : такие же, как и в GDH.2. Этап n: M_n выбирает случайное r_n Î_R Z_q^* , M_n ®Каждому M_i : { ^{r1…rnKin/ ri} | iÎ[1,n]}. При получении M_i вычисляет  ^{(r1…rnKin/ ri)Kin-1ri} =^r1…rn S_n .

В этом протоколе каждый участник группы вырабатывает общий аутентичный ключ с M_n. Более того, если мы доверяем M_n , то каждый участник группы может быть уверен, что такой же ключ имеют и все участники группы, т.е. они выработали общий групповой ключ. Пример протокола для четырех участников приведен на рис. 1.

Очевидно, что протокол обладает свойством контрибутивности, поскольку в результирующем ключе S_n есть вклад i-го участника группы в виде степени r_i.

Теорема 2.1.2 Протокол A-GDH.2 обеспечивает свойство PFS.

Док-во: Предположим, что долговременные ключи K_in, iÎ[1,n] скомпрометированы, тогда противник в состоянии вычислить подмножество V={a^П(S)| SÌ{r₁,…,r_n}}. Но, как было показано в [2], по такому V не возможно восстановить сеансовый ключ S_n. #

Рассмотрим устойчивость описанного протокола к атакам по известным ключам.

Пусть S_n(M_i) – сеансовый ключ, вычисленный каждым M_i. Для 0<i<n-1 можно записать его как a^CiriK-1in. Для M_n S_n(M_n)=a^Cnrn, где ci возможно известно противнику C. C также знает подмножество {a^П(S)| SÌ{r₁,…,r_n}}. В данных условиях нахождение a^Kin или a^K-1in невозможно, если вычислительно трудно решить проблему “распознавания Диффи-Хеллмана” [1].

Однако, некоторые из атак возможны. Если С попытается послать M₁ некоторое a^c1 на последнем этапе протокола (где с₁ выбирается противником), то M₁ в результате получит неверный ключ S_n(M₁)=a^c1r1K-11n, обнаружит проблему и просто заново запустит протокол обмена. Допустим, что противник каким-то образом получил этот неверный ключ (заметим, что на практике это маловероятно). При повторном выполнении протокола С может подменить сообщение от M_n-1 к M_n на

a^c1r1K1n-1,…,a^c1r1.

С подменил первое и последнее слово в сообщении, остальные слова не изменялись. Тогда M_n вычислит ключ S_n(M_n)=(a^c1r1)^rn. M_n также вычислит

(a^c1r1K1n-1)^rnK1n=a^c1r1rn

и отошлет это значение M₁ в последнем этапе протокола. В результате С будет знать ключ M₁. Но (хотя в работе [1] это и не отмечается), общий групповой ключ опять не совпадет, и через некоторое время протокол придется повторить снова. Все дело во времени определения конфликта ключей. Однако, в такого типа атаке очень много условностей, и поэтому ее можно отнести к разряду теоретических, а не к реально осуществимым атакам. Кроме того, как указано в [1], простым средством предотвращения таких атак является вычисление в качестве ключа S_n=h(S_n(M_i ), где h() – любая хеш-функция.

Необходимо заметить, что вышеупомянутый протокол A-GDH.2 выполняет неявную аутентификацию ключа, причем в довольно слабой форме, поскольку ключ не аутентифицируется непосредственно между каждыми любыми двумя M_i и M_j участниками (i¹j). Последний участник M_n (будем далее называть его контролирующим группы, поскольку через него проводятся ключевые операции протокола) отвечает за использование аутентичных ключей K_in, i=1 ... n-1, от которых и зависит аутентификация. Следовательно, участник M_n должен быть лицом, которому все доверяют. Это может быть схема с доверенным сервером в качестве M_n. В противном случае M_n сможет разбить группу на две части без обнаружения этого (поскольку он может перехватывать все сообщения и таким образом получить необходимую информацию в виде  ^{r1…ri / rj} для "i,j).

Поэтому необходимо трансформировать протокол, что и было сделано в работе [1].

2.2 Протокол SA-GDH.2

Для описания протокола требуется несколько дополнительных определений.

Опр. 2.2.1. Пусть R – протокол обмена для n участников и M – множество участников. Мы будем говорить, что R является протоколом, обеспечивающим полную(complete) аутентификацию группового ключа, если для каждых i,j (0< i¹j £n) участники M_i и M_j вычислят общий ключ S_i,j, только если S_i,j был получен при участии каждого M_p Ì M.

Другими словами, полная аутентификация группового ключа есть аутентичный обмен для выработки ключа между всеми парами (M_i, M_j) при (0< i¹j £n).

Для выполнения этого определения можно модифицировать протокол A-GDH.2 в следующий:

Протокол SA-GDH.2. Этап i (0< i <n): 1. M_i получает множество промежуточных величин { V_k | 1£ k £ n}. (в данном контексте можно сказать, что M₁ получает пустое множество на первом этапе):  ^{(r1…ri-1 / rk)(K k1…K k(i-1))} при k £ (i-1) V_k =  ^{(r1…ri-1)(K k1…K k(i-1))} при k > (i-1) . 2. M_i обновляет каждое V_k следующим образом: (V_k ) ^{riK ik} =  ^{(r1…ri / rk)(K k1…K ki)} при k < i V_k = (V_k ) ^{riK ik} =  ^{(r1…ri)(K k1…K ki)} при k > i . V_k при k = i (Замечание: на первом этапе M₁ выбирает V₁ = .) Этап n: 1. M_n рассылает множество всех V_k участникам группы. 2. При получении M_i выбирает свое V_i = ^{(r1…rn / ri)(K1i…K ni)}. M_i вычисляет (V_k ) ^{ri(K1i-1… K ni-1)}= ^r1…rn . Заметим, что вместо того, чтобы вычислять n обратных элементов, M_i может вычислять 1 обратный элемент P_i^-1=(K_1i^-1… K_ni^-1), где P_i=(K_1i… K_ni).

В протоколе SA-GDH.2 требуется, чтобы каждый участник группы имел некоторый общий ключ с любым другим участником (это значение K_ji). Однако, как уже было замечено для каждого такого ключа K_ji не требуется нахождение обратного K_ji^-1. Таким образом, достаточно получить такие ключи перед началом работы в группе и затем эти ключи могут оставаться постоянными, не добавляя лишних действий в протокол.

Протокол основан на кольцевой схеме взаимодействия, т.е. данные проходят по кругу и лишь на последнем этапе идет широковещательная рассылка. Данные, которые передаются, представляют собой множество из n элементов. i-й элемент содержит своеобразное «накопление ключа» для i-го участника. Во время обновления ключа каждый из участников вносит свой вклад в формирование ключа. Только пройдя полный круг, i-й элемент множества будет иметь вклады всех участников и их секретные ключи для связи с i-м абонентом (рис. 1). Это позволяет избежать явной замены противником одного из значений на какое-то другое, выгодное ему (возможное вмешательство противника рассмотрим далее)