XTEA

XTEA

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 related-key differential attack can break 27 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 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).

Implementations

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 in k[0] - k[3] */

void encipher(unsigned int num_rounds, uint32_t v[2], uint32_t const k[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 + 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, uint32_t v[2], uint32_t const k[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 + k[(sum>>11) & 3]);
        sum -= delta;
        v0 -= (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + k[sum & 3]);
    }
    v[0]=v0; v[1]=v1;
}

The changes from the reference source code are minor:

• The reference source code used the unsigned long type rather than the 64-bit clean uint32_t.
• The reference source code did not use const types.
• The reference source code omitted redundant parentheses, using C precedence to write the round function as e.g. 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 Feistel-network rounds. To additionally improve speed, the loop can be unrolled by pre-computing the values of sum+k[].

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.

References

• Youngdai Ko, Seokhie Hong, Wonil Lee, Sangjin Lee, and Jongin Lim. "Related key differential attacks on 27 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.
• 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.
• Lu, Jiqiang (January 2009), "Related-key rectangle attack on 36 rounds of the XTEA block cipher" (PDF), International Journal of Information Security, 8 (1): 1–11, doi:10.1007/s10207-008-0059-9, ISSN 1615-5262

External links

• 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
• PHP implementation of XTEA
• Pascal/Delphi implementation of XTEA
• Java implementation of XTEA (32 rounds)
• Python implementation of XTEA
• Linden Scripting Language (LSL) implementation of XTEA for Second Life scripting
• Verilog implementation of XTEA
• Simple implementation of XTEA in Python for academic purposes