The ISAAC cipher

The ISAAC cipher
You are encouraged to solve this task according to the task description, using any language you may know.

ISAAC is a cryptographically secure pseudo-random number generator (CSPRNG) and stream cipher. It was developed by Bob Jenkins from 1993 (http://burtleburtle.net/bob/rand/isaac.html) and placed in the Public Domain. ISAAC is fast - especially when optimised - and portable to most architectures in nearly all programming and scripting languages. It is also simple and succinct, using as it does just two 256-byte arrays for its state.

ISAAC stands for "Indirection, Shift, Accumulate, Add, and Count" which are the principal bitwise operations employed. To date - and that's after more than 20 years of existence - ISAAC has not been broken (unless GCHQ or NSA did it, but they wouldn't be telling). ISAAC thus deserves a lot more attention than it has hitherto received and it would be salutary to see it more universally implemented.

Your task, should you choose to accept it, is to translate ISAAC's reference C or Pascal code into your language of choice. The RNG should then be seeded with the string "this is my secret key" and finally the message "a Top Secret secret" should be encrypted on that key. Your program's output ciphertext will be a string of hexadecimal digits. Please use the C or Pascal as a reference guide to these operations.

Two encryption schemes are possible: (1) XOR (Vernam) or (2) Caesar-shift mod 95 (Vigenère). XOR is the simplest; C-shifting offers greater security. You may choose either scheme, but please specify which you used. Here are the alternative sample outputs for checking purposes:

Message: a Top Secret secret
Key    : this is my secret key
XOR    : 1C0636190B1260233B35125F1E1D0E2F4C5422
MOD    : 734270227D36772A783B4F2A5F206266236978

No official seeding method for ISAAC has been published, but for this task we may as well just inject the bytes of our key into the randrsl array, padding with zeroes before mixing, like so:

// zeroise mm array
FOR i:= 0 TO 255 DO mm[i]:=0;
// check seed's highest array element
m := High(seed);
// inject the seed
FOR i:= 0 TO 255 DO BEGIN
	// in case seed[] has less than 256 elements.
	IF i>m THEN randrsl[i]:=0  
		ELSE randrsl[i]:=seed[i];
END;
// initialize ISAAC with seed
RandInit(true);

ISAAC can of course also be initialized with a single 32-bit unsigned integer in the manner of traditional RNGs, and indeed used as such for research and gaming purposes. But building a strong and simple ISAAC-based stream cipher - replacing the irreparably broken RC4 - is our goal here: ISAAC's intended purpose.

C

At the top is Bob Jenkins' reference code for ISAAC. Below and in main() is the task's working solution. <lang C> /* Known to compile and work with tcc in win32 & gcc on Linux (with warnings)

---

readable.c: My random number generator, ISAAC. (c) Bob Jenkins, March 1996, Public Domain You may use this code in any way you wish, and it is free. No warrantee.

---

• /

1. include <stdio.h>
2. include <stddef.h>

// maximum length of message

1. define MAXMSG 256

/* a ub4 is an unsigned 4-byte quantity */ typedef unsigned long int ub4;

/* external results */ ub4 randrsl[256], randcnt;

/* internal state */ static ub4 mm[256]; static ub4 aa=0, bb=0, cc=0;

void isaac() {

  register ub4 i,x,y;

  cc = cc + 1;    /* cc just gets incremented once per 256 results */
  bb = bb + cc;   /* then combined with bb */

  for (i=0; i<256; ++i)
  {
    x = mm[i];
    switch (i%4)
    {
    case 0: aa = aa^(aa<<13); break;
    case 1: aa = aa^(aa>>6); break;
    case 2: aa = aa^(aa<<2); break;
    case 3: aa = aa^(aa>>16); break;
    }
    aa              = mm[(i+128)%256] + aa;
    mm[i]      = y  = mm[(x>>2)%256] + aa + bb;
    randrsl[i] = bb = mm[(y>>10)%256] + x;
  }
  // not in original readable.c
  randcnt = 0;

}

/* if (flag!=0), then use the contents of randrsl[] to initialize mm[]. */

1. define mix(a,b,c,d,e,f,g,h) \

{ \

  a^=b<<11; d+=a; b+=c; \
  b^=c>>2;  e+=b; c+=d; \
  c^=d<<8;  f+=c; d+=e; \
  d^=e>>16; g+=d; e+=f; \
  e^=f<<10; h+=e; f+=g; \
  f^=g>>4;  a+=f; g+=h; \
  g^=h<<8;  b+=g; h+=a; \
  h^=a>>9;  c+=h; a+=b; \

}

