Tinyness: An Overview of TEA and Related Ciphers

Matthew D. Russell

27th Feb 2004 - Draft v0.3

Abstract:

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

TEA

 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.

Figure 1: Cycle $i$ of TEA (two Feistel rounds).
\scalebox{0.15}{\includegraphics{TEA-pic}}

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.

Figure 2: Reference C code for TEA encryption.
\begin{figure}\begin{center}
\begin{alltt}
\relax{} \fbox{\parbox{13cm}{
\\ void...
...\}
\\ v[0]=y ; v[1]=z ; \}
\\ }}
\\ \relax \end{alltt}\end{center}
\end{figure}

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

\begin{displaymath}\delta = \lfloor(\sqrt{5}-1)2^{31}\rfloor.\end{displaymath}

XTEA

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.

Figure 3: Cycle $i$ of XTEA (two Feistel rounds).
\scalebox{0.15}{\includegraphics{XTEA}}
Figure 4: Reference C code for XTEA.
\begin{figure}\begin{center}
\begin{alltt}
\relax{} \fbox{\parbox{13cm}{
\\ /* T...
... v[1]=z ;
\\ return ;
\\ \}
\\ }}
\\ \relax \end{alltt}\end{center} \end{figure}
The source-code description of XTEA has sometimes been misunderstood. In C, addition (+) takes precedence over XOR (^). This means that the XTEA round function,
y += (z<<4 ^ z>>5) + z ^ sum + k[sum&3],
is equivalently bracketed
y += ((z<<4 ^ z>>5) + z) ^ (sum + k[sum&3]).
However, this has sometimes been misinterpreted and implemented incorrectly as
y += (z<<4 ^ z>>5) + (z ^ sum) + k[sum&3],
or as
y += (((z<<4 ^ z>>5) + z) ^ sum) + k[sum&3].

XTEA uses the same basic operations as TEA (XOR, addition modulo $2^{32}$, 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.

Block TEA and XXTEA

In the same report describing XTEA [Needham and Wheeler, 1997] another variant was introduced called Block TEA, which operates on variable-length blocks that are some arbitrary multiple of 32-bits in size -- see Figures 5, 6 and 7. This algorithm sequentially applies the XTEA round function to each word in the block and combines it additively with its neighbour. This is repeated for several rounds depending on the block size, but there are at least six. An advantage of this approach is that it eliminates the need for a mode of operation (CBC, OFB, CFB etc.); the cipher can be directly applied to a message. It is also likely to be more efficient than XTEA on longer messages.

Figure 5: Reference C code for Block TEA encryption.
\begin{figure}\begin{center}
\begin{alltt}
\relax{} \fbox{\parbox{13cm}{
\\ long...
...n 1 ; \} /* Signal n=0 */
\\ }}
\\ \relax \end{alltt}\end{center}\end{figure}

Figure 6: The structure of Block TEA.
\scalebox{0.12}{\includegraphics{BlockTEA-overview}}

Figure 7: Block TEA $f$ function, essentially the same as the XTEA round function.
\scalebox{0.25}{\includegraphics{BlockTEA-detail}}

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.

Figure 8: Reference C code for XXTEA encryption.
\begin{figure}\begin{center}
\begin{alltt}
\relax{} \fbox{\parbox{13cm}{
\\
\\ ...
... \} /* Signal n=0,1,-1 */
\\ }}
\\ \relax \end{alltt}\end{center}\end{figure}

Figure 9: The structure of XXTEA.
\scalebox{0.12}{\includegraphics{XXTEA-overview3}}
Figure 10: XXTEA MX function on two inputs.
\scalebox{0.18}{\includegraphics{XXTEA-detail}}


Cryptanalysis


Equivalent Keys and Related-Key Attacks for TEA

The first attacks on TEA targeted its extremely simple key-schedule. TEA divides up the 128-bit key into four words, $K_0$, $K_1$, $K_2$ and $K_3$, and uses the first two in odd-numbered rounds and the last two in even-numbered rounds. It is not as simple as it could be, though; in each cycle a different multiple of $\delta$ is used, making the transformation different. Without this, the cipher becomes vulnerable to slide attacks [Biryukov and Wagner, 1999] as noted by Fleming [1996].

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

Lemma 1   Let $a$ be an $n$-bit word. Let $\boxplus$ denote addition modulo $2^n$ and $\oplus$ exclusive or (XOR). Then a bit flip of the most significant bit of $a$ is equivalent to a modular addition:

\begin{displaymath}a \oplus 2^{n-1} \equiv a \boxplus 2^{n-1}.\end{displaymath}

Lemma 2   Consider two $n$-bit words $a$ and $b$. Then the following identity holds:

\begin{displaymath}a \boxplus \left(b \oplus 2^{n-1}\right) \equiv a \boxplus \l...
...oxplus 2^{n-1} \equiv \left(a \boxplus b\right) \oplus 2^{n-1}.\end{displaymath}

