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

Question

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?

Answer 1

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.

Answer 2

Please ignore this answer, it is a formatting test for this.

For $\LaTeX$/MathJax see this. $n=1$.