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)?


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 Salahi Dec 29 '19 at 12:59

Your Answer

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

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