Task

Data Dictionary

Teacher's Tools

Bit Commitment

Blinding

Certificates

Digital Signatures

Public Key

Secret Splitting

Security Basics

Symmetric Key

But, public key cryptography has an advantage in key distribution.   One of the keys is public, so it can be published.   The entire world can have access to this key.  Therefore, a very simple key distribution protocol is described below:

1. The receiver gives the sender its public key.
2. The sender encrypts a message using the receiver's public key.
3. The receiver can decrypt the message using its private key.

Most of the time, the sender can just read the public key out of a database instead of having the receiver send it.

The last two steps confirm that the sender has received the public key.  The message may be some known piece of data like the current date.  Therefore, the receiver can decrypt the message and compare it to its known value.  If the messages match, then the receiver knows that the sender has its public key.

The public key distribution system also gives a method to exchange symmetric keys.  Consider the following protocol:

1. The receiver gives the sender its public key.
2. The sender generates a random session key.
3. The sender encrypts the random session key with the receiver's public key.
4. The sender sends the encrypted session key to the receiver.
5. The receiver decrypts the encrypted session key by using its private key.

There is now a session key that can be shared between the sender and the receiver.  The session key is encrypted as it is passed from the sender to the receiver, so that it cannot be decrypted by an attacker.  Only the receiver's private key can decrypt the session key.  Since this application uses public key cryptography to generate a symmetric key, it is known as a hybrid cryptosystem.  Typically, session keys will only be used for a short period of time so that hackers have a limited amount of time to try and crack the key.

Surprisingly, the above protocol is vulnerable to the man in the middle attack. Consider the following scenario:

1. The receiver attempts to give the sender its public key.
2. The attacker intercepts the receiver's public key and sends the sender its own public key.
3. The sender receives the attacker's public key and thinks that it is the receiver's public key.

At this point, the man in the middle has simply substituting his own key for the one that the receiver is attempting to send.   The sender receives the attacker's public key and does all of its encryption with this key.   Clearly, the attacker can then decrypt any data that the sender attempts to send.  

Now, let's assume the sender wants to generate a session key with the receiver and the attacker is still monitoring communications.

1. The sender generates a random session key.
2. The sender encrypts the random session key with the attacker's public key, because this is the public key it received.  It thinks it is the receiver's public key, but it really is the attacker's.
3. The sender sends the encrypted random session key to the receiver.
4. The attacker intercepts the encrypted random session key before the receiver gets it.
5. The attacker uses his private key to decrypt the random session key.

The attacker has the session key!   He has established a session with the sender.  However, the attacker may now be worried that the receiver will detect an error since it did not get a session key.   The attacker is smart, so he takes the following action:

1. The attacker encrypts the random session key with the receiver's public key.
2. The attacker sends the encrypted session key to the receiver.
3. The receiver decrypts the encrypted session key using its private key.

The receiver now thinks it has a secret session key with the sender.  But, it really has a session key with the attacker and the sender.  The attacker can now monitor any communication between the sender and the receiver. 

One method to solve this problem is to split the message.

1. The receiver sends the sender its public key.
2. The sender splits the message that it wants to send to the receiver into two pieces.
3. The sender encrypts the first part of the message using the receiver's public key.
4. The sender sends part of the message to the receiver.
5. The receiver decrypts the message using its private key.
6. The sender encrypts the other part of the message.
7. The sender sends the other part of the message to the receiver.
8. The receiver decrypts the second part of the message.
9. The receiver puts together both parts of the message.

The message cannot be interpreted until both parts are received.   The parts can be calculated in several ways.  These methods include:

• The first part being a one way function of the message and the second part being the encrypted message itself.
• Odd bits could be sent in the first part of the message, even parts could be sent in the second part.
• The last few characters of the message could be sent first and the first few characters can be sent afterwards.

The man in the middle would have trouble defeating this protocol because he does not know how the message is broken up.  While he could swap keys, he could not easily interpret the message.

For example, the man in the middle could do the following.

1. The receiver tries to send the sender its public key.
2. The man in the middle intercepts the public key.
3. The man in the middle sends the sender its public key.

At this point, the sender has the wrong public key.   Let us now assume that it wants to establish a session.

1. The sender splits the message that it wants to send to the receiver into two pieces. Let us assume the message is "Happy Birthday."  It will send "Birthday" first and "Happy" afterwards.  The receiver knows it must reverse the orders of the words to get the message.
2. The sender encrypts the first part of the message using the attacker's public key.  This was the key that it had received.  It thinks that it is the receiver's public key, but it really is the attackers.
3. The sender sends out the first part of the message.
4. The attacker receives the message and decrypts it.  He gets the word "Birthday."
5. The attacker encrypts the message with the receiver's public key and passes it to him.
6. The receiver decrypts the message using its private key to reveal the word "Birthday."

Everything is still progressing fine for the attacker.  He has a message and so does the receiver.   However, the last few steps show the power of splitting the message.

1. The sender encrypts the other part of the message with the attacker's public key.
2. The sender sends out the other part of the message.
3. The attacker decrypts the second part of the message with its private key to reveal the word "Happy."
4. The attacker encrypts the second part of the message and sends it to the receiver.
5. The receiver decrypts the second part of the message with its private key to reveal the word "Happy."
6. The receiver puts the two parts of the message together to get "Happy Birthday."  It knew to reverse the words.
7. The attacker does not know to do this operation, so it incorrectly assumes the message is "Birthday Happy."

The attacker cannot interpret messages between the sender and the receiver.  If the message was not "Happy Birthday", but  a session key, the attacker would not have decoded the session key value correctly.   Therefore, it would not be able to interpret any data that was encrypted with this session key.

For more information:

1. "Key Management" by Frame Technology is available at http://www.cs.nps.navy.mil/curricula/tracks/security/notes/chap05_30.html. January 1994.