MQV

MQV (Менезес-Кью-Ванстоун) — это аутентификационный протокол, базирующийся на алгоритме Диффи-Хеллмана. MQV предоставляет защиту против активных атак путём сочетания статического и временного ключей. Протокол может быть модифицирован для работы в произвольной конечной коммутативной группе, и, в частности, в группах эллиптических кривых, где известен как ECMQV.

MQV изначально был предложен Альфредом Менезесом, Мингхуа Кью и Скоттом Ванстоуном в 1995. Был модифицирован в 1998. Существуют одно-, двух- и трёхходовые разновидности алгоритма.

MQV включен в проект по стандартизации криптосистем с открытым ключом — IEEE P1363.

Патенты на некоторые разновидности MQV принадлежат компании Certicom [1].

MQV имеет некоторые слабости, которые были исправлены алгоритмом HMQV в 2005 [2]; см. [3], [4], [5].

Оба алгоритма MQV и HMQV имеют уязвимости, которые были исправлены протоколом FHMQV (см. [6])

Описание

Алиса имеет статическую ключевую пару ([math]\displaystyle{ W_a,w_a }[/math]), где [math]\displaystyle{ W_a }[/math] её открытый ключ и [math]\displaystyle{ w_a }[/math] её секретный ключ. Боб имеет статическую ключевую пару ([math]\displaystyle{ W_b,w_b }[/math]), где [math]\displaystyle{ W_b }[/math] его открытый ключ и [math]\displaystyle{ w_b }[/math] его секретный ключ. Определим [math]\displaystyle{ \bar{R} }[/math]. Пусть [math]\displaystyle{ R = (x,y) }[/math] будет точкой на эллиптической кривой. Тогда [math]\displaystyle{ \bar{R} = (x\, \bmod\, 2^L) + 2^L }[/math], где [math]\displaystyle{ L = \left \lceil \frac{\lfloor \log_{2} n \rfloor + 1}{2} \right \rceil }[/math] и [math]\displaystyle{ n }[/math] есть порядок используемого генератора точки [math]\displaystyle{ P }[/math]. Таким образом, [math]\displaystyle{ \bar{R} }[/math] есть первые [math]\displaystyle{ L }[/math] битов координаты [math]\displaystyle{ x }[/math] для [math]\displaystyle{ R }[/math]. Кроме того введем кофактор [math]\displaystyle{ h }[/math], определённый как [math]\displaystyle{ h = \frac{|G|}{n} }[/math], где [math]\displaystyle{ {|G|} }[/math] есть порядок группы [math]\displaystyle{ {G} }[/math], причем следует учесть, что по техническим причинам должно выполняться требование: [math]\displaystyle{ gcd(n,h) = 1 }[/math].

Шаг	Операция
1	Алиса создает ключевую пару ([math]\displaystyle{ R_a,r_a }[/math]) генерируя случайно [math]\displaystyle{ r_a }[/math] и вычисляя [math]\displaystyle{ R_a }[/math]=[math]\displaystyle{ r_aP }[/math], где [math]\displaystyle{ P }[/math] — точка на эллиптической кривой. После этого она посылает временный открытый ключ [math]\displaystyle{ R_a }[/math] Бобу.
2	Боб создает ключевую пару ([math]\displaystyle{ R_b,r_b }[/math]) генерируя случайно [math]\displaystyle{ r_b }[/math] и вычисляя [math]\displaystyle{ R_b }[/math]=[math]\displaystyle{ r_bP }[/math]. После создания пары он посылает свой временный открытый ключ [math]\displaystyle{ R_b }[/math] Алисе.
3	Алиса проверяет, что временный открытый ключ [math]\displaystyle{ R_b }[/math] принадлежит группе [math]\displaystyle{ G }[/math], а также то что [math]\displaystyle{ R_b }[/math] не является нулевым элементом. После этого вычисляет групповой элемент [math]\displaystyle{ Kab }[/math], как [math]\displaystyle{ Kab=hs_aS_b }[/math], где [math]\displaystyle{ s_a=(r_a+\bar{R_a}w_a)mod n }[/math] и [math]\displaystyle{ S_b=R_b+\bar{R_b}W_b }[/math]. Если [math]\displaystyle{ Kab = O }[/math], Алиса отклоняет данные, полученные от Боба. В противном случае, она принимает вычисленный результат, как общий секретный ключ.
4	Боб проверяет, что временный открытый ключ [math]\displaystyle{ R_a }[/math] принадлежит группе [math]\displaystyle{ G }[/math], а также что [math]\displaystyle{ R_a }[/math] не является нулевым элементом. Вычисляет групповой элемент [math]\displaystyle{ Kba }[/math], как [math]\displaystyle{ Kba=hs_bS_a }[/math], где [math]\displaystyle{ s_b=(r_b+\bar{R_b}w_b)mod n }[/math] и [math]\displaystyle{ S_a=R_a+\bar{R_a}W_a }[/math]. Если [math]\displaystyle{ Kba = O }[/math], Боб отклоняет данные, полученные от Алисы. В противном случае, он принимает вычисленный результат, как общий секретный ключ.

Базовый протокол является привлекательным решением из-за нескольких причин:

1. Предоставляет неявную идентификацию ключа и последующую защиту для каждого из партнеров.
2. Является эффективным не только в плане вычислений, но и в плане пропускной способности, так как использует только операции, заданные над полем и простое отображение. Вычисления каждого участника (в грубой оценке) состоят лишь из 2,5 умножений — одно для генерации временной ключевой пары, другое для скалярного умножения на [math]\displaystyle{ s_a }[/math] или [math]\displaystyle{ s_b }[/math].

Оставшаяся часть вычислений приходится на умножение на [math]\displaystyle{ \bar{R_a} }[/math] или [math]\displaystyle{ \bar{R_b} }[/math]. Стоит также учесть стоимость умножения на кофактор. Однако эта сложность (умножение на кофактор) зависит от размера группы. Для криптосистем, основанных на эллиптических кривых, данная сложность незначительна, так как кофактор обычно мал.

Корректность

Вычисления Боба:[math]\displaystyle{ Kba = h \cdot s_b (R_a + \bar{R_a}W_a) = h \cdot s_b (r_aP + \bar{R_a}w_aP) = h \cdot s_b (r_a + \bar{R_a}w_a)P = h \cdot s_b s_a P }[/math].

Вычисления Алисы:[math]\displaystyle{ Kab = h \cdot s_a (R_b + \bar{R_b}W_b) = h \cdot s_a (r_bP + \bar{R_b}w_bP) = h \cdot s_a (r_b + \bar{R_b}w_b)P = h \cdot s_b s_a P }[/math].

Таким образом, ключи [math]\displaystyle{ Kab=Kba }[/math] действительно эквивалентны ключу [math]\displaystyle{ K = h \cdot s_b s_a P }[/math].

Возможные атаки

Самый простой вариант, которым может воспользоваться злоумышленник (криптоаналитик) — получить сертификат(идентификатор), ассоциирующий его имя с открытым ключом, находящимся у Алисы. Если он заменит идентификатор Алисы своим собственным идентификатором в данном протоколе, существует значительная вероятность, что Боб примет данный идентификатор, не заметив подмены, в действительности думая, что общается с Алисой. Приведём атаку, основанную на подмене источника. Данная атака указывает на необходимость наличия требований к владению ключом: запрашивающая сторона должна знать секретный ключ для того, чтобы получить идентификатор, соответствующий открытому ключу. В принципе, центр идентификации мог бы устроить проверку на дубликат открытых ключей, однако этот шаг является непрактичным решением, так как влечёт за собой участие большого количества центров идентификации. Таким образом, злоумышленник должен получить идентификатор для нового открытого ключа [math]\displaystyle{ W_e }[/math], такого, чтобы существовало соответствие секретному ключу [math]\displaystyle{ w_e }[/math], и такого, чтобы Боб вычислил бы такой же общий секретный ключ при взаимодействии со злоумышленником, какой вычислился бы при взаимодействии Боба и Алисы. Следующая реализация удовлетворяет всем вышеописанным целям. Обозначим злоумышленника как Еву.

Шаг	Операция
1	Ева перехватывает временный открытый ключ Алисы [math]\displaystyle{ R_a }[/math] на пути ключа к Бобу.
2	Ева выбирает целое [math]\displaystyle{ U }[/math] принадлежащее промежутку [math]\displaystyle{ [1, }[/math] [math]\displaystyle{ n-1] }[/math] и вычисляет временный открытый ключ [math]\displaystyle{ R_e }[/math], как [math]\displaystyle{ R_e=R_a -uP + \bar{R_a}W_a }[/math] (заметим, что Ева не знает соответствующий секретный ключ [math]\displaystyle{ r_e }[/math]). Если [math]\displaystyle{ R_e = 0 }[/math], Ева повторяет этот шаг с другим целым [math]\displaystyle{ U }[/math].
3	Ева вычисляет статическую пару [math]\displaystyle{ (W_e, w_e) }[/math], как [math]\displaystyle{ W_e = w_eP }[/math], [math]\displaystyle{ w_e = \bar{R_e}^{-1}u \cdot modn }[/math].
4	Ева получает идентификатор для её статического открытого ключа [math]\displaystyle{ W_e }[/math]. Таким образом, она знает соответствующий секретный ключ [math]\displaystyle{ w_e }[/math]. Следовательно, она удовлетворяет требованиям владения ключа.
5	Ева инициирует запуск протокола с Бобом, посылая свой временный открытый ключ [math]\displaystyle{ R_e }[/math].
6	Ева получает Временный открытый ключ Боба [math]\displaystyle{ R_b }[/math] и передает его Алисе.

