The TEA and XTEA Algorithms

The TEA and XTEA Algorithms

Introduction

The Tiny Encryption Algorithm, or TEA, is one of the simplest block ciphers ever published. The whole thing fits in a handful of lines of code. It uses no S-boxes and no lookup tables, no complicated key schedule, and no operations beyond addition, XOR, and shifts. A student can read the entire algorithm in a minute and still be reading a real, working cipher.

That simplicity comes with a price. TEA has a known flaw in how it uses its key, and the flaw once let hackers break the security of a major game console. Its successor, XTEA, fixed the problem with only a small change. Looking at both side by side shows exactly how much a tiny design decision matters.

Table of Contents

• History
• How TEA Works
• The Magic Constant
• How XTEA Works
• TEA’s Equivalent Keys
• Byte Order
• A Worked Example
• Python Implementation
• Limitations
• Security Status
• FAQ
• References

History

David Wheeler and Roger Needham of the Cambridge Computer Laboratory designed TEA. They presented it at the Fast Software Encryption workshop in Leuven in 1994, and it appeared in the proceedings after that. It was designed to be simple to implement and to need very little code.

Needham and Wheeler published a repair in 1997 in an unpublished technical report. That cipher is XTEA, for “extended TEA.” It changes the mixing steps and the way the key is selected. A further variant, XXTEA, appeared in 1998, and it works on blocks of variable size. XTEA is not subject to any patents.

How TEA Works

TEA encrypts a 64-bit block, split into two 32-bit words v0 and v1. It uses a 128-bit key, split into four words k0 to k3. The cipher is a Feistel network with 64 rounds, which are normally written as 32 cycles of two rounds each. Papers on attacks usually count rounds, not cycles. A running value called sum grows by a constant in every cycle.

sum = 0
repeat 32 times:
    sum = sum + delta
    v0 = v0 + (((v1 << 4) + k0) ^ (v1 + sum) ^ ((v1 >> 5) + k1))
    v1 = v1 + (((v0 << 4) + k2) ^ (v0 + sum) ^ ((v0 >> 5) + k3))

All additions are modulo 2³². Each line updates one half using the other half, shifted left by 4 and right by 5, mixed with two key words and the sum. Decryption simply runs the rounds backward, subtracting where encryption added, starting with sum at its final value.

Interactive Visualizer

The visualizer above runs this exact algorithm. Choose XTEA or TEA and encrypt a block. Each row of the log shows v0, v1, and sum after one cycle. Because TEA and XTEA use the same key and block by default, you can switch between them and watch their ciphertexts differ.

The Magic Constant

The constant delta is 0x9E3779B9, which is 2,654,435,769 in decimal. It is the integer part of 2³² divided by the golden ratio, so it is a “nothing-up-my-sleeve” number. The same golden-ratio constant appears in the key schedules of RC5 and Serpent.

Adding delta to sum once per cycle means that every cycle uses a different value. Without that, all rounds would be identical, and a cipher whose rounds are all the same is easier to attack through symmetry between them. The varying sum breaks the symmetry cheaply.

How XTEA Works

XTEA keeps the structure but changes the round function and, importantly, the way key words are chosen:

