Path: gmdzi!unido!mcvax!uunet!hoptoad!gnu
From: gnu@hoptoad.uucp (John Gilmore)
Newsgroups: sci.crypt
Subject: Online copy of Merkle's "A Software Encryption Function"
Message-ID: <7982@hoptoad.uucp>
Date: 13 Jul 89 10:31:58 GMT
References: <7981@hoptoad.uucp>
Organization: Grasshopper Group in San Francisco
Lines: 1520
Posted: Thu Jul 13 11:31:58 1989
[See the parent article <7981@hoptoad.uucp> for the legalese. This
netnews article is exportable under 22 CFR 120.18, 22 CFR 125.1 (a),
and 15 CFR 379.3(a). It can be sent to all foreign as well as US
domestic destinations. -- John]
A Software Encryption Function
by
Ralph C. Merkle
Xerox PARC
3333 Coyote Hill Road
Palo Alto, CA 94304
ABSTRACT
Encryption hardware is not available on most computer systems in use
today. Despite this fact, there is no well accepted encryption
function designed for software implementation -- instead, hardware
designs are emulated in software and the resulting performance loss is
tolerated. The obvious solution is to design an encryption function
for implementation in software. Such an encryption function is
presented here -- on a SUN 4/260 it can encrypt at 4 to 8 megabits per
second. The combination of modern processor speeds and a faster
algorithm make software encryption feasible in applications which
previously would have required hardware. This will effectively reduce
the cost and increase the availability of cryptographic protection.
Introduction
The computer community has long recognized the need for security and
the essential role that encryption must play. Widely adopted,
standard encryption functions will make a great contribution to
security in the distributed heavily networked environment which is
already upon us. IBM recognized the coming need in the 1970's and
proposed the Data Encryption Standard. or DES [19]. Although
controversy about its key size has persisted, DES has successfully
resisted all public attack and been widely accepted. After some
debate its use as a U.S. Federal Standard has recently been reaffirmed
until 1992 [14]. However, given the inherent limitations of the 56
bit key size used in DES [16] it seems clear that the standard will at
least have to be revised at some point. A recent review of DES by the
Office of Technology Assessment [15] quotes Dennis Branstad as saying
the 'useful lifetime' of DES would be until the late 199O's.
Despite the widespread acceptance of DES the most popular software
commercial encryption packages (for, e.g., the IBM PC or the Apple
Macintosh) typically offer both DES encryption and their own
home-grown encryption function. The reason is simple -- DES is often
50 to 100 times slower than the home-grown alternative. While some of
this performance differential is due to a sub-optimal DES
implementation or a faster but less secure home-grown encryption
function, it seems that DES is inherently 5 to 10 times slower than an
equivalent, equally secure encryption function designed for software
implementation. This is not to fault DES -- one of the design
objectives in DES was quite explicitly a fast hardware implementation:
when hardware is available, DES is an excellent choice. However, a
number of design decisions were made in DES reflecting the hardware
orientation which result in slow software performance -- making the
current extensive use of DES in software both unplanned-for and rather
anomalous.
Having offered a rationale for an encryption function designed for
software implementation, we now turn to the design principles,
followed by the actual design.
[Contents Removed]
--
John Gilmore {sun,pacbell,uunet,pyramid}!hoptoad!gnu g...@toad.com
"And if there's danger don't you try to overlook it,
Because you knew the job was dangerous when you took it"