Протокол обмена ключами MQV и его варианты

Введение

Протокол обмена открытым ключом
MQV (Menezes–Qu–Vanstone) — это аутентифицированный протокол согласования ключей, основанный на схеме Диффи — Хеллмана. Как и другие аутентифицированные схемы Диффи — Хеллмана, MQV обеспечивает защиту от активного злоумышленника. Протокол может быть модифицирован для работы в произвольной конечной группе, в частности, в группах эллиптических кривых, где он известен как MQV на эллиптических кривых (ECMQV). MQV был впервые предложен Альфредом Менезесом, Мингхуа Ку и Скоттом Ванстоуном в 1995 году. Впоследствии он был изменен в совместной работе с Лори Лоу и Джерри Солинасом. Существуют варианты с одним, двумя и тремя раундами обмена данными. MQV включен в стандарт открытых ключей IEEE P1363 и стандарт NIST SP800-56A. Некоторые варианты MQV запатентованы и принадлежат компании Certicom. ECMQV был исключен из набора криптографических стандартов Suite B Агентства национальной безопасности. СОД.

Описание

У Алисы есть пара ключей, состоящая из её открытого и закрытого ключей, а у Боба – пара ключей, состоящая из его открытого и закрытого ключей. Далее под этим подразумевается следующее. Пусть – точка на эллиптической кривой. Тогда, где – и – порядок используемой генераторной точки. Таким образом, первые L битов первой координаты – это…
Шаг Операция 1: Алиса генерирует пару ключей , случайно выбирая и вычисляя , где – точка на эллиптической кривой. 2: Боб генерирует пару ключей таким же образом, как Алиса. 3: Теперь Алиса вычисляет по модулю и отправляет результат Бобу. 4: Боб вычисляет по модулю и отправляет результат Алисе. 5: Алиса вычисляет , а Боб вычисляет , где – кофактор (см. Криптография на эллиптических кривых: параметры области определения). 6: Успешный обмен секретным ключом состоялся. Ключ для симметричного алгоритма шифрования может быть получен из .
Примечание: для обеспечения безопасности алгоритма необходимо выполнить некоторые проверки. См. Хэнкерсон и др.

MQV против HMQV

Первоначальный протокол MQV не включает идентификаторы пользователей обменивающихся сторон в потоках обмена ключами. Идентификаторы пользователей включаются только в последующий процесс подтверждения ключа. Однако, явное подтверждение ключа является необязательным в MQV (и в спецификации IEEE P1363). В 2001 году Калиски представил атаку на основе неизвестного общего секрета, которая использовала отсутствие идентификаторов в протоколе обмена ключами MQV. Атака работает против неявно аутентифицированного MQV, не имеющего явного подтверждения ключа. В этой атаке пользователь устанавливает сеансовый ключ с другим пользователем, но его обманывают, заставляя поверить, что он разделяет ключ с другим пользователем. В 2006 году Менезес и Устаоглу предложили решить эту проблему, включив идентификаторы пользователей в функцию вывода ключа в конце обмена ключами MQV. Процесс подтверждения ключа остается необязательным. В 2005 году Краучик предложил хеш-вариант MQV, названный HMQV. Протокол HMQV был разработан для устранения атаки Калиски (без обязательного подтверждения ключа), с дополнительными целями достижения доказуемой безопасности и повышения эффективности. HMQV внес три изменения в MQV: включение идентификаторов пользователей в потоки обмена ключами, а именно, позволяя и , где и являются идентификаторами Алисы и Боба соответственно; удаление обязательного требования в MQV, согласно которому центр сертификации (CA) должен проверять доказательство владения пользователем закрытым ключом во время регистрации открытого ключа. В HMQV CA просто должен проверить, что представленный открытый ключ не равен 0 или 1; удаление обязательного требования в MQV, согласно которому пользователь должен проверять, является ли полученный эфемерный открытый ключ допустимым открытым ключом (известное как подтверждение открытого ключа). В HMQV пользователю достаточно проверить, что полученный эфемерный открытый ключ не равен 0 или 1. HMQV утверждает, что превосходит MQV по производительности, поскольку отказывается от операций, указанных в пунктах 2) и 3) выше, которые являются обязательными в MQV. В документе HMQV приводятся «формальные доказательства безопасности», подтверждающие безопасность отказа от этих операций. В 2005 году Менезес впервые представил атаку на ограничение малой подгруппы против HMQV. Эта атака использует отсутствие проверки открытого ключа в 2) и 3). Она показывает, что при взаимодействии с активным злоумышленником протокол HMQV раскрывает информацию о долгосрочном закрытом ключе пользователя, и, в зависимости от базовой криптографической группы, злоумышленник может восстановить весь закрытый ключ. Менезес предложил решить эту проблему, по крайней мере, обязав проверку открытых ключей в 2) и 3). В 2006 году, в ответ на атаку Менезеса, Краучик пересмотрел HMQV в представлении в IEEE P1363 (включенном в предварительный проект IEEE P1363 D1). Однако вместо проверки долгосрочных и эфемерных открытых ключей в 2) и 3) соответственно как двух отдельных операций, Краучик предложил проверять их вместе в одной объединенной операции в процессе обмена ключами. Это позволит сэкономить ресурсы. С объединенной проверкой открытого ключа атака Менезеса будет предотвращена. Пересмотренный HMQV все еще может претендовать на более высокую эффективность, чем MQV. В 2010 году Хао представил две атаки на пересмотренный HMQV (как указано в предварительном проекте IEEE P1363 D1). Первая атака использует тот факт, что HMQV позволяет регистрировать любую строку данных, кроме 0 и 1, в качестве долгосрочного открытого ключа. Следовательно, элемент малой подгруппы может быть зарегистрирован как «открытый ключ». Зная этот «открытый ключ», пользователь может пройти все этапы проверки в HMQV и в конечном итоге полностью «аутентифицироваться». Это противоречит общему пониманию, что «аутентификация» в протоколе обмена аутентифицированными ключами определяется на основе доказательства знания закрытого ключа. В этом случае пользователь «аутентифицирован», но не имеет закрытого ключа (фактически закрытого ключа не существует). Эта проблема не относится к MQV. Вторая атака использует режим самокоммуникации, который явно поддерживается в HMQV, чтобы позволить пользователю общаться с самим собой, используя тот же сертификат открытого ключа. В этом режиме HMQV оказывается уязвимым для атаки на основе неизвестного общего секрета. Для решения первой атаки Хао предложил выполнять проверку открытых ключей в 2) и 3) отдельно, как первоначально предлагал Менезес. Однако это изменение снизит преимущества HMQV в эффективности по сравнению с MQV. Для решения второй атаки Хао предложил включить дополнительные идентификаторы для различения копий самого себя или отключить режим самокоммуникации. Две атаки Хао были обсуждены членами рабочей группы IEEE P1363 в 2010 году. Однако консенсуса относительно того, как следует пересмотреть HMQV, достигнуто не было. В результате спецификация HMQV в предварительном проекте IEEE P1363 D1 осталась неизменной, но стандартизация HMQV в IEEE P1363 прекратилась.

