This is a method of combining inline generators of any sort (in the code below I use LFSR skipstate generators) in a way which increases the complexity of the system.

The idea is to use eight inline generators to select a byte from a key-dependent permutation of bytes. The output is used as the input to the generators in the next round, and a 8-bit wraparound counter is also xor'd with the output of the generators before entering the p-box.

Because the 8-bit counter ensures that the output from the generators can select any byte, even if it remains constant, the generators can have rather weak random properties without severely compromising the device's effectiveness (ie, sending it into a short cycle). Clocked LFSR's probably would not be too devastating.

Of course, it makes more sense to use proper generators. In the implementation below I've used LFSR skipstate generators; anything else with good random properties is candidate, and the generators do not have to all be the same type (combining types, in fact, is a very sound idea).

The code below initializes the p-box in the same manner as RC4, and initializes the generators as in Tom7-fselect.

Analysis

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

The biggest weakness I see in this is that the P-Box does not change. This seems to make a known-plaintext pretty reasonable.

Improvements

The P-Box does not change. I tried to think of an elegant way to make it change without totally ripping off RC4, but failed. It would greatly increase security to have the P-Box change. Since the P-Box must change by the key in this implementation anyway, this should not make hardware implementations much more difficult or expensive.

The code below uses generators with periods which are not all relatively prime. I highly recommend using generators which are; my source of data Applied Cryptography did not have enough.

LFSRs are considered insecure and probably should not be used.

Implementation

This implementation just spits out the bits in ascii notation as my other programs do, something like:

while (EOF != (a=getc(stdin))) {
     ... get output byte ...
     putchar(a ^ output);
}

Would be a more appropriate main loop for a filter interface (note that DOS will not handle binary redirection well, but this will work under unix).

/*
   C Implementation of Tom7-byteselect generator (using skipstate LFSRs).
   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.

   If you implement this, use generators which have lengths that are
   relatively prime, and combine different types of generators.

     Tom 7

   http://tom7.org/

*/

#include <stdio.h>
#include <stdlib.h>

#define INPUT_SKIPSTATE 1

#define s(a,b,c) m=a[(b)];a[(b)]=a[(c)];a[(c)]=m;
// swap bytes b and c in array a

typedef struct {
     unsigned long data;
     unsigned long mask;
     unsigned char len;
     unsigned char inputs;
} LFSR;

unsigned char           generator(LFSR * g);
unsigned char skipstate_generator(LFSR * g);

LFSR G[8] = {
     {0,(1<<31)|(1<<6)|(1<<4)|(1<<2)|(1<<1)|1,31,0},
     {0,(1<<29)|(1<<5)|(1<<3)|1,29,0},
     {0,(1<<30)|(1<<12),30,0},
     {0,(1<<18)|(1<<4)|(1<<1)|1,18,0},
     {0,(1<<16)|(1<<4),16,0},
     {0,(1<<12)|(1<<3)|(1<<2)|1,12,0},
     {0,(1<<31)|(1<<6)|(1<<2)|(1<<1)|1,31,0},
     {0,(1<<22)|(1<<4),22,0}
};

int main (int argc, char**argv) {
     int x,z,c,a,m,s;
     unsigned char output=0,counter=0;
     unsigned char P[256],K[256],j;
     char * key = argv[1];

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

     s = strlen(key);
     for (x=c=0;x<8;x++) {
          G[x].data |= key[c++%s] << 24;
          G[x].data |= key[c++%s] << 16;
          G[x].data |= key[c++%s] << 8 ;
          G[x].data |= key[c++%s]      ;
          a = key[c++%s]; while (a--) generator(&G[x]);
     }

     for (x=0;x<256;x++) K[P[x]=x]=key[x%s];
     for (x=j=0;x<256;x++) { j+=P[x]+K[x]; s(P,x,j); }

/* Filled LFSR's, P-Box with key-dependent material */

     if (argc>2) z = atoi(argv[2]); else z=1000;

     while (z--) {
          for (x=0;x<8;x++) G[x].inputs = (output>>x)&1;
          output = counter++;
          for (x=0;x<8;x++) output ^= skipstate_generator(&G[x])<<x;
          output = P[output];
          for (x=0;x<8;x++) putchar('0' + ((output>>x)&1));
     }
     return 0;
}

unsigned char skipstate_generator(LFSR * g) {
     if (g->inputs & INPUT_SKIPSTATE) generator(g);
     g->inputs &= ~INPUT_SKIPSTATE;
     return generator(g);
}

unsigned char generator(LFSR * g) {
     if (!g->data) g->data--; /* LFSR cannot hold 0, or it will cycle */
     if (g->data & 1) {
          g->data = ((g->data ^ g->mask) >> 1)
               | (1<<g->len); /* g->len is already len-1 */
          return 1;
     } else {
          g->data>>=1; return 0;
     }
}

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