Movable Type Scripts

Block TEA (Tiny Encryption Algorithm)

Wheeler & Needham’s Tiny Encryption Algorithm is a simple but powerful encryption algorithm (based on a ‘Feistel cipher’).

This is a JavaScript implementation of the (corrected) ‘Block TEA ’ or ‘large block’ version of the algorithm (also dubbed ‘xxtea’) which operates on variable-sized blocks, as opposed to the 64-bit blocks of the original.

This is a simple but highly effective DES-style encryption algorithm which can be useful for web applications which require security or encryption. It provides very secure cryptographically strong encryption in concise, clear JavaScript code.

The Block TEA version is faster than the original (64-bit block version) when encrypting longer blocks (over 16 chars), and is more secure (‘a single bit change will change about one half of the bits of the entire block, leaving no place where the changes start’). It is also simpler to implement in JavaScript for encrypting arbitrary-length texts (being variable block size, it requires no ‘mode of operation’). For an implementation of the original algorithm, see TEA.html.

TEA uses a 128-bit key, which could (for increased security) be an encrypted (or hashed) form of the supplied password. Here I simply convert the first 16 characters of the password into longs to generate the key. The password might be a user-supplied password, or an internal system password. A system password will be more secure if it avoids plain-text (e.g. ‘dVr4t%G§Uu+mz7+8’).

Wheeler & Needham’s original formulation (in C) of corrected block TEA (aka xxtea) was as follows:

#define MX (z>>5^y<<2) + (y>>3^z<<4)^(sum^y) + (k[p&3^e]^z);

long btea(long* v, long n, long* k) {
  unsigned long z=v[n-1], y=v[0], sum=0, e, DELTA=0x9e3779b9;
  long m, p, q ;
  if (n > 1) {          /* Coding Part */
    q = 6+52/n ;
    while (q-- > 0) {
      sum += DELTA;
      e = sum >> 2&3 ;
      for (p=0; p<n-1; p++) y = v[p+1], z = v[p] += MX;
      y = v[0];
      z = v[n-1] += MX;
    }
    return 0 ; 
  } else if (n < -1) {  /* Decoding Part */
    n = -n ;
    q = 6+52/n ;
    sum = q*DELTA ;
    while (sum != 0) {
      e = sum>>2 & 3;
      for (p=n-1; p>0; p--) z = v[p-1], y = v[p] -= MX;
      z = v[n-1];
      y = v[0] -= MX;
      sum -= DELTA;
    }
    return 0;
  }
  return 1;
}

I have adapted this so that it operates on text rather than just on numeric arrays, and also rearranged it slightly so that p is not referenced outside the for loop (valid in C, but not always in other languages).

Speed: using IE on a 3GHz P4 the script processes around 80kB/sec (around 25 pages of text), though it slows down with longer texts. (Note longsToStr() function was changed March 2005 to improve efficiency).

In other languages: remember always to use either unsigned right-shift operators or unsigned type declarations, according to features available in the language – signed right shift operations will fail; also, in strToLongs(), to avoid running off the end of the string, some languages may need the string to be padded to a multiple of 4 characters, with the equivalent of for (var p=0; p<3-(s.length-1)%4; p++) s += '\0';.

For an explanation of the operation of the TEA algorithm, and cryptography in general, an excellent book is Information Security Intelligence: Cryptographic Principles & Applications by Tom Calabrese (available from Amazon.com). There is also a good article explaining TEA operation and cryptanalysis by Matthew Russell from York University and a short article in Wikipedia.

Note: if you are interested in cryptanalysis of TEA, bear in mind that there are 4 versions described in 3 documents: the original TEA, then Extentions to TEA (addressing weaknesses in TEA and also describing Block TEA), and Corrections to Block TEA (aka xxtea). This page implements the last of these.

If you want industrial-strength encryption, I have also implemented a version of AES.

For some security applications, a cryptographic hash is more appropriate than encryption – if you are interested in a hash function, see my implementation of SHA-1.