void randinit(int flag) {

  int i;
  ub4 a,b,c,d,e,f,g,h;
  aa=bb=cc=0;
  a=b=c=d=e=f=g=h=0x9e3779b9;  /* the golden ratio */

  for (i=0; i<4; ++i)          /* scramble it */
  {
    mix(a,b,c,d,e,f,g,h);
  }

  for (i=0; i<256; i+=8)   /* fill in mm[] with messy stuff */
  {
    if (flag)                  /* use all the information in the seed */

{

      a+=randrsl[i  ]; b+=randrsl[i+1]; c+=randrsl[i+2]; d+=randrsl[i+3];
      e+=randrsl[i+4]; f+=randrsl[i+5]; g+=randrsl[i+6]; h+=randrsl[i+7];
    }
    mix(a,b,c,d,e,f,g,h);
    mm[i  ]=a; mm[i+1]=b; mm[i+2]=c; mm[i+3]=d;
    mm[i+4]=e; mm[i+5]=f; mm[i+6]=g; mm[i+7]=h;
  }

  if (flag)
  {        /* do a second pass to make all of the seed affect all of mm */

for (i=0; i<256; i+=8)

    {
      a+=mm[i  ]; b+=mm[i+1]; c+=mm[i+2]; d+=mm[i+3];
      e+=mm[i+4]; f+=mm[i+5]; g+=mm[i+6]; h+=mm[i+7];
      mix(a,b,c,d,e,f,g,h);
      mm[i  ]=a; mm[i+1]=b; mm[i+2]=c; mm[i+3]=d;
      mm[i+4]=e; mm[i+5]=f; mm[i+6]=g; mm[i+7]=h;
    }
  }

  isaac();            /* fill in the first set of results */
  randcnt=0;        /* prepare to use the first set of results */

}

// Get a random 32-bit value 0..MAXINT ub4 iRandom() { ub4 r = randrsl[randcnt]; ++randcnt; if (randcnt >255) { isaac(); randcnt = 0; } return r; }

// Get a random character in printable ASCII range char iRandA() { return iRandom() % 95 + 32; }

// Seed ISAAC with a string void iSeed(char *seed, int flag) { ub4 i,m; for (i=0; i<256; i++) mm[i]=0; m = strlen(seed); for (i=0; i<256; i++) { // in case seed has less than 256 elements

       if (i>m) randrsl[i]=0;  else randrsl[i] = seed[i];

} // initialize ISAAC with seed randinit(flag); }

// XOR encrypt on random stream. Output: ASCII string char* Vernam(char *msg) { ub4 i,l; char *ms = msg; char v[MAXMSG]; l = strlen(ms); // zeroise v for (i=0; i<MAXMSG; i++) v[i]=0; // XOR message for (i=0; i<l; i++) { v[i] = iRandA() ^ ms[i]; } return v; }

int main() { int n,l; char *msg = "a Top Secret secret"; char *key = "this is my secret key"; char *xctx= ""; char *mctx= ""; // seed ISAAC with key iSeed(key,1); l = strlen(msg); // Vernam XOR encrypt xctx = Vernam(msg); printf("Message: %s\n",msg); printf("Key  : %s\n",key); printf("XOR: "); // Output ciphertext as a string of hex digits for (n=0; n<l; n++) printf("%02X",xctx[n]); printf("\n");

} </lang> Sample output:

Message: a Top Secret secret
Key    : this is my secret key
XOR    : 1C0636190B1260233B35125F1E1D0E2F4C5422

Delphi

Translation of Pascal. <lang Delphi> {$apptype console} PROGRAM RosettaIsaac; USES SysUtils;

// TASK globals VAR msg : STRING = 'a Top Secret secret'; VAR key : STRING = 'this is my secret key'; VAR xctx: STRING = ; // XOR ciphertext VAR mctx: STRING = ; // MOD ciphertext

// ISAAC globals // external results VAR randrsl: ARRAY[0..256] OF CARDINAL; VAR randcnt: cardinal; // internal state VAR mm: ARRAY[0..256] OF CARDINAL; VAR aa: CARDINAL=0; bb: CARDINAL=0; cc: CARDINAL=0;

PROCEDURE Isaac; VAR i,x,y: CARDINAL; BEGIN

  cc := cc + 1;    // cc just gets incremented once per 256 results 
  bb := bb + cc;   // then combined with bb 

  FOR i := 0 TO 255 DO BEGIN
    x := mm[i];
    CASE (i mod 4) OF

