# A5/2 session key derivation

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

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.

• Thanks, but it is not clear for me how multiplication matrix($S$) created? If it is scalar, how we can build it? – R. Jalaei Salahi Dec 29 '19 at 12:59