This is a stream cipher using a 256 byte array, which is operated on by an (imaginary) processor using it as both code and data. This is a very appropriate scheme to be implemented in hardware.

A counter steps through the 256 bytes and the value is xor'd with the plaintext to produce the ciphertext. Between each byte, 127 iterations of the evolve() function are run on the array.

The evolve function (which probably makes much more sense in source code form; see below) uses another separate instruction pointer ip pointing somewhere in the array. It calculates a value size equal to 1 plus the lowest 3 bits of the byte at ip. The most significant bit selects between two operations plus (0) and xor (1), and the second most significant sets whether a binary complement will be performed or not.

Then, the operator combines size bytes pointed to by the byte at ip+1 with the bytes following it one at a time, using the operator determined above. The bytes pointed to are replaced, and ip is moved to the byte after the last byte used in this operation (ip+size+1).

All values wrap around, and the array is initialized through the key, in the manner of RC4. This makes a maximum key length of 2048 bits.

Analysis

Using my program stat, this produces well-distributed pseudo random bits for a variety of keys. This is by no means a thorough test, but it performs as expected, at least.

Unlike RC4, the array does not remain a permutation of the bytes 0-255. This means that its distribution and contents are less predictable, which is good and bad. Good because there are 2^(256*8) * 256^2 (about 2.12 x 10^621) states that the device can be in, but bad because the device is not guaranteed to remain well-distributed and random. For instance, an array of all zeros will remain an array of all zeros, though this arrangement seems extremely unlikely. Plus and Xor should retain a good distribution of bits, and the complementation helps to keep it from snowballing in either direction. Through six hundred billion evolve()'s on all the keys I tried, the ratio of 1's to 0's showed no significant change from 1:1.

Improvements

The first byte is always used for the first xor. If the initialization of the array is not secure (and I suspect it isn't really) then a chosen- or known-plaintext attack could reveal information about the key.

The evolve function does not use all the bits of the byte used to pick the operator and size. It would probably improve things to have it use the three bits in the middle that it doesn't use. (Direction flag?)

Implementation

This implementation acts as a filter -- it will work fine under unix but MS-DOS does not handle binary pipes very well, so it will drop characters (nulls, I think). In MS-DOS you'll need to set source and dest to actual files.

   % ecrypt key < something.txt > encoded.e
   % ecrypt key < encoded.e > compare.txt

   % echo "Meet me at noon by the payphones." | ecrypt key > ~bob/dropbox/message.e

Here is an implementation in C.

/*
   C Implementation of Tom7-ecrypt stream cipher as a filter.
   This code is distributed under the GNU public license;
   see http://www.gnu.org/copyleft/gpl.html.

   I can't make any claims about the security of this algorithm because
   I am not a trained cryptographer, though it produces (as far as I can
   tell) statistically random output. This code should be thought about,
   but not used unless you know more about this than me.

     Tom 7

   http://tom7.org/

*/

#include <stdio.h>

#define uchar unsigned char

#define s(a,b,c) m=a[(b)];a[(b)]=a[(c)];a[(c)]=m;

void evolve(uchar*box);
void printbox(uchar*box);
int iter=-1;
int main (int argc, char ** argv) {
        int z,x,c,m;
        uchar box[256], K[256],j=0,IP=0;
        FILE * source = stdin, 
             * dest   = stdout;
      /*
        source = fopen("test.in","rb+");
        dest   = fopen("test.out","wb+");
        */

     if (argc != 2) { printf("%s key\n", argv[0]); exit(-1); }

     z = strlen(argv[1]);
     for (x=0;x<256;x++) K[box[x]=x]=argv[1][x%z];
     for (x=0;x<256;x++) { j+=box[x]+K[x]; s(box,x,j); }

        while (EOF != (c=fgetc(source))) {
              fputc(c ^ box[IP++],dest);
              x=127;
              while (x--) 
                   evolve(box);
             }

if (source != stdin )        fclose(source);
if (dest   != stdout)        fclose(dest);

return 0;
}

#define BOX(c) box[(c)&255]

int ip;

void evolve(uchar*box) {
     
    int size,x;
    ip &= 255;
    size = 1 + (box[ip]&7);
        switch (box[ip] >>6) {
        case 0:
           for (x=0;x<size;x++) BOX(BOX(ip)+x) += BOX(ip+x);
           break;
        case 1:
           for (x=0;x<size;x++) BOX(BOX(ip)+x) += ~BOX(ip+x);
           break;
        case 2:
           for (x=0;x<size;x++) BOX(BOX(ip)+x) ^= BOX(ip+x);
           break;
        case 3:
           for (x=0;x<size;x++) BOX(BOX(ip)+x) ^= ~BOX(ip+x);
           break;
        }
      ip+=size+1;
}

Back to Tom's Cryptography Thingie.
Back to Tom's CMU Page.

5 June 1998