Cyber Security:

The Key Distribution Problem

Symmetric encryption methods have the advantage that encryption and decryption is extremely fast, making them ideal for transmitting large amounts of secure data - but there is a security problem - and a problem generating enough key pairs.

This problem, called the key distribution problem, affected anyone wishing to use encryption until the 1970s when a method of distributing keys without actually sending the keys themselves was developed independently by GCHQ in the United Kingdom and Whitfield Diffie and Martin Hellman in the United States.

The British discovery was kept secret for many years, so today the solution is known as the Diffie–Hellman key exchange method. See asymmetric encryption.

 

In the video below you see how safe key distribution is achieved between two people, Alice and Bob:

 

This is a video produced by the Open Univerity as part of its 'Open Learn' Program - a free taster to its courses.

Transcript

Alice and Bob want to form some kind of relationship.

It might be business, it could even be romantic. But whatever else, it must be confidential.

The third person in this relationship is Eve. And, as her name suggests, she's an eavesdropper who wants to know what's going on between Alice and Bob.

To do that she has to intercept their information.

Alice and Bob might not even be aware that Eve exists, but she is a threat to their confidentiality.

First of all, let's remind ourselves how messages are sent over the internet.

So we have Alice's and Bob's computers here.

Alice has created a document which she wants to send to Bob.

When you send a message across the internet, it may actually look like the message goes straight from one computer to the other. In reality, there's usually at least one more computer, such as a router or a file server in between. So now the message goes from Alice, to the computer in the middle, to Bob.

In fact, it can get even more complicated, and there may be a large number of different computers in between the two of them.

Alice's message is routed from one computer to another until it reaches Bob.

We've drawn the computers in different colours because they don't belong to either Alice or Bob.

They might belong to their internet service providers, their employers, or to a big telecom company.

Some of the computers may be in a different country, where different laws apply. And some of them might not be trustworthy, which is where Eve comes in.

Here's the same network, except now Eve's going to join in.

She will log on and then compromise one of the computers in the middle.

One way she could do this is to use a packet sniffer, a piece of hardware or software that makes copies of any messages passing between Alice and Bob, and sends them to Eve.

Alice and Bob won't even know these copies are being made, but Eve will have a full transcript of everything that's happening between the two of them.

Alice and Bob can protect themselves using encryption.

The most obvious form of encryption is called symmetric encryption, which uses a single key to encrypt plaintext to ciphertext and decrypt ciphertext back into plaintext.

Symmetric encryption has been around for thousands of years and is still important today in the form of technologies called DES, triple DES, and AES, which are widely used in financial transactions over the internet and within banks.

Let's go back to Alice and Bob.

Aware that Eve wants to learn their secret, they choose to use symmetric encryption.

The first thing for them to do is to generate a shared key and each to make their own copy.

One way of doing this is to meet, discuss their secrets, and come up with a key.

At the end of the meeting they'll each go away with their own copy of the key.

Alice and Bob can now exchange secure messages, each using their own copies of the symmetric encryption key to encrypt and decrypt messages.

However, remember that Alice and Bob don't live locally.

They have to travel a long distance, so meeting is not always possible. And it's entirely possible they're in a situation where it's dangerous to share a key.

An alternative is for Alice to generate a key and send it to Bob, perhaps through the post, perhaps over the internet. However, as we all know, things get lost in the post. And that could happen to our encryption key. Or perhaps Eve is waiting by Bob's post box and makes her own copy when it's delivered.

Alice might choose to generate the key herself, then give it to an armed guard, a bit like the way you might use a courier to send a valuable parcel from one part of the country to the other. Alice generates the key on her computer, hands it over to the armed guard, who then trundles across to Bob and hands the key over. However, as you can imagine, armed guards are very expensive.

Historically, the only people who could afford armed couriers to distribute encryption keys were governments and the very largest companies such as banks and international corporations. This meant that most people were completely unable to use cryptography.

Now you've seen some of the problems of symmetric cryptography, let's see how some of those problems apply to the internet.

Alice and Bob still want to share their secrets. Alice has generated a symmetric encryption key on her computer and needs to send it across the internet to Bob. There are a number of computers in between, one of which has been compromised by Eve. So when Alice sends the key across the network, it passes through the computer now belonging to Eve, who obtains a copy of the key, and so does Bob.

Neither Alice or Bob know that the key has been copied.

So they can carry on using it, thinking their messages are secure, but in reality Eve is reading each and every one of them.

This is called the key distribution problem.

How do we keep keys in the hands of those who need them and not in the hands of criminals or those who would misuse them?

Until the early 1970s it was believed there was no solution to the key distribution problem, hence all those armed guards and couriers.

The solution is called asymmetric encryption.

Now there are two keys.

The first key, called the public key, encrypts plaintext to ciphertext.

The second key, known as the private key, decrypts ciphertext back to plaintext.