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.
Type de document :
Article dans une revue
Cryptography and Communications - Discrete Structures, Boolean Functions and Sequences , Springer, 2012, 4 (3-4), pp.147-171. 〈10.1007/s12095-012-0069-3〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01110510
Contributeur : Anne Canteaut <>
Soumis le : mercredi 28 janvier 2015 - 13:13:56
Dernière modification le : mardi 17 avril 2018 - 11:28:15

Identifiants

Collections

Citation

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〉

Partager

Métriques

Consultations de la notice

118