Skip to Main content Skip to Navigation
Journal articles

Correlation attacks on combination generators

Abstract : The combination generator is a popular stream cipher construction. It consists of several independent devices working in parallel whose outputs are combined by a Boolean function. The output of this function is the keystream. The security of this generator has been extensively studied in the case where the devices are LFSRs. Some particular cases where the devices are nonlinear have also been studied, most notably the different versions of the eSTREAM proposal named Achterbahn. Several cryptanalysis techniques against these ciphers have been published, extending the classical correlation attack. But each of these attacks has been presented mainly in a very particular scenario. Therefore, this paper aims at generalising these methods to any combination generator in order to be able to compare their respective advantages and to determine the optimal attack for each particular generator. Generic formulas for the data-time-space complexities are then provided, which only depend on the number of devices, their periods and the number of their internal states and of the Boolean combining function. Some of the considered improvements can also be used in a much more general context, which includes linear attacks against some block ciphers.
Document type :
Journal articles
Complete list of metadatas
Contributor : Anne Canteaut <>
Submitted on : Wednesday, January 28, 2015 - 1:13:56 PM
Last modification on : Friday, May 25, 2018 - 12:02:05 PM




Anne Canteaut, María Naya-Plasencia. Correlation attacks on combination generators. Cryptography and Communications - Discrete Structures, Boolean Functions and Sequences , Springer, 2012, 4 (3-4), pp.147-171. ⟨10.1007/s12095-012-0069-3⟩. ⟨hal-01110510⟩



Record views