# XTEA

From Wikipedia, the free encyclopedia

| This article includes a list of references, but its sources remain unclear because it has insufficient inline citations. Please help to improve this article by introducing more precise citations. (September 2015)

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 cipher
Rounds | variable; recommended 64 Feistel rounds (32 cycles)
Best public cryptanalysis
A related-key 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 64-bit block Feistel cipher 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.

## Implementations[edit]

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:

- 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-cipher rounds. To additionally improve speed, the loop can be unrolled by pre-computing the values of sum+key[].

## Cryptanalysis[edit]

In 2004, Ko et al. presented a related-key differential attack on 27 out of 64 rounds of XTEA, requiring 220.5 chosen plaintexts and a time complexity of 2115.15 (Ko et al., 2004).

In 2009, Lu presented a related-key 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 264.98 bytes of data and 2126.44 operations, and 263.83 bytes of data and 2104.33 operations respectively.[2]

## Block TEA[edit]

Presented along with XTEA was a variable-width 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.

## See also[edit]

- 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[edit]

1. Jump up ^ Roger M. Needham, David J. Wheeler (October 1997). Tea extensions (PDF). Computer Laboratory, University of Cambridge (Technical report).
2. Jump up ^ Lu, Jiqiang (2008-07-02). "Related-key rectangle attack on 36 rounds of the XTEA block cipher". International Journal of Information Security 8 (1): 1–11. doi:10.1007/s10207-008-0059-9. ISSN 1615-5262.

### Further reading[edit]

- Gautham Sekar, Nicky Mouha, Vesselin Velichkov, and Bart Preneel. "Meet-in-the-Middle Attacks on Reduced-Round XTEA." In Proceedings of CT-RSA 2011, Lecture Notes in Computer Science 6558: 250-267. Springer-Verlag.
- 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.
- 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.
- 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[edit]

- 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 C implementation of XTEA
- PHP implementation of XTEA
- Pascal/Delphi implementation of XTEA
- Java implementation of XTEA (32 rounds)
- JavaScript implementation of XTEA (32 rounds)
- Python implementation of XTEA
- Linden Scripting Language (LSL) implementation of XTEA for Second Life scripting
- Verilog implementation of XTEA
- Smalltalk implementation of XTEA

Block ciphers (security summary)
Common algorithms | AES Blowfish DES (Internal Mechanics, Triple DES) Serpent Twofish
Less common algorithms | Camellia CAST-128 IDEA RC2 RC5 SEED ARIA Skipjack TEA XTEA
Other algorithms | 3-Way Akelarre Anubis BaseKing BassOmatic BATON BEAR and LION CAST-256 Chiasmus CIKS-1 CIPHERUNICORN-A CIPHERUNICORN-E CLEFIA CMEA Cobra COCONUT98 Crab Cryptomeria/C2 CRYPTON CS-Cipher DEAL DES-X DFC E2 FEAL FEA-M FROG G-DES GOST Grand Cru Hasty Pudding cipher Hierocrypt ICE IDEA NXT Intel Cascade Cipher Iraqi KASUMI KeeLoq KHAZAD Khufu and Khafre KN-Cipher Ladder-DES Libelle LOKI (97, 89/91) Lucifer M6 M8 MacGuffin Madryga MAGENTA MARS Mercy MESH MISTY1 MMB MULTI2 MultiSwap New Data Seal NewDES Nimbus NOEKEON NUSH PRESENT Q RC6 REDOC Red Pike S-1 SAFER SAVILLE SC2000 SHACAL SHARK Simon SMS4 Speck Spectr-H64 Square SXAL/MBAL Threefish Treyfer UES Xenon xmx XXTEA Zodiac
Design | Feistel network Key schedule Lai-Massey scheme Product cipher S-box P-box SPN Avalanche effect Block size Key size Key whitening (Whitening transformation)
Attack (cryptanalysis) | Brute-force (EFF DES cracker) MITM (Biclique attack, 3-subset MITM attack) Linear (Piling-up lemma) Differential (Impossible Truncated Higher-order) Differential-linear Distinguishing (Known-key) Integral/Square Boomerang Mod n Related-key Slide Rotational Timing XSL Interpolation Partitioning Davies' Rebound Weak key Tau Chi-square Time/memory/data tradeoff
Standardization | AES process CRYPTREC NESSIE
Utilization | Initialization vector Mode of operation Padding
[show] Cryptography
History of cryptography Cryptanalysis Outline of cryptography
Symmetric-key algorithm Block cipher Stream cipher Public-key cryptography Cryptographic hash function Message authentication code Random numbers Steganography
Category · Portal · WikiProject

Retrieved from "https://en.wikipedia.org/w/index.php?title=XTEA&oldid=703563426"
Categories:

- Block ciphers
- Feistel ciphers
- Free ciphers

Hidden categories:

- Articles lacking in-text citations from September 2015
- All articles lacking in-text citations
- All Wikipedia articles needing clarification
- Wikipedia articles needing clarification from May 2015
- Articles with example C code