**Key differentiation attacks on stream ciphers**

*Enes Pasalic*

**Abstract: ** In this paper the applicability of differential cryptanalytic tool to stream
ciphers is elaborated using the algebraic representation similar to
early Shannon's postulates regarding the concept of confusion. In
2007, Biham and Dunkelman \cite{BihDunk}
have formally introduced the concept of differential
cryptanalysis in stream ciphers by addressing the three different
scenarios of interest. Here we mainly consider the first scenario
where the key difference and/or IV difference influence the internal
state of the cipher $(\Delta key, \Delta IV) \rightarrow \Delta S$.
We then show that under certain circumstances a chosen IV attack may
be transformed in the key chosen attack. That is,
whenever at some stage of the key/IV setup algorithm (KSA) we may
identify linear relations between some subset of key and IV bits,
and these key variables only appear through these linear relations, then
using the differentiation of internal state variables (through chosen
IV scenario of attack) we are able to
eliminate the presence of corresponding key variables. The method
leads to an attack whose complexity is beyond the exhaustive
search, whenever the cipher admits exact algebraic description of
internal state variables and the keystream computation is not
complex. A successful application is especially noted in the
context of stream ciphers whose keystream bits evolve relatively slow
as a function of secret state bits. A modification of the attack
can be applied to the TRIVIUM stream cipher \cite{Trivium}, in this case
12 linear relations could be identified but at the same time the same
12 key variables appear in another part of state register. Still, a
significant decrease in the degree and complexity of state bit
expressions after the KSA is achieved. Computer simulations,
currently in progress,
will answer the question for what number of
initialization rounds the attack is faster than exhaustive search.

**Category / Keywords: **Key related attacks, Chosen IV attacks, Key differentiation, Trivium

**Date: **received 16 Oct 2008, last revised 5 Dec 2008

**Contact author: **enespasalic at yahoo se

**Available format(s): **PDF | BibTeX Citation

**Note: **The original submission contains a small error overlooked by the author, which though substantially impact the application of the attack on Trivium. Namely, due to the appearance of the same subset of key bits for which linear relations exist, the original attack is not directly applicable to Trivium. Modified version of attack is added. This implies that Trivium is still theoretically sound, though the modified version of attack requires an optimal key/IV mixture in the KSA of Trivium to resist the attack. Computer simulations (time demanding ) are currently in progress that will finally answer how many rounds of reduced setup we can attack.

**Version: **20081205:162637 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]