Log in

View Full Version : Tea

crUsAdEr
November 12th, 2002, 13:56
Hi guys,

Just a small question... if i have plaintext and cipher of a TEA encryption, is there a way of extracting the key out of it?

Thanx,
crUsAdEr
NervGaz
November 12th, 2002, 14:10
You could do a bruteforce attack, but other than that I don't think so....
mike
November 12th, 2002, 21:33
If you figure out a way, let me know
r4g3
November 16th, 2002, 14:19
the Tiny Encryption Algorithm is indeed very small and therefore bforcing it may be very fast. Even more - it`s a block cipher so there`s no need to process the whole plaintext. It is sufficient to check if the generated ciphertext for one block mathes the original ciphertext of the same block, this enables to drop the wrong key without processing the whole ciphertext.
The algo implementation has only 2 functions: encipher, decipher.
If to use encipher the above apply.
If decipher - the generated plaintext part & the original plaintext part must be compared.
Well i guess it`s elementary
dunno if any of these is faster than the other ...
NervGaz
November 16th, 2002, 17:17
If anybody's interested... from testing my version of TEA encrypt is roughly 16 clock cycles faster than decrypt... that on a 1.2GHz Tualatin@1.6Ghz In any case 16 clock cycles won't make any major difference
crUsAdEr
November 16th, 2002, 19:31
Hi guys..

hmm.. how feasible is it to bruteforce a full TEA key then?
10h byte = (2^8)^16 = 2^128 key space??? isnt that too much?

NervGaz, i have written a TEA routine myself but it is by no mean optimised... can I take a look at your code then?

Regards,
crUsAdEr
r4g3
November 16th, 2002, 22:19
Quote:
10h byte = (2^8)^16 = 2^128 key space??? isnt that too much?


it may be worse

1. a file can be used as a key. lets say some 700 MB cd image. in such case every block gets a new key until EOF, then wrapps to the start.

2. though the std number of iterations is 32 it can be changed easily - no need to be a rocket scientist (they r supposed to be 'not stupid') Running thru a vast space of 2^128 iterations may be insuficient if a wrong number is chosen. everything from zero again in this case

3. which brand/flavour it is exactly ? the initial streaming or a block cipher ?

what do u expect anyway ? TEA is a strong algo, plus non-standart - XOR & AND. no std known attacks apply (Pollard`s RHO, birthday, ...)

ok. this is the 3rd variant of this post (first 2 went above FFFFFFFF with opera7b crashing )
crUsAdEr
November 17th, 2002, 00:25
I can confirm it is stardard TEA with 16 bytes key length..

it is CBC with known initial vector... each block is 4 bytes so i guess it is fairly fast.. only the key space is huge... you guys reckon it is feasiable to try bruting this one?

Thanx,
crUsAdEr
cyberheg
November 17th, 2002, 11:24
No it's not feasiable with that keysize. I wouldn't even waste my time trying. Unless you can find some shortcut which will make it the real key used much smaller then 128 bits it's wasted time.

There were some talk about TEA not beeing fully secure hence a new variant called XTEA was released but I don't think it's weakend enough to call it broken.

In general anything (depending on the algorithm) it's not worth trying anything above 32bit on home computers.
If any of you remember it took 300000 computers and 5 years to bruteforce a RC5 with 32 rounds in the distributed.net challange which was a 64 bit key used.
So now go think how long it will take to do 128 bit.

Good luck.

// CyberHeg
NervGaz
November 17th, 2002, 21:48
My versions of TEA...

The original TEA version
Code:


Encrypt PROC vWORD, kWORD, nWORD



        mov edi,v

        mov esi,k

        mov ebx,[edi]

        mov ecx,[edi+4]

        xor eax,eax

        .WHILE n > 0

               

               add eax,9e3779b9h

               

               mov edx,ecx

               shl edx,4

               add ebx,edx

               mov edx,[esi]

               xor edx,ecx

               add ebx,edx

               mov edx,ecx

               shr edx,5

               xor edx,eax

               add ebx,edx

               add ebx,[esi+4]

               

               mov edx,ebx

               shl edx,4

               add ecx,edx

               mov edx,[esi+8]

               xor edx,ebx

               add ecx,edx

               mov edx,ebx

               shr edx,5

               xor edx,eax

               add ecx,edx

               add ecx,[esi+12]

               

               dec n

        .ENDW



        mov [edi],ebx

        mov [edi+4],ecx

        ret

Encrypt endp



Decrypt PROC vWORD, kWORD, nWORD



        mov edi,v

        mov esi,k

        mov ebx,[edi]

        mov ecx,[edi+4]

        imul eax,n,9e3779b9h

        .WHILE n > 0

               

               mov edx,ebx

               shl edx,4

               sub ecx,edx

               mov edx,[esi+8]

               xor edx,ebx

               sub ecx,edx

               mov edx,ebx

               shr edx,5

               xor edx,eax

               sub ecx,edx

               sub ecx,[esi+12]

               

               mov edx,ecx

               shl edx,4

               sub ebx,edx

               mov edx,[esi]

               xor edx,ecx

               sub ebx,edx

               mov edx,ecx

               shr edx,5

               xor edx,eax

               sub ebx,edx

               sub ebx,[esi+4]

               

               sub eax,9e3779b9h

               

               dec n

        .ENDW



        mov [edi],ebx

        mov [edi+4],ecx

        ret

Decrypt endp

The newer one I think it was called TEAn or something like that
Code:


