In
cryptography
Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...
, the International Data Encryption Algorithm (IDEA), originally called Improved Proposed Encryption Standard (IPES), is a
symmetric-key block cipher
In cryptography, a block cipher is a deterministic algorithm operating on fixed-length groups of bits, called ''blocks''. Block ciphers are specified cryptographic primitive, elementary components in the design of many cryptographic protocols and ...
designed by
James Massey
James Lee Massey (February 11, 1934 – June 16, 2013) was an American information theorist and
cryptographer, Professor Emeritus of Digital Technology at ETH Zurich. His notable work includes the application of the Berlekamp–Massey algorithm to ...
of
ETH Zurich
(colloquially)
, former_name = eidgenössische polytechnische Schule
, image = ETHZ.JPG
, image_size =
, established =
, type = Public
, budget = CHF 1.896 billion (2021)
, rector = Günther Dissertori
, president = Joël Mesot
, ac ...
and
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 based on the Lai-Massey scheme, the theory of Markov ciphers, and the cryptanalysis of a num ...
and was first described in 1991. The algorithm was intended as a replacement for the
Data Encryption Standard
The Data Encryption Standard (DES ) is a symmetric-key algorithm for the encryption of digital data. Although its short key length of 56 bits makes it too insecure for modern applications, it has been highly influential in the advancement of cry ...
(DES). IDEA is a minor revision of an earlier
cipher
In cryptography, a cipher (or cypher) 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''. To encipher or encode i ...
Proposed Encryption Standard (PES).
The cipher was designed under a research contract with the Hasler Foundation, which became part of Ascom-Tech AG. The cipher was patented in a number of countries but was freely available for non-commercial use. The name "IDEA" is also a
trademark
A trademark (also written trade mark or trade-mark) is a type of intellectual property consisting of a recognizable sign, design, or expression that identifies products or services from a particular source and distinguishes them from others ...
. The last
patent
A patent is a type of intellectual property that gives its owner the legal right to exclude others from making, using, or selling an invention for a limited period of time in exchange for publishing an enabling disclosure of the invention."A p ...
s expired in 2012, and IDEA is now patent-free and thus completely free for all uses.
IDEA was used in
Pretty Good Privacy
Pretty Good Privacy (PGP) is an encryption program that provides cryptographic privacy and authentication for data communication. PGP is used for signing, encrypting, and decrypting texts, e-mails, files, directories, and whole disk partition ...
(PGP) v2.0 and was incorporated after the original cipher used in v1.0,
BassOmatic
In cryptography, BassOmatic is the symmetric-key cipher designed by Phil Zimmermann as part of his email encryption software PGP (in the first release, version 1.0). Comments in the source code indicate that he had been designing the cipher si ...
, was found to be insecure. IDEA is an optional algorithm in the
OpenPGP
Pretty Good Privacy (PGP) is an encryption program that provides cryptographic privacy and authentication for data communication. PGP is used for signing, encrypting, and decrypting texts, e-mails, files, directories, and whole disk partitio ...
standard.
Operation
IDEA operates on 64-bit
blocks using a 128-bit
key
Key or The Key may refer to:
Common meanings
* Key (cryptography), a piece of information that controls the operation of a cryptography algorithm
* Key (lock), device used to control access to places or facilities restricted by a lock
* Key (map ...
and consists of a series of 8 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
A group is a number of persons or things that are located, gathered, or classed together.
Groups of people
* Cultural group, a group whose members share the same cultural identity
* Ethnic group, a group whose members share the same ethnic ide ...
—
modular
Broadly speaking, modularity is the degree to which a system's components may be separated and recombined, often with the benefit of flexibility and variety in use. The concept of modularity is used primarily to reduce complexity by breaking a s ...
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
XOR
Exclusive or or exclusive disjunction is a logical operation that is true if and only if its arguments differ (one is true, the other is false).
It is symbolized by the prefix operator J and by the infix operators XOR ( or ), EOR, EXOR, , ...
(exclusive OR) (denoted with a blue circled plus
).
* Addition modulo 2
16 (denoted with a green boxed plus
).
* Multiplication modulo 2
16 + 1, where the all-zero word (0x0000) in inputs is interpreted as 2
16, and 2
16 in output is interpreted as the all-zero word (0x0000) (denoted by a red circled dot
).
After the 8 rounds comes a final “half-round”, the output transformation illustrated below (the swap of the middle two values cancels out the swap at the end of the last round, so that there is no net swap):
:
Structure
The overall structure of IDEA follows the
Lai–Massey scheme
The Lai–Massey scheme is a cryptographic structure used in the design of block ciphers. It is used in IDEA and IDEA NXT. The scheme was originally introduced by Xuejia LaiX. Lai. On the design and security of block ciphers'. ETH Series in Infor ...
. XOR is used for both subtraction and addition. IDEA uses a key-dependent half-round function. To work with 16-bit words (meaning 4 inputs instead of 2 for the 64-bit block size), IDEA uses the Lai–Massey scheme twice in parallel, with the two parallel round functions being interwoven with each other. To ensure sufficient diffusion, two of the sub-blocks are swapped after each round.
Key schedule
Each round uses 6 16-bit sub-keys, while the half-round uses 4, a total of 52 for 8.5 rounds. The first 8 sub-keys are extracted directly from the key, with K1 from the first round being the lower 16 bits; further groups of 8 keys are created by rotating the main key left 25 bits between each group of 8. This means that it is rotated less than once per round, on average, for a total of 6 rotations.
Decryption
Decryption works like encryption, but the order of the round keys is inverted, and the subkeys for the odd rounds are inversed. For instance, the values of subkeys K1–K4 are replaced by the inverse of K49–K52 for the respective group operation, K5 and K6 of each group should be replaced by K47 and K48 for decryption.
Security
The designers analysed IDEA to measure its strength against
differential 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 information input can aff ...
and concluded that it is immune under certain assumptions. No successful
linear
Linearity is the property of a mathematical relationship (''function'') that can be graphically represented as a straight line. Linearity is closely related to '' proportionality''. Examples in physics include rectilinear motion, the linear r ...
or algebraic weaknesses have been reported. , the best attack applied to all keys could break IDEA reduced to 6 rounds (the full IDEA cipher uses 8.5 rounds).
[
] Note that a "break" is any attack that requires less than 2
128 operations; the 6-round attack requires 2
64 known plaintexts and 2
126.8 operations.
Bruce Schneier
Bruce Schneier (; born January 15, 1963) is an American cryptographer, computer security professional, privacy specialist, and writer. Schneier is a Lecturer in Public Policy at the Harvard Kennedy School and a Fellow at the Berkman Klein Cente ...
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.
In 2011 full 8.5-round IDEA was broken using a meet-in-the-middle attack. Independently in 2012, full 8.5-round IDEA was broken using a narrow-
bicliques attack, with a reduction of cryptographic strength of about 2 bits, similar to the effect of the previous bicliques attack on
AES; however, this attack does not threaten the security of IDEA in practice.
Weak keys
The very simple key schedule makes IDEA subject to a class of
weak 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 rando ...
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: XORing 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 Switzerland
). Swiss law does not designate a ''capital'' as such, but the federal parliament and government are installed in Bern, while other federal institutions, such as the federal courts, are in other cities (Bellinzona, Lausanne, Luzern, Neuchâtel ...
(CH A 1690/90) on May 18, 1990, then an international patent application was filed under the Patent Cooperation Treaty
The Patent Cooperation Treaty (PCT) 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. A patent application filed und ...
on May 16, 1991. Patents were eventually granted in Austria
Austria, , bar, Östareich officially the Republic of Austria, is a country in the southern part of Central Europe, lying in the Eastern Alps. It is a federation of nine states, one of which is the capital, Vienna, the most populous ...
, France
France (), officially the French Republic ( ), is a country primarily located in Western Europe. It also comprises of Overseas France, overseas regions and territories in the Americas and the Atlantic Ocean, Atlantic, Pacific Ocean, Pac ...
, Germany
Germany,, officially the Federal Republic of Germany, is a country in Central Europe. It is the second most populous country in Europe after Russia, and the most populous member state of the European Union. Germany is situated betwe ...
, Italy
Italy ( it, Italia ), officially the Italian Republic, ) or the Republic of Italy, is a country in Southern Europe. It is located in the middle of the Mediterranean Sea, and its territory largely coincides with the homonymous geographical re ...
, the Netherlands
)
, anthem = ( en, "William of Nassau")
, image_map =
, map_caption =
, subdivision_type = Sovereign state
, subdivision_name = Kingdom of the Netherlands
, established_title = Before independence
, established_date = Spanish Netherl ...
, Spain
, image_flag = Bandera de España.svg
, image_coat = Escudo de España (mazonado).svg
, national_motto = ''Plus ultra'' (Latin)(English: "Further Beyond")
, national_anthem = (English: "Royal March")
, i ...
, Sweden
Sweden, formally the Kingdom of Sweden,The United Nations Group of Experts on Geographical Names states that the country's formal name is the Kingdom of SwedenUNGEGN World Geographical Names, Sweden./ref> is a Nordic country located on ...
, Switzerland
). Swiss law does not designate a ''capital'' as such, but the federal parliament and government are installed in Bern, while other federal institutions, such as the federal courts, are in other cities (Bellinzona, Lausanne, Luzern, Neuchâtel ...
, the United Kingdom
The United Kingdom of Great Britain and Northern Ireland, commonly known as the United Kingdom (UK) or Britain, is a country in Europe, off the north-western coast of the continental mainland. It comprises England, Scotland, Wales and North ...
, (, filed May 16, 1991, issued June 22, 1994 and expired May 16, 2011), the United States
The United States of America (U.S.A. or USA), commonly known as the United States (U.S. or US) or America, is a country primarily located in North America. It consists of 50 states, a federal district, five major unincorporated territorie ...
(, issued May 25, 1993 and expired January 7, 2012) and Japan
Japan ( ja, 日本, or , and formally , ''Nihonkoku'') is an island country in East Asia. It is situated in the northwest Pacific Ocean, and is bordered on the west by the Sea of Japan, while extending from the Sea of Okhotsk in the north ...
(JP 3225440, expired May 16, 2011).
MediaCrypt AG is now offering a successor to IDEA and focuses on its new cipher (official release in May 2005) IDEA NXT
In cryptography, the IDEA NXT algorithm (previously known as FOX) is a block cipher designed by Pascal Junod and Serge Vaudenay of EPFL (Lausanne, Switzerland). It was conceived between 2001 and 2003. The project was originally named FOX and wa ...
, 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 Cryptography
Selected Areas in Cryptography (SAC) is an international cryptography conference (originally a workshop) held every August in Canada since 1994. The first workshop was organized by Carlisle Adams, Henk Meijer, Stafford Tavares and Paul van Oorsc ...
, 2004.
* Xuejia Lai and James L. Massey
A Proposal for a New Block Encryption Standard
EUROCRYPT 1990, pp. 389–404
* Xuejia Lai and James L. Massey and S. Murphy, Markov ciphers and differential cryptanalysis, ''Advances in Cryptology — Eurocrypt '91'', Springer-Verlag (1992), pp. 17–38.
References
External links
RSA FAQ on Block Ciphers
Java source code
{{Cryptography navbox , block
Block ciphers
Broken block ciphers