Secure Programming Cookbook for C and C++: Recipes for Cryptography, Authentication, Input Validation & More
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.)
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.
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:
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:
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:
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:
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.)
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
|