8.17 Using Basic Diffie-Hellman Key Agreement

8.17.1 Problem

You want a client and a server to agree on a shared secret such as an encryption key, and you need or want to use the Diffie-Hellman key exchange protocol.

8.17.2 Solution

Your cryptographic library should have an implementation of Diffie-Hellman. If it does not, be aware that Diffie-Hellman is easy to implement on top of any arbitrary precision math library. You will need to choose parameters in advance, as we describe in the following Section 8.17.3.

Once you have a shared Diffie-Hellman secret, use a key derivation function to derive an actual secret for use in other cryptographic operations. (See Recipe 4.11.)

8.17.3 Discussion

Diffie-Hellman is a very simple way for two entities to agree on a key without an eavesdropper's being able to determine the key. However, room remains for a man-in-the-middle attack. Instead of determining the shared key, the attacker puts himself in the middle, performing key agreement with the client as if he were the server, and performing key agreement with the server as if he were the client. That is, when you're doing basic Diffie-Hellman, you don't know who you're exchanging keys with; you just know that no one else has calculated the agreed-upon key by snooping the network. (See Recipe 7.1 for more information about such attacks.)

To solve the man-in-the-middle problem, you generally need to introduce some sort of public key authentication mechanism. With Diffie-Hellman, it is common to use DSA (see Recipe 7.15 and Recipe 8.18).

Basic Diffie-Hellman key agreement is detailed in PKCS (Public Key Cryptography Standard) #3.^[3] It's a much simpler standard than the RSA standard, in part because there is no authentication mechanism to discuss.

^[3] See http://www.rsasecurity.com/rsalabs/pkcs/pkcs-3/.

The first thing to do with Diffie-Hellman is to come up with a Diffie-Hellman modulus n that is shared by all entities in your system. This parameter should be a large prime number, at least 1,024 bits in length (see the considerations in Recipe 8.17). The prime can be generated using Recipe 7.5, with the additional stipulation that you should throw away any value where (n - 1)/2 is not also prime.

Some people like to use a fixed modulus shared across all users. We don't recommend that approach, but if you insist on using it, be sure to read RFCs 2631 and 2785.

Diffie-Hellman requires another parameter g, the "generator," which is a value that we'll be exponentiating. For ease of computation, use either 2 or 5.^[4] Note that not every {prime, generator} pair will work, and you will need to test the generator to make sure that it has the mathematical properties that Diffie-Hellman requires.

^[4] It's possible (but not recommended) to use a nonprime value for n, in which case you need to compute a suitable value for g. See the Applied Cryptography for an algorithm.

OpenSSL expects that 2 or 5 will be used as a generator. To select a prime for the modulus, you can use the function DH_generate_parameters( ), which has the following signature:

DH *DH_generate_parameters(int prime_len, int g,                             void (*callback)(int, int, void *), void *cb_arg);

This function has the following arguments:

prime_len

Size in bits of the prime number for the modulus (n) to be generated.

g

Generator you want to use. It should be either 2 or 5.

callback

Pointer to a callback function that is passed directly to BN_generate_prime( ), as discussed in Recipe 7.4. It may be specified as NULL, in which case no progress will be reported.

cb_arg

Application-specific argument that is passed directly to the callback function, if one is specified.

The result will be a new DH object containing the generated modulus (n) and generator (g) parameters. When you're done with the DH object, free it with the function DH_free( ).

Once parameters are generated, you need to check to make sure the prime and the generator will work together properly. In OpenSSL, you can do this with DH_check( ):

int *DH_check(DH *ctx, int *err);

This function has the following arguments:

ctx

Pointer to the Diffie-Hellman context object to check.

err

Pointer to an integer to which is written an indication of any error that occurs.

This function returns 1 even if the parameters are bad. The 0 return value indicates that the generator is not 2 or 5, as OpenSSL is not capable of checking parameter sets that include other generators. Any error is always passed through the err parameter. The errors are as follows:

H_CHECK_P_NOT_SAFE_PRIME

DH_NOT_SUITABLE_GENERATOR

DH_UNABLE_TO_CHECK_GENERATOR

The first two errors can occur at the same time, in which case the value pointed to by err will be the logical OR of both constants.

Once both sides have the same parameters, they can send each other a message; each then computes the shared secret. If the client initiates the connection, the client chooses a random value x, where x is less than n. The client computes A = gx mod n, then sends A to the server. The server chooses a random value y, where y is less than n. The server computes B = gy mod n, then sends B to the client.