В результате данной атаки, Алиса проверит идентификатор Боба и вычислит общий секретный ключ [math]\displaystyle{ Kab }[/math], в то время как Боб получит и проверит идентификатор Евы и вычислит общий секретный ключ [math]\displaystyle{ Kbe }[/math], как [math]\displaystyle{ Kbe = hs_bS_e }[/math], где [math]\displaystyle{ s_b }[/math] определён ранее и [math]\displaystyle{ S_e = R_e + \bar{R_e}W_e }[/math].

Ключ Боба будет таким же, каким бы он был, если бы Боб взаимодействовал с Алисой.

[math]\displaystyle{ hs_bS_e=hs_b(R_e+\bar{R_e}W_e)=hs_b(R_a+\bar{R_a}W_a }[/math][math]\displaystyle{ -uP+\bar{R_e}w_eP)=hs_b(R_a+\bar{R_a}W_a }[/math][math]\displaystyle{ -uP+\bar{R_e}(\bar{R_e}^{-1}umodn)P)=hs_b(R_a+\bar{R_a}W_a)=hs_bS_a=Kba }[/math].

Ева должна получить идентификатор для её статического открытого ключа во время запуска протокола со стороны Алисы. Таким образом, Алиса может заметить задержку между временем отправки её временного открытого ключа и временем получения идентификатора Боба.

Меры противодействия атакам

Прежде всего, первым шагом необходимо включить в протокол операцию, которая будет зарезервирована для проверки наличия ключа. Данный совет относится ко всем протоколам аутентификации. Таким образом, для прохождения верификации Боба, Еве нужно будет пройти дополнительную проверку. Другой вариант противодействия, который может быть введен в протокол — создание обмена между участниками односторонними хэшами от их временных открытых ключей перед обменом временными ключами. Механизм обмена в данном случае действительно важен. Каждая сторона должна быть уверенна, что другой член действительно получил «посылку» перед тем, как отправлять ему временный открытый ключ. Подтверждение данного факта может быть получено соответствующей последовательностью. К примеру, Алиса посылает её подтверждение, Боб получает его и посылает его подтверждение. Алиса получает подтверждение Боба и посылает свой ключ. Когда же Боб получает ключ Алисы, он посылает его собственный ключ. Без такой последовательности, к примеру, если Боб и Алиса будут делать пересылку одновременно, данный протокол будет уязвимым для некоторых видов атак.

Приведём иные меры противодействия.

1. Детектор задержек — альтернативный вариант, не использующий криптографию. Реализация так называемого «проверщика» задержек. Сторона (Боб или Алиса) прекратит работу протокола, если время ответа другой стороны будет превышать заданное в реализации протокола допустимое значение. Таким образом, когда Ева запрашивает идентификатор, этот шаг может потребовать дополнительного времени (однако существуют возможности обойти эту сложность). Причём, дополнительное время будет сравнимо с временем прочих операций, задействованных в протоколе. Однако данная контрмера не поможет в случае атаки в несколько шагов.
2. «Идентификатор давности». Получатель может запросить подтверждение давности идентификатора. Недавно полученный идентификатор может быть воспринят, как доказательство атаки. После чего канал связи со злоумышленником будет закрыт.
3. Идентификация участников через сообщения. Главный принцип дизайна протоколов — сообщения должны нести достаточно информации, чтобы избежать неправильной интерпретации. Соответственно, сообщения, защищенные с общим секретным ключом, должны идентифицировать участников, вовлеченных в передачу. Такая идентификация препятствовала бы возможности возникновения неправильной интерпретации.

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

См. также

• Эллиптическая криптография

Литература

• Burt Kaliski. An unknown key-share attack on the MQV key agreement protocol. ACM Trans. Inf. Syst. Secur. 4(3) //  (англ.). — 2001.
• Laurie Law, Alfred Menezes, Minghua Qu, Jerry Solinas, Scott A. Vanstone, An Efficient Protocol for Authenticated Key Agreement. Des. Codes Cryptography 28(2): pp. 119—134 (2003)
• Peter J. Leadbitter, Nigel P. Smart: Analysis of the Insecurity of ECMQV with Partially Known Nonces. ISC 2003: pp. 240—251
• A. Menezes, M. Qu, and S. Vanstone, Some new key agreement protocols providing implicit authentication, Preproceedings of Workshops on Selected Areas in Cryptography (1995).
• D. Hankerson, A. Menezes, and S.A. Vanstone, Guide to Elliptic Curve Cryptography, Springer-Verlag, 2004.

Ссылки

• A Secure and Efficient Authenticated Diffie-Hellman Protocol by Sarr, Elbaz-Vincent, and Bajard
• HMQV: A High-Performance Secure Diffie-Hellman Protocol by Hugo Krawczyk
• Another look at HMQV
• An Efficient Protocol for Authenticated Key Agreement
• MQV and HMQV in IEEE P1363 (power point)