Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!ukma!rutgers!njin!princeton!phoenix!bernsten
From: bernsten@phoenix.Princeton.EDU (Dan Bernstein)
Newsgroups: comp.protocols.tcp-ip
Subject: Re:  RSA Encryption on the Internet
Keywords: RSA, Encryption, Public Key
Message-ID: <7432@phoenix.Princeton.EDU>
Date: 28 Mar 89 08:46:00 GMT
References: <8903222040.AA03642@braden.isi.edu> <10061@bloom-beacon.MIT.EDU>
Reply-To: bernsten@phoenix.Princeton.EDU (Dan Bernstein)
Distribution: usa
Organization: Princeton U. Undergrad Math Majors, last time I checked
Lines: 62

In article <10061@bloom-beacon.MIT.EDU> boomer@space.mit.edu (Don Alvarez) writes:
> The most important part of any public-key system is the key distribution
> method.  I can "break" any public key encryption scheme, no matter how
> robust the algorithm, if you aren't sufficiently careful about distributing
> the public keys.

Your argument is mostly based on a fake directory service providing
false encryption keys. As most discussions of public-key systems point
out, the solution to this is easy. (See, e.g., volume 2 of Knuth.)

Let's say X wants to send a message to Y. Given that unencrypted data
and encrypted data come from the same alphabet, X *decrypts* a message
by his encryption function, signs it, encrypts it by Y's function, and
sends it to Y. Y then receives it, decrypts it by Y, checks the signature
to find out X's identity, and then *encrypts* it by X.

X can be confident that only Y can read the message since only Y knows
Y's decryption function. Y can be confident that only X could have sent
the message since only X knows X's decryption function---otherwise the
final message would be garbage. Thus public-key systems (with the same
set of unencrypted and encrypted data) naturally provide sender
authentication as well as privacy.

How does this apply to the directory service D? There is only a single
encryption function, ED, that must be distributed widely. This single
key becomes common, public knowledge; the average sysadmin will know
the number by heart. Assuming only that this single key can be
distributed safely at the beginning of time, the directory can then
send out *signed* messages containing further keys. (The messages
should contain recognizable format information, or at least a few
checksums, to prevent complete screwups.)

Of course, that encryption function will become the world's most
carefully scrutinized. If someone could find out the directory's
decryption, they could indeed begin masquerading as the directory,
thus posing the security risks you bring up. Thus that directory
encryption function must be chosen very carefully---if RSA, it should
probably be several hundred digits long where three hundred is usually
considered safe, and should probably involve quadruple application
of the key choice method in Knuth rather than double. The decryption
must also be protected very carefully, with a paranoia previously
unheard of.

> The info posted to this group has implied that keys need to be registered 
> with some central body.  Presumably what happens is that the central body
> encrypts your name into the public half of your key in some way when it is
> created.

Why? This seems to me to imply an unnecessary security risk. You want
a mapping from user to key, not from key to user. The latter wouldn't
prevent any security problems; if you claim a key is yours, it can be
checked with the directory service, and I don't think there would be
any reason that ``we have to find out who owns this key!''

> So, in short, I'd say that the most important technical question to be asked
> is how do you know that you can trust the public key you are given.

This reduces to the question of how secure we can make a carefully
chosen single example of a single encryption method: the directory's
encryption function.

---Dan Bernstein, bernsten@phoenix.princeton.edu