Cryptanalysis of "Block TEA"

[Markku-Juhani O. Saarinen]

Perhaps someone will find the following attack interesting.
I've implemented this. You can download the 150-line source code that
performs the attack from my home page.

- mj

Markku-Juhani Saarinen <mj...@math.jyu.fi> http://www.math.jyu.fi/~mjos

Chosen ciphertext attack against the Block Tea algorithm

Markku-Juhani Saarinen <mj...@math.jyu.fi>
September 12, 1998


In this memo we show how to break the Block Tea algorithm of [1]
with 2^34 chosen ciphertexts. Block Tea is an attempt to fix
some problems of the original TEA of [2]. ([2] is probably much
stronger.)

In the following, I use the variable names of [1] freely. Sorry if this
is a bit hard to follow.

It is clear that difference propagation in decryption occurs at the
rate of one word per round; changing v[0] in the ciphertext does not
affect v[q..n-1] in the plaintext at all.

The mixing function uses f(z) = ((z << 4) ^ (z >> 5)) + z with
z = v[p - 1] to modify v[p]. This becomes more apparent when one adds
parethesis to the C expression (from [1]):

(z << 4 ^ z >> 5) + z ^ k[p & 3 ^ e] + sum
becomes
(((z << 4) ^ (z >> 5)) + z) ^ (sum + k[(p & 3) ^ e])

We note that f(z) is not bijective; it is many-to-one. Here's some
pairs of values for z that produce the same f(z):

z1 z2 f(z1) = f(z2)
000201e1 00020000 00221000
000403c2 00040000 00442000
00080784 00080000 00884000
00100f08 00100000 01108000
00201e10 00200000 02210000
00f803c2 10000000 10800000
01f00784 20000000 21000000
03e00f08 40000000 42000000
1e2e4a7d 00040000 00442000
3c23d319 00000020 00000221
...

Therefore the difference propagation in decryption does not occur when
v[p - 1] = z1 for one ciphertext and v[p - 1] = z2 for another. The
propagation (to the right) is delayed by one round.

Our attack works as follows. We first try solve the key that is used to
decrypt v[n - 1] at the first decryption round. We do this by decrypting
a pair of ciphertexts that are the same, except that in the other v[n - 1]
gets decrypted as 0x000201e1 and in the another as 0x00020000.
If we have guessed the key word correctly, v[q - 1] will match in the
plaintexts. This can be verified with another "collision pair" from the
table above. Once this key word has been found, we can proceed to
find the next key word using the same technique for v[n - 2].

Since each key word requires 2^32 decryptions (average value), the
entire 128-bit key can be recovered with 2^34 decryptions.

There probably are additional shortcuts that allow this attack to
furthermore streamlined. Some of the f(z) collisions may allow entire
key classes to be immediately discovered. I wouldn't be surprised if
there was an attack that required 2^28 chosen ciphertexts or less.


[1] R. M. Needham and D. J. Wheeler, "Tea extensions"
http://www.cl.cam.ac.uk/ftp/users/djw3/xtea.ps

[2] R. M. Needham and D. J. Wheeler, "TEA, a Tiny Encryption Algorithm",
Fast Software Encryption, 94 pp 363-366.