XTEA

From Wikipedia, the free encyclopedia


XTEA
Two Feistel rounds (one cycle) of XTEA
Designer(s): Roger Needham, David Wheeler
First published: 1997
Derived from: TEA
Key size(s): 128 bits
Block size(s): 64 bits
Structure: Feistel network
Rounds: variable; recommended 64 Feistel rounds (32 cycles)
Best public cryptanalysis:
A related-key differential attack can break 26 out of 64 rounds of XTEA, requiring 220.5 chosen plaintexts and a time complexity of 2115.15 (Ko et al, 2004).

In cryptography, XTEA (eXtended TEA) is a block cipher designed to correct weaknesses in TEA. The cipher's designers were David Wheeler and Roger Needham of the Cambridge Computer Laboratory, and the algorithm was presented in an unpublished technical report in 1997 (Needham and Wheeler, 1997). It is not subject to any patents.

Like TEA, XTEA is a 64-bit block Feistel network with a 128-bit key and a suggested 64 rounds. Several differences from TEA are apparent, including a somewhat more complex key-schedule and a rearrangement of the shifts, XORs, and additions.

Presented along with XTEA was a variable-width block cipher termed Block TEA, which uses the XTEA round function but applies it cyclically across an entire message for several iterations. Because it operates on the entire message, Block TEA has the property that it does not need a mode of operation. An attack on the full Block TEA was described in (Saarinen, 1998), which also details a weakness in Block TEA's successor, XXTEA.

As of 2004, the best attack reported on XTEA is a related-key differential attack on 26 out of 64 rounds of XTEA, requiring 220.5 chosen plaintexts and a time complexity of 2115.15 (Ko et al, 2004).

Contents

[edit] Implementations

This standard C source code, released into the public domain by David Wheeler and Roger Needham, encrypts and decrypts using XTEA:

void encipher(unsigned int num_rounds, unsigned long* v, unsigned long* k) {
    unsigned long v0=v[0], v1=v[1], i;
    unsigned long sum=0, delta=0x9E3779B9;
    for(i=0; i<num_rounds; i++) {
        v0 += ((v1 << 4 ^ v1 >> 5) + v1) ^ (sum + k[sum & 3]);
        sum += delta;
        v1 += ((v0 << 4 ^ v0 >> 5) + v0) ^ (sum + k[sum>>11 & 3]);
    }
    v[0]=v0; v[1]=v1;
}

void decipher(unsigned int num_rounds, unsigned long* v, unsigned long* k) {
    unsigned long v0=v[0], v1=v[1], i;
    unsigned long delta=0x9E3779B9, sum=delta*num_rounds;
    for(i=0; i<num_rounds; i++) {
        v1 -= ((v0 << 4 ^ v0 >> 5) + v0) ^ (sum + k[sum>>11 & 3]);
        sum -= delta;
        v0 -= ((v1 << 4 ^ v1 >> 5) + v1) ^ (sum + k[sum & 3]);
    }
    v[0]=v0; v[1]=v1;
}


It is important to note that some modern programming languages have a slightly different operators order of precedence. Therefore, the interpretation of the original code will lead to different results, making different implementations of the encryption incompatible. This can be corrected with the use of a few parenthesis to enforce precedence order.

void encipher(unsigned int num_rounds, unsigned long* v, unsigned long* k) {
    unsigned long v0=v[0], v1=v[1], i;
    unsigned long sum=0, delta=0x9E3779B9;
    for(i=0; i<num_rounds; i++) {
        v0 += (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + k[sum & 3]);
        sum += delta;
        v1 += (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + k[(sum>>11) & 3]);
    }
    v[0]=v0; v[1]=v1;
}

void decipher(unsigned int num_rounds, unsigned long* v, unsigned long* k) {
    unsigned long v0=v[0], v1=v[1], i;
    unsigned long delta=0x9E3779B9, sum=delta*num_rounds;
    for(i=0; i<num_rounds; i++) {
        v1 -= (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + k[(sum>>11) & 3]);
        sum -= delta;
        v0 -= (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + k[sum & 3]);
    }
    v[0]=v0; v[1]=v1;
}

[edit] See also

  • RC4 - A stream cipher that just like XTEA is designed to be very simple to implement.

[edit] References

  • Youngdai Ko, Seokhie Hong, Wonil Lee, Sangjin Lee, and Jongin Lim. "Related key differential attacks on 26 rounds of XTEA and full rounds of GOST." In Proceedings of FSE '04, Lecture Notes in Computer Science, 2004. Springer-Verlag.
  • Seokhie Hong, Deukjo Hong, Youngdai Ko, Donghoon Chang, Wonil Lee, and Sangjin Lee. "Differential cryptanalysis of TEA and XTEA." In Proceedings of ICISC 2003, 2003b.
  • Dukjae Moon, Kyungdeok Hwang, Wonil Lee, Sangjin Lee, and Jongin Lim. "Impossible differential cryptanalysis of reduced round XTEA and TEA." Lecture Notes in Computer Science, 2365: 49-60, 2002. ISSN 0302-9743.
  • Roger M. Needham and David J. Wheeler. "Tea extensions." Technical report, Computer Laboratory, University of Cambridge, October 1997 (PDF).
  • Vikram Reddy Andem. A Cryptanalysis of the Tiny Encryption Algorithm, Masters thesis, The University of Alabama, Tuscaloosa, 2003.
  • Markku-Juhani Saarinen. "Cryptanalysis of Block TEA." Unpublished manuscript, October 1998. Can be found on the author's homepage or in the sci.crypt.research Usenet archive.

[edit] External links


Block ciphers
v d e
Algorithms: 3-Way | AES | Akelarre | Anubis | BaseKing | Blowfish | C2 | Camellia | CAST-128 | CAST-256 | CMEA | Cobra | Crab | CS-Cipher | DEAL | DES | DES-X | DFC | E2 | FEAL | FROG | G-DES | GOST | Grand Cru | Hasty Pudding Cipher | Hierocrypt | ICE | IDEA | IDEA NXT | Iraqi | KASUMI | KHAZAD | Khufu and Khafre | Libelle | LOKI89/91 | LOKI97 | Lucifer | MacGuffin | Madryga | MAGENTA | MARS | Mercy | MESH | MISTY1 | MMB | MULTI2 | NewDES | NOEKEON | NUSH | Q | RC2 | RC5 | RC6 | REDOC | Red Pike | S-1 | SAFER | SC2000 | SEED | Serpent | SHACAL | SHARK | Skipjack | SMS4 | Square | TEA | Triple DES | Twofish | XTEA
Design: Feistel network | Key schedule | Product cipher | S-box | SPN Attacks: Brute force | Linear / Differential / Integral cryptanalysis | Mod n | Related-key | Slide | XSL
Standardization: AES process | CRYPTREC | NESSIE Misc: Avalanche effect | Block size | IV | Key size | Modes of operation | Piling-up lemma | Weak key
Cryptography
v d e
History of cryptography | Cryptanalysis | Cryptography portal | Topics in cryptography
Symmetric-key algorithm | Block cipher | Stream cipher | Public-key cryptography | Cryptographic hash function | Message authentication code | Random numbers