tean PROC uses ecx ebx esi edi dataWORD,keyWORD,roundsWORD

    LOCAL limitWORD



    mov eax,data

    mov ebx,rounds

    mov edi,key

    mov edx,[eax]

    mov ecx,[eax+4]

    xor eax,eax

    dec eax

        .IF ebx>80000000h

            neg ebx

            imul eax,ebx,9E3779B9h

                .IF eax!=NULL

                    .WHILE eax!=NULL

                        ; First 32 bit chunk

                        mov ebx,edx

                        shl ebx,4

                        mov esi,edx

                        sar esi,5

                        xor ebx,esi

                        mov esi,eax

                        xor esi,edx

                        add ebx,esi

                        mov esi,eax

                        sar esi,11

                        and esi,3

                        add ebx,[edi+esi*4]

                        sub ecx,ebx

                        ; Second 32 bit chunk

                        sub eax,9E3779B9h

                        mov ebx,ecx

                        shl ebx,4

                        mov esi,ecx

                        sar esi,5

                        xor ebx,esi

                        mov esi,eax

                        xor esi,ecx

                        add ebx,esi

                        mov esi,eax

                        and esi,3

                        add ebx,[edi+esi*4]

                        sub edx,ebx

                    .ENDW

                .ENDIF

        .ELSE

            inc eax

            imul ebx,9E3779B9h

            mov limit,ebx

                .IF eax!=limit

                    .WHiLE eax!=limit

                        ; First 32 bit chunk

                        mov ebx,ecx

                        shl ebx,4

                        mov esi,ecx

                        sar esi,5

                        xor ebx,esi

                        mov esi,eax

                        xor esi,ecx

                        add ebx,esi

                        mov esi,eax

                        and esi,3

                        add ebx,[edi+esi*4]

                        add edx,ebx

                        ; Second 32 bit chunk

                        add eax,9E3779B9h

                        mov ebx,edx

                        shl ebx,4

                        mov esi,edx

                        sar esi,5

                        xor ebx,esi

                        mov esi,eax

                        xor esi,edx

                        add ebx,esi

                        mov esi,eax

                        sar esi,11

                        and esi,3

                        add ebx,[edi+esi*4]

                        add ecx,ebx

                    .ENDW

                .ENDIF

        .ENDIF

    mov eax,data

    mov [eax],edx

    mov [eax+4],ecx

    ret

tean ENDP


both of them could be optimized both for speed and size if I felt like it but the easiest oine would be to remove the possibilty to chose the amount of rounds and calculating a set limit value, but that probably won't happen
Bengaly
November 18th, 2002, 19:44
hey , same algorithm as in REA #4
geeker
December 4th, 2002, 06:25
TEA and XTEA are both Fiestel networks. Attemping to recover a key under a known plaintext attack is equivalent to solving nonlinear equations over Z_2. This is NP-hard.

On a slightly related note, for encrypting large blocks of data with TEA (or XTEA), the inner loop can be sped up significantly by pulling the keyschedule computations out. Unrolling the loop by a couple of iterations also helps. Check out libtomcrypt at http://libtomcrypt.iahu.ca

Granted, this won't help brute forcing a key, since any single key isn't reused, so you'd need to recompute a new key schedule anyway.
mac
December 30th, 2002, 11:07
I totally agree with cyberheg - 128 bit keysize are completly out of range. Imagine a counter counting from 0 to 2^128 - even if this counter runs with 10 mio counts per second you would need longer than the universe will exist to count...

so try finding some papers on vulnerabilities of TEA - but i guess you wont be that lucky....

cya

mac
tgodd
December 30th, 2002, 16:40
You could speed up your bruting by considering the following:

The highest likelyhood is that there will be an equivalent number of high bits as low bits in the key.
On the flip side it is less likely that the key will contain all the bits high, or all bits low.

So as opposed to using an algo that would do a standard count,
i.e. 1 2 3 4 5 6 . . .
you would have a routine which would start with equal high bits to low bits, i.e.
on an 8 bit key it would start 0f 17 1b 1d 1e 27 2b 2d . . .
and once finished the equal high to equal low
it would then start with the sequences which are unevenly balanced by 2 bits then by 4 , etc, etc.


regards,

tgodd
mike
December 30th, 2002, 22:10
Quote:
you would have a routine which would start with equal high bits to low bits, i.e.
on an 8 bit key it would start 0f 17 1b 1d 1e 27 2b 2d . . .
and once finished the equal high to equal low
it would then start with the sequences which are unevenly balanced by 2 bits then by 4 , etc, etc.
Let's consider how many of those there are, OK?

Given 128 bits, you want to pick 64 of them to be on and 64 off. That's 128 choose 64 = 128!/(64!64!) = 2x10^37 = 2^124. So you've only cut down the search space by a factor of 16, and you don't even know if your assumption is right!
tgodd
December 30th, 2002, 22:45
You are correct that an assumption is being made.

However, you must treat the unknown as a random.

Statistically, what I have suggested is by far the quickest
way to brute force the unknown number.

Random numbers:
If you analyze any random number it rarely reaches the maximum and rarely reaches minimum, and is more likely to be someplace closer to the middle.

Whatever gains can be made in bruting out a number, can only be advantageous.

P.S. It was only a suggestion. I am only trying to contribute, based on my experiences.

Regards,

tgodd
mike
January 3rd, 2003, 05:25
Quote:
P.S. It was only a suggestion. I am only trying to contribute, based on my experiences.
We appreciate that. I was trying to point out that 2^124 is still far too big a keyspace to brute-force.
tgodd
January 4th, 2003, 01:17
Don't get me wrong.
My method will not reduce the total loop count.

It will statistically increase the chances of an early hit.

that is all.

regards,

tgodd
comrade
January 4th, 2003, 04:53
How did this discussion go from finding key if both plaintext and ciphertext are known to brute-forcing key?
mike
January 4th, 2003, 09:24
Well, you can't bruteforce the key if you know less than a plaintext and its ciphertext, and there's no faster way known to get the right key given plaintext & ciphertext than by bruteforce.