0: aa := aa xor (aa shl 13); 1: aa := aa xor (aa shr 6); 2: aa := aa xor (aa shl 2); 3: aa := aa xor (aa shr 16);

    END;
    aa := mm[(i+128) mod 256] + aa;

y  := mm[(x shr 2) mod 256] + aa + bb;

    mm[i] := y; 	
    bb := mm[(y shr 10) mod 256] + x; 
    randrsl[i]:= bb; 
  END;
  // this reset was not in original readable.c!
  randcnt:=0;  // prepare to use the first set of results 

END; {Isaac}

// if (flag==TRUE), then use the contents of randrsl[] to initialize mm[]. PROCEDURE mix(VAR a,b,c,d,e,f,g,h: CARDINAL); BEGIN a := a xor b shl 11; d:=d+a; b:=b+c; b := b xor c shr 2; e:=e+b; c:=c+d; c := c xor d shl 8; f:=f+c; d:=d+e; d := d xor e shr 16; g:=g+d; e:=e+f; e := e xor f shl 10; h:=h+e; f:=f+g; f := f xor g shr 4; a:=a+f; g:=g+h; g := g xor h shl 8; b:=b+g; h:=h+a; h := h xor a shr 9; c:=c+h; a:=a+b; END; {mix}

PROCEDURE iRandInit(flag: BOOLEAN); VAR i,a,b,c,d,e,f,g,h: CARDINAL; BEGIN

  aa:=0; bb:=0; cc:=0;
  a:=$9e3779b9; 	// the golden ratio
  
  b:=a; c:=a; d:=a; e:=a; f:=a; g:=a; h:=a; 

  FOR i := 0 TO 3 DO          // scramble it 
       mix(a,b,c,d,e,f,g,h);
  
  i:=0;
  REPEAT  // fill in mm[] with messy stuff 

IF flag THEN BEGIN // use all the information in the seed

      a:=a+randrsl[i  ]; b:=b+randrsl[i+1]; c:=c+randrsl[i+2]; d:=d+randrsl[i+3];
      e:=e+randrsl[i+4]; f:=f+randrsl[i+5]; g:=g+randrsl[i+6]; h:=h+randrsl[i+7];
   END;
    
   mix(a,b,c,d,e,f,g,h);
   mm[i  ]:=a; mm[i+1]:=b; mm[i+2]:=c; mm[i+3]:=d;
   mm[i+4]:=e; mm[i+5]:=f; mm[i+6]:=g; mm[i+7]:=h;

i:=i+8;

  UNTIL i>255;

  IF (flag) THEN BEGIN
  // do a second pass to make all of the seed affect all of mm 
    i:=0;
    REPEAT
     a:=a+mm[i  ]; b:=b+mm[i+1]; c:=c+mm[i+2]; d:=d+mm[i+3];
     e:=e+mm[i+4]; f:=f+mm[i+5]; g:=g+mm[i+6]; h:=h+mm[i+7];
     mix(a,b,c,d,e,f,g,h);
     mm[i  ]:=a; mm[i+1]:=b; mm[i+2]:=c; mm[i+3]:=d;
     mm[i+4]:=e; mm[i+5]:=f; mm[i+6]:=g; mm[i+7]:=h;
     i:=i+8;
    UNTIL i>255; 
  END;
  isaac();           // fill in the first set of results 
  randcnt:=0;       // prepare to use the first set of results 

END; {randinit}

{ Seed ISAAC with a given string.

 The string can be any size. The first 256 values will be used.}

PROCEDURE iSeed(seed: STRING; flag: BOOLEAN); VAR i,m: CARDINAL; BEGIN FOR i:= 0 TO 255 DO mm[i]:=0; m := Length(seed)-1; FOR i:= 0 TO 255 DO BEGIN // in case seed has less than 256 elements

       IF i>m THEN randrsl[i]:=0  

// Pascal strings are 1-based ELSE randrsl[i]:=ord(seed[i+1]); END; // initialize ISAAC with seed iRandInit(flag); END; {iSeed}

{ Get a random 32-bit value 0..MAXINT } FUNCTION iRandom : Cardinal; BEGIN result := randrsl[randcnt]; inc(randcnt); IF (randcnt >255) THEN BEGIN Isaac(); randcnt := 0; END; END; {iRandom}

{ Get a random character in printable ASCII range } FUNCTION iRandA: BYTE; BEGIN result := iRandom mod 95 + 32; END;

{ convert an ASCII string to a hexadecimal string } FUNCTION ascii2hex(s: STRING): STRING; VAR i,l: CARDINAL; BEGIN result := ; l := Length(s); FOR i := 1 TO l DO result := result + IntToHex(ord(s[i]),2); END;

