48 views

Skip to first unread message

Sep 13, 1998, 3:00:00 AM9/13/98

to

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.

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu