2004-05-22 Written by Steve Redler IV
What is it?
TEA stands for the Tiny Encryption Algorithm.
http://www.ftp.cl.cam.ac.uk/ftp/papers/djw-rmn/djw-rmn-tea.html
It is a simple/fast cypher that is supposedly quite secure.
Without going into a long dragged out crytptography primer, Im going to leave it to you to research unfamiliar topics. This is in my words, not in that of a professional cryptoanalyst. Feel free to chime in to correct me or elaborate.
Two common modes of cyphers are block cyphers and stream cyphers. I firsted 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 fashion. 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 benifit of this is that you dont have to pad the data, you just discard the unused crypted counter bytes if any are left over. Anothe benefit of CTR mode is that to decrypt the data, you run in back through the encryption algorithm. Nifty, we save %50 on code :) .
Who cares, and what does it do?
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/recieve the encrypted data on, otherwise expect to loose a lot of sleep and/or hair.
# 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
# tclscrypt.tcl Steve Redler IV, steve A T sr-tech D O T com
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
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"
wcf3 Your scrypt procedure is a much cleaner frontend to the TEA encryption than mine [L1 ]. 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. Im 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? Id 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 firsted implemented TEA in block cypher mode, first in pure tcl..., you might have said something about it actually being my code from [L2 ] 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 have implemented this in C before (but not released it) and one thing you need to concider is host system endianess. 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.