{ XOR encrypt on random stream. Output: string of hex chars } FUNCTION Vernam(msg: STRING): STRING; VAR i: CARDINAL; BEGIN result := ; FOR i := 1 to length(msg) DO result := result + chr(iRandA xor ord(msg[i])); result := ascii2hex(result); END;

{ Get position of the letter in chosen alphabet } FUNCTION letternum(letter, start: CHAR): byte; BEGIN result := (ord(letter)-ord(start)); END;

{ Caesar-shift a character <shift> places: Generalized Vigenere } FUNCTION Caesar(ch: CHAR; shift, modulo: INTEGER; start: CHAR): CHAR; VAR n: INTEGER; BEGIN n := letternum(ch,start) + shift; n := n MOD modulo; result := chr(ord(start)+n); END;

{ Vigenere mod 95 encryption. Output: string of hex chars } FUNCTION Vigenere(msg: STRING): STRING; VAR i: CARDINAL; BEGIN result := ; FOR i := 1 to length(msg) DO result := result + Caesar(msg[i],iRandA,95,' '); result := ascii2hex(result); END;

BEGIN // 1) seed ISAAC with the key iSeed(key,true); // 2) Vernam XOR encryption xctx := Vernam(msg); // 3) MOD encryption mctx := Vigenere(msg); // program output Writeln('Message: ',msg); Writeln('Key  : ',key); Writeln('XOR  : ',xctx); Writeln('MOD  : ',mctx); END. </lang> Sample output:

Message: a Top Secret secret
Key    : this is my secret key
XOR    : 1C0636190B1260233B35125F1E1D0E2F4C5422
MOD    : 734270227D36772A783B4F2A5F206266236978

Pascal

Free Pascal. A fully functional and complete reference solution of the task. <lang Pascal> PROGRAM RosettaIsaac; USES StrUtils;

// TASK globals VAR msg : STRING = 'a Top Secret secret'; VAR key : STRING = 'this is my secret key'; VAR xctx: STRING = ; // XOR ciphertext VAR mctx: STRING = ; // MOD ciphertext

// ISAAC globals // external results VAR randrsl: ARRAY[0..256] OF CARDINAL; VAR randcnt: cardinal; // internal state VAR mm: ARRAY[0..256] OF CARDINAL; VAR aa: CARDINAL=0; bb: CARDINAL=0; cc: CARDINAL=0;

PROCEDURE Isaac; VAR i,x,y: CARDINAL; BEGIN

  cc := cc + 1;    // cc just gets incremented once per 256 results 
  bb := bb + cc;   // then combined with bb 

  FOR i := 0 TO 255 DO BEGIN
    x := mm[i];
    CASE (i mod 4) OF

0: aa := aa xor (aa shl 13); 1: aa := aa xor (aa shr 6); 2: aa := aa xor (aa shl 2); 3: aa := aa xor (aa shr 16);

    END;
    aa := mm[(i+128) mod 256] + aa;

y  := mm[(x shr 2) mod 256] + aa + bb;

    mm[i] := y; 	
    bb := mm[(y shr 10) mod 256] + x; 
    randrsl[i]:= bb; 
  END;
  // this reset was not in original readable.c!
  randcnt:=0;  // prepare to use the first set of results 

END; {Isaac}

// if (flag==TRUE), then use the contents of randrsl[] to initialize mm[]. PROCEDURE mix(VAR a,b,c,d,e,f,g,h: CARDINAL); BEGIN a := a xor b shl 11; d:=d+a; b:=b+c; b := b xor c shr 2; e:=e+b; c:=c+d; c := c xor d shl 8; f:=f+c; d:=d+e; d := d xor e shr 16; g:=g+d; e:=e+f; e := e xor f shl 10; h:=h+e; f:=f+g; f := f xor g shr 4; a:=a+f; g:=g+h; g := g xor h shl 8; b:=b+g; h:=h+a; h := h xor a shr 9; c:=c+h; a:=a+b; END; {mix}

PROCEDURE iRandInit(flag: BOOLEAN); VAR i,a,b,c,d,e,f,g,h: CARDINAL; BEGIN

  aa:=0; bb:=0; cc:=0;
  a:=$9e3779b9; 	// the golden ratio
  
  b:=a; c:=a; d:=a; e:=a; f:=a; g:=a; h:=a; 

  FOR i := 0 TO 3 DO          // scramble it 
       mix(a,b,c,d,e,f,g,h);
  
  i:=0;
  REPEAT  // fill in mm[] with messy stuff 

