Paper 2008/443

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.

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.