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
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
You could do a bruteforce attack, but other than that I don't think so....
Eyes to see...what the others see not
Ears to hear...the voice of the elders guides
Eyes to see...and the blind, they wither away
You fools! These eyes are never for you
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 ...
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
Eyes to see...what the others see not
Ears to hear...the voice of the elders guides
Eyes to see...and the blind, they wither away
You fools! These eyes are never for you
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
it may be worse10h byte = (2^8)^16 = 2^128 key space??? isnt that too much?
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 )
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
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
My versions of TEA...
The original TEA version
The newer one I think it was called TEAn or something like thatCode:Encrypt PROC v:DWORD, k:DWORD, n:DWORD 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 v:DWORD, k:DWORD, n:DWORD 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
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 happenCode:tean PROC uses ecx ebx esi edi data:DWORD,key:DWORD,rounds:DWORD LOCAL limit:DWORD 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
Eyes to see...what the others see not
Ears to hear...the voice of the elders guides
Eyes to see...and the blind, they wither away
You fools! These eyes are never for you
hey , same algorithm as in REA #4
"knowledge is now free at last, everything should be free from now on, enjoy knowledge and life and never work for everybody else"
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.
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
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
Let's consider how many of those there are, OK?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.
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!
Bookmarks