This is a construction for inline generators (bit generators which take input) which combines five generators to increase the complexity of the system. The construction can either operate in generator or inline generator mode (taking input or not).

The idea is to have three inline generators in series, a fourth parallel to the first two, and the fifth parallel to the second two. The output is recombined using an exclusive or operation.

The device as pictured above has self-feedback. The input to the two left generators could be replaced by an input, making the entire construction an inline generator.

Analysis

Using my program stat, this produces well-distributed pseudorandom bits on the example initial state. This is not surprising, for the output of the final skipstate generator should be well distributed regardless of the input.

This should definitely be at least as secure as each generator. However, even knowing one of the generators does not give you much; the parallelizing seems to make it very difficult to correlate the effects of each bit.

The weakest part of this might be the feedback mechanism; if you know the output stream then you know the input feedback. Operating this in inline-generator mode would of course alleviate that problem.

Improvements

The use of different inline generators (skipstate LFSRs are used below).

Expanding this to patterns which include more generators.

Feedback within the device (this seems to make it less elegant).

Implementation

/*
   C Implementation of a Tom7-bridge device 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.

     Tom 7

   http://tom7.org/

*/

#include 

#define INPUT_SKIPSTATE 1

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

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

LFSR G[5] ={
     {0xFEEDBABE,(1<<30)|(1<<12),30,0},
     {0xDEAFDAD ,(1<<18)|(1<<4)|(1<<1)|1,18,0},
     {0xFEEDF00D,(1<<16)|(1<<4),16,0},
     {0xBADCAB  ,(1<<12)|(1<<3)|(1<<2)|1,12,0},
     {0xDEADBEEF,(1<<31)|(1<<6)|(1<<4)|(1<<2)|(1<<1)|1,31,0},
};

/*
(no keys here; just some arbitrary initialization vectors for the LFSRs.
 This is just for demonstration!)
*/

main (int argc, char**argv) {
     int z,last=0;

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

   while (z--) {
        G[0].inputs = G[0].inputs = last; /* top, left*/
        G[2].inputs = G[3].inputs = sgenerator(&G[0]); /* middle, bottom */
        G[4].inputs = sgenerator(&G[1]) ^ sgenerator(&G[2]); /* right */
        last = sgenerator(&G[3]) ^ sgenerator(&G[4]);
        putchar('0'+last);
   }
}

unsigned char sgenerator(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++;
     if (g->data & 1) {
          g->data = ((g->data ^ g->mask) >> 1)
               | (1<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.