Протоколы A-DH, GDH.2  и A-GDH.2

Прежде чем привести описание протокола аутентичного обмена для двух сторон A-DH, важно подчеркнуть, что существует множество разнообразных протоколов аутентичного обмена для выработки ключа, но одни из них не поддерживают двусторонний вклад в общий ключ (как в El Gamal), другие требуют большого числа сообщений или предполагают априорный доступ к сертифицированным долговременным ключам. Многие не обладают свойством PFS. Поэтому, наиболее подходящим протоколом для групп в соответствии с [1] считают A-DH. Необходимо также отметить, что протокол предполагает наличие у участников аутентичных открытых ключей друг друга.  

Протокол A-DH. Пусть p,q,G – величины, определенные выше и пусть образующий элемент G.
Предварительный этап. Пусть x1 и x2 – два целых числа, т. ч. 1 x1 ,x2  q-1. Пусть M1 и M2 – два участника, которые хотят выработать общий ключ и пусть (x1 ,x1 mod p) и (x2 ,x2 mod p)- секретные и открытые ключи M2  и M2 соответственно. Открытые величины системы: (p, q,  x1 ,x2 ).
Этап 1:
M1  выбирает случайное r1 R Zq* ,
M1  M2 :  r1 mod p.
Этап 2:
M2 выбирает случайное r2 R Zq* и вычисляет K=F( x1x2 mod p),
M2  M1 :  r2K mod p.
Когда M1 получает J= r2K mod p, он вычисляет K-1 mod q и затем J r1K-1 mod p. Получаемый в результате ключ будет S2= r2r1 mod p. Функция F() может быть либо F(x)=x mod q либо F(x)=h(x), где h – хэш-функция : {0,1}* Zq* .

Очевидно, что в полученном в результате ключе имеется вклад обоих сторон (т.к. r1 и r2 случайны и вырабатываются разными сторонами), т.е. протокол обладает контрибутивностью. В то же время обеспечивается аутентификация ключа, поскольку при его формировании участвуют открытые ключи обоих абонентов, которые переданы по аутентичному каналу. 

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

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

Протокол GDH.2. Пусть M = {M1 , M2 …Mn} – множество пользователей, которым необходимо выработать общий ключ Sn .  GDH.2 протокол выполняется за n шагов. На первой стадии (n-1 этапе) идет сбор информации от отдельных участников группы, а на второй стадии (n шаге) всем рассылается материал для вычисления общего ключа.
Предварительный этап. Пусть p – простое и q – простой делитель p-1. Пусть G-циклическая подгруппа Zp* порядка q и образующий элемент G.
Этап i:
Mi  выбирает случайное ri R Zq* ,
Mi  Mi+1 : { r1…ri / rj | j[1,i]},  r1…ri .
Этап n:
Mn выбирает случайное rn R Zq* ,
Mn Каждому Mi : { (r1…rn) / ri | i[1,n]}.
Общим ключом будет значение  r1…rn .

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

Протокол A-GDH.2. 
Этапы c 1 по n-1 : такие же, как и в GDH.2.
Этап n:
Mn выбирает случайное rn R Zq* ,
Mn Каждому Mi : { r1…rnKin/ ri | i[1,n]}.
При получении Mi вычисляет  (r1…rnKin/ ri)Kin-1ri =r1…rn Sn .

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

Теорема 2.1.2 Протокол A-GDH.2 обеспечивает свойство PFS.
Док-во: Предположим, что долговременные ключи Kin, i[1,n] скомпрометированы, тогда противник в состоянии вычислить подмножество V={П(S)| S{r1,…,rn}}. Но, как было показано в [2], по такому V не возможно восстановить сеансовый ключ Sn. #

Рассмотрим устойчивость описанного протокола к атакам по известным ключам. 
Пусть Sn(Mi) – сеансовый ключ, вычисленный каждым Mi. Для 0<i<n-1  можно записать его как CiriK-1in. Для Mn Sn(Mn)=Cnrn, где ci возможно известно противнику C. C также знает подмножество {П(S)| S{r1,…,rn}}. В данных условиях нахождение Kin или K-1in невозможно, если вычислительно трудно решить проблему “распознавания Диффи-Хеллмана” [1].
Однако, некоторые из атак возможны. Если С попытается послать M1 некоторое  c1 на последнем этапе протокола (где с1 выбирается противником), то M1 в результате получит неверный ключ Sn(M1)=c1r1K-11n, обнаружит проблему и просто заново запустит протокол обмена. Допустим, что противник каким-то образом получил этот неверный ключ (заметим, что на практике это маловероятно). При повторном выполнении протокола С может подменить сообщение от Mn-1  к Mn  на 

c1r1K1n-1,…,c1r1.

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

(c1r1K1n-1)rnK1n=c1r1rn

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

Необходимо заметить, что вышеупомянутый протокол A-GDH.2 выполняет неявную аутентификацию ключа, причем в довольно слабой форме, поскольку ключ не аутентифицируется непосредственно между каждыми любыми двумя Mi и Mj участниками (ij). Последний участник Mn (будем далее называть его контролирующим группы, поскольку через него проводятся ключевые операции протокола) отвечает за использование аутентичных ключей Kin, i=1 ... n-1, от которых и зависит аутентификация. Следовательно, участник Mn должен быть лицом, которому все доверяют. Это может быть схема с доверенным сервером в качестве Mn. В противном случае Mn сможет разбить группу на две части без обнаружения этого (поскольку он может перехватывать все сообщения и таким образом получить необходимую информацию в виде      r1…ri / rj для i,j).
Поэтому необходимо трансформировать протокол