International Data Encryption Algorithm
Encyclopedia
In cryptography
, the International Data Encryption Algorithm (IDEA) is a block cipher
designed by James Massey
of ETH Zurich
and Xuejia Lai
and was first described in 1991. As a block cipher, it is also symmetric. The algorithm was intended as a replacement for the Data Encryption Standard
[DES]. IDEA is a minor revision of an earlier cipher
, PES (Proposed Encryption Standard); IDEA was originally called IPES (Improved PES).
The cipher was designed under a research contract with the Hasler Foundation, which became part of Ascom-Tech AG. The cipher is patented in a number of countries but is freely available for non-commercial use. The name "IDEA" is also a trademark
. The patent
s will expire in 2011–2012. Today, IDEA is licensed in all the countries where it is patented by MediaCrypt.
IDEA was used in Pretty Good Privacy
(PGP) v2.0, and was incorporated after the original cipher used in v1.0, BassOmatic
, was found to be insecure. IDEA is an optional algorithm in the OpenPGP standard.
using a 128-bit key
, and consists of a series of eight identical transformations (a round, see the illustration) and an output transformation (the half-round). The processes for encryption and decryption are similar. IDEA derives much of its security by interleaving operations from different groups
— modular
addition and multiplication, and bitwise eXclusive OR (XOR) — which are algebraically "incompatible" in some sense. In more detail, these operators, which all deal with 16-bit quantities, are:
After the eight rounds comes a final "half round", the output transformation illustrated below:
and concluded that it is immune under certain assumptions. No successful linear
or algebraic weaknesses have been reported. , the best attack which applies to all keys can break IDEA reduced to 6 rounds (the full IDEA cipher uses 8.5 rounds). Note that a "break" is any attack which requires less than 2128 operations; the 6-round attack requires 264 known plaintexts and 2126.8 operations.
Bruce Schneier
thought highly of IDEA in 1996, writing, "In my opinion, it is the best and most secure block algorithm available to the public at this time." (Applied Cryptography, 2nd ed.) However, by 1999 he was no longer recommending IDEA due to the availability of faster algorithms, some progress in its cryptanalysis, and the issue of patents.
s; some keys containing a large number of 0 bits produce weak encryption. These are of little concern in practice, being sufficiently rare that they are unnecessary to avoid explicitly when generating keys randomly. A simple fix was proposed: exclusive-ORing each subkey with a 16-bit constant, such as
Larger classes of weak keys were found in 2002.
This is still of negligible probability to be a concern to a randomly-chosen key, and some of the problems are fixed by the constant XOR proposed earlier, but the paper is not certain if all of them are. A more comprehensive redesign of the IDEA key schedule may be desirable.
(CH A 1690/90) on May 18, 1990, then an international patent application was filed under the Patent Cooperation Treaty
on May 16, 1991. Patents were eventually granted in Austria
, France
, Germany
, Italy
, the Netherlands
, Spain
, Sweden
, Switzerland
, the United Kingdom
, , the United States
and Japan
(JP 3225440). (According to the PGP FAQ, the US patent expired on May 25, 2010. However, US patent law was changed in 1995 such that patents now expire 20 years after filing, not 17 years after issuing. This holds retroactively for all patents that had not yet expired at the time the changed law came into effect, and it thus holds for IDEA. International treaties may or may not cause expiry as early as May 16, 2011.)
MediaCrypt AG is now offering a successor to IDEA and focuses on its new cipher (official release on May 2005) IDEA NXT
, which was previously called FOX.
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
, the International Data Encryption Algorithm (IDEA) is a block cipher
Block cipher
In cryptography, a block cipher is a symmetric key cipher operating on fixed-length groups of bits, called blocks, with an unvarying transformation. A block cipher encryption algorithm might take a 128-bit block of plaintext as input, and output a corresponding 128-bit block of ciphertext...
designed by James Massey
James Massey
James Lee Massey is an information theorist andcryptographer, Professor Emeritus of Digital Technology at ETH Zurich. His notable work...
of ETH Zurich
ETH Zurich
The Swiss Federal Institute of Technology Zurich or ETH Zürich is an engineering, science, technology, mathematics and management university in the City of Zurich, Switzerland....
and Xuejia Lai
Xuejia Lai
Xuejia Lai is a cryptographer, currently a professor at Shanghai Jiao Tong University. His notable work includes the design of the block cipher IDEA, the theory of Markov ciphers, and the cryptanalysis of a number of cryptographic hash functions. His book On the Design and Security of Block...
and was first described in 1991. As a block cipher, it is also symmetric. The algorithm was intended as a replacement for the Data Encryption Standard
Data Encryption Standard
The Data Encryption Standard is a block cipher that uses shared secret encryption. It was selected by the National Bureau of Standards as an official Federal Information Processing Standard for the United States in 1976 and which has subsequently enjoyed widespread use internationally. It is...
[DES]. IDEA is a minor revision of an earlier cipher
Cipher
In cryptography, a cipher is an algorithm for performing encryption or decryption — a series of well-defined steps that can be followed as a procedure. An alternative, less common term is encipherment. In non-technical usage, a “cipher” is the same thing as a “code”; however, the concepts...
, PES (Proposed Encryption Standard); IDEA was originally called IPES (Improved PES).
The cipher was designed under a research contract with the Hasler Foundation, which became part of Ascom-Tech AG. The cipher is patented in a number of countries but is freely available for non-commercial use. The name "IDEA" is also a trademark
Trademark
A trademark, trade mark, or trade-mark is a distinctive sign or indicator used by an individual, business organization, or other legal entity to identify that the products or services to consumers with which the trademark appears originate from a unique source, and to distinguish its products or...
. The patent
Patent
A patent is a form of intellectual property. It consists of a set of exclusive rights granted by a sovereign state to an inventor or their assignee for a limited period of time in exchange for the public disclosure of an invention....
s will expire in 2011–2012. Today, IDEA is licensed in all the countries where it is patented by MediaCrypt.
IDEA was used in Pretty Good Privacy
Pretty Good Privacy
Pretty Good Privacy is a data encryption and decryption computer program that provides cryptographic privacy and authentication for data communication. PGP is often used for signing, encrypting and decrypting texts, E-mails, files, directories and whole disk partitions to increase the security...
(PGP) v2.0, and was incorporated after the original cipher used in v1.0, BassOmatic
BassOmatic
In cryptography, BassOmatic was the symmetric-key cipher designed by Phil Zimmermann as part of his email encryption software, PGP . Comments in the source code indicate that he had been designing the cipher since as early as 1988, but it was not publicly released until 1991...
, was found to be insecure. IDEA is an optional algorithm in the OpenPGP standard.
Operation
IDEA operates on 64-bit blocksBlock size (cryptography)
In modern cryptography, symmetric key ciphers are generally divided into stream ciphers and block ciphers. Block ciphers operate on a fixed length string of bits. The length of this bit string is the block size...
using a 128-bit key
Key (cryptography)
In cryptography, a key is a piece of information that determines the functional output of a cryptographic algorithm or cipher. Without a key, the algorithm would produce no useful result. In encryption, a key specifies the particular transformation of plaintext into ciphertext, or vice versa...
, and consists of a series of eight identical transformations (a round, see the illustration) and an output transformation (the half-round). The processes for encryption and decryption are similar. IDEA derives much of its security by interleaving operations from different groups
Group (mathematics)
In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...
— modular
Modular arithmetic
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value—the modulus....
addition and multiplication, and bitwise eXclusive OR (XOR) — which are algebraically "incompatible" in some sense. In more detail, these operators, which all deal with 16-bit quantities, are:
- Bitwise eXclusive OR (denoted with a blue circled plus ).
- Addition modulo 216 (denoted with a green boxed plus ).
- Multiplication modulo 216+1, where the all-zero word (0x0000) is interpreted as 216 (denoted by a red circled dot ).
After the eight rounds comes a final "half round", the output transformation illustrated below:
Key schedule
Each round uses six 16-bit sub-keys, while the half-round uses four, a total of 52 for 8.5 rounds. The first eight sub-keys are extracted directly from the key, with K1 from the first round being the lower sixteen bits; further groups of eight keys are created by rotating the main key left 25 bits between each group of eight. This means that it is rotated less than once per round, on average, for a total of six rotations.Security
The designers analysed IDEA to measure its strength against differential cryptanalysisDifferential cryptanalysis
Differential cryptanalysis is a general form of cryptanalysis applicable primarily to block ciphers, but also to stream ciphers and cryptographic hash functions. In the broadest sense, it is the study of how differences in an input can affect the resultant difference at the output...
and concluded that it is immune under certain assumptions. No successful linear
Linear cryptanalysis
In cryptography, linear cryptanalysis is a general form of cryptanalysis based on finding affine approximations to the action of a cipher. Attacks have been developed for block ciphers and stream ciphers...
or algebraic weaknesses have been reported. , the best attack which applies to all keys can break IDEA reduced to 6 rounds (the full IDEA cipher uses 8.5 rounds). Note that a "break" is any attack which requires less than 2128 operations; the 6-round attack requires 264 known plaintexts and 2126.8 operations.
Bruce Schneier
Bruce Schneier
Bruce Schneier is an American cryptographer, computer security specialist, and writer. He is the author of several books on general security topics, computer security and cryptography, and is the founder and chief technology officer of BT Managed Security Solutions, formerly Counterpane Internet...
thought highly of IDEA in 1996, writing, "In my opinion, it is the best and most secure block algorithm available to the public at this time." (Applied Cryptography, 2nd ed.) However, by 1999 he was no longer recommending IDEA due to the availability of faster algorithms, some progress in its cryptanalysis, and the issue of patents.
Weak keys
The very simple key schedule makes IDEA subject to a class of weak keyWeak key
In cryptography, a weak key is a key, which, used with a specific cipher, makes the cipher behave in some undesirable way. Weak keys usually represent a very small fraction of the overall keyspace, which usually means that, if one generates a random key to encrypt a message, weak keys are very...
s; some keys containing a large number of 0 bits produce weak encryption. These are of little concern in practice, being sufficiently rare that they are unnecessary to avoid explicitly when generating keys randomly. A simple fix was proposed: exclusive-ORing each subkey with a 16-bit constant, such as
0x0DAE.Larger classes of weak keys were found in 2002.
This is still of negligible probability to be a concern to a randomly-chosen key, and some of the problems are fixed by the constant XOR proposed earlier, but the paper is not certain if all of them are. A more comprehensive redesign of the IDEA key schedule may be desirable.
Availability
A patent application for IDEA was first filed in SwitzerlandSwitzerland
Switzerland name of one of the Swiss cantons. ; ; ; or ), in its full name the Swiss Confederation , is a federal republic consisting of 26 cantons, with Bern as the seat of the federal authorities. The country is situated in Western Europe,Or Central Europe depending on the definition....
(CH A 1690/90) on May 18, 1990, then an international patent application was filed under the Patent Cooperation Treaty
Patent Cooperation Treaty
The Patent Cooperation Treaty is an international patent law treaty, concluded in 1970. It provides a unified procedure for filing patent applications to protect inventions in each of its contracting states...
on May 16, 1991. Patents were eventually granted in Austria
Austria
Austria , officially the Republic of Austria , is a landlocked country of roughly 8.4 million people in Central Europe. It is bordered by the Czech Republic and Germany to the north, Slovakia and Hungary to the east, Slovenia and Italy to the south, and Switzerland and Liechtenstein to the...
, France
France
The French Republic , The French Republic , The French Republic , (commonly known as France , is a unitary semi-presidential republic in Western Europe with several overseas territories and islands located on other continents and in the Indian, Pacific, and Atlantic oceans. Metropolitan France...
, Germany
Germany
Germany , officially the Federal Republic of Germany , is a federal parliamentary republic in Europe. The country consists of 16 states while the capital and largest city is Berlin. Germany covers an area of 357,021 km2 and has a largely temperate seasonal climate...
, Italy
Italy
Italy , officially the Italian Republic languages]] under the European Charter for Regional or Minority Languages. In each of these, Italy's official name is as follows:;;;;;;;;), is a unitary parliamentary republic in South-Central Europe. To the north it borders France, Switzerland, Austria and...
, the Netherlands
Netherlands
The Netherlands is a constituent country of the Kingdom of the Netherlands, located mainly in North-West Europe and with several islands in the Caribbean. Mainland Netherlands borders the North Sea to the north and west, Belgium to the south, and Germany to the east, and shares maritime borders...
, Spain
Spain
Spain , officially the Kingdom of Spain languages]] under the European Charter for Regional or Minority Languages. In each of these, Spain's official name is as follows:;;;;;;), is a country and member state of the European Union located in southwestern Europe on the Iberian Peninsula...
, Sweden
Sweden
Sweden , officially the Kingdom of Sweden , is a Nordic country on the Scandinavian Peninsula in Northern Europe. Sweden borders with Norway and Finland and is connected to Denmark by a bridge-tunnel across the Öresund....
, Switzerland
Switzerland
Switzerland name of one of the Swiss cantons. ; ; ; or ), in its full name the Swiss Confederation , is a federal republic consisting of 26 cantons, with Bern as the seat of the federal authorities. The country is situated in Western Europe,Or Central Europe depending on the definition....
, the United Kingdom
United Kingdom
The United Kingdom of Great Britain and Northern IrelandIn the United Kingdom and Dependencies, other languages have been officially recognised as legitimate autochthonous languages under the European Charter for Regional or Minority Languages...
, , the United States
United States
The United States of America is a federal constitutional republic comprising fifty states and a federal district...
and Japan
Japan
Japan is an island nation in East Asia. Located in the Pacific Ocean, it lies to the east of the Sea of Japan, China, North Korea, South Korea and Russia, stretching from the Sea of Okhotsk in the north to the East China Sea and Taiwan in the south...
(JP 3225440). (According to the PGP FAQ, the US patent expired on May 25, 2010. However, US patent law was changed in 1995 such that patents now expire 20 years after filing, not 17 years after issuing. This holds retroactively for all patents that had not yet expired at the time the changed law came into effect, and it thus holds for IDEA. International treaties may or may not cause expiry as early as May 16, 2011.)
MediaCrypt AG is now offering a successor to IDEA and focuses on its new cipher (official release on May 2005) IDEA NXT
IDEA NXT
In cryptography, the IDEA NXT algorithm is a block cipher designed by Pascal Junod and Serge Vaudenay of EPFL . It was conceived between 2001 and 2003, the project was originally named FOX and was published in 2003. In May 2005 it was announced by MediaCrypt under the name IDEA NXT...
, which was previously called FOX.
Literature
- Hüseyin Demirci, Erkan Türe, Ali Aydin Selçuk, A New Meet in the Middle Attack on The IDEA Block Cipher, 10th Annual Workshop on Selected Areas in CryptographySelected Areas in CryptographySelected Areas in Cryptography is a series of international cryptography workshops held annually in Canada, every August since 1994. Through 1999, it was held at either Queen's University or Carleton University; the locations have varied more in recent years...
, 2004. - Xuejia Lai and James L. Massey, A Proposal for a New Block Encryption Standard, EUROCRYPTEuroCryptEuroCrypt is a conditional access system for Multiplexed Analogue Components-encoded analogue satellite television. It had several versions . It supported receivers with card slots and those with embedded keys...
1990, pp389–404 - Xuejia Lai and James L. Massey and S. Murphy, Markov ciphers and differential cryptanalysis, Advances in Cryptology — Eurocrypt '91, Springer-Verlag (1992), pp17–38.