The original MQV protocol does not include user identities of the communicating parties in the key exchange flows. User identities are only included in the subsequent explicit key confirmation process. However, explicit key confirmation is optional in MQV (and in the IEEE P1363 specification). In 2001, Kaliski presented an unknown key share attack that exploited the missing identities in the MQV key exchange protocol. The attack works against implicitly authenticated MQV that does not have explicit key confirmation. In this attack, the user establishes a session key with another user but is tricked into believing that he shares the key with a different user. In 2006, Menezes and Ustaoglu proposed to address this attack by including user identities in the key derivation function at the end of the MQV key exchange. The explicit key confirmation process remains optional. In 2005, Krawczyk proposed a hash variant of MQV, called HMQV. The HMQV protocol was designed to address Kaliski's attack (without mandating explicit key confirmation), with the additional goals of achieving provable security and better efficiency. HMQV made three changes to MQV:
Including the user identities in the key exchange flows: more specifically, letting and where and are identities of Alice and Bob respectively. Removing the mandatory requirement in MQV that a certificate authority (CA) must verify the proof of possession of the user's private key during the public key registration. In HMQV, the CA merely needs to check the submitted public key is not 0 or 1. Removing the mandatory requirement in MQV that a user must verify whether the received ephemeral public key is a valid public key (known as public key validation). In HMQV, a user merely needs to check the received ephemeral public key is not 0 or 1. HMQV claims to be superior to MQV in performance because it dispenses with the operations in 2) and 3) above, which are mandatory in MQV. The HMQV paper provides "formal security proofs" to support that dispensing with these operations is safe. In 2005, Menezes first presented a small subgroup confinement attack against HMQV. This attack exploits the exact missing of public key validations in 2) and 3). It shows that when engaged with an active attacker, the HMQV protocol leaks information about the user's long term private key, and depending on the underlying cryptographic group setting, the entire private key may be recovered by the attacker. Menezes proposed to address this attack by at least mandating public key validations in 2) and 3). In 2006, in response to Menezes's attack, Krawczyk revised HMQV in the submission to IEEE P1363 (included in the IEEE P1363 D1 pre draft). However, instead of validating the long term and ephemeral public keys in 2) and 3) respectively as two separate operations, Krawczyk proposed to validate them together in one combined operation during the key exchange process. This would save cost. With the combined public key validation in place, Menezes's attack would be prevented. The revised HMQV could still claim to be more efficient than MQV. In 2010, Hao presented two attacks on the revised HMQV (as specified in the IEEE P1363 D1 pre draft). The first attack exploits the fact that HMQV allows any data string other than 0 and 1 to be registered as a long term public key. Hence, a small subgroup element is allowed to be registered as a "public key". With the knowledge of this "public key", a user is able to pass all verification steps in HMQV and is fully "authenticated" in the end. This contradicts the common understanding that "authentication" in an authenticated key exchange protocol is defined based on proving the knowledge of a private key. In this case, the user is "authenticated" but without having a private key (in fact, the private key does not exist). This issue is not applicable to MQV. The second attack exploits the self communication mode, which is explicitly supported in HMQV to allow a user to communicate with himself using the same public key certificate. In this mode, HMQV is shown to be vulnerable to an unknown key share attack. To address the first attack, Hao proposed to perform public key validations in 2) and 3) separately, as initially suggested by Menezes. However, this change would diminish the efficiency advantages of HMQV over MQV. To address the second attack, Hao proposed to include additional identities to distinguish copies of self, or to disable the self communication mode. Hao's two attacks were discussed by members of the IEEE P1363 working group in 2010. However, there was no consensus on how HMQV should be revised. As a result, the HMQV specification in the IEEE P1363 D1 pre draft was unchanged, but the standardisation of HMQV in IEEE P1363 has stopped progressing since.