//
// TEAencrypt: Use Corrected Block TEA to encrypt plaintext using password
//             (note plaintext & password must be strings not string objects)
//
// Return encrypted text as string
//
function TEAencrypt(plaintext, password)
{
    if (plaintext.length == 0) return('');  // nothing to encrypt
    // 'escape' plaintext so chars outside ISO-8859-1 work in single-byte packing, but keep
    // spaces as spaces (not '%20') so encrypted text doesn't grow too long (quick & dirty)
    var asciitext = escape(plaintext).replace(/%20/g,' ');
    var v = strToLongs(asciitext);  // convert string to array of longs
    if (v.length <= 1) v[1] = 0;  // algorithm doesn't work for n<2 so fudge by adding a null
    var k = strToLongs(password.slice(0,16));  // simply convert first 16 chars of password as key
    var n = v.length;

    var z = v[n-1], y = v[0], delta = 0x9E3779B9;
    var mx, e, q = Math.floor(6 + 52/n), sum = 0;

    while (q-- > 0) {  // 6 + 52/n operations gives between 6 & 32 mixes on each word
        sum += delta;
        e = sum>>>2 & 3;
        for (var p = 0; p < n; p++) {
            y = v[(p+1)%n];
            mx = (z>>>5 ^ y<<2) + (y>>>3 ^ z<<4) ^ (sum^y) + (k[p&3 ^ e] ^ z);
            z = v[p] += mx;
        }
    }

    var ciphertext = longsToStr(v);

    return escCtrlCh(ciphertext);
}

//
// TEAdecrypt: Use Corrected Block TEA to decrypt ciphertext using password
//
function TEAdecrypt(ciphertext, password)
{
    if (ciphertext.length == 0) return('');
    var v = strToLongs(unescCtrlCh(ciphertext));
    var k = strToLongs(password.slice(0,16)); 
    var n = v.length;

    var z = v[n-1], y = v[0], delta = 0x9E3779B9;
    var mx, e, q = Math.floor(6 + 52/n), sum = q*delta;

    while (sum != 0) {
        e = sum>>>2 & 3;
        for (var p = n-1; p >= 0; p--) {
            z = v[p>0 ? p-1 : n-1];
            mx = (z>>>5 ^ y<<2) + (y>>>3 ^ z<<4) ^ (sum^y) + (k[p&3 ^ e] ^ z);
            y = v[p] -= mx;
        }
        sum -= delta;
    }

    var plaintext = longsToStr(v);

    // strip trailing null chars resulting from filling 4-char blocks:
    plaintext = plaintext.replace(/\0+$/,'');

    return unescape(plaintext);
}


// supporting functions

function strToLongs(s) {  // convert string to array of longs, each containing 4 chars
    // note chars must be within ISO-8859-1 (with Unicode code-point < 256) to fit 4/long
    var l = new Array(Math.ceil(s.length/4));
    for (var i=0; i<l.length; i++) {
        // note little-endian encoding - endianness is irrelevant as long as 
        // it is the same in longsToStr() 
        l[i] = s.charCodeAt(i*4) + (s.charCodeAt(i*4+1)<<8) + 
               (s.charCodeAt(i*4+2)<<16) + (s.charCodeAt(i*4+3)<<24);
    }
    return l;  // note running off the end of the string generates nulls since 
}              // bitwise operators treat NaN as 0

function longsToStr(l) {  // convert array of longs back to string
    var a = new Array(l.length);
    for (var i=0; i<l.length; i++) {
        a[i] = String.fromCharCode(l[i] & 0xFF, l[i]>>>8 & 0xFF, 
                                   l[i]>>>16 & 0xFF, l[i]>>>24 & 0xFF);
    }
    return a.join('');  // use Array.join() rather than repeated string appends for efficiency
}

function escCtrlCh(str) {  // escape control chars etc which might cause problems with encrypted texts
    return str.replace(/[\0\t\n\v\f\r\xa0'"!]/g, function(c) { return '!' + c.charCodeAt(0) + '!'; });
}

function unescCtrlCh(str) {  // unescape potentially problematic nulls and control characters
    return str.replace(/!\d\d?\d?!/g, function(c) { return String.fromCharCode(c.slice(1,-1)); });
}