Elliptic Curve Diffie-Hellman

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

Elliptic Curve Diffie-Hellman (ECDH) is key agreement protocol performed using elliptical curves rather than traditional integers (see, for example DH and DH2). The protocol allows parties to create a secure channel for communications.

There are two variants of ECDH - ephemeral-ephemeral and ephemeral-static. ephemeral-ephemeral is anonymous and suffers Man in the Middle (MitM) attacks. When using plain ECDH, you usually pair it with a signing algorithm like ECDSA or RSA. See, for example, RFC 4492, Elliptic Curve Cryptography (ECC) Cipher Suites for Transport Layer Security (TLS). For authenticated Diffie-Hellman using elliptic curves (and other security assurances such as key confirmation and forward secrecy), see ECMQV, HMQV and FHMQV.

An example of using Crypto++ ECDH class and Java can be found on Stack Overflow at ECDH Shared Secret does not match between Crypto++ and Android.

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.

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.

Choice of Fields

ECDH is defined over both prime fields (Fp) and binary fields (F2m). To operate over a prime field, use ECP: 

ECDH<ECP>::Domain ecdh;

For binary fields, specify EC2N: 

ECDH<EC2N>::Domain ecdh;

Key Agreement

The code below performs key agreement using NIST's 256 bit curve over Fp. 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;

ECDH < ECP >::Domain dhA( CURVE ), dhB( CURVE );
SecByteBlock privA(dhA.PrivateKeyLength()), pubA(dhA.PublicKeyLength());
SecByteBlock privB(dhB.PrivateKeyLength()), pubB(dhB.PublicKeyLength());

dhA.GenerateKeyPair(rng, privA, pubA);
dhB.GenerateKeyPair(rng, privB, pubB);

if(dhA.AgreedValueLength() != dhB.AgreedValueLength())
    throw runtime_error("Shared shared size mismatch");

SecByteBlock sharedA(dhA.AgreedValueLength()), sharedB(dhB.AgreedValueLength());

if(!dhA.Agree(sharedA, privA, pubB))
    throw runtime_error("Failed to reach shared secret (A)");

if(!dhB.Agree(sharedB, privB, pubA))
    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 and fails to authenticate. This can be remedied with a key confirmation protocol.

A typical run is shown below. 

$ ./ecdh.exe
(A): 2b21da66d49b8faa85abc71a4cb23298c9b0c035841eef618fded5eaeb551fb6h
(B): 2b21da66d49b8faa85abc71a4cb23298c9b0c035841eef618fded5eaeb551fb6h
Agreed to shared secret

Public and Private Keys

The format used by the public and private keys is a constant source of interop problems. The following shows what Crypto++ uses. 

AutoSeededRandomPool prng;

OID oid = ASN1::secp256r1();
ECDH<ECP>::Domain ecdh(oid);

SecByteBlock privKey(ecdh.PrivateKeyLength()), pubKey(ecdh.PublicKeyLength());
ecdh.GenerateKeyPair(prng, privKey, pubKey);

HexEncoder encoder(new FileSink(cout));

cout << "Private key: ";
encoder.Put(privKey, privKey.size());
cout << endl;

cout << "Public key: ";
encoder.Put(pubKey, pubKey.size());
cout << endl;

After running the program the output is similar to: 

$ ./test.exe 
Private key: 4E832960415F2B5FA2B1FDA75C1A8F3C84BAEB189EDC47211EF6D27A21FC0ED8
Public key: 042166AE4F89981472B7589B8D79B8F1244E2EEE6E0A737FFBFED2981DA3E193D
6643317E054D2A924F2F56F1BF4BECA13192B27D8566AF379FBBF8615A223D899

The private key is the exponent, which is a scalar or an integer. You can convert it to a Crypto++ Integer with the following because the private key is just a big-endian array. 

Integer x("0x4E832960415F2B5FA2B1FDA75C1A8F3C84BAEB189EDC47211EF6D27A21FC0ED8");

Since the private key is just a big-endian array, you could perform the following in the example under Key Agreement. Integer's Decode takes a big-endian array of bytes: 

Integer ssa;
ssa.Decode(sharedA.BytePtr(), sharedA.SizeInBytes());

The public key is an element, which is a point on the curve. The leading 0x04 says its an uncompressed point. You can convert it to a Crypto++ Point with the following because a point is a pair of scalars or integers, and the integers are just a big-endian arrays. 

Integer x("0x2166AE4F89981472B7589B8D79B8F1244E2EEE6E0A737FFBFED2981DA3E193D6");
Integer y("0x643317E054D2A924F2F56F1BF4BECA13192B27D8566AF379FBBF8615A223D899");

ECP::Point q(x, y);

If you take the curve's base point G and exponentiate it with x (private key), then you will get the point Q (public key).

Ephemeral Key as (x,y)

If you have the other party's public key as an (X,Y) pair, then the following will allow you to use it with ECDH class. You will have to supply the values used for the ECP::Point q(x,y) below, but you already have x and y. 

OID curve = ASN1::secp256r1();
DL_GroupParameters_EC<ECP> params(curve);

size_t size = params.GetEncodedElementSize(true);
vector<byte> otherPublicKey(size);

ECP::Point q(x,y);
params.EncodeElement(true, q, &otherPublicKey[0]);

Later, you can use it as so: 

ecdh.Agree(sharedKey, myPrivateKey, &otherPublicKey[0]);

The preceding works because internally the ephemeral public and private keys are created in pubkey.h around line 1380. The code for them is below. 

void GeneratePrivateKey(RandomNumberGenerator &rng, byte *privateKey)
{
    Integer x(rng, Integer::One(), GetAbstractGroupParameters().GetMaxExponent());
    x.Encode(privateKey, PrivateKeyLength());
}

void GeneratePublicKey(RandomNumberGenerator &rng, const byte *privateKey, byte *publicKey)
{
    const DL_GroupParameters<T> &params = GetAbstractGroupParameters();
    Integer x(privateKey, PrivateKeyLength());
    Element y = params.ExponentiateBase(x);
    params.EncodeElement(true, y, publicKey);
}

The line of interest above is the params.EncodeElement(true, y, publicKey). More details are available at eccrypto.h around line 70: 

void EncodeElement(bool reversible, const Element &element, byte *encoded)
{
    if (reversible)
        GetCurve().EncodePoint(encoded, element, m_compress);
    else
        element.x.Encode(encoded, GetEncodedElementSize(false));
}

reversible is true, so params.EncodeElement calls ECP::EncodePoint. The code for ECP::EncodePoint is located in ecp.cpp around line 120. The routine writes a uncompressed point, but blocks x and y on the maximum size of the public element, which should be the field size or the subgroup order. 

void ECP::EncodePoint(BufferedTransformation &bt, const Point &P, bool compressed)
{
    if (P.identity)
        NullStore().TransferTo(bt, EncodedPointSize(compressed));
    else if (compressed)
    {
        bt.Put(2 + P.y.GetBit(0));
        P.x.Encode(bt, GetField().MaxElementByteLength());
    }
    else
    {
        unsigned int len = GetField().MaxElementByteLength();
        bt.Put(4);      // uncompressed
        P.x.Encode(bt, len);
        P.y.Encode(bt, len);
    }
}

Downloads

ecdh-agree.zip - Elliptic Curve Diffie-Hellman (ECDH) key agreement (unauthenticated).

Retrieved from "https://www.cryptopp.com/w/index.php?title=Elliptic_Curve_Diffie-Hellman&oldid=28525"