Abstract
Feedback with Carry Shift Registers (FCSRs) have been first proposed in 2005 by F. Arnault and T. Berger as a promising alternative to LFSRs for the design of stream ciphers. The original proposal called F-FCSR simply filters the content of a FCSR in Galois mode using a linear function. In 2008, Hell and Johannson attacked this version using a method called LFSRization of F-FCSR. This attack is based on the fact that a single feedback bit controls the values of all the carry cells. Thus, a trail of 0 in the feedback bit annihilates the content of the carry register, leading to transform the FCSR into an LFSR during a sufficient amount of time.
Following this attack, a new version of F-FCSR was proposed based on a new ring FCSR representation that guarantees that each carry cell depends on a distinct cell of the main register. This new proposal prevents the LFSRization from happening and remains unbroken since 2009. In parallel, Alaillou, Marjane and Mokrane proposed to replace the FCSR in Galois mode of the original proposal by a Vectorial FCSR (V-FCSR) in Galois mode.
In this paper, we first introduce a general theoretical framework to show that Vectorial FCSRs could be seen as a particular case of classical FCSRs. Then, we show that Vectorial FCSRs used in Galois mode stay sensitive to the LFSRization of FCSRs. Finally, we demonstrate that hardware implementations of V-FCSRs in Galois mode are less efficient than those based on FCSRs in ring mode.
This work was partially supported by the French National Agency of Research: ANR-11-INS-011.
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
Allailou, B., Marjane, A., Mokrane, A.: Design of a Novel Pseudo-Random Generator Based on Vectorial FCSRs. In: Chung, Y., Yung, M. (eds.) WISA 2010. LNCS, vol. 6513, pp. 76–91. Springer, Heidelberg (2011)
Arnault, F., Berger, T.P., Pousse, B., Minier, M.: Revisiting LFSRs for cryptographic applications. IEEE Transactions on Information Theory 57(12), 8095–8113 (2011)
Arnault, F., Berger, T.P., Pousse, B.: A matrix approach for FCSR automata. Cryptography and Communications 3(2), 109–139 (2011)
Arnault, F., Berger, T.P., Lauradoux, C.: The F-FCSR primitive specification and supporting documentation. In: ECRYPT - Network of Excellence in Cryptology, Call for stream Cipher Primitives (2005), http://www.ecrypt.eu.org/stream/
Arnault, F., Berger, T.P.: F-FCSR: Design of a New Class of Stream Ciphers. In: Gilbert, H., Handschuh, H. (eds.) FSE 2005. LNCS, vol. 3557, pp. 83–97. Springer, Heidelberg (2005)
Arnault, F., Berger, T.P., Lauradoux, C., Minier, M.: X-FCSR – A New Software Oriented Stream Cipher Based Upon FCSRs. In: Srinathan, K., Rangan, C.P., Yung, M. (eds.) INDOCRYPT 2007. LNCS, vol. 4859, pp. 341–350. Springer, Heidelberg (2007)
Arnault, F., Berger, T., Lauradoux, C.: F-FCSR Stream Ciphers. In: Robshaw, M., Billet, O. (eds.) New Stream Cipher Designs. LNCS, vol. 4986, pp. 170–178. Springer, Heidelberg (2008)
Arnault, F., Berger, T., Lauradoux, C., Minier, M., Pousse, B.: A New Approach for FCSRs. In: Jacobson Jr., M.J., Rijmen, V., Safavi-Naini, R. (eds.) SAC 2009. LNCS, vol. 5867, pp. 433–448. Springer, Heidelberg (2009)
Arnault, F., Berger, T.P., Minier, M.: Some Results on FCSR Automata With Applications to the Security of FCSR-Based Pseudorandom Generators. IEEE Transactions on Information Theory 54(2), 836–840 (2008)
Berger, T.P., Minier, M., Pousse, B.: Software Oriented Stream Ciphers Based upon FCSRs in Diversified Mode. In: Roy, B., Sendrier, N. (eds.) INDOCRYPT 2009. LNCS, vol. 5922, pp. 119–135. Springer, Heidelberg (2009)
Klapper, A., Xu, J.: Algebraic Feedback Shift Registers. Theoretical Computer Science 226, 61–93 (1999)
Goresky, M., Klapper, A.: Fibonacci and Galois representations of feedback-with-carry shift registers. IEEE Transactions on Information Theory 48(11), 2826–2836 (2002)
Hell, M., Johansson, T.: Breaking the F-FCSR-H Stream Cipher in Real Time. In: Pieprzyk, J. (ed.) ASIACRYPT 2008. LNCS, vol. 5350, pp. 557–569. Springer, Heidelberg (2008)
Klapper, A., Goresky, M.: 2-Adic Shift Registers. In: Anderson, R. (ed.) FSE 1993. LNCS, vol. 809, pp. 174–178. Springer, Heidelberg (1994)
Marjane, A., Allailou, B.: Vectorial Conception of FCSR. In: Carlet, C., Pott, A. (eds.) SETA 2010. LNCS, vol. 6338, pp. 240–252. Springer, Heidelberg (2010)
eSTREAM, ECRYPT Stream Cipher Project, http://www.ecrypt.eu.org/stream
Silvester, J.R.: Determinants of Blocks Matrices. The Mathematical Gazette 84(501), 460–467 (2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Berger, T.P., Minier, M. (2012). Cryptanalysis of Pseudo-random Generators Based on Vectorial FCSRs. In: Galbraith, S., Nandi, M. (eds) Progress in Cryptology - INDOCRYPT 2012. INDOCRYPT 2012. Lecture Notes in Computer Science, vol 7668. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-34931-7_13
Download citation
DOI: https://doi.org/10.1007/978-3-642-34931-7_13
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-34930-0
Online ISBN: 978-3-642-34931-7
eBook Packages: Computer ScienceComputer Science (R0)