Page 1 of 2 12 LastLast
Results 1 to 15 of 20

Thread: Tea

  1. #1

    Tea

    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

  2. #2
    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

  3. #3
    הבּרוּ נשׂאי כּלי יהוה mike's Avatar
    Join Date
    Mar 2001
    Posts
    491
    If you figure out a way, let me know

  4. #4
    r4g3
    Guest
    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 ...
    Last edited by r4g3; November 16th, 2002 at 14:47.
    I promise that I have read the FAQ and tried to use the Search to answer my question.

  5. #5
    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

  6. #6
    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

  7. #7
    r4g3
    Guest
    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 )
    Last edited by r4g3; November 16th, 2002 at 22:22.
    I promise that I have read the FAQ and tried to use the Search to answer my question.

  8. #8
    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

  9. #9
    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

  10. #10
    My versions of TEA...

    The original TEA version
    Code:
    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
    The newer one I think it was called TEAn or something like that
    Code:
    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
    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
    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

  11. #11
    Programmer Run Amock... Bengaly's Avatar
    Join Date
    Aug 2001
    Location
    Somewhere over the Rainbow
    Posts
    289
    Blog Entries
    1

    :)

    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"

  12. #12
    geeker
    Guest
    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 promise that I have read the FAQ and tried to use the Search to answer my question.

  13. #13
    mac
    Guest

    Thumbs down

    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
    I promise that I have read the FAQ and tried to use the Search to answer my question.

  14. #14
    tgodd
    Guest
    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
    I promise that I have read the FAQ and tried to use the Search to answer my question.

  15. #15
    הבּרוּ נשׂאי כּלי יהוה mike's Avatar
    Join Date
    Mar 2001
    Posts
    491
    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!

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •