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:
|
|
|
|
|
Bob uses his private key to
encrypt the message and returns the encrypted version to Alice:
|
|
|
|
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:
By using a
digest, Bob can protect himself. He computes the digest of the random message
sent by Alice and then encrypts the result. He sends the encrypted digest back
to Alice. Alice can compute the same digest and authenticate Bob by decrypting
Bob's message and comparing values.
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.
|
|
|
|
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:
|
|
|
|
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 is signed using the certificate issuer's private key. Everybody
knows the certificate issuer's public key (that is, the certificate issuer has
a certificate, and so on...). Certificates are a standard way of binding a
public key to a name.
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:
|
|
|
|
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:
|
|
|
|
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:
|
|
|
|
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 |
|
|
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):
|
B->M A->M B->M M->A
B->M |
|
Hi, I'm Bob, bobs-certificate prove it Alice, This Is bob ok bob, here is a secret {secret} bobs-public-key {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:
|
|
|
|
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:
|
|
|
|
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.
For the latest technical information on Sun-Netscape
Alliance products, go to: http://developer.iplanet.com
For more Internet development resources, try Netscape TechSearch.
Copyright © 1999 Netscape
Communications Corporation.
This site powered by: Netscape Enterprise Server and Netscape
Compass Server.