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.