Re: A chosen plaintext attack for XXTEA

On Dec 4, 6:08 am, Elias Yarrkov <yarr...@xxxxxxxxx> wrote:
On Dec 3, 12:31 am, matt...@xxxxxxxxxxxxxxxxxx wrote:





On Nov 27, 3:40 pm, yarr...@xxxxxxxxx wrote:

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.

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.

http://cipherdev.org/break-xxtea-7.c.txt

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?

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.- Hide quoted text -

- 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
.