MQV

Short description: Public-key exchange protocol

MQV (Menezes–Qu–Vanstone) is an authenticated protocol for key agreement based on the Diffie–Hellman scheme. Like other authenticated Diffie–Hellman schemes, MQV provides protection against an active attacker. The protocol can be modified to work in an arbitrary finite group, and, in particular, elliptic curve groups, where it is known as elliptic curve MQV (ECMQV).

MQV was initially proposed by Alfred Menezes, Minghua Qu and Scott Vanstone in 1995. It was later modified in joint work with Laurie Law and Jerry Solinas. There are one-, two- and three-pass variants.

MQV is incorporated in the public-key standard IEEE P1363 and NIST's SP800-56A standard.

Some variants of MQV are claimed in patents assigned to Certicom.

ECMQV has been dropped from the National Security Agency's Suite B set of cryptographic standards.

Description

Alice has a key pair [math]\displaystyle{ (A,a) }[/math] with [math]\displaystyle{ A }[/math] her public key and [math]\displaystyle{ a }[/math] her private key and Bob has the key pair [math]\displaystyle{ (B,b) }[/math] with [math]\displaystyle{ B }[/math] his public key and [math]\displaystyle{ b }[/math] his private key.

In the following [math]\displaystyle{ \bar{R} }[/math] has the following meaning. Let [math]\displaystyle{ R = (x,y) }[/math] be a point on an elliptic curve. Then [math]\displaystyle{ \bar{R} = (x\, \bmod\, 2^L) + 2^L }[/math] where [math]\displaystyle{ L = \left \lceil \frac{\lfloor \log_{2} n \rfloor + 1}{2} \right \rceil }[/math] and [math]\displaystyle{ n }[/math] is the order of the used generator point [math]\displaystyle{ P }[/math]. So [math]\displaystyle{ \bar{R} }[/math] are the first L bits of the first coordinate of [math]\displaystyle{ R }[/math].

Step	Operation
1	Alice generates a key pair [math]\displaystyle{ (X,x) }[/math] by generating randomly [math]\displaystyle{ x }[/math] and calculating [math]\displaystyle{ X=xP }[/math] with [math]\displaystyle{ P }[/math] a point on an elliptic curve.
2	Bob generates a key pair [math]\displaystyle{ (Y,y) }[/math] in the same way as Alice.
3	Now, Alice calculates [math]\displaystyle{ S_a = x + \bar{X} a }[/math] modulo [math]\displaystyle{ n }[/math] and sends [math]\displaystyle{ X }[/math] to Bob.
4	Bob calculates [math]\displaystyle{ S_b = y + \bar{Y} b }[/math] modulo [math]\displaystyle{ n }[/math] and sends [math]\displaystyle{ Y }[/math] to Alice.
5	Alice calculates [math]\displaystyle{ K = h \cdot S_a (Y + \bar{Y}B) }[/math] and Bob calculates [math]\displaystyle{ K = h \cdot S_b (X + \bar{X}A) }[/math] where [math]\displaystyle{ h }[/math] is the cofactor (see Elliptic curve cryptography: domain parameters).
6	The communication of secret [math]\displaystyle{ K }[/math] was successful. A key for a symmetric-key algorithm can be derived from [math]\displaystyle{ K }[/math].

Note: for the algorithm to be secure some checks have to be performed. See Hankerson et al.

Correctness

Bob calculates: [math]\displaystyle{ K = h \cdot S_b (X + \bar{X}A) = h \cdot S_b (xP + \bar{X}aP) = h \cdot S_b (x + \bar{X}a)P = h \cdot S_b S_a P }[/math]

Alice calculates: [math]\displaystyle{ K = h \cdot S_a (Y + \bar{Y}B) = h \cdot S_a (yP + \bar{Y}bP) = h \cdot S_a (y + \bar{Y}b)P = h \cdot S_b S_a P }[/math]

So the shared secrets [math]\displaystyle{ K }[/math] are indeed the same with [math]\displaystyle{ K = h \cdot S_b S_a P }[/math]

MQV vs HMQV

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:

1. Including the user identities in the key exchange flows: more specifically, letting [math]\displaystyle{ \bar{X} = H(X, B) }[/math] and [math]\displaystyle{ \bar{Y} = H(Y, A) }[/math] where [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math] are identities of Alice and Bob respectively.
2. 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.
3. 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.

See also

• Elliptic curve cryptography

Bibliography

• Kaliski, B. S. Jr (2001). "An unknown key-share attack on the MQV key agreement protocol". ACM Transactions on Information and System Security 4 (3): 275–288. doi:10.1145/501978.501981. 
• Law, L.; Menezes, A.; Qu, M.; Solinas, J.; Vanstone, S. (2003). "An Efficient Protocol for Authenticated Key Agreement". Des. Codes Cryptography 28 (2): 119–134. doi:10.1023/A:1022595222606. 
• Leadbitter, P. J.; Smart, N. P. (2003). "Analysis of the Insecurity of ECMQV with Partially Known Nonces". 6th International Conference, ISC 2003, Bristol, UK, October 1–3, 2003. Proceedings. 2851. pp. 240–251. doi:10.1007/10958513_19. ISBN 978-3-540-20176-2. 
• Menezes, Alfred J.; Qu, Minghua; Vanstone, Scott A. (2005). "Some new key agreement protocols providing implicit authentication". 2nd Workshop on Selected Areas in Cryptography (SAC '95). Ottawa, Canada. pp. 22–32. http://sacworkshop.org/proc/SAC_95_003.pdf. 
• Hankerson, D.; Vanstone, S.; Menezes, A. (2004). Guide to Elliptic Curve Cryptography. Springer Professional Computing. New York: Springer. doi:10.1007/b97644. ISBN 978-0-387-95273-4. 

External links

• 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)