Abstract
Stream ciphers are widely used for online-encryption of arbitrarily long data, for example when transmitting speech-data between a mobile phone and a base station. An important class of stream ciphers are combiners with memory, with the E 0 generator from the Bluetooth standard for wireless communication being their most prominent example. In this paper, we develop design principles for increasing the resistance of combiners with memory against the most dangerous types of cryptanalytic attacks, namely correlation attacks and algebraic attacks. In the case of algebraic attacks, we introduce the first method to guarantee lower bounds on the attack complexity. Starting from the design of the E 0 generator, we combine our results in order to construct ciphers that are simultaneously strengthened against both kinds of attacks. Our analysis shows that small changes in the design of E 0 already suffice to improve its security enormously.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Armknecht, F., Krause, M.: Algebraic Attacks on Combiners with Memory. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 162–175. Springer, Heidelberg (2003)
Armknecht, F.: Improving Fast Algebraic Attacks. In: Roy, B., Meier, W. (eds.) FSE 2004. LNCS, vol. 3017, pp. 65–82. Springer, Heidelberg (2004)
Armknecht, F., Lano, J., Preneel, B.: Extending the Resynchronization attack. In: Handschuh, H., Hasan, M.A. (eds.) SAC 2004. LNCS, vol. 3357, pp. 19–38. Springer, Heidelberg (2004)
Armknecht, F.: On the Existence of Low-Degree Equations for Algebraic Attacks, Cryptology ePrint Archive: Report 2004/185
Braeken, A., Lano, J.: On the (im)possibiliy of practical and secure nonlinear filters and combiners. In: Preneel, B., Tavares, S. (eds.) SAC 2005. LNCS, vol. 3897, pp. 159–174. Springer, Heidelberg (2006)
Courtois, N.T.: Fast Algebraic Attacks on Stream Ciphers with Linear Feedback. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 176–194. Springer, Heidelberg (2003)
Courtois, N.T., Klimov, A.B., Patarin, J., Shamir, A.: Efficient algorithms for solving overdefined systems of multivariate polynomial equations. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 392–407. Springer, Heidelberg (2000)
Dalai, D.K., Gupta, K.C., Maitra, S.: Cryptographically Significant Boolean Functions: Construction and Analysis in Terms of Algebraic Immunity. In: Gilbert, H., Handschuh, H. (eds.) FSE 2005. LNCS, vol. 3557, pp. 98–111. Springer, Heidelberg (2005)
Faugère, J.-C., Ars, G.: An Algebraic Cryptanalysis of Nonlinear Filter Generators using Gröbner Bases (2003), Available at http://www.inria.fr/rrrt/rr-4739.html
Golić, J.D.: Correlation via linear sequential circuit approximation of combiners with memory. In: Rueppel, R.A. (ed.) EUROCRYPT 1992. LNCS, vol. 658, pp. 113–123. Springer, Heidelberg (1993)
Golić, J.D.: Correlation Properties of General Binary Combiners with Memory. Journal of Cryptology 9(2), 111–126 (1996)
Hawkes, P., Rose, G.G.: Rewriting Variables: the Complexity of Fast Algebraic Attacks on Stream Ciphers. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 390–406. Springer, Heidelberg (2004)
Key, J.D., McDonough, T.P., Mavron, V.C.: Information sets and partial permutation decoding for codes from finite geometries. Preprint Clemson Univ., to appear in Finite Field Applic (2005)
Lu, Y., Vaudenay, S.: Faster Correlation Attack on the Bluetooth Keystream Generator. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 407–425. Springer, Heidelberg (2004)
Lu, Y., Vaudenay, S.: Cryptanalysis of Bluetooth Keystream Generator Two-Level E0. In: Lee, P.J. (ed.) ASIACRYPT 2004. LNCS, vol. 3329, pp. 483–499. Springer, Heidelberg (2004)
Meier, W., Pasalic, E., Carlet, C.: Algebraic Attacks and Decomposition of Boolean Functions. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 474–491. Springer, Heidelberg (2004)
Rueppel, R.A.: Analysis and Design of Stream Ciphers. Springer, Heidelberg (1986)
Salmasizadeh, M., Golić, J.D., Dawson, E.P., Simpson, L.R.: A Systematic Procedure for Applying Fast Correlation Attacks to Combiners with Memory, SAC 1997 (1997)
Siegenthaler, T.: Correlation Immunity of Nonlinear Combining Functions for Cryptographic Applications. IEEE Inform. Theory IT-30, 776–780 (1984)
The Bluetooth SIG: Bluetooth SIG Lays Out Roadmap for Bluetooth Wireless Technology, SIG press release, November 8 (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Armknecht, F., Krause, M., Stegemann, D. (2005). Design Principles for Combiners with Memory. In: Maitra, S., Veni Madhavan, C.E., Venkatesan, R. (eds) Progress in Cryptology - INDOCRYPT 2005. INDOCRYPT 2005. Lecture Notes in Computer Science, vol 3797. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11596219_9
Download citation
DOI: https://doi.org/10.1007/11596219_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-30805-8
Online ISBN: 978-3-540-32278-8
eBook Packages: Computer ScienceComputer Science (R0)