Fully Hashed Menezes-Qu-Vanstone

From Crypto++ Wiki
Jump to navigation Jump to search

Fully Hashed Menezes-Qu-Vanstone (FHMQV) is ECMQV key agreement with enhancement and additional security properties published in A Secure and Efficient Authenticated Diffie–Hellman Protocol by by Augustin P. Sarr and Philippe Elbaz–Vincent, and Jean–Claude Bajard. FHMQV is based upon Hugo Krawczyk's HMQV: A High-Performance Secure Diffie-Hellman Protocol, in which Krawczyk identified and remediated issues from the original MQV.

The patch and code below was contributed to the Crypto++ community by Enrgies, Ray Clayton and Jeffrey Walton. Enrgies wanted to use an MQV-based key agreement scheme in a project and graciously donated the implementation back to the community.

The patch was later improved by Uri Blumenthal with feedback from colleagues. The improved patch is not compatible with the original patch. The compatibility differences are not security related; rather, they relate to the size of some operands (subgroup sizes versus hash sizes).

The improved patch was added to the Crypto++ 6.0 library. Prior to Crypto++ 6.0, you need to download the patch and install it into the Crypto++ directory.

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.

Crypto++ Validation

Crypto++'s valdat2.cpp test file performs FHMQV validation over Fp. See the ValidateFHMQV function for details.

Hashes and Curves

By default, Crypto++ uses SHA256 as the hash function for FHMQV. The hash meets current security level requirements for 3TDEA and AES. For a smaller or larger hash, we can perform the following.

typedef FHMQV< ECP, DL_GroupParameters_EC< ECP >::DefaultCofactorOption, SHA1 >::Domain FHMQV160;
typedef FHMQV< ECP, DL_GroupParameters_EC< ECP >::DefaultCofactorOption, SHA384 >::Domain FHMQV384;

FHMQV uses hashing at key points to harden against information leakage. Internally, the hash function is similar to below, where A and B are static public keys, and X and Y are ephemeral public keys. agreedValueLength specifies the size of the output buffer agreedValue.

Hash(sigma, XX, YY, AA, BB, agreedValue, agreedValueLength);

agreedValueLength depends on the hash block size and not the field element size. To determine the required size, call the AgreedValueLength function as shown in the example below.

Sample Program

Fully Hashed MQV is somewhat different than other key agreement classes, such as DH, DH2, ECDH and ECMQV. FHMQV has some symmetry, but it is necessary to specify a role: client or server. For example, in the code below, fhmqvA is assuming the client role by specifying true in its constructor, and fhmqvB is assuming the server role by specifying false.

While its not readily apparent, it does not matter which object sends the first message (ie, who takes the 'client' role and who takes the 'server' role). What matters is the roles are opposed between the parties participating in the exchange. For example, a 'server' could send the first message to a 'client'. In fact, Sarr, Elbaz–Vincent and Bajard's paper uses the terms Initiator and Recipient (the recipient responds to the initiator).

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). In the case of FHMQV, the shared secret does not require hashing.

AutoSeededRandomPool rng;
const OID CURVE = secp256r1();

FHMQV < ECP >::Domain fhmqvA( CURVE, true /*client*/ ), fhmqvB( CURVE, false /*server*/ );


// Party A, static (long term) key pair
SecByteBlock sprivA(fhmqvA.StaticPrivateKeyLength()), spubA(fhmqvA.StaticPublicKeyLength());

// Party A, ephemeral (temporary) key pair
SecByteBlock eprivA(fhmqvA.EphemeralPrivateKeyLength()), epubA(fhmqvA.EphemeralPublicKeyLength());

// Party B, static (long term) key pair
SecByteBlock sprivB(fhmqvB.StaticPrivateKeyLength()), spubB(fhmqvB.StaticPublicKeyLength());

// Party B, ephemeral (temporary) key pair
SecByteBlock eprivB(fhmqvB.EphemeralPrivateKeyLength()), epubB(fhmqvB.EphemeralPublicKeyLength());


// Imitate a long term (static) key
fhmqvA.GenerateStaticKeyPair(rng, sprivA, spubA);

// Ephemeral (temporary) key
fhmqvA.GenerateEphemeralKeyPair(rng, eprivA, epubA);

// Imitate a long term (static) key
fhmqvB.GenerateStaticKeyPair(rng, sprivB, spubB);

// Ephemeral (temporary) key
fhmqvB.GenerateEphemeralKeyPair(rng, eprivB, epubB);


SecByteBlock sharedA(fhmqvA.AgreedValueLength()), sharedB(fhmqvB.AgreedValueLength());

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

if(!fhmqvB.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 will not authenticate.

A typical run of the program using secp256r1 is shown below.

$ ./fhmqv-agree.exe 
(A): 32f11d394abc3bf499e7c35e7b88103f5aec0e8d74eae7bd8c670994d26fc95h
(B): 32f11d394abc3bf499e7c35e7b88103f5aec0e8d74eae7bd8c670994d26fc95h
Agreed to shared secret

Other Patches

If you applied the DataDir patch, then you will need to apply the DataDir patch by hand. Simply change the following line in validat2.cpp:

FileSource f("TestData/fhmqv256.dat", true, new HexDecoder());


FileSource f(DataDir("TestData/fhmqv256.dat").c_str(), true, new HexDecoder());


fhmqv.zip - Fully Hashed Menezes-Qu-Vanstone (FHMQV) key agreement rollup of source files. Download and unpack over exiting Crypto++ sources. Be sure to put fhmqv.dat in the TestData folder.

fhmqv-diff.zip - Fully Hashed Menezes-Qu-Vanstone (FHMQV) key agreement patch.

fhmqv-agree.zip - Fully Hashed Menezes-Qu-Vanstone (FHMQV) key agreement (authenticated).

fhmqv-tamper.zip - Fully Hashed Menezes-Qu-Vanstone (FHMQV) key agreement run under tampering. Entity A's public key is first modified so that (x,y) → (x,y+1), which is not on the curve. The second tampering modifies the public key so that a valid point on the curve is created (but Entity A does not have the private key).