This is a modification to any clocked generator which allows feedback different from the clock and improves over 'shrinking' type generators.

Analysis

I believe that this is a better solution than using the clock for feedback or 'shrinking' the generator. Shrinking provides good random properties but is nondeterministic -- you are not guaranteed to get an output in a finite amout of time. This seems unrealistic for implementation, particularly in hardware. Clocking the generator is deterministic but tends to produce longer strings of 1's and 0's (when the generator remains unclocked, it produces the same output as in its last state). Poorly designed clocking feedback can also yield embarassing locking states, where none of the generators are being clocked and continue to produce the same output.

Skipstate uses a separate 'skipstate' input, which is like a second clock. When skipstate is high and clock is high (at time t-1), the generator advances two states and outputs a bit. When clock is high but skipstate is low, it advances one state and outputs a bit. When clocks is low, the state is not advanced. In general, the clock input remains permanently high in a skipstate generator.

If the original generator has a statistically random output, the output from a skipstate generator (no matter what the input on the skipstate line is, as long as it is independent) should also be statistically random.

Improvements

See some skipstate generator constructions.

It is my opinion that inelegance is often an indicator of poorness. It strikes me that there were a few inelegant (arbitrary) decisions made:

• Why skip one state, and not two or three?
• When the clock input is low, why not advance the state anyway when the skipstate line is high?

Other variations of the skipstate generator might include:

• skipstate-register: a register of arbitrary size controls the amount of states skipped when the skipstate line goes high. This register might be the outputs of log₂(n) generators, or a counter which is incremented by some other source.
• skipstate-multi: a generator with multiple skipstate inputs; skip 1, skip 2, skip 4, skip 8, etc. forming a power sequence so that any number of states can be skipped depending on the combination of inputs.
• skipstate-alternate: Same as standard skipstate, but when the clock input is low, the internal state will still advance one cycle if skipstate was high at time t-1.

Implementation

/*
   C Implementation of Tom7-skipstate generator (using LFSR).
   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 skipstate_generator(LFSR * g);

LFSR G[2] = {
     {0xDEADBEEF,(1<<31)|(1<<6)|(1<<4)|(1<<2)|(1<<1)|1,31,0},
     {0xFEEDBABE,(1<<29)|(1<<5)|(1<<3)|1,29,0},
};

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

 G[0] is our skipstate generator; G[1] drives it.
*/

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

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

     while (z--) {
          G[0].inputs = generator(&G[1]);
          putchar('0' + skipstate_generator(&G[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++;
     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.