Elliptic Curve Fully Hashed Menezes-Qu-Vanstone

From Crypto++ Wiki
Jump to navigation Jump to search
#include <cryptopp/eccrypto.h>

Elliptic Curve Fully Hashed Menezes-Qu-Vanstone, or ECFHMQV, is an 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).

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.

Hashes and Curves

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

typedef ECFHMQV< ECP, DL_GroupParameters_EC< ECP >::DefaultCofactorOption, SHA1 >::Domain ECFHMQV160;
typedef ECFHMQV< ECP, DL_GroupParameters_EC< ECP >::DefaultCofactorOption, SHA384 >::Domain ECFHMQV384;

ECFHMQV 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.

#include "cryptlib.h"
#include "eccrypto.h"
#include "secblock.h"
#include "osrng.h"
#include "oids.h"
#include "hex.h"

#include <iostream>
#include <string>
#include <stdexcept>

int main(int argc, char* argv[])
    using namespace CryptoPP;

    AutoSeededRandomPool rng;
    const OID CURVE = ASN1::secp256r1();

    ECFHMQV < 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 std::runtime_error("Failed to reach shared secret (A)");

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

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

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

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

    return 0;

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): dbe578871efac819e2cd1499bbc3aeebd91236ff1668106398bb3c2a1a1c33a6h
(B): dbe578871efac819e2cd1499bbc3aeebd91236ff1668106398bb3c2a1a1c33a6h
Agreed to shared secret


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