Alternating step generator

In cryptography, an alternating step generator (ASG) is a cryptographic pseudorandom number generator intended to be used in a stream cipher. The design was published in 1987 by C. G. Günther. It is also known as the alternating stop-and-go generator.

Overview

An ASG comprise three linear feedback shift registers. For each bit produced, LFSR2 is clocked, and either LFSR0 or LFSR1 is clocked, depending on the output of LFSR2. The output is the Exclusive-OR of the last bit produced by LFSR0 and LFSR1. The initial state of the LFSRs is the key.

Customarily, the LFSRs use primitive polynomials of distinct but close degree, preset to non-stationary state, so that each LFSR generates a maximum-length sequence. With such hypothesis, the ASG's output demonstrably has long period, high linear complexity, and even distribution of short subsequences.

Illustration, in C:

// 16-bit toy ASG (much too small for practical usage); return 0 or 1.
 unsigned ASG16toy(void)
  {
  static unsigned // unsigned type with at least 16 bits
    lfsr2  = 0x8102, // initial state, 16 bits, must not be 0
    lfsr1  = 0x4210, // initial state, 15 bits, must not be 0
    lfsr0  = 0x2492; // initial state, 14 bits, must not be 0
// LFSR2 use  x^^16 + x^^14 + x^^13 + x^^11 + 1
  lfsr2 = (-(lfsr2&1))&0x8016 ^ lfsr2>>1;
  if (lfsr2&1)
// LFSR1 use  x^^15 + x^^14 + 1
    lfsr1 = (-(lfsr1&1))&0x4001 ^ lfsr1>>1;
  else
// LFSR0 use  x^^14 + x^^13 + x^^3 + x^^2 + 1
    lfsr0 = (-(lfsr0&1))&0x2C01 ^ lfsr0>>1;
  return (lfsr0 ^ lfsr1)&1;
  }

An ASG is very simple and efficient to implement in hardware. In particular, contrary to the shrinking generator and self-shrinking generator, an output bit is produced at each clock.

Security

The creator of the present Wikipedia entry did not locate a reference to any attack of complexity less than $O(2^{n})$ where $n$ is the size of the shortest of the three LFSR, under the assumption that the initial state of the LFSRs is independently choosen at random.

References

C. G. Günther. Alternating step generators controlled by de Bruijn sequences, Advances in Cryptology - EuroCrypt '87 (p5-14), LNCS 304, Springer Verlag, ISBN 3-540-19102-X. See [1]. May be freely available as [2].
Schneier, Bruce. Applied Cryptography (p383-384), Second Edition, John Wiley & Sons, 1996. ISBN 0-471-11709-9