XTEA
From Wikipedia, the free encyclopedia
Two Feistel rounds (one cycle) of XTEA 

General  

Designers  Roger Needham, David Wheeler 
First published  1997 
Derived from  TEA 
Successors  Corrected Block TEA 
Cipher detail  
Key sizes  128 bits 
Block sizes  64 bits 
Structure  Feistel network 
Rounds  variable; recommended 64 Feistel rounds (32 cycles) 
Best public cryptanalysis  
A relatedkey differential attack can break 26 out of 64 rounds of XTEA, requiring 2^{20.5} chosen plaintexts and a time complexity of 2^{115.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 64bit block Feistel network with a 128bit key and a suggested 64 rounds. Several differences from TEA are apparent, including a somewhat more complex keyschedule and a rearrangement of the shifts, XORs, and additions.
Presented along with XTEA was a variablewidth 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^{[update]}, the best attack reported on XTEA is a relatedkey differential attack on 26 out of 64 rounds of XTEA, requiring 2^{20.5} chosen plaintexts and a time complexity of 2^{115.15} (Ko et al., 2004).
The unusually small size of the XTEA algorithm would make it a viable option in situations where there are extreme constraints e.g. legacy hardware systems (perhaps embedded) where the amount of available RAM is minimal.
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; }
This code is not 64bit clean: it will operate incorrectly (and in 128bit blocks) on platforms where unsigned longs are 64 bits. If portability is a concern, these must be changed to a guaranteed 32bit type, such as uint32_t from stdint.h. In Java, use the data type 'int' and the operator >>> instead of >>.
The recommended value for the "num_rounds" parameter is 32, not 64, as each iteration of the loop does two Feistelnetwork rounds. To additionally improve speed, the loop can be unrolled by precomputing the values of sum+k[].
In the original paper, less brackets have been used. Due to the Coperator precedence order, the above code is identical to the original one using the fact that a + b ^ c + d == (a + b) ^ (c + d)).
[edit] See also
 RC4  A stream cipher that, just like XTEA, is designed to be very simple to implement.
 XXTEA  Block TEA's successor.
 TEA  Block TEA's precursor.
[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. SpringerVerlag.
 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: 4960, 2002. ISSN 03029743.
 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.
 MarkkuJuhani 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
 Tea extensions, Roger M. Needham and David J. Wheeler, 1997
 DataFlow Diagram
 A web page advocating TEA and XTEA and providing a variety of implementations
 Test vectors for TEA and XTEA
 A Cryptanalysis of the Tiny Encryption Algorithm
 A survey of TEA and XTEA and their cryptanalysis(DEAD)
 JavaScript implementation of XXTEA with Base64
 PHP implementation of XTEA
 Pascal/Delphi implementation of XTEA
 JavaScript and PHP implementation of XXTEA
 PHPlibrary for XXTEA: Crypt_XXTEA (from the PEARproject)
 Python implementation of XTEA
 Ruby implementation of XXTEA with Base64
 Annotated JavaScript implementation of Block TEA (xxtea)
 Linden Scripting Language (LSL) implementation of XTEA for Second Life scripting