sum = 0
repeat 32 times:
    v0 = v0 + ((((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + key[sum & 3]))
    sum = sum + delta
    v1 = v1 + ((((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + key[(sum >> 11) & 3]))

There are two changes. First, the shifts, XORs, and additions are rearranged so that the shifted pieces are combined with XOR and then added to the word itself. Second, the key words are no longer used in a fixed pattern. A different key word is picked each round, depending on bits of sum. In the first half-round the choice is sum & 3, and in the second it is (sum >> 11) & 3. Because sum changes every cycle, the key words come up in a varying order.

The cipher is still just shifts, adds, and XORs. Its code is slightly longer than TEA’s, and it is still tiny.

TEA’s Equivalent Keys

TEA’s key handling has a flaw that XTEA removed. Look at the two terms that contain key words in the same line, ((v1 << 4) + k0) and ((v1 >> 5) + k1). If you flip the top bit of both k0 and k1, each term changes only in its top bit, because any carry out of a 32-bit addition is discarded. The two changes then cancel in the XOR. The same trick works on k2 and k3.

The result is that every TEA key is equivalent to three other keys. They are different 128-bit values that encrypt identically. That means the effective key size is only 126 bits, not 128. You can check it with the code below. Flipping the top bits of k0 and k1 turns the key 000102030405060708090a0b0c0d0e0f into 800102038405060708090a0b0c0d0e0f, and TEA’s output does not change. I checked this on 300 random keys and blocks, flipping either the first pair or the second pair of key words, and TEA’s output never changed. XTEA’s output changed every time I flipped the top bits of k0 and k1.

A related-key attack on TEA needs 2²³ chosen plaintexts and about 2³² operations. The equivalent keys also caused a real problem. The weakness led to a method for hacking Microsoft’s Xbox game console, where TEA had been used as a hash function. Only the version 1.1 boot ROM of the console used TEA, while version 1.0 used RC4. A hash built on a cipher must not have two keys that give identical results, and TEA does.

Byte Order

TEA and XTEA are defined on 32-bit words, and the original papers do not say how bytes become words. Libraries do not all agree. Some, such as libtomcrypt, read the bytes as big-endian words, and the Linux kernel reads them as little-endian words. The same key bytes and plaintext bytes therefore give different ciphertext bytes in the two worlds. Take the key bytes 000102030405060708090a0b0c0d0e0f and the plaintext bytes 4142434445464748. XTEA gives 497df3d072612cb5 when the bytes are read as big-endian words, and cae7697e006ee921 when they are read as little-endian words.

The code here reads bytes as big-endian words. I verified it against vectors that are given as word values, which avoids the question entirely, and against byte-level vectors from libraries of each kind.

A Worked Example

Take the key 000102030405060708090a0b0c0d0e0f and the plaintext 4142434445464748, which is the ASCII text ABCDEFGH. The key words are k0 = 00010203, k1 = 04050607, k2 = 08090a0b, and k3 = 0c0d0e0f. The plaintext words are v0 = 41424344 and v1 = 45464748.

TEA, first cycle. Add delta to the sum, which makes sum = 9e3779b9. For the first line, (v1 << 4) + k0 = 54657683, v1 + sum = e37dc101, and (v1 >> 5) + k1 = 062f3841. XORing those three gives b1378fc3, and adding it to v0 gives v0 = f279d307. The second line produces v1 = f1fdf164. After all 32 cycles, TEA gives:

df25fc4279b8f929

XTEA, first cycle. With sum = 0 the left side is (((v1 << 4) ^ (v1 >> 5)) + v1) = 9b948e02 and the key side is sum + key[0] = 00010203. XORing the two sides and adding the result to v0 gives v0 = dcd7cf45. Then sum becomes 9e3779b9, and (sum >> 11) & 3 selects key word number 3, which gives v1 = 477ce5ef. After 32 cycles, XTEA gives:

497df3d072612cb5

This XTEA result appears in the libtomcrypt test suite. Known vectors with an all-zero key and block give 41ea3a0a94baa940 for TEA and dee9d4d8f7131ed9 for XTEA.

Python Implementation

This is a complete TEA and XTEA: both encryptions and both decryptions. Each function takes a cycles argument, which defaults to the standard 32, so you can also experiment with fewer rounds.

# tea.py
#
# TEA and XTEA, the Tiny Encryption Algorithms of David Wheeler and Roger
# Needham. A 64-bit block (two 32-bit words), a 128-bit key (four words), and
# 32 cycles of two Feistel rounds. Each round needs only shifts, additions
# and XORs. XTEA is the 1997 fix that mixes the key in a better way.
# Words are read big-endian here; some libraries read them little-endian.

MASK = 0xFFFFFFFF
DELTA = 0x9E3779B9  # 2^32 divided by the golden ratio
CYCLES = 32


def split(key, block):
    k = [int.from_bytes(key[4 * i:4 * i + 4], "big") for i in range(4)]
    v0, v1 = (int.from_bytes(block[4 * i:4 * i + 4], "big") for i in range(2))
    return k, v0, v1


def join(v0, v1):
    return v0.to_bytes(4, "big") + v1.to_bytes(4, "big")


def tea_encrypt_block(key, block, cycles=CYCLES):
    k, v0, v1 = split(key, block)
    total = 0
    for _ in range(cycles):
        total = (total + DELTA) & MASK
        v0 = (v0 + (((v1 << 4) + k[0]) ^ (v1 + total) ^ ((v1 >> 5) + k[1]))) & MASK
        v1 = (v1 + (((v0 << 4) + k[2]) ^ (v0 + total) ^ ((v0 >> 5) + k[3]))) & MASK
    return join(v0, v1)


def tea_decrypt_block(key, block, cycles=CYCLES):
    k, v0, v1 = split(key, block)
    total = (DELTA * cycles) & MASK
    for _ in range(cycles):
        v1 = (v1 - (((v0 << 4) + k[2]) ^ (v0 + total) ^ ((v0 >> 5) + k[3]))) & MASK
        v0 = (v0 - (((v1 << 4) + k[0]) ^ (v1 + total) ^ ((v1 >> 5) + k[1]))) & MASK
        total = (total - DELTA) & MASK
    return join(v0, v1)


def xtea_encrypt_block(key, block, cycles=CYCLES):
    k, v0, v1 = split(key, block)
    total = 0
    for _ in range(cycles):
        v0 = (v0 + ((((v1 << 4) ^ (v1 >> 5)) + v1) ^ (total + k[total & 3]))) & MASK
        total = (total + DELTA) & MASK
        v1 = (v1 + ((((v0 << 4) ^ (v0 >> 5)) + v0) ^ (total + k[(total >> 11) & 3]))) & MASK
    return join(v0, v1)


def xtea_decrypt_block(key, block, cycles=CYCLES):
    k, v0, v1 = split(key, block)
    total = (DELTA * cycles) & MASK
    for _ in range(cycles):
        v1 = (v1 - ((((v0 << 4) ^ (v0 >> 5)) + v0) ^ (total + k[(total >> 11) & 3]))) & MASK
        total = (total - DELTA) & MASK
        v0 = (v0 - ((((v1 << 4) ^ (v1 >> 5)) + v1) ^ (total + k[total & 3]))) & MASK
    return join(v0, v1)


if __name__ == "__main__":
    key = bytes.fromhex("000102030405060708090a0b0c0d0e0f")
    plaintext = bytes.fromhex("4142434445464748")

    for name, enc, dec in (("TEA", tea_encrypt_block, tea_decrypt_block),
                           ("XTEA", xtea_encrypt_block, xtea_decrypt_block)):
        ciphertext = enc(key, plaintext)
        print(f"{name} ciphertext: {ciphertext.hex()}   recovered: {dec(key, ciphertext).hex()}")

Running it produces this output:

TEA ciphertext: df25fc4279b8f929   recovered: 4142434445464748
XTEA ciphertext: 497df3d072612cb5   recovered: 4142434445464748

I checked this code against three sources before writing it up. It matches 64 TEA vectors and 64 XTEA vectors from the Crypto++ test suite, which come from Wheeler and Needham’s published test sets and include XTEA at every cycle count from 1 to 64. It matches 10 XTEA vectors from libtomcrypt. It also matches the Linux kernel’s vectors once the byte order is switched to little-endian. Every vector round-trips through decryption.

For Fun: Both Ciphers in 21 Lines

This is the same spirit as the compact bonus sections elsewhere on this site. It is not for learning the algorithm from. This version squeezes the 71-line implementation above into 21 lines. The word splitting is a pair of lambdas, and each cipher’s round loop is a single line. It needs no imports and no other files.

MASK=0xFFFFFFFF;DELTA=0x9E3779B9;CYCLES=32
split=lambda key,block: ([int.from_bytes(key[4*i:4*i+4],"big") for i in range(4)],int.from_bytes(block[:4],"big"),int.from_bytes(block[4:],"big"))
join=lambda v0,v1: v0.to_bytes(4,"big")+v1.to_bytes(4,"big")
def tea_encrypt_block(key,block,cycles=CYCLES):
 k,v0,v1=split(key,block);t=0
 for _ in range(cycles): t=(t+DELTA)&MASK; v0=(v0+(((v1<<4)+k[0])^(v1+t)^((v1>>5)+k[1])))&MASK; v1=(v1+(((v0<<4)+k[2])^(v0+t)^((v0>>5)+k[3])))&MASK
 return join(v0,v1)
def tea_decrypt_block(key,block,cycles=CYCLES):
 k,v0,v1=split(key,block);t=(DELTA*cycles)&MASK
 for _ in range(cycles): v1=(v1-(((v0<<4)+k[2])^(v0+t)^((v0>>5)+k[3])))&MASK; v0=(v0-(((v1<<4)+k[0])^(v1+t)^((v1>>5)+k[1])))&MASK; t=(t-DELTA)&MASK
 return join(v0,v1)
def xtea_encrypt_block(key,block,cycles=CYCLES):
 k,v0,v1=split(key,block);t=0
 for _ in range(cycles): v0=(v0+((((v1<<4)^(v1>>5))+v1)^(t+k[t&3])))&MASK; t=(t+DELTA)&MASK; v1=(v1+((((v0<<4)^(v0>>5))+v0)^(t+k[(t>>11)&3])))&MASK
 return join(v0,v1)
def xtea_decrypt_block(key,block,cycles=CYCLES):
 k,v0,v1=split(key,block);t=(DELTA*cycles)&MASK
 for _ in range(cycles): v1=(v1-((((v0<<4)^(v0>>5))+v0)^(t+k[(t>>11)&3])))&MASK; t=(t-DELTA)&MASK; v0=(v0-((((v1<<4)^(v1>>5))+v1)^(t+k[t&3])))&MASK
 return join(v0,v1)
key=bytes.fromhex("000102030405060708090a0b0c0d0e0f"); pt=bytes.fromhex("4142434445464748")
for name,enc,dec in (("TEA",tea_encrypt_block,tea_decrypt_block),("XTEA",xtea_encrypt_block,xtea_decrypt_block)):
 ct=enc(key,pt); print(f"{name} ciphertext: {ct.hex()}   recovered: {dec(key,ct).hex()}")

Running it prints the same two lines as the readable version, with the TEA and XTEA ciphertexts for the example block:

TEA ciphertext: df25fc4279b8f929   recovered: 4142434445464748
XTEA ciphertext: 497df3d072612cb5   recovered: 4142434445464748

I checked it against the readable code on 300 random keys and blocks, at 1, 5, 32, and 64 cycles, for both ciphers. Encryption matched every time, and decryption recovered every block. It also reproduces the all-zero test vectors for TEA and XTEA.

Limitations

These implementations are faithful teaching versions, not production ones:

• Single 64-bit block only. There is no mode of operation for longer messages and no padding for partial blocks.
• TEA has equivalent keys. Do not use TEA where a key must be unique, such as in a hash construction.
• The block is small. A 64-bit block limits how much data you should encrypt under one key, as the 3DES guide explains.
• No side-channel hardening. The code has no protection against timing or power analysis, although with no table lookups the cipher is naturally friendlier to constant-time code than most.

Security Status

TEA is considered broken as a hash and weak as a cipher. Its equivalent keys reduce the effective key to 126 bits, and the related-key attack needs only 2²³ chosen plaintexts. With a single key, the best published attack is a zero-correlation linear attack on 21 rounds, which needs about 2¹²¹·⁵ operations. For ordinary encryption with a single random key, TEA’s remaining weaknesses are minor, but nobody should choose it for a new design.

XTEA has held up much better. The best published attack is a related-key rectangle attack on 36 rounds, by Jiqiang Lu in 2009, and it needs about 2¹²⁶ operations and a huge amount of data. That is only a reduced-round attack, since the full cipher has 64 rounds. XTEA’s main limits are its 64-bit block and its slow, many-round design. It is a reasonable teaching cipher and a possible choice for tiny devices, and AES is the better choice almost everywhere else.

FAQ

Is TEA secure?

Not for new designs. It has equivalent keys, a practical related-key attack, and a history of being broken in real systems. XTEA fixes those problems, but modern ciphers are a better choice.

What is the difference between TEA and XTEA?

XTEA rearranges the shifts and XORs in the round function and picks a different key word each round, depending on bits of the running sum. That removes the equivalent-keys flaw. Both ciphers use 64 rounds and the same constant.

Why does TEA use 32 cycles?

A cycle is two rounds, so 32 cycles give 64 rounds, which is the standard setting. Reduced-round versions are much weaker, and the code’s cycles argument lets you try them.

What is the magic number 0x9E3779B9?

It is the integer part of 2³² divided by the golden ratio. It is a nothing-up-my-sleeve number, and the same value appears in RC5 and Serpent. Its job is to make each cycle use a different sum.

Why do different libraries give different TEA results?

They disagree on whether bytes become words in big-endian or little-endian order. The cipher itself works on words, so the algorithm is the same, but the bytes in and out differ.

References

1. Wheeler, D. and Needham, R. “TEA, a Tiny Encryption Algorithm.” Fast Software Encryption (FSE) 1994, Lecture Notes in Computer Science 1008.

2. Needham, R. and Wheeler, D. “Tea Extensions.” Technical report, Computer Laboratory, University of Cambridge, 1997.

3. Kelsey, J., Schneier, B., and Wagner, D. “Related-Key Cryptanalysis of 3-WAY, Biham-DES, CAST, DES-X, NewDES, RC2, and TEA.” ICICS 1997.

4. Lu, J. “Related-Key Rectangle Attack on 36 Rounds of the XTEA Block Cipher.” International Journal of Information Security, 8(1), 2009.

5. Wikipedia. “Tiny Encryption Algorithm.” Available at: https://en.wikipedia.org/wiki/Tiny_Encryption_Algorithm

6. Wikipedia. “XTEA.” Available at: https://en.wikipedia.org/wiki/XTEA