Let talk about Implementation and performance analysis of Barkan, Biham and Keller’s attack on A5/2. In this paper, mentioned that we need to brute force attack on register 4 ($R_4$) to get keystream from below:

$$HP^{-1}C=HP^{-1}K. \tag{1}$$ Where $HP^{-1}$ is parity check and $C$ is ciphertext and $K$ is keystream.

On the other hand, the equations on the key stream must be adapted into equations on the variables of the $LFSRs$. So we have the following linear system:

$$Sr=K. \tag{2}$$

where $S$ is multiplication matrix of size $1368*656$ and $K$ is the concatenation of $3$ unknown key streams $k_1$, $k_2$, and $k_3$, and $r$ is the vector of unknowns representing the state of the $LFSRs$.

  1. Where is $R_4$ influence in the first equation?

  2. How we can construct the second equation(Please with details)?


1 Answer 1


The authors state in 4.3 that the design of the cipher has the following clever feature:

The dependencies between the LFSRs and the keystream vary greatly with the initial value of $R_4$ and since the variables of $R_4$ play no role in the value of the keystream, so it is not possible to find them.

So, later on they suggest the values of $R_4$ must be bruteforced, as a precomputation.

As for your question 2, you need to plug things in, as in the equations at the end of section 4.3.

  • $\begingroup$ Thanks, but it is not clear for me how multiplication matrix($S$) created? If it is scalar, how we can build it? $\endgroup$
    – R_Jalaei
    Commented Dec 29, 2019 at 12:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.