zbMATH — the first resource for mathematics

New cryptanalysis of irregularly decimated stream ciphers. (English) Zbl 1267.94106
Jacobson, Michael J. jun. (ed.) et al., Selected areas in cryptography. 16th annual international workshop, SAC 2009, Calgary, Alberta, Canada, August 13–14, 2009. Revised selected papers. Berlin: Springer (ISBN 978-3-642-05443-3/pbk). Lecture Notes in Computer Science 5867, 449-465 (2009).
Summary: In this paper we investigate the security of irregularly decimated stream ciphers. We present an improved correlation analysis of various irregular decimation mechanisms, which allows us to get much larger correlation probabilities than previously known methods. Then new correlation attacks are launched against the shrinking generator with Krawczyk’s parameters, LILI-\(\Pi\), DECIM\(^{v2}\) and DECIM-128 to access the security margin of these ciphers. We show that the shrinking generator with Krawczyk’s parameters is practically insecure; the initial internal state of LILI-\(\Pi \) can be recovered reliably in \(2^{72.5}\) operations, if \(2^{24.1}\)-bit keystream and \(2^{74.1}\)-bit memory are available. This disproves the designers’ conjecture that the complexity of any divide-and-conquer attack on LILI-\(\Pi \) is in excess of \(2^{128}\) operations and requires a large amount of keystream. We also examine the main design idea behind DECIM, i.e., to filter and then decimate the output using the ABSG algorithm, by showing a class of correlations in the ABSG mechanism and mounting attacks faster than exhaustive search on a 160-bit (out of 192-bit) reduced version of DECIM\(^{v2}\) and on a 256-bit (out of 288-bit) reduced version of DECIM-128. Our result on DECIM is the first nontrivial cryptanalytic result besides the time/memory/data tradeoffs. While our result confirms the underlying design idea, it shows an interesting fact that the security of DECIM rely more on the length of the involved LFSR than on the ABSG algorithm.
For the entire collection see [Zbl 1177.94012].

94A60 Cryptography
Full Text: DOI