**Matthew D. Russell**

**27th Feb 2004 - Draft v0.3**

The Tiny Encryption Algorithm (TEA) and related variants
(XTEA, Block TEA, XXTEA) are block ciphers notable for their
simplicity of description and implementation (typically a few lines of
code), and consequently enjoy a measure of popularity. This article
provides an overview of these ciphers together with known cryptanalytic results and
some garish illustrations. It concludes with some musings on the design goal of `tinyness'.

It was presented at the rump session of one of the early algorithms workshops, not as a refereed paper, but as an impromtu talk...As it turned out, it was included in the proceedings.

-- Bruce Schneier, `sci.crypt` posting [Schneier, 1998]

This ``early algorithms workshop'' was the Fast Software Encryption workshop in 1994. TEA's designers were David Wheeler and Roger Needham of the Cambridge Computer Laboratory.

TEA [Wheeler and Needham, 1994] operates on 64-bit message blocks with a
128-bit key, and is a Feistel network with a suggested 64 rounds
(though the authors speculate that 32 rounds might suffice). Two TEA
Feistel rounds are termed a *cycle*. One cycle of TEA is
illustrated in Figure 1. Figure 2 is a
reference encryption routine in the C programming language --
decryption is similar.

The algorithm uses multiples of a *magic constant*, ,
derived from the golden ratio, to ensure that the encryption in each
cycle is different; the precise value of is probably
unimportant, but for TEA it is defined as:

In response to the discovery of weaknesses in TEA (see Section 4.1), the designers suggested an updated version of TEA, XTEA (sometimes called `tean') [Needham and Wheeler, 1997]. See Figures 3 and 4.

