In Introduction to Symmetric Encryption for the Working Developer, we saw how to encrypt and decrypt data. Being symmetric encryption, both the process of encryption and decryption needed the same key. This poses a challenge, which was not addressed in the post: How do one get across the same key to both parties who want to engage in encrypted communication?
Basically how do we perform key exchange? How do we get the same key to parties who want to encrypt and decrypt messages?
An approach is perhaps for the parties involved to first meet in person and exchange the key?
Another approach could be to use another communication channel to first share the key? But then again, if the other communication channel is digital, and it uses symmetric encryption, how should its encryption key be also exchanged? This becomes a catch 22 real quick.
This is the problem Key exchange schemes seek to solve, and thankfully there is a secure way to have two parties exchange secret keys without the need to physically meet in person. This is what this post is about. We will be looking at two popular mechanisms for key exchange: Diffie-Hellman key exchange procedures and application of RSA for key exchange.
As always, as with the other posts in this series, the idea is to provide the basic information needed by the working developer to be able to understand and use these cryptographic primitives without going into the thick of their internal details or implementation.
This post contains the following sections
- Entering the realm of Public Key Cryptography
- Introduction to Diffie-Hellman Key Exchange: An Intuition.
- Whirlwind tour of the Mathematics
- Diffie-Hellman in code
- Diffie-Hellman Standards
- Using RSA for key exchange
- Conclusion and References
Entering the Realm of Public Key Cryptography
Public key cryptography (or Asymmetric key cryptography) is a class of cryptography primitives that makes use of dissimilar keys. This is different from Symmetric key cryptography which makes use of similar keys for its operations.
Public key cryptography also relies more heavily on Mathematics, especially number theory, and the security properties and guarantees it provides is often as a result of a direct consequence of some mathematical theory. Hence in discussion of cryptographic primitives that can be classified as public key cryptography there is more encounter of mathematical notations and theorems.
This post will not go into the mathematical underpinning of the cryptography primitives discussed. Instead, I will highlight the mathematical theories in this post and point to resources, motivated readers can check out to learn more.
Let's start by exploring one of the two schemes that uses public key cryptography for key exchange: that is: Diffie-Hellman.
Introduction to Diffie-Hellman Key Exchange: An Intuition
The Diffie-Hellman key exchange is a method that allows two parties, communicating in a public, insecure channel, to exchange messages that allows them to derive the same secret key. But the method has the property that eavesdroppers observing the messages being exchanged won't be able to use it to construct the secret key derived by the parties engaged in the key exchange.
How is this possible? To have two parties exchange two numbers, that anyone can see, and then, separately, these two parties use the numbers they receive from each other to compute another number privately, and the number they compute will end up being the same (ie the secret key) but the people that observed the numbers that was exchange cannot do the same computation to arrive at the secret key?
A good intuition to have about how the process works is this. It is a process for two parties to first exchange two secret numbers. But they do not just exchange this secret number, they first mix it up with another number both parties agree with.
So each party comes up with a secret number, mixes it up with a publicly agreed number and shares.
After the sharing, both parties have the secret number generated by the other party mixed up with an agreed number. Anyone observing the exchange can only see the results of the mixed number (that is, party A's secret number mixed with an agreed number which is not secret and party B's secret number mixed with the same agreed number). The security of this exchange boils down to the inability to break apart the result of this number mixing to reveal the secret number that was mixed with it. In Diffie-Hellman, this is impossible to achieve based on the discrete algorithm problem which will be briefly explored later on. But for this intuition, we agree that, parties mixed numbers and share, and anyone observing cannot break this number apart.
After the mixing and sharing what do we have? We actually have both parties having each other's secret number. Only that, this secret number they have of each other is not "bare" but mixed up with an agreed number.
What then happens is that both parties perform a computation using their secret number on the other party's secret number (but mixed up in an agreed number) and they will both arrive at another secret number which can be used as the secret key.
That is the intuition. The Diffie-Hellman is a process for two parties to first initially exchange a secret number mixed up with an agreed and non-secretive number, and then use this to perform a computation. What ends up happening is that the inputs to the computation on each party's side are the same. That is for party A, it is compute(secret A, M1 = (mixing number + secret B)) while for party B, it is compute(secret B, M2 = (mixing number + secret A)).
Even if the mixing number is known, as long as it is impossible to break M1 or M2 apart to retrieve secret B or secret A, then the scheme works.
That is the intuition of the process. Now let's dig deeper into how things work, without also going into too much of the mathematics.
Whirlwind tour of the Mathematics
The idea of this section is to give an overview of the key concepts from mathematics that come together to make Diffie-Hellman possible. For obvious reasons, an in depth coverage of these concepts is not possible in this one post, but links would be sprinkled in pointing to where more information can be gotten.
So let's start.
We all know about sets from elementary mathematics. When sets fulfil certain characteristics, they are said to form a group. These characteristics include Closure, Associativity, Presence of an Identity Element and presence of an Inverse element. The study of these characteristics is called group theory.
A key part of a group is the presence of a binary operation. That is an operation that operates on two inputs to produce an output that is also a member of the set. Examples of binary operations include addition, or multiplication or Modulo multiplication. Modulo operation are mathematical operations involving numbers that wrap around. It is also often called clock arithmetics.
The two flavors of Diffie-Hellman algorithms that we have, Diffie-Hellman in a modulo multiplicative group and Elliptic Curve Diffie Hellman (ECDH) both make use of groups and binary operations.
In the first flavor, the group includes the set of strictly positive integers 1, 2, p – 1 for p a prime number, along with modular multiplication, where the modulo is a prime.
The second flavor makes use of groups that form an elliptic curve, while the binary operation is addition. The algorithm for ECDH is a bit involved when compared hence a quick overview of the first flavor is given in this post.
So as stated, the first (or classic) Diffie-Hellman algorithm makes use of groups made up of positive integers, with binary operation being multiplication with the modulo being a prime P.
The algorithm involves picking a number that forms a primitive root with the modulo prime. This number that we pick when multiplied with itself ad-infinitum, in modulo prime, will generate a cyclic subgroup, ie when it is raised to power n, where n = 1,2,3, (infinity - 1), under modulo prime P, will produce a cyclic group. This extra characteristic is important in order to ensure the discrete logarithm problem is sufficiently hard enough to ensure the security of the algorithm.
And the discrete logarithm problem is a class of problems that is sometimes referred to as one way function, i.e. functions easy to compute given inputs, but hard or almost impossible to retrieve the inputs given the results of the computation. The discrete logarithm problem simply states that, given a number x and y where y is greater than x, it is hard to find the number of times n, x needs to be multiplied by itself to result into y, under modulo of another number p.
In the classic Diffie-Hellman algorithm, a prime number P and an integer g, the generator is agreed upon by the two parties. This is what they use to mix the secret number they want to pass on to each other that would be used to derive the private key.
Party A generates a secret number sa, and then mixes it up with prime p and generator g by computing = AK = g^sa mod p
AK is referred to as a public key and Party A sends this value to party B.
Party B generates a secret number sb, and then mixes it up with prime p and generator g by computing = BK = g^sb mod p
BK is referred to as a public key and party B sends this value to party A.
At this point, party A has BK, while party B has AK.
Party A now computes the secret key by computing SK= BK^sa mod p and party B also computes the secret key by computing SK= AK^sb mod p. They both arrive at the same value because:
BK^sa = (g^sb)sa = g^(sb)(sa) = (g^sa)sb = AK^sa mod p
The two values publicly transmitted are AK = g^sa mod p and BK = g^sb mod p.
g and p are known, AK and BK are also known, as they are communicated in the clear. But anyone observing these numbers won't be able to derive what sa or sb is. Because of the discrete logarithm problem.
It is worth mentioning that in practice, the SK arrived is not used directly as the secret key, but usually passed through a Key derivation function.
Let's see how this procedure looks in code.
Diffie-Hellman in code
Before showing the code, let's go over the steps again.
As stated, the objective is for two parties to arrive at the same secret key that can be used for symmetric encryption, without having to directly share the key.
A rough step by step outline of how it works is as follows:
- Both Alice and Bob agree on using Diffie-Hellman. This involves agreeing on two numbers. One small usually referred to as g, and another big, which is a prime number, usually referred to as p.
- Alice generates a secret number. Performs a modulus computation with it together with g and the prime number p. This computation derives another number called the public key. This is why this procedure falls under Public Key Cryptography.
- Bob also does the same.
- Alice gives Bob her public number, while keeping her secret one. Bob also gives Alice his public number and keeps his secret number. Now Alice has her secret number and technically Bob's secret number mixed within Bob's public number. Bob also has his secret number and Alice's secret number mixed in the public number he received from her.
- Alice uses her secret number and Bob's public number to calculate another number
- Bob does the same, using his own secret number and Alice's public number.
- Both Alice and Bob will then arrive at the same generated number which can then be used for symmetric encryption.
- Eve who observed all the exchanges, could know the algorithm being used and can see all the numbers exchanged, including the g and p agreed upon, won't be able to compute the shared secret both Alice and Bob compute independently.
The following Javascript code snippets in nodejs demonstrates how the Diffie-Hellman scheme can be put to use.
const crypto = require('crypto')
const assert = require('assert');
// -- Select mod p group
// Alice is using the modp15 group
const groupA = crypto.getDiffieHellman('modp15')
// const groupA = crypto.createECDH('brainpoolP160t1')
// Bob is also using the modp15 group
const groupB = crypto.getDiffieHellman('modp15')
// const groupB = crypto.createECDH('brainpoolP160t1')
// The modp15 group just like others define same generator and prime. hence the prime and generator for groupA and groupB should be same
assert(groupA.getPrime().toString("hex") === groupB.getPrime().toString("hex"))
assert(groupA.getGenerator().toString("hex") === groupB.getGenerator().toString("hex"))
// -- Generate the keys
// With this call, the secret key k1 is generated
// The k1 is then use to generate the public key, which is = g^k1 mod p
// Note that new k1 is generated on each invocation of this function.
groupA.generateKeys()
// With this call, the secret key k2 is generated
// The k2 is then use to generate the public key, which is = g^k2 mod p
// Note that new k2 is generated on each invocation of this function.
groupB.generateKeys()
// At this point the public key can be shared with other parties which can then be used to arrive at the shared secret
// Not that the private key is also available via getPrivateKey call but there should be no need to retrieve this. Having
// this value known by a malicious actor will compromise the integrity of the protocol
console.log(`Public key of group A ${groupA.getPublicKey().toString("hex")}`)
console.log(`Public key of group B ${groupB.getPublicKey().toString("hex")}`)
// --- Now each party use the other public key to generate the shared secret
let sharedSecretA = groupA.computeSecret(groupB.getPublicKey())
let sharedSecretB = groupB.computeSecret(groupA.getPublicKey())
// Confirm that same value was arrived at
assert(sharedSecretA.toString("hex") === sharedSecretB.toString("hex"))
Diffie-Hellman Standards
The Diffie-Hellman scheme is made up of components that can be varied. Depending on how these components are configured, the security guarantees of the scheme can be affected.
The main components that are configurable is the value of g (the generator), and p (the prime) to be used.
Thing is, anyone implementing Diffie-Hellman key exchange is free to pick whatever value they think is secured for these two components. For example this file contains some popular Diffie-Hellman configuration observed in the wild.
The only problem is, not all values lead to a secured scheme. For example in 2016, it was discovered that socat a networking utility, was using Diffie-Hellman configuration that makes it insecure. Hence as a developer, implementing or using any service that makes use of Diffie-Hellman key, to be aware what secured configurations are being used.
To help with this, there are recommendations stated in various RFCs. These recommendations are largely categorized into two: Recommended values to be used for multiplicative groups and those based on elliptic curves.
Recommendation for DH For the multiplicative groups, it is advised to use prime numbers whose values are not less than 2048 bits. This ensures that a minimum of 128 bit of security is provided. The recent RFC that contains up to date best practices and recommendations can be found in RFC 7919
Recommendation for ECDH For the Elliptic curve diffie-hellman, there are a couple of curves that most applications have standardized around. These include P-256, Curve25519, and Curve448. The curve P-256, and Curve25519 provides 128 bit of security, while Curve448 offers around 224 bit of security. When Curve25519 is used to implement the Diffie-Hellman key exchange, it is also referred to as X25519. ECDH is preferred over DH due to its smaller key size. To get a 128 bit of security DH requires nothing less than 2048 bits, but with ECDH, the requirement is nothing less than 256 bits.
Using RSA for key exchange
RSA is a popular asymmetric crypto-system which can also be used for exchanging keys. RSA by itself is a distinct topic that should be covered separately but for completeness it is mentioned here as another way for two parties to exchange secret keys.
Conclusion and References
Summary
- Two parties can arrive at the same secret number by performing the Diffie Hellman key exchange. This helps solve the problem of how two parties securely share the secret key needed for encryption.
- Diffie Hellman requires numbers that form what is mathematically known as groups. Two popular groups are widely used: Multiplicative groups modulo a prime number and Elliptic curves
- When Multiplicative groups modulo a prime number is used, it is usually referred to as just Diffie-Hellman ie DH
- When Elliptic curves are used, it is usually referred to as Elliptic Curve Diffie Hellman ie ECDH
- The recommended standard to use for DH is found in RFC 7919
- The popular curves used in ECDH are P-256, Curve25519, and Curve448, with Curve25519 being quite popular.
- When Curve25519 is used to implement the Diffie-Hellman key exchange, it is also referred to as X25519.
- ECDH is preferred over DH due to its smaller key size. To get a 128 bit of security DH requires nothing less than 2048 bits, but with ECDH, the requirement is nothing less than 256 bits.
Mathematical Concepts
- Introduction to set theory
- Introduction to group theory
- Subgroup Generators
- Modular Arithmetic
- Discrete Log Problem
- Elliptic Curves
- Diffie-Hellman Explained
No comments:
Post a Comment