This page uses content from Wikipedia and is licensed under CC BYSA.
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 cipher 
Rounds  variable; recommended 64 Feistel rounds (32 cycles) 
Best public cryptanalysis  
A relatedkey rectangle attack on 36 rounds of XTEA (Lu, 2009)^{[vague]} 
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.^{[1]}
Like TEA, XTEA is a 64bit block Feistel cipher 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.
This standard C source code, adapted from the reference code released into the public domain by David Wheeler and Roger Needham, encrypts and decrypts using XTEA:
#include <stdint.h>
/* take 64 bits of data in v[0] and v[1] and 128 bits of key[0]  key[3] */
void encipher(unsigned int num_rounds, uint32_t v[2], uint32_t const key[4]) {
unsigned int i;
uint32_t v0=v[0], v1=v[1], sum=0, delta=0x9E3779B9;
for (i=0; i < num_rounds; i++) {
v0 += (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + key[sum & 3]);
sum += delta;
v1 += (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + key[(sum>>11) & 3]);
}
v[0]=v0; v[1]=v1;
}
void decipher(unsigned int num_rounds, uint32_t v[2], uint32_t const key[4]) {
unsigned int i;
uint32_t v0=v[0], v1=v[1], delta=0x9E3779B9, sum=delta*num_rounds;
for (i=0; i < num_rounds; i++) {
v1 = (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + key[(sum>>11) & 3]);
sum = delta;
v0 = (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + key[sum & 3]);
}
v[0]=v0; v[1]=v1;
}
The changes from the reference source code are minor:
unsigned long
type rather than the 64bit clean uint32_t
.const
types.v1 +=
(v0<<4 ^ v0>>5) + v0 ^ sum + k[sum>>11 & 3]
;
The recommended value for the "num_rounds" parameter is 32, not 64, as each iteration of the loop does two Feistelcipher rounds. To additionally improve speed, the loop can be unrolled by precomputing the values of sum+key[].
In 2004, Ko et al. presented a relatedkey differential attack on 27 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 2009, Lu presented a relatedkey rectangle attack on 36 rounds of XTEA, breaking more rounds than any previously published cryptanalytic results for XTEA. The paper presents two attacks, one without and with a weak key assumption, which corresponds to 2^{64.98} bytes of data and 2^{126.44} operations, and 2^{63.83} bytes of data and 2^{104.33} operations respectively.^{[2]}
Presented along with XTEA was a variablewidth block cipher termed Block TEA, which uses the XTEA round function, but Block TEA 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.