Proposition 1   Let $\mbox{TEA}_i(z, K_0, K_1)$ denote the $i$th round TEA Feistel function on a 32-bit word $z$ with subkeys $K_0$ and $K_1$. Then,

\begin{eqnarray*}
\mbox{TEA}_i(z, K_0 \oplus 2^{31}, K_1 \oplus 2^{31}) & = & \l...
...oxplus \delta_i \right] \\
& = & \mbox{TEA}_i(z, K_0, K_1) \\
\end{eqnarray*}

Similarly, flipping the MSBs of $K_2$ and $K_3$ has no effect on the encryption. Therefore each TEA key has three other equivalent keys -- one with the MSBs of $K_0$ and $K_1$ flipped, one with the MSBs of $K_2$ and $K_3$ flipped, and one with the MSBs of $K_0$, $K_1$, $K_2$ and $K_3$ flipped -- and the effective key space is reduced to $2^{126}$. 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.
-- http://news.zdnet.co.uk/software/developer/0,39020387,2123851,00.htm

Several related-key attacks on TEA were published in [Kelsey et al., 1997]. The best requires $2^{23}$ chosen plaintexts encrypted under two related keys and $2^{32}$ 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

There is an attack on Block TEA which makes use of weaknesses in the decryption algorithm [Saarinen, 1998]; differences propagate quickly in the encryption direction, but more slowly in the reverse direction. The entire key can be recovered with $2^{34}$ chosen-ciphertext queries.

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

Finding Distinguishers for TEA

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 $2^{25}$ 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 ($\mathcal{P}$) which maps to a partition of the ciphertext space ($\mathcal{C}$) in an uneven way -- uneven in the sense of being detectable by a statistical $\chi^2$ test. The plaintext subset is defined by a bitmask $M$ specifying certain bits which must be fixed to zero, i.e. a set $P_M \subseteq
\mathcal{P}$ defined as


\begin{displaymath}P_M = \{ p \in \mathcal{P} \;\vert\; (p\mbox{ AND }M) = p \}. \end{displaymath}

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.


\begin{displaymath}\pi(c) = (c\mbox{ AND }\mbox{\texttt{0x000000FF00000000}}).\end{displaymath}

The bitmask $M$ is evolved by the genetic algorithm, evaluating the $\chi^2$ 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.

Differential Attacks on TEA and XTEA

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 $2^{62.5}$ chosen plaintexts and the computation time of $2^{85}$ encryptions. The equivalent attack on TEA is on 11-rounds and needs $2^{52.5}$ chosen plaintexts and $2^{84}$ 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 $2^{59}$ chosen plaintexts. Truncated differentials of probability 1 are used in an attack on 17-round TEA ($1920$ chosen plaintexts and $2^{123.37}$ time complexity) and 23-round XTEA ($2^{20.55}$ chosen plaintexts and $2^{120.65}$ 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 $2^{20.5}$ chosen-plaintexts under a related key-pair and has a time complexity of $2^{115.15}$ 27-round XTEA encryptions.

Summary of Attacks

Cipher Type of Attack Rounds Plaintexts Time Reference
TEA Equivalent Keys Any 1 $2^{126}$ [Kelsey et al., 1996]
TEA Related-Key 64 $2^{23}$ $2^{32}$ [Kelsey et al., 1997]
TEA SAC Distinguisher 10 $2^{25}$ - [Hernández et al., 2001]
TEA Partitioning 2-8 - - [Hernández et al., 2003]
TEA Impossible Differential 11 $2^{52.5}$ $2^{84}$ [Moon et al., 2002]
XTEA Impossible Differential 14 $2^{62.5}$ $2^{85}$ [Moon et al., 2002]
XTEA Differential 15 $2^{59}$ $2^{120}$ [Hong et al., 2003b]
XTEA Truncated Differential 23 $2^{20.55}$ $2^{120.65}$ [Hong et al., 2003b]
XTEA Related-Key 27 $2^{20.5}$ $2^{115.15}$ [Ko et al., 2004]
Block TEA Differential - $2^{34}$ - [Saarinen, 1998]
XXTEA Distinguisher 6 $2^{80}$ - [Saarinen, 1998]

Miscellaneous

TEA and its variants are unencumbered by patents and the reference implementation has been released into the public domain2.

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

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.

Discussion, Opinion and Questions

Tinyness

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.
-- [Wheeler and Needham, 1994]

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 with RC5

The block cipher RC5 [Rivest, 1994] was published at the same workshop as TEA and can also described very simply, or at least the round function can; the key-schedule is more complex. Comparing TEA, XTEA and RC5:

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

Questions

Here are some musings (if I thought other people cared I'd call them `open problems'...):

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

Bibliography

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



Footnotes

... cycles1
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.
... domain2
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.
... weak3
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