Reference : New Cryptanalysis of Irregularly Decimated Stream Ciphers.
Scientific congresses, symposiums and conference proceedings : Paper published in a book
Social & behavioral sciences, psychology : Multidisciplinary, general & others
Engineering, computing & technology : Computer science
New Cryptanalysis of Irregularly Decimated Stream Ciphers.
Zhang, Bin [University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC) >]
Selected Areas in Cryptography
Lecture Notes in Computer Science, 5867
16th Annual International Workshop, SAC 2009
August 13-14, 2009
Calgary, AB
[en] 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-∐, 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-∐ can be recovered reliably in 272.5 operations, if 224.1-bit keystream and 274.1-bit memory are available. This disproves the designers’ conjecture that the complexity of any divide-and-conquer attack on LILI-∐ is in excess of 2128 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.

File(s) associated to this reference

Fulltext file(s):

Limited access
Zhang.pdfPublisher postprint353.16 kBRequest a copy

Bookmark and Share SFX Query

All documents in ORBilu are protected by a user license.