Prev: Rolex Oyster Perpetual Cosmograph Daytona Mens Watch 116523-WDO Collection
Next: ready to use javascript cryptopage - crypto-js
From: Dave -Turner on 29 Nov 2008 11:56
ps. I hope you didn't think my original post was sarcastic, as I did not
intend it in that way.


From: Mark Wooding on 29 Nov 2008 11:50
Dave -Turner <admin(a)127.0.0.1> wrote:

> 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 'admin(a)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]
From: matthew on 2 Dec 2008 17:31
On Nov 27, 3:40 pm, yarr...(a)gmail.com 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?

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
From: Dave -Turner on 2 Dec 2008 23:24

"Mark Wooding" <mdw(a)distorted.org.uk> wrote in message
news:slrngj2smt.5k5.mdw(a)metalzone.distorted.org.uk...
> Dave -Turner <admin(a)127.0.0.1> wrote:
>
> > The 'admin(a)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!


From: Elias Yarrkov on 4 Dec 2008 08:08
On Dec 3, 12:31 am, matt...(a)dynamic-memory.com wrote:
> On Nov 27, 3:40 pm, yarr...(a)gmail.com 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.
First  |  Prev  | 
Pages: 1 2
Prev: Rolex Oyster Perpetual Cosmograph Daytona Mens Watch 116523-WDO Collection
Next: ready to use javascript cryptopage - crypto-js