# Proof that Alternating Step Generator and modifed ASG' have equivalent security?

The Alternating Step Generator (ASG) is a PRNG combining 3 LFSRs. Output of the ASG is the XOR of the output of two clock-gated LFSRs. At each step, a single one of these LFSRs is clocked, according to the output of the control LFSR.

The best (AFAIK) claimed attack on the ASG is Reduced Complexity Attacks on the ASG (Slides). However it attacks a variant ASG', which output is the output of the clock-gated LFSR that was clocked.

Justification given in that paper is: It is known [13, 8, 12] that instead of working with the original definition of ASG we can consider a slightly different description (..). [13] only states It is not hard to show that ASG and ASG’ are equivalent (..) with no argument. I fail to find a discussion about ASG' in [8]. [12] has a constructive proof, but I fail to get it (unless I assume that one of the LFSR is known/enumerated).

Any clue on a proof/sketch/argument that an attack on ASG' reconstructing the initial states of the LFSRs can be turned into an equally efficient attack on ASG?

-

Okay, I had a look at your source [12], e.g. ON EDIT DISTANCE ATTACK TO ALTERNATING STEP GENERATOR.

The original ASG defines the key stream Z = {z_i} from three shift registers X = {x_i}, Y = {y_i} and C = {c_i} via these steps:

1. Initially, l = 0, t = 1.
2. If ct = 1, then l = l + 1;
3. Output z_t = x_l ⊕ y_(t−l) , where ⊕ is XOR operator;
4. t = t + 1 and go to step 2.

E.g. we step one them depending on c_t, and use the latest output of both.

For the variant, we define w_i = z_i ⊕ z_(i-1), u_i = x_i ⊕ x_(i-1), v_i = y_i ⊕ y_(i-1), e.g simply the "difference sequences" of the original ones.

U = {u_i} and V = {v_i} can easily be created by LFSRs of the same length as these for X and Y, simply by adding or removing one feedback link. (And if we have the registers for U and V, we can get the registers for X and Y back.)

It now shows that we can derive W = {w_i} not only directly from Z, but also from U, V and C, using the modified construction:

1. Initially l = 0, t = 1;
2. If c_t = 1, then l = l + 1 and output w_t = u_l ;
3. If c_t = 0, output w_t = v_(t−l).
4. t = t + 1, go to step 2.

Why? Simply put the formulas:

If c_t = 1, then

w_t =      z_t        ⊕        z_(t-1)
= (x_l ⊕ y_(t−l)) ⊕ (x_(l-1) ⊕ y_((t-1)−(l-1)))
= (x_l ⊕ x_(l-1)) ⊕ (y_((t-1)−(l-1)) ⊕ y_(t−l))
=      u_l        ⊕ (y_(t−l) ⊕ y_(t−l))
=      u_l        ⊕         0
=      u_l.


If c_t = 0, then

w_t =     z_t         ⊕     z_(t-1)
= (x_l ⊕ y_(t−l)) ⊕ (x_l ⊕ y_((t-1)−l))
= (x_l ⊕ x_l) ⊕ (y_(t−l) ⊕ y_((t-1)−l)
=       0     ⊕ (y_(t−l) ⊕ y_((t-l)−1)
=       0     ⊕      v_(t-l)
=                    v_(t-l).


It is a bit confusing because of 1 and l looking quite similar here.

So, how would we do our attack on Z, given an attack on W?

1. Transform the observed sequence of Z into a sequence for W, by calculating differences of consecutive elements.
2. Break W, get formulas for C, U and V.
3. Transform the formulas for U and V back into these for X and Y by adding/removing one feedback link.
-
Many thanks. I had missed that proof sketch. –  fgrieu Aug 18 '11 at 6:33
A minor detail: while the "difference sequence" U for X has the same linear complexity as X, going from one to the other is not quite adding or removing a tap. E.g. with the poly x^2+x+1 the sequence X is 110110110110.., U is 01101101101.. and has the same poly. Which is not surprising as there –  fgrieu Aug 18 '11 at 10:34
More generally, adding or removing a coefficient from a primitive polynomial leaves us with a non-primitive polynomial, so the relationship must be something else. It remains that an attack breaking ANY ASG' (for some polynomial sizes) with some probability breaks any ASG (with same polynomial sizes). –  fgrieu Aug 18 '11 at 10:45
You are right, simply adding/removing a link does not fit it - we would need a link from the original register, not from our own register. –  Paŭlo Ebermann Aug 18 '11 at 14:19
Thinking about it: the "difference sequence" U for X uses the same polynomial as X, just a different initial state, which can be obtained by XORing the initial state of X, and its states after one step. Getting back from U to X is nearly as trivial. Therefore, we do not need the ANY in my above comment. –  fgrieu Aug 18 '11 at 21:20