Elliptic Curve Menezes-Qu-Vanstone

From Crypto++ Wiki
Jump to navigation Jump to search

Elliptic Curve Menezes-Qu-Vanstone (ECMQV) is key agreement performed using elliptical curves rather than traditional integers (see, for example DH and DH2). The protocol was introduced by Laurie Law, Alfred Menenzes and others in An Efficient Protocol for Authenticated Key Agreement. ECMQV is authenticated, so it does not suffer Man in the Middle (MitM) attacks.

ECMQV leaks private session information and should not be used. Use HMQV or FHMQV instead. For unauthenticated Diffie-Hellman using elliptic curves, see ECDH.

Ján Jančár showed Crypto++ 8.2 and below leaked timing information in elliptic curve gear. You should upgrade to Crypto++ 8.3 and above. Also see Issue 869, Elliptic Curve timing leaks.

Finally, this page is concerned with two party key agreement. For group key agreement and multicast scenarios, see Multicast Security: A Taxonomy and Some Efficient Constructions and Provably Authenticated Group Diffie-Hellman Key Exchange. Also see the Elliptic Curve Cryptography wiki page.

Crypto++ Validation

Crypto++'s valdat2.cpp test file performs ECMQV validation over Fp and F2m. See the ValidateMQV function for details.

Key Agreement

The code below performs ephemeral-ephemeral key agreement using NIST's 256 bit curve over Fp. The ephemeral-ephemeral refers to temporary keys used by both parties (as opposed to static or long term keys). Though each party has a static, long term key, the static keys are used to authenticate the parties and not to perform the customary exponentiation.

The agreed upon value is encoded as an Integer because the class overloads the output operator, which makes it easy to print. In practice, the shared secret is usually hashed before use, and then used as a Key Encryption Key (KEK) to transport a random session key; or used as a Content Encryption Key (CEK).

OID CURVE = secp256r1();
AutoSeededRandomPool rng;

ECMQV < ECP >::Domain mqvA( CURVE ), mqvB( CURVE );

// Party A, static (long term) key pair
SecByteBlock sprivA(mqvA.StaticPrivateKeyLength()), spubA(mqvA.StaticPublicKeyLength());
// Party A, ephemeral (temporary) key pair
SecByteBlock eprivA(mqvA.EphemeralPrivateKeyLength()), epubA(mqvA.EphemeralPublicKeyLength());

// Party B, static (long term) key pair
SecByteBlock sprivB(mqvB.StaticPrivateKeyLength()), spubB(mqvB.StaticPublicKeyLength());
// Party B, ephemeral (temporary) key pair
SecByteBlock eprivB(mqvB.EphemeralPrivateKeyLength()), epubB(mqvB.EphemeralPublicKeyLength());

// Imitate a long term (static) key
mqvA.GenerateStaticKeyPair(rng, sprivA, spubA);
// Ephemeral (temporary) key
mqvA.GenerateEphemeralKeyPair(rng, eprivA, epubA);

// Imitate a long term (static) key
mqvB.GenerateStaticKeyPair(rng, sprivB, spubB);
// Ephemeral (temporary) key
mqvB.GenerateEphemeralKeyPair(rng, eprivB, epubB);

if(mqvA.AgreedValueLength() != mqvB.AgreedValueLength())
    throw runtime_error("Shared secret size mismatch");

SecByteBlock sharedA(mqvA.AgreedValueLength()), sharedB(mqvB.AgreedValueLength());

if(!mqvA.Agree(sharedA, sprivA, eprivA, spubB, epubB))
    throw runtime_error("Failed to reach shared secret (A)");

if(!mqvB.Agree(sharedB, sprivB, eprivB, spubA, epubA))
    throw runtime_error("Failed to reach shared secret (B)");

Integer ssa, ssb;

ssa.Decode(sharedA.BytePtr(), sharedA.SizeInBytes());
cout << "(A): " << std::hex << ssa << endl;

ssb.Decode(sharedB.BytePtr(), sharedB.SizeInBytes());
cout << "(B): " << std::hex << ssb << endl;

if(ssa != ssb)
    throw runtime_error("Failed to reach shared secret (C)");

cout << "Agreed to shared secret" << endl;

In production, the test ssa != ssb cannot be performed since the values will be on different hosts. A problem with agreement will not be detected until data starts flowing - the first data packet received with not authenticate.

A typical run is shown below.

$ ./mqv-agree.exe
(A): 5d00d3c434f852b626a32775e0b87a49c27f2eb9ec7b634f3480c2bae25bf0e5h
(B): 5d00d3c434f852b626a32775e0b87a49c27f2eb9ec7b634f3480c2bae25bf0e5h
Agreed to shared secret


mqv-agree.zip - Elliptic Curve Menezes-Qu-Vanstone (ECMQV) key agreement (authenticated).