International Data Encryption Algorithm
IDEA | |
---|---|
An encryption round of the IDEA algorithm | |
developer | James L. Massey , Xueija Lai |
Released | 1991 |
Derived from | PES |
Key length | 128 bit |
Block size | 64 bit |
structure | Lai-Massey scheme |
Round | 8.5 |
Best known cryptanalysis | |
A plaintext attack with ^{264} known plaintext blocks can decrypt up to 6 rounds with a key length of 128 bits with ^{2,126.8} operations. |
The International Data Encryption Algorithm ( IDEA ) was developed in 1990 as a joint project between ETH Zurich and Ascom Systec AG by James L. Massey and Xueija Lai . IDEA is a symmetrical algorithm and belongs to the block ciphers . The algorithm was developed through a revision of an earlier cryptosystem called PES (Proposed Encryption Standard), initially it was called IPES (Improved PES) and was considered as a replacement for DES .
The Ascom Systec AG held the patents to IDEA. The corresponding European patent EP 0 482 154 B1 was registered with effect for the EPC contracting states Germany , France , Italy , Liechtenstein , the Netherlands , Austria , Sweden , Switzerland , Spain and the United Kingdom and expired on May 16, 2011. The corresponding US patent US 5,214,703 also expired on May 16, 2011.
Working method
IDEA uses a series of eight identical transformations, each corresponding to one round, and one output transformation, which corresponds to half a round. The decryption process is the same as the encryption process in reverse. With encryption , the plain text is divided into 64-bit blocks and the key is broken down into 16-bit pieces. The encryption is done by combining the following three operations:
- The Boolean operation XOR , also called "exclusives or" (shown with a plus circled in blue ⊕ )
- The addition modulo 2 ^{16} (shown with a green, framed plus ⊞ ).
- The multiplication modulo 2 ^{16} +1, where all NULL word values (0x0000) are interpreted as value 2 ^{16} (shown with a point circled in red ⊙ ).
The combination of these three operations from different algebraic groups is intended to ensure a high level of security. The method is optimized to withstand attacks by differential cryptanalysis . After eight rounds, a final half-round, the output transformation, is used, which is shown in the illustration below.
Key Schedule
Each of the eight rounds uses six 16-bit partial keys, while the final half round uses four of these, making a total of 52 partial keys for 8.5 rounds. The first eight partial keys are extracted directly from the key, the key K1 of the first round being formed from the 16 least significant bits . Then the key is rotated 25 bits to the left and eight partial keys are extracted from the rotated key. This is repeated until, after a total of six rotations, all 52 subkeys have been created.
safety
The developers analyzed IDEA to measure its strength against differential cryptanalysis and concluded that the algorithm may be immune to this type of attack under certain circumstances. No further linear or algebraic weaknesses were discovered. The best attack on IDEA is a clear text attack and dates back to 2011. This breaks the algorithm if it is reduced to 6 rounds and requires 16 clear text blocks and fewer than ^{2,112} operations.
Bruce Schneier had a high opinion of IDEA in 1996 and wrote in his book Applied Cryptography : "In my opinion, IDEA is the best and most secure block algorithm currently publicly available." In 1999, however, he recommended the algorithm based on cryptanalysis - Progress and problems with software patents no longer.
The simple key schedule makes IDEA vulnerable to attack with a class of weak keys. Keys that contain a large number of bits with the value 0 lead to weak encryption. These are of little importance in practice, as they rarely occur and therefore do not have to be bypassed explicitly when generating the random key. In order to solve the problem, it was proposed: During the XOR operation, each partial key should be linked with a 16-bit constant with the value 0x0DAE. Larger classes of weak keys were discovered in 2002.
literature
- Xuejia Lai, James L. Massey: A Proposal for a New Block Encryption Standard . In: EUROCRYPT . 1990, ISBN 3-540-46877-3 , pp. 389-404 .