The source-code description of XTEA has sometimes been misunderstood. In C, addition (

`y += (z<<4 ^ z>>5) + z ^ sum + k[sum&3]`

,
`y += ((z<<4 ^ z>>5) + z) ^ (sum + k[sum&3])`

.
`y += (z<<4 ^ z>>5) + (z ^ sum) + k[sum&3]`

,
`y += (((z<<4 ^ z>>5) + z) ^ sum) + k[sum&3]`

.
XTEA uses the same basic operations as TEA (XOR, addition modulo , shifts), but the ordering differs quite significantly. To prevent key-schedule attacks, the four subkeys are mixed in a less regular fashion, and at a slower rate.

When a cryptanalysis of Block TEA surfaced (see
Section 4.2) a new algorithm was described
named XXTEA [Wheeler and Needham, 1998]; see
Figures 9 and 10. XXTEA is
similar to Block TEA in structure, but makes use of both neighbours
when processing each word in the block. Instead of using the XTEA
round function, a more involved function, `MX`, is used that
takes two inputs.

Cryptanalysis

Equivalent Keys and Related-Key Attacks for TEA

TEA suffers from having equivalent keys [Kelsey et al., 1996]. Simultaneously flipping the most significant bits (MSBs) in and does not affect the encryption, as they cancel each other out. In detail,

Similarly, flipping the MSBs of and has no effect on the encryption. Therefore each TEA key has three other equivalent keys -- one with the MSBs of and flipped, one with the MSBs of and flipped, and one with the MSBs of , , and flipped -- and the effective key space is reduced to . Because of this, TEA is unsuitable for use in certain hashing modes (e.g. Davis-Meyer).

This weakness in TEA was put to good effect by hackers attempting to run Linux on Microsoft's Xbox gaming console. The boot process relied on TEA as a hash function (implemented on a ROM) to check whether the contents of the Flash memory had been tampered with:

According to Andy Green, a UK-based programmer who was part of the effort, the Flash memory is signed with a cryptographic hash - a method of summarising a large amount of data with a short random sequence that is very sensitive to any changes in the original.

However, there is a known weakness in the algorithm used to create the Xbox's hash, an algorithm called TEA. "In every group of 64 bits, it cannot detect a change when the 32nd and 64th bit both change together," explained Green.

The Xbox Linux group that Green works with, along with a group working for the mod chip company Xecuter, both managed to exploit this weakness to gain control of the machine. "It turned out that flipping the 32nd and 64th bit of the very first 64-bit block of the protected area caused the Xbox to begin executing from RAM (random-access memory)," Green said. It was then a simple matter of embedding a command in RAM that allowed the user to control the machine.

Several related-key attacks on TEA were published in [Kelsey et al., 1997]. The best requires chosen plaintexts encrypted under two related keys and computation time. It was these related-key weaknesses together with the equivalent keys problem that motivated the design of the TEA variants, XTEA and Block TEA.

Cryptanalysis of Block TEA and XXTEA

XXTEA was the proposed fix, yet Saarinen [1998] also detailed a distinguisher for XXTEA (termed `Block TEA 2' in the paper) which requires chosen plaintexts, and can be used to recover the key in time.

Some work has been done on experimentally discovering distinguishers
for reduced round versions of TEA. In [Hernández et al., 2001], TEA
is tested for the Strict Avalanche Criterion. In this way TEA with
five or fewer cycles^{1}can be distinguished from random with chosen plaintexts.

In a series of papers [Hernández et al., 2002,2003; Hernández et al., 2002] genetic algorithms are used to evolve distinguishers for increasing numbers of rounds of TEA. The idea is to identify a subset of the plaintext space () which maps to a partition of the ciphertext space () in an uneven way -- uneven in the sense of being detectable by a statistical test. The plaintext subset is defined by a bitmask specifying certain bits which must be fixed to zero, i.e. a set defined as

The ciphertext partition is defined by mapping a ciphertext to the 8 or 10 least significant bits of its left 32-bit half, e.g.

The bitmask is evolved by the genetic algorithm, evaluating the score over the ciphertext partition for some random set of plaintexts, and trying to maximise the weight of the mask.

In fact, the search is slightly more complex; the mask also contains a bitmask for the key input, specifying a key-subset in a similar way to the plaintext subset. The evolved distinguisher is then effective only over a weak-key class. These techniques seem sufficient to find distinguishers for up to four cycles (eight rounds) of TEA.

In the last couple of years (X)TEA has been subject to several differential attacks, to which, surprisingly, TEA emerges less vulnerable than XTEA. Moon et al. [2002] use impossible differentials to attack 14-round XTEA, requiring chosen plaintexts and the computation time of encryptions. The equivalent attack on TEA is on 11-rounds and needs chosen plaintexts and encryptions.

TEA and XTEA are analysed for differential and truncated differential weaknesses in [Hong et al., 2003b,a]. An ordinary differential attack can break 15 rounds of XTEA with chosen plaintexts. Truncated differentials of probability 1 are used in an attack on 17-round TEA ( chosen plaintexts and time complexity) and 23-round XTEA ( chosen plaintexts and time complexity).

The best attack to date on XTEA is a related-key differential attack on 27 rounds [Ko et al., 2004]. The attack requires chosen-plaintexts under a related key-pair and has a time complexity of 27-round XTEA encryptions.

Cipher | Type of Attack | Rounds | Plaintexts | Time | Reference |

TEA | Equivalent Keys | Any | 1 | [Kelsey et al., 1996] | |

TEA | Related-Key | 64 | [Kelsey et al., 1997] | ||

TEA | SAC Distinguisher | 10 | - | [Hernández et al., 2001] | |

TEA | Partitioning | 2-8 | - | - | [Hernández et al., 2003] |

TEA | Impossible Differential | 11 | [Moon et al., 2002] | ||

XTEA | Impossible Differential | 14 | [Moon et al., 2002] | ||

XTEA | Differential | 15 | [Hong et al., 2003b] | ||

XTEA | Truncated Differential | 23 | [Hong et al., 2003b] | ||

XTEA | Related-Key | 27 | [Ko et al., 2004] | ||

Block TEA | Differential | - | - | [Saarinen, 1998] | |

XXTEA | Distinguisher | 6 | - | [Saarinen, 1998] |

TEA and its variants are unencumbered by patents and the reference
implementation has been released into the public
domain^{2}.

Mirza [1998] gives a detailed tutorial on block ciphers and their cryptanalysis. As the running example, an extremely simplified version of TEA is analysed -- STEA. Comments on the real TEA are interspersed.

Andem [2003] provides a survey of the TEA algorithm family
and some cryptanalysis. It reports on the results of a batch of
statistical tests, concluding that TEA with less than six rounds is
weak^{3}.

Some test vectors for TEA and XTEA can be found at [Wheeler, 2000]. Shepherd [2004] maintains a website containing various implementations and resources for TEA algorithms.

To my mind, the redeeming virtue of TEA and XTEA is that they are easy
to reproduce from memory in their entirety. They were, in fact,
designed explicitly with simplicity of description and implementation,
and hence memorability, as a design goal. Let's term this property
*tinyness*. The authors wrote,

We present a simple algorithm which can be translated into a number of different languages and assembly languages very easily. It is short enough to be programmed from memory or a copy. It is hoped it is safe because of the number of cycles in the encoding and the length of the key.

Even though the most important criteria used for evaluating ciphers are (rightly) evidence of security and efficiency of implementation, I think there is a certain elegance to tiny encryption algorithms (that's tiny with a small `t'), so, out of contrariness, for the rest of this section I'll make it an axiom that tinyness is more important than efficiency (but not security). TEA illustrates a design strategy: Many rounds of a simple round function can produce a secure cipher. To quote Bruce Schneier again,

``I have never been a TEA fan, although 64 rounds can cure a lot of sins.''

-- Post to the Coderpunks mailing list,
`http://www.privacy.nb.ca/cryptography/archives/coderpunks/new/1998-06/0298.html`

Is this a good design strategy? To get a secure design this way you
might have to be overly conservative with the number of rounds, and
that is unlikely to result in an efficient cipher. However, if
tinyness is a the dominant requirement it seems a reasonable strategy.

Comparison | TEA | XTEA | RC5 |

Memorisation of main network | Easy | Easy | Very Easy |

Memorisation of key schedule | Very Easy | Easy | Harder |

Qty of published cryptanalysis | Some | Some | Heaps |

Broken (even `certificationally')? | Yes | No | No |

- Q1.
- Is there a better way of repairing the TEA key-schedule problems than the XTEA redesign?
- Q2.
- Is there a secure replacement key-schedule for RC5 that would make it easier to remember, even if it meant tacking on extra rounds?
- Q3.
- How secure are various reduced variants of (X)TEA, e.g. dropping the left shifts? (This would slow down right-to-left diffusion quite a bit). How many additional rounds are needed to fix the problems? Such analysis has been published for RC5 variants, and gives insight into its security.
- Q4.
- Are there tiny ciphers with provable security against differential and linear cryptanalysis?
- Q5.
- Ultimately, how legitimate is a requirement of tinyness for real-world applications, and not just for aesthetics? Is there a niche? (e.g. [Yang, 2001].)

- Vikram Reddy Andem.
- A cryptanalysis of the tiny encryption algorithm.

Master's thesis, Dept. of Computer Science, Graduate School of the University of Alabama, 2003.

URL`http://www.bama.ua.edu/ reddy001/`.

- A. Biryukov and D. Wagner.
- Slide attacks.

In Lars Knudsen, editor,*Fast software encryption: 6th International Workshop, FSE'99, Rome, Italy, March 24-26, 1999: proceedings*, volume 1636 of*Lecture Notes in Computer Science*, pages 245-259, Berlin, Germany / Heidelberg, Germany / London, UK / etc., 1999. Springer-Verlag.

ISBN 3-540-66226-X (softcover).

- Roger Fleming.
- An attack on a weakened version of TEA.

`sci.crypt`posting, October 1996.

URL`http://groups.google.com/groups?selm=roger_sf-2210961222000001%40mg4-50.its.utas.edu.au`.

- J. C. Hernández, J. M. Sierra, P. Isasi, and A. Ribagorda.
- Genetic cryptoanalysis of two rounds TEA.

*Lecture Notes in Computer Science*, 2331: 1024-1031, 2002.

ISSN 0302-9743.

- Julio César Hernández, Pedro Isasi, and Arturo Ribagorda.
- An aplication of genetic algorithms to the cryptoanalysis of one
round tea.

In*Proceedings of the 2002 Symposium on Artificial Intelligence and its Application*, 2002.

- Julio César Hernández, José María Sierra, Pedro Isasi, and Arturo Ribargorda.
- Finding efficient distinguishers for cryptographic mappings, with an
application to the block cipher TEA.

In*Proceedings of the 2003 Congress on Evolutionary Computation*, 2003.

- Julio César Hernández, José María Sierra, Arturo Ribagorda, Benjamín Ramos, and J. C. Mex-Perera.
- Distinguishing TEA from a random permutation: Reduced round
versions of TEA do not have the SAC or do not generate random numbers.

In*Proceedings of the IMA Int. Conf. on Cryptography and Coding 2001*, pages 374-377, 2001.

- Deukjo Hong, Youngdai Ko, Donghoon Chang, Wonil Lee, and Jongin Lim.
- Differential cryptanalysis of XTEA.

Technical Report TR03_13, Center for the Information Security and Technologies (CIST), Seoul, Korea, 2003a.

- 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.

- John Kelsey, Bruce Schneier, and David Wagner.
- Key-schedule cryptanalysis of IDEA, G-DES, GOST, SAFER, and
Triple-DES.

*Lecture Notes in Computer Science*, 1109: 237-251, 1996.

ISSN 0302-9743.

- John Kelsey, Bruce Schneier, and David Wagner.
- Related-key cryptanalysis of -WAY, Biham-DES, CAST, DES-X
NewDES, RC2, and TEA.

*Lecture Notes in Computer Science*, 1334: 233-246, 1997.

ISSN 0302-9743.

- 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, Berlin, Germany / Heidelberg, Germany / London, UK / etc., 2004. Springer-Verlag.

- Fauzan Mirza.
- Block ciphers and cryptanalysis.

Technical report, Department of Mathematics, Royal Holloway University of London, 1998.

- 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.

- Ronald L. Rivest.
- The RC5 encryption algorithm.

In Bart Preneel, editor,*Fast software encryption: second international workshop, Leuven, Belgium, December 14-16, 1994: proceedings*, volume 1008 of*Lecture Notes in Computer Science*, pages 86-96, Berlin, Germany / Heidelberg, Germany / London, UK / etc., 1994. Springer-Verlag.

ISBN 3-540-60590-8 (softcover).

- Markku-Juhani Saarinen.
- Cryptanalysis of block tea.

Unpublished manuscript, October 1998.

URL`http://www.cc.jyu.fi/ mjos/block_tea.ps`.

- Bruce Schneier.
- Re: Status of TEA?

`sci.crypt`posting, September 1998.

URL`http://groups.google.com/groups?selm=35f89ac4.1413616%40news.visi.com`.

- Simon Shepherd.
- TEA web page, 2004.

URL`http://www.simonshepherd.supanet.com/tea.htm`.

- David J. Wheeler.
- TEA test vectors, 2000.

URL`http://www.cix.co.uk/ klockstone/teavect.htm`.

- David J. Wheeler and Roger M. Needham.
- TEA, a tiny encryption algorithm.

In Bart Preneel, editor,*Fast Software Encryption: Second International Workshop*, volume 1008 of*Lecture Notes in Computer Science*, pages 363-366, Leuven, Belgium, 14-16 December 1994. Springer-Verlag.

- David J. Wheeler and Roger M. Needham.
- Correction to xtea.

Technical report, Computer Laboratory, University of Cambridge, October 1998.

- Albert Yang.
- Re: Memorizable block ciphers.

`sci.crypt`posting, October 2001.

URL`http://groups.google.com/groups?selm=49f67bff12280f4631f3362c367ac7ea%40spamfreenews.com`.

- ... cycles
^{1} - The authors of the papers in this section appear to use the term `round' to refer to a TEA cycle, that is, two Feistel rounds.
- ...
domain
^{2} - This is by unanimous assertion from dozens of places on the Web and Usenet archives, though I can't find a statement from the authors to this effect.
- ...
weak
^{3} - It is also claimed that there are equivalent keys for Block TEA (XXTEA), but this unfortunately appears to be an artifact of the Javascript implementation used; specifically, the mechanism for entering keys seems to be flawed.

Matthew Russell 2004-02-27