The server calculates the shared secret by computing k = Ay mod n. The client calculates the same secret by computing Bx mod n.

Generating the message to send with OpenSSL is done with a call to the function DH_generate_key( ):

int DH_generate_key(DH *ctx);

The function returns 1 on success. The value to send to the other party is stored in ctx->pub_key.

Once one side receives the public value from the other, it can generate the shared secret with the function DH_compute_key( ):

int DH_compute_key(unsigned char *secret, BIGNUM *pub_value, DH *dh);

This function has the following arguments:

secret

Buffer into which the resulting secret will be written, which must be large enough to hold the secret. The size of the secret can be determined with a call to DH_size(dh).

pub_value

Public value received from the other party.

dh

DH object containing the parameters and public key.

Once both sides have agreed on a secret, it generally needs to be turned into some sort of fixed-size key, or a set of fixed-size keys. A reasonable way is to represent the secret in binary and cryptographically hash the binary value, truncating if necessary. Often, you'll want to generate a set of keys, such as an encryption key and a MAC key. (See Recipe 4.11 for a complete discussion of key derivation.)

Key exchange with Diffie-Hellman isn't secure unless you have some secure way of authenticating the other end. Generally, you should digitally sign messages in this protocol with DSA or RSA, and be sure that both sides securely authenticate the signature for example, through a public key infrastructure.

Once a key or keys are established, the two parties try to communicate. If both sides are using message integrity checks, they'll quickly know whether or not the exchange was successful (if it's not, nothing will validate on decryption).

If you don't want to use an existing API, here's an example of generating a random secret and computing the value to send to the other party (we use the OpenSSL arbitrary precision math library):

#include <openssl/bn.h>     typedef struct {   BIGNUM *n;   BIGNUM *g; /* use a BIGNUM even though g is usually small. */   BIGNUM *private_value;   BIGNUM *public_value; } DH_CTX;     /* This function assumes that all BIGNUMs are already allocated, and that n and g  * have already been chosen and properly initialized.  After this function  * completes successfully, use BN_bn2bin(  ) on ctx->public_value to get a binary  * representation you can send over a network.  See Recipe 7.4 for more info on  * BN<->binary conversions.  */ int DH_generate_keys(DH_CTX *ctx) {   BN_CTX *tmp_ctx;       if (!(tmp_ctx = BN_CTX_new(  ))) return 0;   if (!BN_rand_range(ctx->private_value, ctx->n)) {     BN_CTX_free(tmp_ctx);     return 0;   }   if (!BN_mod_exp(ctx->public_value, ctx->g, ctx->private_value, ctx->n, tmp_ctx)) {     BN_CTX_free(tmp_ctx);     return 0;   }   BN_CTX_free(tmp_ctx);   return 1; }

When one side receives the Diffie-Hellman message from the other, it can compute the shared secret from the DH_CTX object and the message as follows:

BIGNUM *DH_compute_secret(DH_CTX *ctx, BIGNUM *received) {   BIGNUM *secret;   BN_CTX *tmp_ctx;       if (!(secret = BN_new(  ))) return 0;   if (!(tmp_ctx = BN_CTX_new(  ))) {     BN_free(secret);     return 0;   }   if (!BN_mod_exp(secret, received, ctx->private_value, ctx->n, tmp_ctx)) {     BN_CTX_free(tmp_ctx);     BN_free(secret);     return 0;   }   BN_CTX_free(tmp_ctx);   return secret; }

You can turn the shared secret into a key by converting the BIGNUM object returned by DH_compute_secret( ) to binary (see Recipe 7.4) and then hashing it with SHA1, as discussed above.

Traditional Diffie-Hellman is sometimes called ephemeral Diffie-Hellman, because the algorithm can be seen as generating key pairs for one-time use. There are variants of Diffie-Hellman that always use the same values for each client. There are some hidden "gotchas" when doing that, so we don't particularly recommend it. However, if you wish to explore it, see RFC 2631 and RFC 2785 for more information.

8.17.4 See Also

• RFC 2631: Diffie-Hellman Key Agreement Method

• RFC 2785: Methods for Avoiding the "Small-Subgroup" Attacks on the Diffie-Hellman Key Agreement Method for S/MIME

• Recipe 4.11, Recipe 7.1, Recipe 7.4, Recipe 7.5, Recipe 7.15, Recipe 8.17, Recipe 8.18