You’ll recall from my previous post on the public key infrastructure that symmetrical encryption relies on some mechanism for securely exchanging keys.
While the use of public and private keys solves this problem, there are other problems that they don’t solve.
The most important of these are:
- If an attacker were ever to obtain a private key, all historical communications between the owner of the private key and other parties could be decrypted. Recall that although Bob put his private key securely in an office safe, someone might crack the safe combination and obtain the private key. Or an attacker might simply threaten Bob with physical violence, thus coercing him to hand over the private key.
- The mathematical processes behind public and private key encryption are quite complex and it is very expensive in compute power to encrypt and decrypt messages. On the other hand, symmetrical encryption algorithms such as AES, (which stands for the Advanced Encryption Standard) are much faster.
For these reasons, it would be very desirable to be able to securely exchange keys and use symmetrical encryption. We can augment this with the PKI for verifying the identities of senders and receivers, but, if there were some mechanism for securely exchanging a symmetrical encryption key each time we wanted to talk to another party, we could then exploit the increased efficiency of symmetrical encryption, and at the same time ensure that historical communications can never be decrypted by an adversary, since the session key used for that conversation is ephemeral, or in other words, never re-used.
For a very long time, it was thought to be impossible to implement a mechanism for securely exchanging keys over a public connection. Then, in the early 1970s, three people at GCHQ (Ellis, Cocks, and Williamson) invented a protocol they called ‘non-secret encryption’. This was tightly classified until the late 1990s, but in the mid-1970s, Diffie and Hellman independently rediscovered the same technique and shared it publicly.
Note: Ironically, Clifford Cocks also invented the public/private key cryptography algorithms that Rivest, Shamir, and Adleman subsequently rediscovered. Sadly, due to an obsession with secrecy, these three pioneers never got the public recognition they deserved. I’m pleased to note that all three have now been honored by the IEEE for the contributions they made.
The Diffie-Hellman key exchange process
In the continuing spirit of trying to explain cryptographic principles while avoiding mathematics, I am going to re-use a very good diagram in Wikipedia that provides an intuitive explanation of the process.
Suppose our old friends, Alice and Bob, want to exchange messages and wish to define a secret key that they will share to encrypt and decrypt messages.
To understand the D-H key negotiation process, the analogy uses colored paint. The ‘paints’ are actually very long numbers and the mixing processes are complex mathematical algorithms.
We assume that any communication between Alice and Bob is easily interceptable by a third party – in this case, the infamous Eve, whom we met last time trying to steal secret documents.
- Alice and Bob choose an initial paint color
Alice and Bob start by randomly selecting a common paint color from some huge library of paints. Although the diagram below shows relatively simple colors for clarity, imagine that Alice and Bob can choose from a vast range of tints – just as you can go to a paint shop where they have machines that add a squirt of several primary tints to white paint to make you just about any color you want.
- They share this color with each other publicly
Suppose Alice takes the initiative in choosing a color and communicates her choice to Bob.
- Each party chooses a second (different) secret color
Each of them now chooses a second secret color. This color has a relationship with the public color. The secret color that Alice chooses will be different from the secret color that Bob chooses because each will choose randomly from a huge list of secret color choices. Those choices were determined by the paint color they originally chose to exchange at the start.
- They each blend their public and secret colors and share their blends with each other
Both parties now blend their secret colors with their public colors.
They then exchange the result with each other publicly. Because Alice and Bob both chose different secret colors, the public blends they exchange with each other are different.
- They each blend their secret colors with the other party’s shared blended color.
Alice then blends the secret color she chose with the public blended color she receives from Bob.
Bob blends the secret color he chose with the public blended color he receives from Alice
Both Alice and Bob now have the same color. This is the secret key that they will use to exchange messages.
Now suppose an attacker intercepts both the original public exchange of the starting paint color, and both the blends from Alice and Bob. Because they do not know the secret colors that Alice and Bob chose, it is very difficult for them to determine them from the blended paint.
If you thought to choose the right color for your bathroom was enough of a challenge, then you can see that an adversary intercepting Alice and Bob’s public paint choices would have an enormous challenge trying to replicate their secret paint blend.
Just to really hammer this home, imagine I gave you a can of pink paint and asked you to separate out every single molecule of red paint that had been mixed into the original can of white paint and tell me EXACTLY how many molecules of red paint had been added. I’m sure you can see I’m setting quite a challenge there!. Now in the analogy here, Alice and Bob can mix in all sorts of colors to create their original common paint and secret colors, so that the blends they exchange publicly are a mixture of lots of colors. As an attacker, I must literally separate out each color, molecule by molecule. If I get the result wrong by a single molecule, I’ve failed to guess the secret key.
Because the use of paint is just an analogy, you’ll have to trust me that, compared to that herculean challenge, reverse-engineering the secret key from the exchanged numbers is even more difficult.
D-H and the PKI
Remember Eve, our adversary from the previous post.
The Diffie-Hellman algorithm is susceptible to a ‘Man-in-the-middle (MITM) attack – or ‘WITM’ in the case of Eve!.
In that scenario when Alice attempts to share her public paint color with Bob, Eve intercepts her communication. Before forwarding it to Bob she maliciously changes Alice’s choice of color to another color that Eve has chosen.
Similarly, she intercepts any communication from Bob and alters his public choices to choices that she controls.
When negotiations are complete, both Alice and Bob think that they have established a single, shared secret key. However, they have in fact independently negotiated two separate keys with Eve, so that she can decrypt either side of the conversation, then re-encrypt it and forward it to the other party. Eve acts as a ‘man-in-the-middle’ or proxy, fooling each party into thinking they are communicating directly with each other while still being able to read everything they say.
However, because the PKI allows Alice and Bob to independently verify each other’s identities, they can use digital signatures to ensure that their public communications cannot be subverted.
By signing these communications, they make them tamper-proof.
Consequently, although Eve can, of course, intercept their public communications, she is unable to alter them to fraudulently establish a MITM attack. Nor can she initiate a communication with either party and successfully pretend to be the other party, since she cannot create valid signed messages on behalf of that party.
Conclusion
We see that it is possible to securely negotiate a shared key for use in subsequent symmetrical encryption between two parties. This key can be re-negotiated for each session, which protects the parties from an attack in the future that would allow historically intercepted communications to be decrypted.
Digital signatures, which we will discuss in our next post, provide protection from MITM attacks by an adversary. These digital signatures are, in turn, supported by the public key infrastructure which we discussed in our previous post.
