Prev: Rolex Oyster Perpetual Cosmograph Daytona Mens Watch 116523-WDO Collection
Next: ready to use javascript cryptopage - crypto-js
From: yarrkov on 27 Nov 2008 17:40
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
From: Elias Yarrkov on 27 Nov 2008 20:10
On Nov 28, 12:40 am, 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.
>

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.)
From: Dave -Turner on 29 Nov 2008 08:51
Sounds pretty interesting, im disappointed nobody has commented yet


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

> 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]
From: Dave -Turner on 29 Nov 2008 11:37
"Mark Wooding" <mdw(a)distorted.org.uk> wrote in message
news:slrngj2ktf.5k5.mdw(a)metalzone.distorted.org.uk...
> Dave -Turner <admin(a)127.0.0.1> wrote:
>
> > 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]

???

I don't post through Google Groups, i post directly through my ISP's NNTP
news server.

The 'admin(a)127.0.0.1' is intentional.


 |  Next  |  Last
Pages: 1 2
Prev: Rolex Oyster Perpetual Cosmograph Daytona Mens Watch 116523-WDO Collection
Next: ready to use javascript cryptopage - crypto-js