TEA Streaming encryption extension

2004-05-22 Written by Steve Redler IV

What is it?

TEA stands for the Tiny Encryption Algorithm. (TEA is also the initialism of the Tcl Extension Architecture.)

http://www.ftp.cl.cam.ac.uk/ftp/papers/djw-rmn/djw-rmn-tea.html

(Oct 23, 2011 link broken)

It is a simple/fast cypher that is supposedly quite secure.

Without going into a long dragged out cryptography primer, I'm going to leave it to you to research unfamiliar topics. This is in my words, not in that of a professional cryptanalyst. Feel free to chime in to correct me or elaborate.

Two common modes of cyphers are block cyphers and stream cyphers. I first implemented TEA in block cypher mode, first in pure tcl, then in c using critcl. Both worked well, the C version was naturally 100 times faster. The problem with a block cypher is that since you work with blocks of data (ie: 8 bytes), the data needs to be padded to a size divisible by eight, then the padding has to be removed during decryption. Both issues have many common solutions that work well, as did the one I chose.

When sending data over a channel like a socket, the padding becomes a nuisance to handle. A stream cypher works byte by byte, XORing the data byte with a crypted byte based off the key in some manner. More specifically, CTR or counter mode, is a cypher method whereby you generate the crypted byte by encrypting a 128 bit counter value with your 128 bit key, incrementing the counter after all 8 bytes have been used to encrypt 8 bytes of data. The benefit of this is that you don't have to pad the data, you just discard the unused crypted counter bytes if any are left over. Another benefit of CTR mode is that to decrypt the data, you run it back through the encryption algorithm. Nifty, we save %50 on code :) .

Who cares, and what does it do? edit

In the C extension below, I create a tcl command named scrypt. The scrypt command takes data, a 16 char key and a counter value as its arguments. The counter may just be set to zero. The data may be text or binary. The encrypted result is binary. Remember to use binary translation on any channel i/o that you send/receive the encrypted data on, otherwise expect to lose a lot of sleep and/or hair.

Correction: These programs utilize the XTEA variant of the TEA algorithm.

# scrypt.tcl  Steve Redler IV, steve A T sr-tech D O T com
package provide scrypt 0.2 
package require critcl
#command to build lib:  tclkit critcl.kit -pkg scrypt.tcl

critcl::ccode {  
  char encryptc(unsigned long *v, unsigned long *k) 
  {
    /* v = datablock, k = key */

    unsigned long y=v[0],z=v[1],sum=0,       /* set up */
    delta=0x9e3779b9, n=32 ;         /* key schedule constant*/
    /*  printf("v0=%d v1=%d k0=%d k1=%d k2=%d k3=%d \n",v[0], v[1], k[0], k[1], k[2], k[3]);*/
    while (n-->0)
    {                                              /* basic cycle start*/
      y += (z<<4 ^ z>>5) + z ^ sum + k[sum&3];
      sum += delta;
      z += (y<<4 ^ y>>5) + y ^ sum + k[sum>>11 &3] ;     /* end cycle */
    }
    v[0] = y;
    v[1] = z;
  }
}

critcl::ccommand scrypt {dummy ip objc objv} {
  int x, klen, datalen, ctrlen, bytenum;
  unsigned char *key;
  unsigned char k[16] = "0000000000000000";
  unsigned char *datain, *dataout;

  unsigned long long counter = 0;
  unsigned long long *ctraddr;
  
  unsigned char xorpad[8] = "00000000";
  unsigned long long *xorpadaddr;
  
  Tcl_Obj *resultPtr;

  ctraddr = &counter;
  xorpadaddr = &xorpad;
  
  if (objc != 4) {
    Tcl_WrongNumArgs(ip, 1, objv, "data key counter");
    return TCL_ERROR;
  }

  datain = Tcl_GetByteArrayFromObj(objv[1], &datalen);
  key = Tcl_GetByteArrayFromObj(objv[2], &klen);
  Tcl_GetLongFromObj(ip, objv[3], &counter);
  
  /* put key into correct var type */
  for (x = 0; x < 16 ; x++) {
    k[x] = key[x];
  }

  /* datalen holds the length of the incomming crypted code */

  dataout = ckalloc(datalen);

  x = 8;

  for (bytenum = 0; bytenum < datalen ; bytenum++) {
    if (x == 8) {
      *xorpadaddr = *ctraddr;
      encryptc(xorpadaddr, &k);
      x = 0;
      counter++;
    }

    dataout[bytenum] = xorpad[x] ^ datain[bytenum];
    x++;
  }

  resultPtr = Tcl_NewByteArrayObj(dataout, (datalen));

  Tcl_SetObjResult(ip, resultPtr);
  ckfree(dataout);
  return TCL_OK;
}

I've tested it on Linux and Windows and it works well so far.

To compile the extension, place critcl.kit in the same dir as scrypt.tcl, then run:

  tclkit critcl.kit -pkg scrypt.tcl

#test usage example
# test.tcl 
lappend auto_path [file join [file dirname [info script]] lib/]
package require scrypt

set data "Hello World"
 
set encrypted [scrypt $data thistopsecretkey 0]
puts "encrypted=$encrypted"

set decrypted [scrypt $encrypted thistopsecretkey 0]
puts "decrypted=$decrypted"

Pure Tcl Version edit

# tclscrypt.tcl  Steve Redler IV, steve A T sr-tech D O T com

