TEA's Equivalent Keys and the Xbox Hack

TEA’s Equivalent Keys and the Xbox Hack

Introduction

The Tiny Encryption Algorithm is famously small, just a few lines of code with a 128-bit key. That 128-bit key is a lie, though, and the shortfall is not statistical or approximate. Every TEA key has exactly three other keys that encrypt every possible block to exactly the same ciphertext. The four keys are indistinguishable from the outside.

The cause is a single bit. Flipping the top bit of two specific key words changes the round function in two places that cancel each other in an XOR. This guide shows the cancellation, verifies that all four keys of a group produce identical output across thousands of random blocks, and then uses the same flaw to forge a hash collision, which is how the original Xbox was broken.

Table of Contents

• The Round Function
• Why the Top Bits Cancel
• Four Keys, One Cipher
• From Equivalent Keys to a Hash Collision
• Interactive Visualizer
• A Worked Example
• Python Implementation
• For Fun: The Whole Thing in a Few Lines
• Limitations
• Security Status
• FAQ
• References

The Round Function

TEA splits a 64-bit block into two 32-bit halves, v0 and v1, and a 128-bit key into four words, k0 through k3. It runs 32 cycles, each updating both halves. All arithmetic is modulo 2^32. The update for v0 is the piece that matters:

v0 += ( (v1 << 4) + k0 ) ^ ( v1 + sum ) ^ ( (v1 >> 5) + k1 )

Two of the three XORed terms carry a key word. The first mixes in k0, the third mixes in k1, and the middle term has no key at all. The v1 update uses k2 and k3 in the same pattern. That symmetry, two key words XORed together inside one line, is exactly the gap the attack walks through.

Why the Top Bits Cancel

Consider what happens when you add 0x80000000 to a key word, which flips its top bit. In 32-bit arithmetic, (v1 << 4) + k0 changes only in bit 31, because adding 0x80000000 toggles bit 31 and any carry out of the top is discarded. So ((v1 << 4) + k0) with k0 flipped differs from the original only in its top bit.

Flip k1 the same way, and ((v1 >> 5) + k1) also differs only in its top bit. Now XOR the two changed terms together. Each contributes one flipped top bit, and two flips of the same bit in an XOR cancel. The middle term (v1 + sum) never used a key, so it does not move. The entire line produces the identical result. The same reasoning applies to k2 and k3 in the other half.

Four Keys, One Cipher

Flipping the top bits of k0 and k1 together is one safe move. Flipping the top bits of k2 and k3 together is another. The two moves are independent, so you can do neither, either, or both. That gives four keys in every equivalence group:

( k0,     k1,     k2,     k3     )
( k0+2^31, k1+2^31, k2,     k3     )
( k0,     k1,     k2+2^31, k3+2^31 )
( k0+2^31, k1+2^31, k2+2^31, k3+2^31 )

All four encrypt every block identically. Since each key belongs to a group of four, the number of distinct ciphers is one quarter of the 2^128 keys, so the effective key size is 126 bits, not 128. Two bits of the key do nothing. An attacker brute-forcing TEA searches a quarter of the space, and any key found reveals three free twins.

From Equivalent Keys to a Hash Collision

Losing two bits of a 128-bit cipher is not fatal on its own. The real damage came from using TEA as a hash. A common way to build a hash from a block cipher feeds the message in as the key. Microsoft did this in the original Xbox boot ROM, in a Davies-Meyer style construction, roughly H = E_message(IV) XOR IV, with the message block used as the cipher key.

That turns the equivalent-key property into a collision. If the message is the key, then two messages that are equivalent keys produce the same cipher output, so they hash to the same value. Flip the top bits of the first two words of a message, and the hash does not change, even though the message did. A hash must never let two inputs collide so cheaply. This gave Xbox hackers a way to alter the boot code while keeping its hash, which helped unlock the console.

Interactive Visualizer

The visualizer above runs real TEA. Enter a key and a block, and it shows all four equivalent keys and the ciphertext each one produces, which is always the same value. Flip to the hash view to see two different messages collide to the same digest, the Xbox mistake in miniature. Every number is computed by the genuine 32-cycle TEA, checked against the standard test vectors, with nothing faked.

Change the key or the plaintext and watch the four ciphertexts stay locked together. That is the whole point: two of the key’s bits are invisible to TEA, so you cannot move the output by touching them.

A Worked Example

Take the key 000102030405060708090a0b0c0d0e0f and the plaintext 4142434445464748, the ASCII text ABCDEFGH. Real TEA encrypts it to df25fc4279b8f929. The four equivalent keys all produce that same ciphertext:

key 000102030405060708090a0b0c0d0e0f -> df25fc4279b8f929
key 800102038405060708090a0b0c0d0e0f -> df25fc4279b8f929
key 000102030405060788090a0b8c0d0e0f -> df25fc4279b8f929
key 800102038405060788090a0b8c0d0e0f -> df25fc4279b8f929

Across 2,000 random keys and blocks, each checked against all four of its equivalents, there was not a single mismatch. The equivalence is exact, not probabilistic. The hash collision is just as clean:

message A : cafebabe0badf00ddeadbeef12345678
message B : 4afebabe8badf00ddeadbeef12345678   (top bits of first two words flipped)
hash(A)   : ffcc1bb14bf486c0
hash(B)   : ffcc1bb14bf486c0

Two different 128-bit messages, one hash. That is a collision found by hand, in one step, with no search at all.

Python Implementation

The code is self-contained and runnable. It is real TEA, checked against the standard all-zero vector and the ABCDEFGH example, plus the equivalent-key generator and the TEA-as-hash collision.

# tea_equivalent_keys.py
#
# TEA's equivalent keys. In the v0 update, ((v1<<4)+k0) ^ (v1+sum) ^ ((v1>>5)+k1), two of the three XORed
# terms carry a key word. Flip the top bit of BOTH k0 and k1 and each term changes only in bit 31, so the
# two flips cancel in the XOR. The same holds for k2,k3 in the v1 update. So every TEA key has 3 twins that
# encrypt identically: the effective key is 126 bits, not 128. Used as a hash (message as the key), this
# becomes a trivial collision, which is how the original Xbox boot ROM was broken.

MASK = 0xFFFFFFFF
DELTA = 0x9E3779B9
MSB = 0x80000000


def tea_encrypt(v0, v1, k, cycles=32):
    s = 0
    for _ in range(cycles):
        s = (s + DELTA) & MASK
        v0 = (v0 + ((((v1 << 4) + k[0]) & MASK) ^ ((v1 + s) & MASK) ^ (((v1 >> 5) + k[1]) & MASK))) & MASK
        v1 = (v1 + ((((v0 << 4) + k[2]) & MASK) ^ ((v0 + s) & MASK) ^ (((v0 >> 5) + k[3]) & MASK))) & MASK
    return v0, v1


def tea_decrypt(v0, v1, k, cycles=32):
    s = (DELTA * cycles) & MASK
    for _ in range(cycles):
        v1 = (v1 - ((((v0 << 4) + k[2]) & MASK) ^ ((v0 + s) & MASK) ^ (((v0 >> 5) + k[3]) & MASK))) & MASK
        v0 = (v0 - ((((v1 << 4) + k[0]) & MASK) ^ ((v1 + s) & MASK) ^ (((v1 >> 5) + k[1]) & MASK))) & MASK
        s = (s - DELTA) & MASK
    return v0, v1


def equivalent_keys(k):
    return [
        [k[0],       k[1],       k[2],       k[3]],
        [k[0] ^ MSB, k[1] ^ MSB, k[2],       k[3]],
        [k[0],       k[1],       k[2] ^ MSB, k[3] ^ MSB],
        [k[0] ^ MSB, k[1] ^ MSB, k[2] ^ MSB, k[3] ^ MSB],
    ]


def words(hexstr):
    b = bytes.fromhex(hexstr)
    return [int.from_bytes(b[i:i + 4], "big") for i in range(0, len(b), 4)]


def hw(*ws):
    return "".join(f"{w:08x}" for w in ws)


def tea_hash(msg_key, iv=(0x01234567, 0x89ABCDEF)):
    c0, c1 = tea_encrypt(iv[0], iv[1], msg_key)       # message used AS the key
    return (c0 ^ iv[0]) & MASK, (c1 ^ iv[1]) & MASK


if __name__ == "__main__":
    assert hw(*tea_encrypt(0, 0, [0, 0, 0, 0])) == "41ea3a0a94baa940"
    k = words("000102030405060708090a0b0c0d0e0f")
    v0, v1 = words("4142434445464748")
    assert hw(*tea_encrypt(v0, v1, k)) == "df25fc4279b8f929"
    assert tea_decrypt(*tea_encrypt(v0, v1, k), k) == (v0, v1)
    print("TEA self-tests: PASS")

    print("plaintext:", hw(v0, v1), '("ABCDEFGH")')
    outs = set()
    for ek in equivalent_keys(k):
        ct = hw(*tea_encrypt(v0, v1, ek))
        outs.add(ct)
        print(f"key {hw(*ek)} -> {ct}")
    print("all four identical:", len(outs) == 1)

    msg = words("cafebabe0badf00ddeadbeef12345678")
    msg2 = [msg[0] ^ MSB, msg[1] ^ MSB, msg[2], msg[3]]
    print("hash(A):", hw(*tea_hash(msg)), " hash(B):", hw(*tea_hash(msg2)),
          " collision:", tea_hash(msg) == tea_hash(msg2))

Running it prints the worked example:

TEA self-tests: PASS
plaintext: 4142434445464748 ("ABCDEFGH")
key 000102030405060708090a0b0c0d0e0f -> df25fc4279b8f929
key 800102038405060708090a0b0c0d0e0f -> df25fc4279b8f929
key 000102030405060788090a0b8c0d0e0f -> df25fc4279b8f929
key 800102038405060788090a0b8c0d0e0f -> df25fc4279b8f929
all four identical: True
hash(A): ffcc1bb14bf486c0  hash(B): ffcc1bb14bf486c0  collision: True

For Fun: The Whole Thing in a Few Lines

The attack has no search to golf. The equivalent keys are just XORs with a constant, so the “break” is a one-liner given the key words:

MSB = 0x80000000
twins = lambda k: [[k[0] ^ a, k[1] ^ a, k[2] ^ b, k[3] ^ b] for a in (0, MSB) for b in (0, MSB)]

# every key in twins(k) encrypts identically; pick any two for a hash collision

There is nothing to brute-force and nothing probabilistic. The weakness is structural, so naming the four keys is the entire attack.

Limitations

The equivalence is exact, but it is worth being precise about what it does and does not give:

• It costs two bits, not the whole key. Equivalent keys reduce TEA from 128 to 126 effective bits. That alone does not make TEA’s encryption breakable, since 2^126 is still far out of reach. It matters most when a single key must be unique.
• The collision needs TEA used as a hash. The dramatic break comes from feeding the message in as the key. A system that uses TEA only for encryption, with a fixed secret key, does not hand an attacker the freedom to choose equivalent keys.
• Byte order must be fixed. TEA is defined on 32-bit words, and libraries disagree on how bytes become words. The worked example reads bytes as big-endian words, matching the base TEA guide. The equivalence itself is independent of that choice.
• Other TEA weaknesses exist too. Beyond equivalent keys, TEA has a practical related-key attack needing about 2^23 chosen plaintexts. XTEA was designed specifically to remove the equivalent-key flaw and the related-key weakness.

Security Status

• TEA is broken as a hash and weak as a cipher. The equivalent keys make it unusable in any construction that treats the key as data, and the related-key attack weakens it further. It should never be chosen for a hash or a MAC.
• XTEA fixed this. XTEA changed the key schedule so that the key words no longer pair up inside a single XOR, which removes the equivalent keys. It also resists the related-key attack. If you must use something in the TEA family, use XTEA, not TEA.
• The real lesson is about reusing a cipher as a hash. A block cipher with even a small key symmetry becomes a collision machine when the message plays the role of the key. The Xbox break is the classic reminder that a cipher’s key schedule is part of its security, and that hashes need their own design.

FAQ

What is an equivalent key?

It is a different key that produces identical encryption for every possible input. For TEA, each key has three such twins, formed by flipping the top bits of k0 and k1 together, or k2 and k3 together, or both. From the outside the four keys are indistinguishable.

Why does flipping the top bit cancel out?

Adding 0x80000000 to a 32-bit value flips only bit 31, since the carry past the top is discarded. Two key words in the same line each get their top bit flipped, and XORing two values whose top bits both flipped leaves that bit unchanged. The rest of the computation is untouched.

How much security does TEA actually lose?

The effective key size drops from 128 bits to 126 bits, a factor of four. For encryption with a single random key that is a minor loss. The serious consequence is for hashing, where equivalent keys become easy collisions.

How was the Xbox broken with this?

The Xbox boot ROM used TEA as a hash by feeding code in as the key. Because equivalent keys give identical output, two different pieces of code could produce the same hash. Hackers used that to alter the boot process while keeping the expected hash value, part of unlocking the console.

Does XTEA have the same problem?

No. XTEA’s key schedule selects one key word per round based on the round counter, instead of XORing two key words in one line. That breaks the symmetry, so XTEA has no equivalent keys and resists the related-key attack that also affects TEA.

References

1. Kelsey, John, Bruce Schneier, and David Wagner. “Related-Key Cryptanalysis of 3-WAY, Biham-DES, CAST, DES-X, NewDES, RC2, and TEA,” ICICS 1997 (the equivalent-key and related-key results).

2. Wheeler, David, and Roger Needham. “TEA, a Tiny Encryption Algorithm,” FSE 1994.

3. Steil, Michael. “17 Mistakes Microsoft Made in the Xbox Security System,” 22C3, 2005 (the TEA-as-hash break).

4. The TEA and XTEA guide on this site, whose cipher this breaker attacks: /blog/tea_xtea_guide/