Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.

Dismiss

56 views

Skip to first unread message

Oct 22, 1996, 3:00:00 AM10/22/96

to

Abstract:

TEA (the Tiny Encryption Algorithm) can be weakened by fixing "sum" for

all rounds, instead of having sum+=delta every round. TEA weakened in this

fashion can be attacked using a technique similar to that used by David

Wagner against the S-1 algorithm.

The attack can be completed with 2^32 known plain/cipher pairs and 2^98

encryptions; tradeoffs may be possible and I don't guarantee that this is

optimised. This is independent of the number of rounds. 2^98 encryptions

is still pretty strong, and this weakness in the key schedule is entirely

fixed by the full TEA.

The attack:

Collect 2^32 well distributed plain/cipher pairs (ie used in some mode

other than ECB). By the birthday paradox, there should exist P,Q such that

P_1 = Q_0; since the weak TEA key schedule is identical for every round,

P_(i+1) = Q_i for all i (subscript denotes, "after i rounds"). Since we

cannot identify this set directly, we try all possible combinations for

2^64 trials.

Denote left and right halves by Py, Qz, etc, so the left half of Q after 1

round is Qy_1.

Let:

a0 = Qy_0 - Py_0 - (Pz_0>>5)^sum - (Pz_0<<4) = k1 + Pz_0^k0

b0 = Qz_0 - Pz_0 - (Qy_0>>5)^sum- (Qy_0<<4) = k3 + Qy_0^k2

a32 = Qy_32 - Py_32 - (Pz_32>>5)^sum - (Pz_32<<4) = k1 + Pz_32^k0

b32 = Qz_32 - Pz_32 - (Qy_32>>5)^sum - (Qy_32<<4) = k3 + Qy_32^k2

Now a0 - a32 = Pz_0^k0 - Pz_32^k0, in which only k0 is unknown.

Unfortunately, the xor gives this equation some odd properties (as the

designers intended, with the "mixing of incompatible operations").

Briefly, the number of bits of information about k0 which can be obtained

from this equation is equal to the number of bits in which Pz_0 and Pz_32

differ, less one. On average, this will be 15. In a similar manner we

obtain 15 bits of k2. k1 and k3 can be derived exactly from their

corresponding k0 and k2. Thus, for each trial {P,Q}, 2^34 trial

encryptions are required, for a total of 2^98.

If more plain/cipher pairs are available, we can preferentially try pairs

in which the number of bits of difference between plain and cipher is

greater than 32; this will allow the extraction of more information from

a0 - a32 and b0 - b32, and reduce the factor of 2^34.

Summary:

Although other fixes to the key schedule of weak TEA are possible, the

inclusion of sum+=delta does the job nicely. This shows that sum is an

important part of the TEA key schedule, which should not be considered as

completely weak. It is also shown that the mixing of xor and addition mod

2^32 adds considerably to the strength of the cipher; in this case, a work

factor of 2^34.

Appendix:

TEA encrypt (important bits, in C)

delta= ... // Integral part of golden ratio x 2^32

sum=0;

for (rounds=0;rounds<32;rounds++)

{

sum+=delta;

y+= k1 + (z>>5)^sum + z^k0 + (z<<4);

z+= k3 + (y>>5)^sum + y^k2 + (y<<4);

}

Oct 24, 1996, 3:00:00 AM10/24/96

to

In article <roger_sf-221...@mg4-50.its.utas.edu.au>,

Roger Fleming <roge...@postoffice.utas.edu.au> wrote:

: TEA (the Tiny Encryption Algorithm) can be weakened by fixing "sum" for

: all rounds, instead of having sum+=delta every round. TEA weakened in this

: fashion can be attacked using a technique similar to that used by David

: Wagner against the S-1 algorithm.

:

: The attack can be completed with 2^32 known plain/cipher pairs and 2^98

: encryptions; tradeoffs may be possible and I don't guarantee that this is

: optimised. This is independent of the number of rounds.

Neat! Nice post.

: Collect 2^32 well distributed plain/cipher pairs (ie used in some mode

: other than ECB). By the birthday paradox, there should exist P,Q such that

: P_1 = Q_0; since the weak TEA key schedule is identical for every round,

: P_(i+1) = Q_i for all i (subscript denotes, "after i rounds"). Since we

: cannot identify this set directly, we try all possible combinations for

: 2^64 trials.

:

: Denote left and right halves by Py, Qz, etc, so the left half of Q after 1

: round is Qy_1.

:

: Let:

: a0 = Qy_0 - Py_0 - (Pz_0>>5)^sum - (Pz_0<<4) = k1 + Pz_0^k0

: b0 = Qz_0 - Pz_0 - (Qy_0>>5)^sum- (Qy_0<<4) = k3 + Qy_0^k2

: a32 = Qy_32 - Py_32 - (Pz_32>>5)^sum - (Pz_32<<4) = k1 + Pz_32^k0

: b32 = Qz_32 - Pz_32 - (Qy_32>>5)^sum - (Qy_32<<4) = k3 + Qy_32^k2

:

: Now a0 - a32 = Pz_0^k0 - Pz_32^k0, in which only k0 is unknown.

: Unfortunately, the xor gives this equation some odd properties (as the

: designers intended, with the "mixing of incompatible operations").

: Briefly, the number of bits of information about k0 which can be obtained

: from this equation is equal to the number of bits in which Pz_0 and Pz_32

: differ, less one. On average, this will be 15. In a similar manner we

: obtain 15 bits of k2. k1 and k3 can be derived exactly from their

: corresponding k0 and k2. Thus, for each trial {P,Q}, 2^34 trial

: encryptions are required, for a total of 2^98.

Here's an improvement under a chosen-plaintext assumption. For each

of the 2^32 known pairs (X_0,X_32) obtain the encryption of (the ciphertext!)

X_32, and call the result X_64. Now iterate over all 2^64 pairs P,Q.

You get a series of equations that gives you ~ 15 bits of k0 from

P_0,Q_0,P_32,Q_32. You can also derive a similar series equations

from P_32,Q_32,P_64,Q_64; and yet another from P_0,Q_0,P_64,Q_64.

(Note that if P_1 = Q_0, then P_33 = Q_32, so when you try the right

combination of P,Q, it'll show up in all three series of equations.)

This should provide enough overlap to recover all (or nearly all) of

the key bits; on average one trial encryption per P,Q combination

will more than suffice. Therefore with about 2^33 chosen plaintexts,

you can get the number of trial encryptions needed down to about 2^64.

Perhaps one can reduce the work even further with a counting scheme,

with some clever filtering, or with a well-chosen hash table; but I

don't see how at the moment.

0 new messages

Search

Clear search

Close search

Google apps

Main menu