# the following proc for TEA was written by Chuck Ferril
proc teaencrypt { v k } {
    binary scan $v "ii" y z
    binary scan $k "i4" k

    set sum 0
    set n 32
    while {[incr n -1] >= 0} {
        incr y [expr {(($z << 4) ^ (($z >> 5) & 0x7FFFFFF)) + $z ^ ($sum + [lindex $k [expr $sum & 3]])}]
        #incr sum 0x9E3779B9 ;# took this out due to changes in 8.5
        incr sum -1640531527
        incr z [expr {(($y << 4) ^ (($y >> 5) & 0x7FFFFFF)) + $y ^ ($sum + [lindex $k [expr ($sum >> 11) & 3]])}]
    }

    return [binary format "ii" $y $z]
}

proc scrypt { data key ctr} {
    set result ""

    if { [string length $key] < 0 || [string length $key] > 16 } {
        return "error"
    }
    while { [string length $key] < 16 } {
        append key " "
    }

    set x 8

    set datalen [string length $data]
    for {set byte 0} {$byte < $datalen} {incr byte} {
        if {$x == 8} {
            set xorpad [teaencrypt [binary format "w" $ctr] $key]
            set x 0
            incr ctr
        }
        binary scan  [string index $data $byte] "c" binchar
        binary scan  [string index $xorpad $x] "c" padchar  
        set binchar [expr {($binchar + 0x100) % 0x100}]
        set padchar [expr {($padchar + 0x100) % 0x100}]
        append result [binary format "c" [expr {$binchar ^ $padchar}]]
        incr x
    }

    return $result
}

#test usage example
set data "Hello World"
 
set encrypted [scrypt $data thistopsecretkey 0]
puts "encrypted=$encrypted"

set decrypted [scrypt $encrypted thistopsecretkey 0]
puts "decrypted=$decrypted"

Discussion edit

wcf3 Your scrypt procedure is a much cleaner frontend to the TEA encryption than mine [1]. Nice work.

SRIV Thanks. Keep in mind that this is incompatible with block mode encrypted files. I will post those versions when I have a moment. I'm curious if our versions are compatible.

wcf3 No, I'm pretty sure they aren't. When I have time (ha ha) I may dig into it a bit to see if they can be made compatible.

SRIV Assuming you implemented block mode, what method did you use to handle padding? I'd think thats where we differed. I tried 3 ways before I settled on padding the last 1 to 7 bytes with all ones to all sevens, depending on the number of pad bytes appended, I finally tossed it all in favor of CTR mode for its simplicity.

wcf3 <ICKYSTUFF> I think when you stated I first implemented TEA in block cypher mode, first in pure tcl..., you might have said something about it actually being my code from [2] that you used for that part. I'm thrilled that someone is using my work and expanding on it; but a little credit would have been nice. If I am mistaken, I apologise, but the code is identical and that kind of hurt.</ICKYSTUFF>

SRIV Indeed! My sincere apologies! I found a copy of your tea.kit in one of my backups, I now fully recall using your code as a base. I worked so much on it that my memory was fogged. Thank you for bringing that up to me. Had I realized what I did I would have consulted you first. Boy do I feel like a smuck :)

wcf3 I should have emailed you privately first...sorry about that. Anyway; this is one of the first times that I have seen some of my code picked up and enhanced by someone else and I guess my fragile ego was crushed when I wasn't mentioned. :-( I hope it didn't came across as sour grapes because I didn't mean it that way. I'm actually much happier to see the code grow into something bigger and better; that's what us software junkies really live for...No more about this (since this isn't the place, my bad) Back to the code! :-)

wcf3 I have implemented this in C before (but not released it) and one thing you need to consider is host system endianness. I was sharing data between Intel and PPC hosts and had to flip bytes on one machine to make things work. I believe the pure Tcl version does not have this problem. I'll have to check with the company I did the C version for and see if I can share that code.

wcf3 Please release it buddy!

TP I did a little googling for TEA strengths and attacks. This paper [3] by J. Kelsey, B. Schneier, and D. Wagner (1997) includes an attack on TEA requiring only 2^23 chosen-plaintext and one related key query. This page [4] (dead link 2007-11-15, in WBM as [5]) shows a nice pictorial view of the algorithm, and proposes enhanced Block TEA, XTEA [6] and XXTEA [7] algorithms. This page [8] has Pascal source for the related TEA algorithms.

SRIV Thanks for the above links Tom! It's intriguing to read about attempts to break the algorithm. I'll clarify that the above algorithm is XTEA, which is only slightly different from the original TEA, but is not vulnerable to the key schedule attack that TEA is. I wonder if my method of using XTEA in this streaming mode introduces weakness.

[ivanixdev] The pure tcl version seems to not work with the given example. returns error "interger value too large to represent"

[CJE] - 2013-07-04 00:57:37

Above code does not run with anymore with Tcl8.5 where integers don't overflow anymore. In order to get it running I had to make the following changes in teaencrypt:

        #8.4#incr y [expr {(($z << 4) ^ (($z >> 5) & 0x7FFFFFF)) + $z ^ ($sum + [lindex $k [expr $sum & 3]])}]
        #8.4#incr sum -1640531527
        #8.4#incr z [expr {(($y << 4) ^ (($y >> 5) & 0x7FFFFFF)) + $y ^ ($sum + [lindex $k [expr ($sum >> 11) & 3]])}]

        set y [expr {int ($y + [expr {int((int($z << 4) ^ (int($z >> 5) & 0x7FFFFFF)) + $z ^ int($sum + [lindex $k [expr $sum & 3]]))}])}]
        set sum [expr {int ($sum - 1640531527)}]
        set z [expr {int ($z + [expr {int((int($y << 4) ^ (int($y >> 5) & 0x7FFFFFF)) + $y ^ int($sum + [lindex $k [expr ($sum >> 11) & 3]]))}])}]

Category Package

Category Cryptography