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.
Metadata
 Available format(s)
 Publication info
 Published elsewhere. Unknown where it was published
 Keywords
 Key related attacksChosen IV attacksKey differentiationTrivium
 Contact author(s)
 enespasalic @ yahoo se
 History
 20081205: revised
 20081020: received
 See all versions
 Short URL
 https://ia.cr/2008/443
 License

CC BY
BibTeX
@misc{cryptoeprint:2008/443, author = {Enes Pasalic}, title = {Key differentiation attacks on stream ciphers}, howpublished = {Cryptology {ePrint} Archive, Paper 2008/443}, year = {2008}, url = {https://eprint.iacr.org/2008/443} }