gnu@hoptoad.uucp (John Gilmore) (07/31/87)
[This appeared in comp.org.fidonet, the FidoNet Newsletter, V4 #28.
You can read the whole newsletter, in vnews, by typing "p" to this article.]
Copyright 1987 by the International FidoNet Association. All
rights reserved. Duplication and/or distribution permitted for
noncommercial purposes only. For use in other circumstances,
please contact IFNA at (314) 576-4067.
AUTHENTIC SECURE SECRET FIDO MAIL WITH PUBLIC KEY ENCRYPTION
INTRODUCTION
============
This article was written by Prodex Labs, for examination and
comment by IFNA (International Fidonet Association) Sysops,
members, Fidonet users, and others interested in electronic mail
and security. Prodex Labs (Lee Rothstein, Phil Zimmermann &
Steve Welch) is very much interested in your comments and
suggestions.
PRODEX LABS, PUBLIC KEY ENCRYPTION & FIDO
-----------------------------------------
We are now about ready to deliver C-based modules that can carry
out public key encryption.
We are writing this article because of the extreme relevance we
see of public key cryptography to electronic mail. We assume
electronic mail is near and dear to your hearts, and we think you
might be interested in the application of public key encryption
to Fidomail and Fidonet transfers. The discussion, we provide
here, on public key cryptography aims specifically at electronic
mail applications.
Public key encryption technology allows the convenient
distribution of messages through an electronic mail system secure
against other users, sysops ("superusers") and even systems
programmers. It allows this security in the face of inherently
insecure networks and hosts. This we think is a feature whose
time has come. We think it lends itself well to the expansion of
Fidonet services, as well as the opportunity for Fido sysops to
unobtrusively draw revenue from a subset of Fido services--
specifically those that have to do with private and commercial
mail.
Specifically, we suspect the lack of privacy of messages (from
Sysops and technotwits) has discouraged the use of Fido as a
national distribution medium for personal mail, and business
mail. Second, the lack of an authentication mechanism has
discouraged commercial concerns from using Fidomail as a
distribution mechanism for authentic marketing programs and
documents such as ads, coupons and purchase orders. By adding
these commercial services to Fido, the revenue produced could be
used to subsidize other Fido services such as mass storage
(downloads) and Techline distribution (long distance charges).
The authentication capability mentioned in the previous paragraph
might also be of use directly to Fidonet as it grows.
Authentication would allow nodes that are operating in a store
and forward sub-net to prove their legitimacy prior to a relay
operation. Since we are not familiar with the daily operational
problems of Hosts, we do not know if we have proposed a solution
to a non-existent problem.
Finally, we think that the recent introduction of "Dutchie" may
be one of the key ingredients to the success of the introduction
and use of public key encryption in Fidonet. For those of you
not yet familiar with it, Dutchie is the private delivery point
implementation for Fidonet by Henk Wevers.
SINGLE KEY ENCRYPTION: WHY PUBLIC KEY ENCRYPTION IS REQUIRED!
--------------------------------------------------------------
Public key encryption technology differs from the more well-known
single key technology in that each person has two keys associated
with him/her--a public key, and a private key. (DES--Data
Encryption Standard--is the most well-known example of single key
encryption.)
In public key encryption, the public key is known by everyone and
either can be looked up by the user from a table of keys versus
user names or automatically looked up by the applications
software (e.g., electronic mail software).
In single key encryption, Fred encrypts file 'nerd.msg' with the
key "secret_potion". When Bill wants to decrypt the file, he
must have been told by Fred what the key for decrypting (i.e.,
encrypting) 'nerd.msg' is. Specifically, Bill must supply the
key "secret_potion" to decrypt 'nerd.msg'. If "secret_potion" is
always associated with Fred's files, then Bill knows the key for
those files that Fred does not want him to see. More succinctly,
the decryption and encryption functions are inverses of each
other. Symbolically:
(1) encrypted_file <- sk_encrypt(file, key)
(2) file <- sk_encrypt(encrypted_file, key) i.e., decryption
is encryption
and the key is
the same going
in both
directions
The above notation assumes that objects with the same name
and only objects with the same name are identical.
Let's look at the consequences of the logic of single key
encryption within an electronic mail system. Anyone that wants
to send secret messages to someone else must either know the
recipient's one and only secret key, or relinquish their own
secret key, or maintain a list of secret keys by recipient or
file; not a very attractive alternative.
What's worse, if the key information is exchanged by users
through the mail system, then the sysop has a crack at the key.
This seems very likely when you consider that you probably want
the mail system itself to automatically monitor, maintain and
administer the keys because of the previously described problems.
PUBLIC KEY ENCRYPTION
=====================
PUBLIC KEY ENCRYPTION EXPLAINED
-------------------------------
These and other problems can be made to disappear with a public
key encryption system. The public and private keys make a
matched, idiosyncratic set. A file encrypted with the public key
can only be decrypted by the private key. A file encrypted by
the private key can only be decrypted by the public key. These
properties can be used to significant advantage in an electronic
mail system. The obvious advantage of the public key technology
over the more normal single private key technology such as DES,
is that a user does not have to give away his/her private key.
Secrecy
-------
If you want secrecy in a message that you send us, you encrypt
the message with our public key and then we decrypt it with our
private key.
Signature Function
------------------
If you want to authenticate a message as really coming from you,
you encrypt it with your private key and then we decrypt it with
your public key. If your public key does not make the message
intelligible then it wasn't encrypted with your private key and
therefore it didn't come from you--the one and only person who
has access to your private key.
Secrecy & Authentication
------------------------
The secrecy and authentication encryptions outlined above can be
combined sequentially to provide a complete framework of security
for electronic mail.
Symbolically, we could describe these properties as:
If A were sending a message to B:
(1) encrypted_file <- pk_encrypt(file, public_key_B)
(2) file <- pk_decrypt(encrypted_file,
private_key_B)
(1) Would be used by the sender to achieve privacy.
(2) Would be used by the receiver to achieve
"legibility."
AND
(3) encrypted_file <- pk_encrypt(file, private_key_A)
(4) file <- pk_decrypt(encrypted_file,
public_key_A)
(3) Would be used by the sender to achieve
authentication.
(4) Would be used by the receiver to prove
authentication and achieve "legibility."
If we wished privacy and authentication in a message from A to B:
(5) double_encrypted_file <-
pk_encrypt(pk_encrypt(file, public_key_B),
private_key_A)
(6) file <- pk_decrypt(pk_decrypt(double_encrypted_file,
private_key_B), public_key_A)
(5) Would be used by the sender to achieve privacy and
authentication.
(6) Would be used by the receiver to achieve
"legibility", and prove authentication.
In the above notation we again assume that objects with the
same name and only objects with the same name are
equivalent.
OTHER REQUIREMENTS & PROPERTIES
-------------------------------
Several other properties of public key encryption require
explanation to fully understand how security can be maintained
and how a mail system can work.
First, the program that generates the key pairs can be widely
distributed so that it can be used by each user privately and
securely.
Second, the algorithm that generates the public key from the
private key is not reversible either by the generating program or
by any other program a hacker would write.
Third, the kinds of keys generated and required by the encrypt /
decrypt function(s) are on the order of a 1000 bits. This is
what makes trial and error computation of the private key
extremely unlikely to the point of impossibility, and also what
makes users generating like public keys unlikely.
Fourth, the electronic mail nodes (for Fidonet, Fido nodes) would
have to provide a key server function. Once a user had
calculated his public key from a private key he would have to
submit it to a node to be paired with his/her user ID. The
server function would also have to supply the public key to
private mail sent to the corresponding user ID. Another major
function of the key server is an automatic certification process
that is beyond the scope of a first release product or this
paper.
Finally, for performance sake, any reasonable implementation of
public key cryptography would transparently (unknown to users)
invoke an internal method of single key encryption. However, all
user and crackers would ever (or could ever) see is the public
key mechanisms.
IMPLEMENTING PUBLIC KEY ENCRYPTION WITHIN THE FIDO ENVIRONMENT
==============================================================
THE IMPOSSIBLE DREAM
--------------------
If we were to directly implement an automatic, public key
cryptography security system into Fido mail that would avoid
sysops having any possibility of access to the private keys or
the mail prior to encryption, we would have to accomplish the
following:
(a) We would have to add a secure mail option to the terminal
emulation program. We would further have to modify the
user's terminal emulation program so that all mail text
entered was encrypted before each line was sent by the user
to the mail edit/entry function on the BBS.
There are some outs here, but they are pretty well
invalidated by several properties of BBS software. First,
mail entry is designed to be an online editing activity
rather than via upload. Second, the mail entry function is
designed to handle pure text and not the binary files that
result from encryption. Third, most mail input software
strongly limits the length and format (e.g., line length,
blank lines, use of tabs) of input messages. If one uses
"ASCII transfer" capability there is a possibility the file
will fail the length test or be modified by the format
assumptions, because it was not edited with the length and
format tests operative. Fourth, the prompting feature of
the mail editor very often interferes with ASCII upload.
(b) We would have to make modifications to the BBS mail
edit/entry function so that some text was accepted in
unencrypted format (i.e., 'To:' and 'From:' information) and
the remainder was in encrypted format (i.e., 'Subject:' and
body of message. ('From:' can be hidden if BBS Sysops do not
object.)
(c) We would have to add a public key server function to the BBS
that would maintain and service public keys. This would
also have to allow for the distribution of keys from node to
node.
(d) We would have to make sure that encryption did not interfere
with Fidomail routing line additions to the text body.
This theory will not work or rather will not work without a
ground swell of support for private mail. We cannot get control
of all of the following simultaneously: (a) user terminal
emulation software, (b) Fido mail entry software, (c) Fido
general BBS software, (d) Fido networking and mail exchange
software. How do we create the ground swell, then?
FIRST STEPS
-----------
Step 1
------
We develop two program functions (they may or may not actually be
separate programs) that can be distributed via Fido. Currently,
we estimate we can have these two programs done within two
months.
The first program is a DOS (Unix style) filter. It has two
functions. First, given one file that contains the private key
and a second file that contains the text to be encrypted, this
first program, which I will call 'pk_crypt', provides an output
file that is encrypted and can be decrypted with the public key.
This serves the authentication function. Second, 'pk_crypt' can
encrypt a file with public key so that it can be decrypted with
the private key. This provides the privacy function.
The second program generates unique key pairs.
Step 2
------
Sysops provide a message section and a coordinated file section.
The message section allows users to notify each other that there
are secure messages that have been uploaded to the respective
users that have been notified via standard Fido text message.
The file section is not only a safe (reliable, not secure) port
for uploaded secure message files but also for a single text file
that contains a list of the mapping of user IDs to public keys.
Users upload their public keys as they generate them and the
sysops collate these standard format subfiles into a single
standard format public key-user ID list.
We will provide documentation not only for the use of the
program, but also for how users can "certify" new users and new
keys, since we will not at this stage be able to provide a key
server automated certification process.
Step 3
------
Sysops provide a standard service that allows binary files to be
"attached to" Fidomail messages. Nothing automatic is implied by
the previous sentence.
Step 4
------
We would have to provide a mail function that from the same level
of menu allowed the entry of a text tag message into the message
system, followed by the immediate upload of an encrypted (perhaps
archived) file to the secure message file section.
The inverse of these two processes would also have to be
provided. Users would have to be able, from the same level of
message menu, to first read a tag message, and, then,
immediately, download the associated secure binary message file.
.
.
.
WHAT DO YOU THINK?
==================
This is a lot to lay on anyone in one swell foop. What do you
think about practically any of this? We are especially
interested in your views and ideas as to how (or if) it can fit
into Fidonet. We await your responses.
Lee Rothstein, Phil Zimmermann, Steve Welch
Prodex Laboratories
------ ------------
COMPUTER AND COMMUNICATIONS SYSTEMS
PRODUCT DEVELOPMENT CONSULTING
o Computer and communications system product development:
Software, Hardware & Integration
o Marketing requirements, product, business & strategic
plans
o Market research
o New venture evaluation
o Technical marketing, marketing programs, seminar
development
o Product definition, architecture development, systems
engineering, human interface design
o Strategic information systems & computerized marketing
Lee D. Rothstein
Prodex Laboratories
7723 Arlington Drive
Boulder, CO 80303-3207
(303) 499-8716 (Voice)
We can be contacted via any of these BBSes, or via FidoNet at one
of these BBSes:
o Microlink B Fido. Fido 104/108. (303) 972-4181.
o Eighth Sea Fido. Fido 104/610. (303) 252-9235.
o Day's End Fido. Fido 104/ 20. (303) 650-5636.
o Mile Hi Tech Fido. Fido 104/ 56. (303) 973-9338.
[There is an experimental FidoNet/Usenet gateway currently operating through
hoptoad, due to a lot of work by Tim Pozar (hoptoad!pozar) and others. You
can try reaching the author through
...!hoptoad!node108.net104.zone1.fido.net!lee_rothstein
and note that I haven't tried this address! -- John Gilmore]
--
{dasys1,ncoast,well,sun,ihnp4}!hoptoad!gnu gnu@postgres.berkeley.edu
Alt.all: the alternative radio of the Usenet.jbn@glacier.STANFORD.EDU (John B. Nagle) (07/31/87)
This is an excellent idea. It's time for the widespread use of public
key systems. But one that is generally considered cryptologically sound
must be employed. Recent progress on factoring and the knapsack problem
render public key systems, including RSA, based on those problems somewhat
suspect.
Whatever is done should be published in Cryptologia for comment before
it is deployed, since that journal seems to contain more "how I broke X"
type articles than anything else in the field. You need to have the
system looked at by people who break cryptosystems.
Incidentally, if getting binary data through FidoNet is a problem,
why not just recode every 3 bytes of binary data into 4 ASCII characters,
using 6 bits of data per ASCII character and
coding only into printing characters. Messages get 1/3 bigger, but
that's tolerable in exchange for not having to modify the network.
John Nagle