PDA

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.