10
$\begingroup$

The Alternating Step Generator was proposed by Christoph G. Günther: Alternating step generators controlled by de Bruijn sequences, in proceedings of Eurocrypt 1987. It's perhaps the conceptually simplest CSPRNG producing bits at a constant rate. Its best-known cryptanalysis is by Shahram Khazaei, Simon Fischer, and Willi Meier: Reduced Complexity Attacks on the Alternating Step Generator, in proceedings of SAC 2007.

The ASG combines three Linear Feedback Shift Registers. To produce a bit:

  • advance LFSR2
  • according to its low-order bit, advance LFSR0 or LFSR1
  • output the XOR of the low order bits of LFSR0 and LFSR1

ASG

The key is the initial state of the LFSRs (assumed to be random and independent bits, save for the state of each LFSR not being all-zero). It is customary to use primitive binary polynomials of distinct degree $n_i$. In the initial exposition, LFSR2 is modified to generate a de Bruijn sequence, that is the output sequence has an extra zero inserted after $n_2-1$ consecutive zeroes. But this detail makes no cryptanalytic difference, since that point in the sequence is reached with negligible probability for $n_2$ large enough for security.

Would using binary trinomials sizably reduce the cryptanalytic resistance of the ASG?

The rationale to want to use trinomial:

$\endgroup$
  • $\begingroup$ You could begin by asking "why is the original ASG so hard to break". One possible explanation is that the random clocking causes LFSR0 and LFSR1 to behave as "sticky channels" with no error correcting bits. What is the channel capacity of such a channel? Now invoke Yao's XOR lemma by XOR'ing both sticky channels and you have something very hard to analyze. $\endgroup$ – William Hird Nov 5 '18 at 1:34
  • $\begingroup$ @WilliamHird what is the channel capacity of "sticky channels with no error correcting bits"? $\endgroup$ – kodlu Nov 6 '18 at 13:41
  • $\begingroup$ @kodlu: I don't know, let's "channel" (pun intended) Michael Mitzenmacher and find out , :-) $\endgroup$ – William Hird Nov 6 '18 at 16:09
  • $\begingroup$ @kodlu: Actually, I just saw your profile, it says you dabble in coding and information theory. What do you think the channel capacity is for the IID sticky channel if it is just a raw channel, ie., no error correction bits? $\endgroup$ – William Hird Nov 6 '18 at 23:22
  • $\begingroup$ I was asking since I am unsure what the definition of the sticky channel is $\endgroup$ – kodlu Nov 7 '18 at 0:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.