MQV (Менезес-Кью-Ванстоун) — это аутентификационный протокол, базирующийся на алгоритме Диффи-Хеллмана. MQV предоставляет защиту против активных атак путём сочетания статического и временного ключей. Протокол может быть модифицирован для работы в произвольной конечной коммутативной группе, и, в частности, в группах эллиптических кривых, где известен как ECMQV.
MQV изначально был предложен Альфредом Менезесом, Мингхуа Кью и Скоттом Ванстоуном в 1995. Был модифицирован в 1998. Существуют одно-, двух- и трёхходовые разновидности алгоритма.
MQV включен в проект по стандартизации криптосистем с открытым ключом — IEEE P1363.
Патенты на некоторые разновидности MQV принадлежат компании Certicom [1].
MQV имеет некоторые слабости, которые были исправлены алгоритмом HMQV в 2005 [2]; см. [3], [4], [5].
Оба алгоритма MQV и HMQV имеют уязвимости, которые были исправлены протоколом FHMQV (см. [6])
Описание
Алиса имеет статическую ключевую пару ( W a , w a {displaystyle W_{a},w_{a}} ), где W a {displaystyle W_{a}} её открытый ключ и w a {displaystyle w_{a}} её секретный ключ. Боб имеет статическую ключевую пару ( W b , w b {displaystyle W_{b},w_{b}} ), где W b {displaystyle W_{b}} его открытый ключ и w b {displaystyle w_{b}} его секретный ключ. Определим R ¯ {displaystyle {ar {R}}} . Пусть R = ( x , y ) {displaystyle R=(x,y)} будет точкой на эллиптической кривой. Тогда R ¯ = ( x mod 2 L ) + 2 L {displaystyle {ar {R}}=(x,{mod {,}}2^{L})+2^{L}} , где L = ⌈ ⌊ log 2 n ⌋ + 1 2 ⌉ {displaystyle L=leftlceil {frac {lfloor log _{2}n floor +1}{2}} ight ceil } и n {displaystyle n} есть порядок используемого генератора точки P {displaystyle P} . Таким образом, R ¯ {displaystyle {ar {R}}} есть первые L {displaystyle L} битов координаты x {displaystyle x} для R {displaystyle R} . Кроме того введем кофактор h {displaystyle h} , определённый как h = | G | n {displaystyle h={frac {|G|}{n}}} , где | G | {displaystyle {|G|}} есть порядок группы G {displaystyle {G}} , причем следует учесть, что по техническим причинам должно выполняться требование: g c d ( n , h ) = 1 {displaystyle gcd(n,h)=1} .
Базовый протокол является привлекательным решением из-за нескольких причин:
Оставшаяся часть вычислений приходится на умножение на R a ¯ {displaystyle {ar {R_{a}}}} или R b ¯ {displaystyle {ar {R_{b}}}} . Стоит также учесть стоимость умножения на кофактор. Однако эта сложность (умножение на кофактор) зависит от размера группы. Для криптосистем, основанных на эллиптических кривых, данная сложность незначительна, так как кофактор обычно мал.
Корректность
Вычисления Боба: K b a = h ⋅ s b ( R a + R a ¯ W a ) = h ⋅ s b ( r a P + R a ¯ w a P ) = h ⋅ s b ( r a + R a ¯ w a ) P = h ⋅ s b s a P {displaystyle Kba=hcdot s_{b}(R_{a}+{ar {R_{a}}}W_{a})=hcdot s_{b}(r_{a}P+{ar {R_{a}}}w_{a}P)=hcdot s_{b}(r_{a}+{ar {R_{a}}}w_{a})P=hcdot s_{b}s_{a}P} .
Вычисления Алисы: K a b = h ⋅ s a ( R b + R b ¯ W b ) = h ⋅ s a ( r b P + R b ¯ w b P ) = h ⋅ s a ( r b + R b ¯ w b ) P = h ⋅ s b s a P {displaystyle Kab=hcdot s_{a}(R_{b}+{ar {R_{b}}}W_{b})=hcdot s_{a}(r_{b}P+{ar {R_{b}}}w_{b}P)=hcdot s_{a}(r_{b}+{ar {R_{b}}}w_{b})P=hcdot s_{b}s_{a}P} .
Таким образом, ключи K a b = K b a {displaystyle Kab=Kba} действительно эквивалентны ключу K = h ⋅ s b s a P {displaystyle K=hcdot s_{b}s_{a}P} .
Возможные атаки
Самый простой вариант, которым может воспользоваться злоумышленник (криптоаналитик) — получить сертификат(идентификатор), ассоциирующий его имя с открытым ключом, находящимся у Алисы. Если он заменит идентификатор Алисы своим собственным идентификатором в данном протоколе, существует значительная вероятность, что Боб примет данный идентификатор, не заметив подмены, в действительности думая, что общается с Алисой. Приведём атаку, основанную на подмене источника. Данная атака указывает на необходимость наличия требований к владению ключом: запрашивающая сторона должна знать секретный ключ для того, чтобы получить идентификатор, соответствующий открытому ключу. В принципе, центр идентификации мог бы устроить проверку на дубликат открытых ключей, однако этот шаг является непрактичным решением, так как влечёт за собой участие большого количества центров идентификации. Таким образом, злоумышленник должен получить идентификатор для нового открытого ключа W e {displaystyle W_{e}} , такого, чтобы существовало соответствие секретному ключу w e {displaystyle w_{e}} , и такого, чтобы Боб вычислил бы такой же общий секретный ключ при взаимодействии со злоумышленником, какой вычислился бы при взаимодействии Боба и Алисы. Следующая реализация удовлетворяет всем вышеописанным целям. Обозначим злоумышленника как Еву.
В результате данной атаки, Алиса проверит идентификатор Боба и вычислит общий секретный ключ K a b {displaystyle Kab} , в то время как Боб получит и проверит идентификатор Евы и вычислит общий секретный ключ K b e {displaystyle Kbe} , как K b e = h s b S e {displaystyle Kbe=hs_{b}S_{e}} , где s b {displaystyle s_{b}} определён ранее и S e = R e + R e ¯ W e {displaystyle S_{e}=R_{e}+{ar {R_{e}}}W_{e}} .
Ключ Боба будет таким же, каким бы он был, если бы Боб взаимодействовал с Алисой.
h s b S e = h s b ( R e + R e ¯ W e ) = h s b ( R a + R a ¯ W a {displaystyle hs_{b}S_{e}=hs_{b}(R_{e}+{ar {R_{e}}}W_{e})=hs_{b}(R_{a}+{ar {R_{a}}}W_{a}} − u P + R e ¯ w e P ) = h s b ( R a + R a ¯ W a {displaystyle -uP+{ar {R_{e}}}w_{e}P)=hs_{b}(R_{a}+{ar {R_{a}}}W_{a}} − u P + R e ¯ ( R e ¯ − 1 u m o d n ) P ) = h s b ( R a + R a ¯ W a ) = h s b S a = K b a {displaystyle -uP+{ar {R_{e}}}({ar {R_{e}}}^{-1}umodn)P)=hs_{b}(R_{a}+{ar {R_{a}}}W_{a})=hs_{b}S_{a}=Kba} .
Ева должна получить идентификатор для её статического открытого ключа во время запуска протокола со стороны Алисы. Таким образом, Алиса может заметить задержку между временем отправки её временного открытого ключа и временем получения идентификатора Боба.
Меры противодействия атакам
Прежде всего, первым шагом необходимо включить в протокол операцию, которая будет зарезервирована для проверки наличия ключа. Данный совет относится ко всем протоколам аутентификации. Таким образом, для прохождения верификации Боба, Еве нужно будет пройти дополнительную проверку. Другой вариант противодействия, который может быть введен в протокол — создание обмена между участниками односторонними хэшами от их временных открытых ключей перед обменом временными ключами. Механизм обмена в данном случае действительно важен. Каждая сторона должна быть уверенна, что другой член действительно получил «посылку» перед тем, как отправлять ему временный открытый ключ. Подтверждение данного факта может быть получено соответствующей последовательностью. К примеру, Алиса посылает её подтверждение, Боб получает его и посылает его подтверждение. Алиса получает подтверждение Боба и посылает свой ключ. Когда же Боб получает ключ Алисы, он посылает его собственный ключ. Без такой последовательности, к примеру, если Боб и Алиса будут делать пересылку одновременно, данный протокол будет уязвимым для некоторых видов атак.
Приведём иные меры противодействия.
Все вышеописанные улучшения вносят минимальные модификации в структуру протокола. Стоит заметить, что нет формального доказательства полной безопасности протокола, который модифицирован с помощью вышеописанных рекомендаций.