An attack on a weakened version of TEA
Roger Fleming
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);
}
David Wagner
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.