From: schneier@chinet.chinet.com (Bruce Schneier)
Date: Wed, 6 Jul 94 14:48:31 PDT
To: bart@netcom.com (Harry Bartholomew)
Subject: Re: Please post your article
In-Reply-To: <199407060933.CAA02628@netcom5.netcom.com>
Message-ID: <m0qLeVR-0002GdC@chinet.chinet.com>
MIME-Version: 1.0
Content-Type: text/plain



                                                   Bruce Schneier
                                                730 Fair Oaks Ave
                                              Oak Park, IL  60302
                                                   (708) 524-9461
                                                        750 words


       IDEA - THE INTERNATIONAL DATA ENCRYPTION ALGORITHM

For the past fifteen years, most of us have relied on the Data
Encryption Standard, or DES, for encryption.  It's a good
algorithm, and very secure against the mid-1970s technology is
was designed for.  Advances in computing power and new
discoveries in cryptanalysis have made the algorithm vulnerable. 
DES is no longer secure against the world's most powerful
adversaries.  Cryptographers are looking for alternatives to
serve their needs well into the 21st century.  IDEA may be the
current best choice.

IDEA is the International Data Encryption Algorithm, and it was
invented in 1991 by James Massey and Xuejia Lai of ETH Zurich in
Switzerland.  An earlier variant of the algorithm was called PES:
Proposed Encryption Standard.  After strengthening the algorithm
against differential cryptanalysis, they changed its name to
IPES, for Improved Proposed Encryption Standard, and then to
IDEA.

The algorithm is structured along the same general lines of DES. 
It is an iterated block cipher, with a 64-bit block size and a
128-bit key size.  "Iterated" means that the algorithm uses a
simple encryption function multiple times.  "Block cipher" means
that the algorithm encrypts data in blocks: 64 bits of plaintext
go in one end, and 64 bits of ciphertext come out the other.  And
the algorithm accepts a 128-bit key.

This means that IDEA can be a plug-in replacement for DES, only
with a longer key length.  IDEA can be used in all the different
modes of operation--electronic codebook, cipher block chaining,
output feedback, and cipher feedback-- specified for DES in FIPS
PUB 81 or ANSI X3.106.

The design philosophy behind IDEA is one of "mixing operations
from different algebraic groups."  The operations are XOR,
modular addition, and modular multiplication.  All operations are
based on 16-bit words, and hence are efficiently implemented in
software.  (DES has numerous bit twiddling operations, making it
very inefficient in software.)  IDEA only has eight iterations,
compared with DES's 16, but each IDEA iteration can be thought of
as a double DES iteration.  IDEA is also faster than DES when
implemented in software.

IDEA's 128-bit key length over twice that of DES; its key length
is even longer than triple-DES.  And it is much faster than
triple-DES.  A brute-force attack against IDEA would have to try
2^128, or 3*10^38, possible keys.  Michael Wiener's brute-force
DES-cracking machine, which could find a DES key in an average of
3.5 hours would require 10^18 years to break IDEA.  A machine a
million times faster would still require 10^12, or one trillion,
years to break IDEA.

Does this mean that IDEA is secure?  Is there a more efficient
way to break IDEA than brute force?  No one knows.  IDEA is a
very new algorithm.  Remember that it took cryptographers fifteen
years of studying DES to invent differential cryptanalysis,
something that the NSA knew about all along.  Who knows what
tricks the NSA knows about now that allows them to break IDEA. 
Maybe they know none.  Maybe they know something that we will
discover for ourselves around the year 2006.

There are no assurances in the cryptography business.  Several
academic groups have tried to cryptanalyze IDEA with no success. 
Yet.  Several military intelligence agencies have tried to
cryptanalyze IDEA; they're not talking about what they found. 
IDEA is a good-looking algorithm, but it is also a new algorithm. 
Ten years from now we will all consider it an amazing feat of
security or an impressive failure.  I would bet on the former,
but recognize that it is a bet.

The most widespread product that uses IDEA is PGP: Pretty Good
Privacy.  PGP uses IDEA in cipher feedback mode for data
encryption.  Several other security companies offer the algorithm
as an optional alternative to DES.  It is available both in
software and as a custom ASIC.

Details of the algorithm (with source code) can be found in: 

     X. Lai, J. Massey, and S. Murphy, "Markov Ciphers and
     Differential Cryptanalysis," Advances in Cryptology--
     EUROCRYPT '91 Proceedings, Berlin: Springer-Verlag, 1991,
     pp. 17-38.

     B. Schneier, "The IDEA Encryption Algorithm." Dr. Dobbs
     Journal, Dec 93, pp. 50-56.

     B. Schneier, Applied Cryptography, New York: John Wiley &
     Sons, 1994.

IDEA is patented in the United States (J.L. Massey and X. Lai,
"Device for the Conversion of a Digital Block and the Use of
Same," U.S. Patent #5,214,703, 25 May 1993) and in Europe.  The
patents are held by Ascom-Tech AG.  There is no license fee
required for noncommercial use.  Commercial users interested in
licensing the algorithm should contact: Dr. Peter Profos, Ascom
Tech AG, Solothurn Lab, Postfach 151, 4502 Solothurn,
Switzerland; telephone +41 65 242 885; facsimile +41 65 235 761.


From owner-cypherpunks  Wed Jul  6 14:47:07 1994
Return-Path: <owner-cypherpunks>
Received: by toad.com id AA06562; Wed, 6 Jul 94 14:47:07 PDT