From AES to Red Pike

From AES to Red Pike

The Mighty Prof Ross Anderson

The AES method is a block cipher which uses a block size of 128-bits and key sizes of 128 bits, 192 bits and 256 bits. It operates by uses a key scheduling method which takes part of the key for a number of rounds. For a 128-bit key, we have 10 rounds, and for a 256-bit key, we have 14 rounds. In each round, we take a 4ⅹ4 matrix of byte values (16 bytes = 128 bits), and then swap rows and columns. We also use an S-box to scramble the bytes:

But what happens if we want to make our block cipher simpler, and just implement it in just a few lines of code? This might be the case for a limited-memory IoT device. One such cipher is Red Pike, which was proposed as a standard for the NHS in 1996 [here]:

the NHS’s needs should be addressed by a family of related encryption products built on the Red Pike encryption algorithm. This algorithm has recently been made available to the NHS by CESG, the National Technical Security Authority within HMG

Red Pike — a name which is likely to derive from an area of the English Lake District — is a classified UK government encryption algorithm. It was created for the NHS by GCHQ but could be used in a range of applications. Overall it is a 64-bit block cipher with a 64-bit key length. Over the last two decades, there are few referenced articles to it, but it is quoted in a paper by Ross Anderson and Markus Kuhn [here]. Overall it uses simple bitwise operations, and has no S-boxes, no key scheduling, no look-up tables, and is implemented in a few lines of code.

Ross creates an interesting narrative in how the BMA was persuaded that Red Pike a study involving four academics:

In order to try and persuade the BMA that Red Pike was sound, the government commissioned a study of it by four academics [7]. This study states that Red Pike `uses the same basic operations as RC5' (p 4) in that the principal operations are add, exclusive or, and left shift. It `has no look-up tables, virtually no key schedule and requires only five lines of code' (p 4). Other hints include that `the influence of each key bit quickly cascades' (p 10) and
 each encryption involves of the order of 100 operations' (p 19).

Ross didn’t hold back in his criticism and in its RC5-derived roots, “RC5 may be about the worst possible algorithm choice for secret-algorithm hardware applications”, and that it was susceptible to the glitch attack.

In the end, Ross outlined that he had serious doubts about the methods and that S-boxes should be used. So, in an era of standards in cryptography, where “rolling your own” is not seen as a good thing, it is rather strange to see a method which was kept fairly secret.

A 64-bit key, unfortunately, is too small these days, and could be cracked by modern machines, but, at the time (1996), the key size would have been fairly secure. It must be remembered that in 1996, the Intel Pentium was the King of processors and had a blistering clock speed of 200MHz. With processor clock speeds now of nearly 4GHz, and with GPUs containing thousands of processing elements, modern computing devices would find cracking a 64-bit key a fairly easy task.

A demonstration of the code is here:

Red Pike uses a key size of 64-bits and a buffer size of 64-bits [here]:

/* Red Pike cipher source code */
 
 #include <stdint.h>
 #include <string.h>
 #include <stdlib.h>
 #include <stdio.h>

 typedef uint32_t word;
 
 #define CONST 0x9E3779B9
 #define ROUNDS 16
 
 #define ROTL(X, R) (((X) << ((R) & 31)) | ((X) >> (32 - ((R) & 31))))
 #define ROTR(X, R) (((X) >> ((R) & 31)) | ((X) << (32 - ((R) & 31))))
 
 void encrypt(word * x, const word * k)
 {
   unsigned int i;
   word rk0 = k[0];
   word rk1 = k[1];
 
   for (i = 0; i < ROUNDS; i++)
   {
     rk0 += CONST;
     rk1 -= CONST;
 
     x[0] ^= rk0;
     x[0] += x[1];
     x[0] = ROTL(x[0], x[1]);
 
     x[1] = ROTR(x[1], x[0]);
     x[1] -= x[0];
     x[1] ^= rk1;
   }
 
   rk0 = x[0]; x[0] = x[1]; x[1] = rk0;
 }
 
 void decrypt(word * x, const word * k)
 {
   word dk[2] =
   {
     k[1] - CONST * (ROUNDS + 1),
     k[0] + CONST * (ROUNDS + 1)
   };
 
   encrypt(x, dk);
 }

main ( int argc, char *argv[] ) 
{

char *key;
char *buffer;
char dec[100]="";
char ch[5]="";

if (argc==3) 
{

	buffer=argv[1];
	key=argv[2];
}

word b[2]={6,6};
word k[2]={6,6};

printf ("\nEncrypt: ");

for (int i=0;i<strlen(buffer);i+=4)
{
	b[0]=(int)buffer[i]+(int)(buffer[i+1]<<8);
	b[1]=(int)buffer[i+2]+(int)(buffer[i+3]<<8);

	k[0]=(int)key[0]+ (int)key[1]<<8;
	k[1]=(int)key[2]+ (int)key[3]<<8;
 	

	encrypt(b,key);
	printf ("%x%x",b[0],b[1]);
	decrypt(b,key);
        ch[0]=b[0]& 0xff;
        ch[1]=(b[0]& 0xff00)>>8;
        ch[2]=b[1]& 0xff;
        ch[3]=(b[1]& 0xff00)>>8;
	ch[4]=0;

	strcat(dec,ch);

}

printf ("\nDecrypt: %s",dec);
}

My favouriate bit of code is the way the decrypt is just the encrypt process, with a small change [here]:

void decrypt(word * x, const word * k)
 {
   word dk[2] =
   {
     k[1] - CONST * (ROUNDS + 1),
     k[0] + CONST * (ROUNDS + 1)
   };
 
   encrypt(x, dk);
 }

A sample run is [here]:

PIKE Encryption 
Message: abcde
Key: aaaa

Encrypt: d3d6e4c6dae19022ea46529fe5210331
Decrypt: abcde

Conclusions

While AES and other symmetric key methods are robust. They are also complex in their operation. For simplicity there’s not much around that can rival Red Pike for its speed, memory requirements and simplicity.