3.11 Example: Establishing a shared secret

As one example that involves most predicates of this library, we explain a way to establish a shared secret over an insecure channel. We shall use elliptic curves for this purpose.

Suppose Alice wants to establish an encrypted connection with Bob. To achieve this even over a channel that may be subject to eavesdrooping and man-in-the-middle attacks, Bob performs the following steps:

1. Choose an elliptic curve C, using crypto_name_curve/2.
2. Pick a random integer k such that k is greater than 0 and smaller than the order of C. This can be done using crypto_curve_order/2 and crypto_n_random_bytes/2.
3. Use crypto_curve_generator/2 to obtain the generator G of C, and use crypto_curve_scalar_mult/4 to compute the scalar product k*G. We call this result R, denoting a point on the curve.
4. Sign R (using for example rsa_sign/4 or ecdsa_sign/4) and send this to Alice.

This mechanism hinges on a way for Alice to establish the authenticity of the signed message (using predicates like rsa_verify/4 and ecdsa_verify/4), for example by means of a public key that was previously exchanged or is signed by a trusted party in such a way that Alice can be sufficiently certain that it belongs to Bob. However, none of these steps require any encryption!

Alice in turn performs the following steps:

1. Create a random integer j such that j is greater than 0 and smaller than the order of C. Alice can also use crypto_curve_order/2 and crypto_n_random_bytes/2 for this.
2. Compute the scalar product j*G, where G is again the generator of C as obtained via crypto_curve_generator/2.
3. Further, compute the scalar product j*R, which is a point on the curve that we shall call Q. We can derive a shared secret from Q, using for example crypto_data_hkdf/4, and encrypt any message with it (using for example crypto_data_encrypt/6).
4. Send the point j*G and the encrypted message to Bob.

Bob receives j*G in plain text and can arrive at the same shared secret by performing the calculation k*(j*G), which is - by associativity and commutativity of scalar multiplication - identical to the point j*(k*G), which is again Q from which the shared secret can be derived, and the message can be decrypted with crypto_data_decrypt/6.

This method is known as Diffie-Hellman-Merkle key exchange over elliptic curves, abbreviated as ECDH. It provides forward secrecy (FS): Even if the private key that was used to establish the authenticity of Bob is later compromised, the encrypted messages cannot be decrypted with it.

A major attraction of using elliptic curves for this purpose is found in the comparatively small key size that suffices to make any attacks unrealistic as far as we currently know. In particular, given any point on the curve, we currently have no efficient way to determine by which scalar the generator was multiplied to obtain that point. The method described above relies on the hardness of this so-called elliptic curve discrete logarithm problem (ECDLP). On the other hand, some of the named curves have been suspected to be chosen in such a way that they could be prone to attacks that are not publicly known.

As an alternative to ECDH, you can use the original DH key exchange scheme, where the prime field GF(p) is used instead of an elliptic curve, and exponentiation of a suitable generator is used instead of scalar multiplication. You can use crypto_generate_prime/3 to generate a sufficiently large prime for this purpose.