Matthew D. Russell
27th Feb 2004 - Draft v0.3
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.
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.
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.
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.
XXTEA was the proposed fix, yet Saarinen  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 cycles1can 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.  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]|
TEA and its variants are unencumbered by patents and the reference implementation has been released into the public domain2.
Mirza  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  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 weak3.
Some test vectors for TEA and XTEA can be found at [Wheeler, 2000]. Shepherd  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.''
|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|