IF flag THEN BEGIN // use all the information in the seed

      a+=randrsl[i  ]; b+=randrsl[i+1]; c+=randrsl[i+2]; d+=randrsl[i+3];
      e+=randrsl[i+4]; f+=randrsl[i+5]; g+=randrsl[i+6]; h+=randrsl[i+7];
   END;
    
   mix(a,b,c,d,e,f,g,h);
   mm[i  ]:=a; mm[i+1]:=b; mm[i+2]:=c; mm[i+3]:=d;
   mm[i+4]:=e; mm[i+5]:=f; mm[i+6]:=g; mm[i+7]:=h;

i+=8;

  UNTIL i>255;

  IF (flag) THEN BEGIN
  // do a second pass to make all of the seed affect all of mm 
    i:=0;
    REPEAT
     a+=mm[i  ]; b+=mm[i+1]; c+=mm[i+2]; d+=mm[i+3];
     e+=mm[i+4]; f+=mm[i+5]; g+=mm[i+6]; h+=mm[i+7];
     mix(a,b,c,d,e,f,g,h);
     mm[i  ]:=a; mm[i+1]:=b; mm[i+2]:=c; mm[i+3]:=d;
     mm[i+4]:=e; mm[i+5]:=f; mm[i+6]:=g; mm[i+7]:=h;
     i+=8;
    UNTIL i>255; 
  END;
  isaac();           // fill in the first set of results 
  randcnt:=0;       // prepare to use the first set of results 

END; {randinit}

{ Seed ISAAC with a given string.

 The string can be any size. The first 256 values will be used.}

PROCEDURE iSeed(seed: STRING; flag: BOOLEAN); VAR i,m: CARDINAL; BEGIN FOR i:= 0 TO 255 DO mm[i]:=0; m := Length(seed)-1; FOR i:= 0 TO 255 DO BEGIN // in case seed has less than 256 elements

       IF i>m THEN randrsl[i]:=0  

// Pascal strings are 1-based ELSE randrsl[i]:=ord(seed[i+1]); END; // initialize ISAAC with seed iRandInit(flag); END; {iSeed}

{ Get a random 32-bit value 0..MAXINT } FUNCTION iRandom : Cardinal; BEGIN iRandom := randrsl[randcnt]; inc(randcnt); IF (randcnt >255) THEN BEGIN Isaac(); randcnt := 0; END; END; {iRandom}

{ Get a random character in printable ASCII range } FUNCTION iRandA: BYTE; BEGIN iRandA := iRandom mod 95 + 32; END;

{ convert an ASCII string to a hexadecimal string } FUNCTION ascii2hex(s: STRING): STRING; VAR i,l: CARDINAL; BEGIN ascii2hex := ; l := Length(s); FOR i := 1 TO l DO ascii2hex += Dec2Numb(ord(s[i]),2,16); END;

{ XOR encrypt on random stream. Output: string of hex chars } FUNCTION Vernam(msg: STRING): STRING; VAR i: CARDINAL; BEGIN Vernam := ; FOR i := 1 to length(msg) DO Vernam += chr(iRandA xor ord(msg[i])); Vernam := ascii2hex(Vernam); END;

{ Get position of the letter in chosen alphabet } FUNCTION letternum(letter, start: CHAR): byte; BEGIN letternum := (ord(letter)-ord(start)); END;

{ Caesar-shift a character <shift> places: Generalized Vigenere } FUNCTION Caesar(ch: CHAR; shift, modulo: INTEGER; start: CHAR): CHAR; VAR n: INTEGER; BEGIN n := letternum(ch,start) + shift; n := n MOD modulo; Caesar := chr(ord(start)+n); END;

{ Vigenere mod 95 encryption. Output: string of hex chars } FUNCTION Vigenere(msg: STRING): STRING; VAR i: CARDINAL; BEGIN Vigenere := ; FOR i := 1 to length(msg) DO Vigenere += Caesar(msg[i],iRandA,95,' '); Vigenere := ascii2hex(Vigenere); END;

BEGIN // 1) seed ISAAC with the key iSeed(key,true); // 2) Vernam XOR encryption xctx := Vernam(msg); // 3) MOD encryption mctx := Vigenere(msg); // program output Writeln('Message: ',msg); Writeln('Key  : ',key); Writeln('XOR  : ',xctx); Writeln('MOD  : ',mctx); END. </lang> Sample output:

Message: a Top Secret secret
Key    : this is my secret key
XOR    : 1C0636190B1260233B35125F1E1D0E2F4C5422
MOD    : 734270227D36772A783B4F2A5F206266236978