MQV

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

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

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

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

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

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

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

Шаг	Операция
1	Алиса создает ключевую пару (${\displaystyle R_{a},r_{a}}$) генерируя случайно ${\displaystyle r_{a}}$ и вычисляя ${\displaystyle R_{a}}$=${\displaystyle r_{a}P}$, где ${\displaystyle P}$ — точка на эллиптической кривой. После этого она посылает временный открытый ключ ${\displaystyle R_{a}}$ Бобу.
2	Боб создает ключевую пару (${\displaystyle R_{b},r_{b}}$) генерируя случайно ${\displaystyle r_{b}}$ и вычисляя ${\displaystyle R_{b}}$=${\displaystyle r_{b}P}$. После создания пары он посылает свой временный открытый ключ ${\displaystyle R_{b}}$ Алисе.
3	Алиса проверяет, что временный открытый ключ ${\displaystyle R_{b}}$ принадлежит группе ${\displaystyle G}$, а также то что ${\displaystyle R_{b}}$ не является нулевым элементом. После этого вычисляет групповой элемент ${\displaystyle Kab}$, как ${\displaystyle Kab=hs_{a}S_{b}}$, где ${\displaystyle s_{a}=(r_{a}+{\bar {R_{a}}}w_{a})modn}$ и ${\displaystyle S_{b}=R_{b}+{\bar {R_{b}}}W_{b}}$. Если ${\displaystyle Kab=O}$, Алиса отклоняет данные, полученные от Боба. В противном случае, она принимает вычисленный результат, как общий секретный ключ.
4	Боб проверяет, что временный открытый ключ ${\displaystyle R_{a}}$ принадлежит группе ${\displaystyle G}$, а также что ${\displaystyle R_{a}}$ не является нулевым элементом. Вычисляет групповой элемент ${\displaystyle Kba}$, как ${\displaystyle Kba=hs_{b}S_{a}}$, где ${\displaystyle s_{b}=(r_{b}+{\bar {R_{b}}}w_{b})modn}$ и ${\displaystyle S_{a}=R_{a}+{\bar {R_{a}}}W_{a}}$. Если ${\displaystyle Kba=O}$, Боб отклоняет данные, полученные от Алисы. В противном случае, он принимает вычисленный результат, как общий секретный ключ.

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

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

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

Вычисления Боба:${\displaystyle Kba=h\cdot s_{b}(R_{a}+{\bar {R_{a}}}W_{a})=h\cdot s_{b}(r_{a}P+{\bar {R_{a}}}w_{a}P)=h\cdot s_{b}(r_{a}+{\bar {R_{a}}}w_{a})P=h\cdot s_{b}s_{a}P}$.

Вычисления Алисы:${\displaystyle Kab=h\cdot s_{a}(R_{b}+{\bar {R_{b}}}W_{b})=h\cdot s_{a}(r_{b}P+{\bar {R_{b}}}w_{b}P)=h\cdot s_{a}(r_{b}+{\bar {R_{b}}}w_{b})P=h\cdot s_{b}s_{a}P}$.

Таким образом, ключи ${\displaystyle Kab=Kba}$ действительно эквивалентны ключу ${\displaystyle K=h\cdot s_{b}s_{a}P}$^[3].

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

Шаг	Операция
1	Ева перехватывает временный открытый ключ Алисы ${\displaystyle R_{a}}$ на пути ключа к Бобу.
2	Ева выбирает целое ${\displaystyle U}$ принадлежащее промежутку ${\displaystyle [1,}$ ${\displaystyle n-1]}$ и вычисляет временный открытый ключ ${\displaystyle R_{e}}$, как ${\displaystyle R_{e}=R_{a}-uP+{\bar {R_{a}}}W_{a}}$ (заметим, что Ева не знает соответствующий секретный ключ ${\displaystyle r_{e}}$). Если ${\displaystyle R_{e}=0}$, Ева повторяет этот шаг с другим целым ${\displaystyle U}$.
3	Ева вычисляет статическую пару ${\displaystyle (W_{e},w_{e})}$, как ${\displaystyle W_{e}=w_{e}P}$, ${\displaystyle w_{e}={\bar {R_{e}}}^{-1}u\cdot modn}$.
4	Ева получает идентификатор для её статического открытого ключа ${\displaystyle W_{e}}$. Таким образом, она знает соответствующий секретный ключ ${\displaystyle w_{e}}$. Следовательно, она удовлетворяет требованиям владения ключа.
5	Ева инициирует запуск протокола с Бобом, посылая свой временный открытый ключ ${\displaystyle R_{e}}$.
6	Ева получает Временный открытый ключ Боба ${\displaystyle R_{b}}$ и передает его Алисе.

В результате данной атаки, Алиса проверит идентификатор Боба и вычислит общий секретный ключ ${\displaystyle Kab}$, в то время как Боб получит и проверит идентификатор Евы и вычислит общий секретный ключ ${\displaystyle Kbe}$, как ${\displaystyle Kbe=hs_{b}S_{e}}$, где ${\displaystyle s_{b}}$ определён ранее и ${\displaystyle S_{e}=R_{e}+{\bar {R_{e}}}W_{e}}$.

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

${\displaystyle hs_{b}S_{e}=hs_{b}(R_{e}+{\bar {R_{e}}}W_{e})=hs_{b}(R_{a}+{\bar {R_{a}}}W_{a}}$${\displaystyle -uP+{\bar {R_{e}}}w_{e}P)=hs_{b}(R_{a}+{\bar {R_{a}}}W_{a}}$${\displaystyle -uP+{\bar {R_{e}}}({\bar {R_{e}}}^{-1}umodn)P)=hs_{b}(R_{a}+{\bar {R_{a}}}W_{a})=hs_{b}S_{a}=Kba}$.

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

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

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

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)