A chosen plaintext attack for XXTEA
yar...@gmail.com
bother.
The structure of XXTEA is basically
m[i] += f(m[i-1], m[i+1], ...)
The idea is to find a delta so that
f(m[i-1], m[i+1], ...) == f(m[i-1]+delta, m[i+1], ...)
and
f(m[i-1], m[i+1], ...) == f(m[i-1], m[i+1]+delta, ...)
hold with a reasonable probability, so that the difference will remain
in only one block.
5 is a good D.
The total number of full cycles in XXTEA is reduced to only 6 if the
block is at least 53 words wide.
Only passing 5 is required.
Here are the approximate passing probabilities (for a random key, D=5)
for the two conditions for each of the 5 rounds (it's modified by the
variable `sum`):
Left-to-right: 2^-14.38, 2^-14.32, 2^-14.37, 2^-14.32, 2^-14.37
Right-to-left: 2^-7.23, 2^-8.10, 2^-6.77, 2^-6.96, 2^-8.17
(Referring to m[i-1] ==> m[i] and m[i+1] ==> m[i] difference non-
propagation, respectively)
The passing probability for 5 rounds in total is about 2^-109. When we
put the delta in the second last block and it passes 5 full cycles, it
can only affect the 3 last words of the block during the sixth (final)
full cycle. When we have a right pair, key information can be
extracted trivially.
I have implemented my attack in C. It can break 2 full cycles pretty
much instantly, and it broke 3 full cycles overnight on my Athlon XP
3000+ (I don't know the exact time because the timer overflowed). It
can break 6 full cycles faster than brute-force, taking about 2^110
chosen plaintexts to find a single right pair.
Elias Yarrkov
> Just something I found a while ago. I'll write a paper if I can
> bother.
>
> The structure of XXTEA is basically
> m[i] += f(m[i-1], m[i+1], ...)
>
> The idea is to find a delta so that
> f(m[i-1], m[i+1], ...) == f(m[i-1]+delta, m[i+1], ...)
> and
> f(m[i-1], m[i+1], ...) == f(m[i-1], m[i+1]+delta, ...)
> hold with a reasonable probability, so that the difference will remain
> in only one block.
>
> 5 is a good D.
>
By D I mean a delta.
> The total number of full cycles in XXTEA is reduced to only 6 if the
> block is at least 53 words wide.
> Only passing 5 is required.
>
> Here are the approximate passing probabilities (for a random key, D=5)
> for the two conditions for each of the 5 rounds (it's modified by the
> variable `sum`):
>
> Left-to-right: 2^-14.38, 2^-14.32, 2^-14.37, 2^-14.32, 2^-14.37
> Right-to-left: 2^-7.23, 2^-8.10, 2^-6.77, 2^-6.96, 2^-8.17
>
> (Referring to m[i-1] ==> m[i] and m[i+1] ==> m[i] difference non-
> propagation, respectively)
>
> The passing probability for 5 rounds in total is about 2^-109. When we
> put the delta in the second last block and it passes 5 full cycles, it
Correction: The second last /word/.
> can only affect the 3 last words of the block during the sixth (final)
> full cycle. When we have a right pair, key information can be
> extracted trivially.
>
> I have implemented my attack in C. It can break 2 full cycles pretty
> much instantly, and it broke 3 full cycles overnight on my Athlon XP
> 3000+ (I don't know the exact time because the timer overflowed). It
> can break 6 full cycles faster than brute-force, taking about 2^110
> chosen plaintexts to find a single right pair.
>
> http://cipherdev.org/break-xxtea-7.c.txt
(Yes, it's still me.)
Dave -Turner
Mark Wooding
> Sounds pretty interesting, im disappointed nobody has commented yet
I filter all posts from googlegroups because it's a major source of spam
and cluelessness. Thanks for bringing it to my attention.
You need to configure your user agent properly.
-- [mdw]
Dave -Turner
news:slrngj2kt...@metalzone.distorted.org.uk...
???
I don't post through Google Groups, i post directly through my ISP's NNTP
news server.
The 'ad...@127.0.0.1' is intentional.
Dave -Turner
intend it in that way.
Mark Wooding
> I don't post through Google Groups, i post directly through my ISP's NNTP
> news server.
No, but the original poster did. I got your message just fine, which
led me to read the original interesting article. Thanks for the
pointer.
> The 'ad...@127.0.0.1' is intentional.
Oh. Shame it's invalid, then. If you mean to point it at localhost,
you need square brackets to construct a domain literal,
viz. admin@[127.0.0.1]. To me it just looked like a misconfiguration.
-- [mdw]
mat...@dynamic-memory.com
Elias,
Interesting idea, just took quick look. A few questions.
1. How many bits of the key are recovered by the attack? Is it the
whole key, 32 bits or some other subset?
2. Can you spell out the algorithm a bit more clearly? It appears
that you are creating a collision in the round function that
eventually appears the cipher text. The collision will appear as two
blocks having the same ciphertext in the first half of the block?
3. The XXTEA algorithm is so compressed it is hard to view as Fiestel
cipher. Perhaps go through a round or two.
4. Why is 5 a good delta? Have you done a fully differential
probability search? Could another delta have a better characteristic?
5. Can the attack be switch to Chosen Key by using your delta between
(lots of) key pairs?
6. Can you explain your key recovery algorithm? The code was not
immediately obvious to me.
--Matt
Dave -Turner
> Dave -Turner <ad...@127.0.0.1> wrote:
>
> > The 'ad...@127.0.0.1' is intentional.
>
> Oh. Shame it's invalid, then. If you mean to point it at localhost,
> you need square brackets to construct a domain literal,
> viz. admin@[127.0.0.1]. To me it just looked like a misconfiguration.
Well it's just that I have no need to provide a real email address, so I
figure if I have to provide an email address I might as well use one that's
useless to spammers, and maybe in some cases results in them just trying to
send the email to their own computer. I'm always open to better suggestions!
Elias Yarrkov
All bits except the highest bit of each key word can be recovered with
enough right pairs, even though my implementation only tries to
recover one word. How many key bits can be recovered with each right
pair depends on luck, basically.
> 2. Can you spell out the algorithm a bit more clearly? It appears
> that you are creating a collision in the round function that
> eventually appears the cipher text. The collision will appear as two
> blocks having the same ciphertext in the first half of the block?
The two blocks will collide in all except one word through 5 rounds
when all goes well. After the final round, they will collide in all
but the three last words -- this depends on which word you place the
delta in, though.
> 3. The XXTEA algorithm is so compressed it is hard to view as Fiestel
> cipher. Perhaps go through a round or two.
XXTEA is
for(i=0;i<block_length*full_cycles;i++)
m[i] += f(m[i-1], m[i+1], key, counter)
(array positions reduced modulo block_length, wrapping around the
sides of the block)
Now if you have
f(m[i-1]+delta, m[i+1], key, counter) == f(m[i-1], m[i+1], key,
counter)
and
f(m[i-1], m[i+1]+delta, key, counter) == f(m[i-1], m[i+1], key,
counter)
then delta can't have any effect on other words in the block until at
the next full cycle.
I can't think of a way to explain it better.
> 4. Why is 5 a good delta? Have you done a fully differential
> probability search? Could another delta have a better characteristic?
I bruteforced through all 1 to 5 (or something) -bit deltas, checking
their success probability for each of the two conditions I mentioned.
The product of those two probabilities is the probability the delta
passes through one full cycle.
> 5. Can the attack be switch to Chosen Key by using your delta between
> (lots of) key pairs?
Nope. (I'm assuming you mean a related key attack.)
> 6. Can you explain your key recovery algorithm? The code was not
> immediately obvious to me.
> --Matt
The basic idea is the same as in a classic differential attack --
decrypt(block2, key) - decrypt(block1, key) = delta, determine which
round keys give this result.
The round function f(...) in XXTEA can't allow a bit in the key to
affect any bit lower than it. The round key can be solved fast using
this property, recursively checking all "legal" keys working down to
up.
But this technique is just a trick and isn't necessary, you could just
bruteforce through all possible round keys (2^32 of them). The time
taken by this is neglible when you attack more than 2 rounds.
Any literature on differential cryptanalysis should explain this
better. I'm not a teacher.
mat...@dynamic-memory.com
>
> - Show quoted text -
Elias,
I have a good understanding of Differential Analysis. Search for
"Matthew Fisher" in sci.crypt. I used to post a lot.
Interesting attack. So basically we are just concerned with the last
3 blocks. The differential will look like
0 ... 0X0 -> 0 ... 0X0 with a probability of 2^-21 or so. The 0 is a
32 bit word that is the same between two plain/ciphertexts. The X
denotes a difference. The '...' is a bunch of 0 blocks and the -> is
the round function.
Since the block size is so large, I think at least a 2R attack can be
mounted. Near the end only one of the differentials has to hold.
Plain 0 ... 0X0
Round 1 0 ... 0X0
Round 2 0 ... 0X0
Round 3 0 ... 0X0
Round 4 0 ... 0X0
Round 5 0 ... XX0
Round 6 0 ... XXXX // cipher text
So we have 53 - 4 = 49 words the same, a full breach of the cipher.
Probability here is 2^-99 or is it 2^-92?
Let push it back some more, it appears the only the -last- word is
vital since a change there will cascade through the full block. The
cipher has slow diffusion.
Plain 0 ... 0X0
R1 0 ... 0X0
R2 0 ... 0X0
R3 0 ... 0X0 // only half the differenial suceeds, p = 2^-7?
R4 0 ... XX0 // what is the prob here? 2^-32? Can we do better?
R5 0 ... XXX0
R6 0 ...XXXXX
As another possiblity let us guess the last two round keys for 2^64
computation.
Plain 0 ... 0X0
R1 0 ... 0X0
R2 0 ... 0X0
R3 0 ... 0X0
R4 0 ... XXX
R5 X ... XXX // all different
R6 X ....XXX // all different
Is this case we need 2^64 pairs, vaguely practical. One good pair
distinguishes the cipher from random and reveals half the key.
An Impossible Differential seems likely as well.
If the probablitiies hold up, the attack looks like a full break of
the cipher to me. Good work!
--Matt
Elias Yarrkov
Firstly, I try to use the terminology that I think is standard with
Feistel-like structures and what Wikipedia also seems to conform to
(as strange as it is). A round is defined as a single m[i] += f(m
[i-1], m[i+1], ...) operation, a full cycle is running that for every
word in m.
And now for other business...
I don't understand this. If the right-to-left equality doesn't hold
during full cycle 5 when modifying the 3rd last word, then the 3rd
last words will differ messily instead of being equal. Then when
modifying the 2nd last word, the difference will also become something
messy. Then the other equality doesn't make sense when modifying the
final word, and you can't expect the final words to remain the same
with a probability greater than 2^-32 without some analysis. The
probability for this all happening would seem to be about
2^-((14.38 + 14.32 + 14.37 + 14.32) + (7.23 + 8.10 + 6.77 + 6.96) +
32) = 2^-118.45.
> Let push it back some more, it appears the only the -last- word is
> vital since a change there will cascade through the full block. The
> cipher has slow diffusion.
>
> Plain 0 ... 0X0
> R1 0 ... 0X0
> R2 0 ... 0X0
> R3 0 ... 0X0 // only half the differenial suceeds, p = 2^-7?
> R4 0 ... XX0 // what is the prob here? 2^-32? Can we do better?
> R5 0 ... XXX0
> R6 0 ...XXXXX
Same thing here. The expected probability would seem to be about
2^-((14.38 + 14.32 + 14.37) + (7.23 + 8.10 + 6.77) + 32 + 32) =
2^-129.17.
> As another possiblity let us guess the last two round keys for 2^64
> computation.
>
> Plain 0 ... 0X0
> R1 0 ... 0X0
> R2 0 ... 0X0
> R3 0 ... 0X0
> R4 0 ... XXX
> R5 X ... XXX // all different
> R6 X ....XXX // all different
>
> Is this case we need 2^64 pairs, vaguely practical. One good pair
> distinguishes the cipher from random and reveals half the key.
XXTEA rotates through the key words as it goes through a full cycle,
beginning at a cycle-specific position. So it's not directly possible
to decrypt the whole block one round with a round key, only a single
word can be decrypted. Or two words, with two round keys.
> An Impossible Differential seems likely as well.
I've no experience with those yet.
> If the probablitiies hold up, the attack looks like a full break of
> the cipher to me. Good work!
>
> --Matt
--yarrkov
mat...@dynamic-memory.com
>
> - Show quoted text -
yarrkov,
You seem to have it right. After some more thought, I have not seen
an improvement to your original attack.
Good work,
--Matt