AN INTRODUCTION TO KEY CRYPTOGRAPHY

This document explains how Netscape uses RSA public key cryptography for Internet security. Netscape's implementation of the Secure Sockets Layer (SSL) protocol employs the techniques discussed in this document.

RSA public key cryptography is widely used for authentication and encryption in the computer industry. Netscape has licensed RSA public key cryptography from RSA Data Security Inc. for use in its products, specifically for authentication.

Public key encryption is a technique that uses a pair of asymmetric keys for encryption and decryption. Each pair of keys consists of a public key and a private key. The public key is made public by distributing it widely. The private key is never distributed; it is always kept secret.

Data that is encrypted with the public key can be decrypted only with the private key. Conversely, data encrypted with the private key can be decrypted only with the public key. This asymmetry is the property that makes public key cryptography so useful.

USING PUBLIC KEY CRYPTOGRAPHY FOR AUTHENTICATION

Authentication is the process of verifying identity so that one entity can be sure that another entity is who it claims to be. In the following example involving Alice and Bob, public key cryptography is easily used to verify identity. The notation {something}key means that something has been encrypted or decrypted using key.

Suppose Alice wants to authenticate Bob. Bob has a pair of keys, one public and one private. Bob discloses to Alice his public key (the way he does this is discussed later). Alice then generates a random message and sends it to Bob:

A->B

random-message

Bob uses his private key to encrypt the message and returns the encrypted version to Alice:

B->A

{random-message}bobs-private-key

Alice receives this message and decrypts it by using Bob's previously published public key. She compares the decrypted message with the one she originally sent to Bob; if they match, she knows she's talking to Bob. An imposter presumably wouldn't know Bob's private key and would therefore be unable to properly encrypt the random message for Alice to check.

BUT WAIT, THERE'S MORE

Unless you know exactly what you are encrypting, it is never a good idea to encrypt something with your private key and then send it to somebody else. This is because the encrypted value can be used against you (remember, only you could have done the encryption because only you have the private key).

So, instead of encrypting the original message sent by Alice, Bob constructs a message digest and encrypts that. A message digest is derived from the random message in a way that has the following useful properties:

• The digest is difficult to reverse. Someone trying to impersonate Bob couldn't get the original message back from the digest.
• An impersonator would have a hard time finding a different message that computed to the same digest value.

GETTING CLOSER

The technique just described is known as a digital signature. Bob has signed a message generated by Alice, and in doing so he has taken a step that is just about as dangerous as encrypting a random value originated by Alice. Consequently, our authentication protocol needs one more twist: some (or all) of the data needs to be originated by Bob.

A->B B->A

hello, are you bob? Alice, This Is bob { digest[Alice, This Is Bob] } bobs-private-key

When he uses this protocol, Bob knows what message he is sending to Alice, and he doesn't mind signing it. He sends the unencrypted version of the message first, "Alice, This Is Bob." Then he sends the digested-encrypted version second. Alice can easily verify that Bob is Bob, and Bob hasn't signed anything he doesn't want to.

HANDING OUT PUBLIC KEYS

How does Bob hand out his public key in a trustworthy way? Let's say the authentication protocol looks like this:

A->B B->A A->B B->A

hello Hi, I'm Bob, bobs-public-key prove it Alice, This Is bob { digest[Alice, This Is Bob] } bobs-private-key

With this protocol, anybody can be Bob. All you need is a public and private key. You lie to Alice and say you are Bob, and then you provide your public key instead of Bob's. Then you prove it by encrypting something with the private key you have, and Alice can't tell you're not Bob.

To solve this problem, the standards community has invented an object called a certificate. A certificate has the following content:

• The certificate issuer's name
• The entity for whom the certificate is being issued (aka the subject)
• The public key of the subject
• Some time stamps

By using this certificate technology, everybody can examine Bob's certificate to see whether it's been forged. Assuming that Bob keeps tight control of his private key and that it really is Bob who gets the certificate, then all is well. Here is the amended protocol:

A->B B->A A->B B->A

hello Hi, I'm Bob, bobs-certificate prove it Alice, This Is bob { digest[Alice, This Is Bob] } bobs-private-key

Now when Alice receives Bob's first message, she can examine the certificate, check the signature (as above, using a digest and public key decryption), and then check the subject (that is, Bob's name) and see that it is indeed Bob. She can then trust that the public key is Bob's public key and request Bob to prove his identity. Bob goes through the same process as before, making a message digest of his design and then responding to Alice with a signed version of it. Alice can verify Bob's message digest by using the public key taken from the certificate and checking the result.

A bad guy - let's call him Mallet - can do the following:

A->M M->A A->M M->A

hello Hi, I'm Bob, bobs-certificate prove it ????

But Mallet can't satisfy Alice in the final message. Mallet doesn't have Bob's private key, so he can't construct a message that Alice will believe came from Bob.

EXCHANGING A SECRET

Once Alice has authenticated Bob, she can do another thing - she can send Bob a message that only Bob can decode:

A->B

{secret}bobs-public-key

The only way to find the secret is by decrypting the above message with Bob's private key. Exchanging a secret is another powerful way of using public key cryptography. Even if the communication between Alice and Bob is being observed, nobody but Bob can get the secret.

This technique strengthens Internet security by using the secret as another key, but this time it's a key to a symmetric cryptographic algorithm (such as DES, RC4, or IDEA). Alice knows the secret because she generated it before sending it to Bob. Bob knows the secret because Bob has the private key and can decrypt Alice's message. Because they both know the secret, they can both initialize a symmetric cipher algorithm and then start sending messages encrypted with it. Here is a revised protocol:

A->B B->A A->B B->A A->B B->A

hello Hi, I'm Bob, bobs-certificate prove it Alice, This Is bob { digest[Alice, This Is Bob] } bobs-private-key ok bob, here is a secret {secret} bobs-public-key {some message}secret-key

How secret-key is computed is up to the protocol being defined, but it could simply be a copy of secret.

YOU SAID WHAT?

Mallet's bag contains a few more tricks. Although Mallet can't discover the secret that Alice and Bob have exchanged, he can interfere in their conversation by damaging it. For example, if Mallet is sitting between Alice and Bob, he can choose to pass most information back and forth unchanged but mangle certain messages (easy for him to do because he knows the protocol that Alice and Bob are speaking):

A->M M->B B->M M->A A->M M->B B->M M->A A->M M->B B->M M->A

hello hello Hi, I'm Bob, bobs-certificate Hi, I'm Bob, bobs-certificate prove it prove it Alice, This Is bob { digest[Alice, This Is Bob] } bobs-private-key Alice, This Is bob { digest[Alice, This Is Bob] } bobs-private-key ok bob, here is a secret {secret} bobs-public-key ok bob, here is a secret {secret} bobs-public-key {some message}secret-key Garble[ {some message}secret-key ]

Mallet passes the data through without modification until Alice and Bob share a secret. Then Mallet gets in the way by garbling Bob's message to Alice. By this point Alice trusts Bob, so she may believe the garbled message and try to act on it. Note that Mallet doesn't know the secret - all he can do is damage the data encrypted with the secret key. Depending on the protocol, Mallet may not produce a valid message. Then again, he may get lucky.

To prevent this kind of damage, Alice and Bob can introduce a message authentication code (MAC) into their protocol. A MAC is a piece of data that is computed by using a secret and some transmitted data. The digest algorithm described above has just the right properties for building a MAC function that can defend against Mallet:

MAC := Digest[ some message, secret ]

Because Mallet doesn't know the secret, he can't compute the right value for the digest. Even if Mallet randomly garbles messages, his chance of success is small if the digest data is large. For example, by using MD5 (a good cryptographic digest algorithm invented by RSA), Alice and Bob can send 128-bit MAC values with their messages. The odds of Mallet's guessing the right MAC are approximately 1 in 18,446,744,073,709,551,616 - for all practical purposes, never.

Here is the sample protocol, revised yet again:

A->B B->A A->B B->A

hello Hi, I'm Bob, bobs-certificate prove it Alice, This Is bob { digest[Alice, This Is Bob] } bobs-private-key ok bob, here is a secret {secret} bobs-public-key {some message,MAC}secret-key

Mallet is in trouble now. He can garble messages all he wants, but the MAC computations will reveal him for the fraud he is. Alice or Bob can discover the bogus MAC value and stop talking. Mallet can no longer put words in Bob's mouth.

WHEN WAS THAT SAID?

Last but not least to protect against is Mallet the Parrot. If Mallet is recording conversations, he may not understand them but he can replay them. In fact, Mallet can do some really nasty things sitting between Alice and Bob. The solution is to introduce random elements from both sides of the conversation.