I’ve been writing about block ciphers lately, and finishing with a discussion of lightweight ciphers: ciphers designed to tun in little memory, or with little computational overhead. A classic such cipher is the Tiny Encryption Algorithm – TEA – originally proposed by David Wheeler and Roger Needham from Cambridge in 1994. It has a 64-bit block size and a 128-bit key. Here is their initial C code to describe it:

void code(long* v, long* k) { unsigned long y=v[0], z=v[1], sum=0, /* set up */ delta=0x9e3779b9, n=32; /* a key schedule constant */ while (n-->0) { /* basic cycle start */ sum += delta; y += ((z<<4) + k[0]) ^ (z + sum) ^ ((z>>5) + k[1]); z += ((y<<4) + k[2]) ^ (y + sum) ^ ((y>>5) + k[3]); } /* end cycle */ v[0]=y ; v[1]=z ; }

It is in fact easier to show the code than it is to describe the cipher in words! It consists of two Feistel steps, one after the other forming a “cycle”, and there are 32 such cycles in the encryption step. The authors decided that a large number of rounds would overcome deficiencies in the trivial key schedule. The cipher is easily translated into Sage:

def tea(plaintext,key): n = 32; N = 2^n delta = ZZ('0x9e3779b9'); sm = 0 [z,y] = ZZ(plaintext).digits(N,padto=2) [k3,k2,k1,k0] = ZZ(key).digits(N,padto=4) for i in range(n): sm = (sm + delta)%N y = (y+ (((z<<4)+k0) ^^ (z+sm) ^^ ((z>>5)+k1)))%N z = (z+ (((y<<4)+k2) ^^ (y+sm) ^^ ((y>>5)+k3)))%N return hex(N*y+z)

There have been some successful attacks on TEA, and several iterations later, the most recent version is XXTEA, which can be described as:

void xxtea_full_cycle(uint32_t *v, int n, uint32_t*key, int cycle) { uint32_t sum, z , y , e; int r; sum = cycle*0x9e3779b9; e = sum>>2; for (r = 0; r < n; r++) { z = v[(r+n−1)%n]; // the left neighboring word y = v[(r+1)%n]; // the right neighboring word v[r] += ((z>>5^y<<2)+(y>>3^z<<4))^((sum^y)+(key[(r^e)%4]^z)) ; } } void xxtea (uint32_t *v, unsigned int n, uint32_t *k) { int i , cycles = 6+52/n; for (i = 1; i < cycles; i++) xxtea_full_cycle(v , n , k , i); }

Again, this is not as safe as it looks, but it is nonetheless remarkable that such a simple construction can yield at least some non-trivial security.

Another super-simple cipher is Treyfer, developed by Gideon Yuval in 1997. It has a key and block size of 8 bytes each. In the article introducing it, he claimed: “By using a large number of rounds, we hope to be able to scrounge an Sbox out of nowhere, in an environment for which even TEA and the SAFERs are gross overdesign.” Here it is:

for(r=0; r<NumRounds; r++) { text[8]=text[0] ; for(i=0; i<8; i++) { text[i+1]=(text[i+1] + Sbox[(key[i]+text[i])%256])<<<1; // rotate i left } text[0]=text[8] ; }

It uses an S-box which is not prescribed; any 256 x 8 bytes will do, and these bytes can be obtained from anywhere, again minimizing the effective size of the cipher. Yuval showed how the entire cipher can be implemented in only 30 bytes.

Filed under: Computation, Cryptography, Sage | Leave a comment »