Abstract
The Feedback with Carry Shift Registers (FCSRs) have been proposed as an alternative to Linear Feedback Shift Registers (LFSRs) for the design of stream ciphers. FCSRs have good statistical properties and they provide a built-in non-linearity. However, two attacks have shown that the current representations of FCSRs can introduce weaknesses in the cipher. We propose a new “ring” representation of FCSRs based upon matrix definition which generalizes the Galois and Fibonacci representations. Our approach preserves the statistical properties and circumvents the weaknesses of the Fibonacci and Galois representations. Moreover, the ring representation leads to automata with a quicker diffusion characteristic and better implementation results. As an application, we describe a new version of F-FCSR stream ciphers.
This work was partially supported by the french National Agency of Research: ANR-06-SETI-013.
Chapter PDF
Similar content being viewed by others
References
Klapper, A., Goresky, M.: 2-adic shift registers. In: Anderson, R. (ed.) FSE 1993. LNCS, vol. 809, pp. 174–178. Springer, Heidelberg (1994)
Klapper, A., Goresky, M.: Feedback shift registers, 2-adic span and combiners with memory. Journal of Cryptology 10(2), 111–147 (1997)
Klapper, A.: A survey of feedback with carry shift registers. In: Helleseth, T., Sarwate, D., Song, H.-Y., Yang, K. (eds.) SETA 2004. LNCS, vol. 3486, pp. 56–71. Springer, Heidelberg (2005)
Fischer, S., Meier, W., Stegemann, D.: Equivalent Representations of the F-FCSR Keystream Generator. In: ECRYPT Network of Excellence - SASC Workshop, pp. 87–94 (2008), http://www.ecrypt.eu.org/stvl/sasc2008/
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)
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.: Update on F-FCSR Stream Cipher. ECRYPT - Network of Excellence in Cryptology (Call for stream Cipher Primitives - Phase 2 2006) (2006), http://www.ecrypt.eu.org/stream/
Roggeman, Y.: Varying feedback shift registers. In: Quisquater, J.-J., Vandewalle, J. (eds.) EUROCRYPT 1989. LNCS, vol. 434, pp. 670–679. Springer, Heidelberg (1990)
Jansen, C.J., Helleseth, T., Kholosha, A.: Cascade jump controlled sequence generator and pomaranch stream cipher (version 2). eSTREAM, ECRYPT Stream Cipher Project, Report 2006/006 (2006), http://www.ecrypt.eu.org/stream
Mrugalski, G., Rajski, J., Tyszer, J.: Ring generators - new devices for embedded test applications. IEEE Trans. on CAD of Integrated Circuits and Systems 23(9), 1306–1320 (2004)
Jansen, C.J., Helleseth, T., Kholosha, A.: Pomaranch version 3. eSTREAM, ECRYPT Stream Cipher Project (2006), http://www.ecrypt.eu.org/stream
Koblitz, N.: p-adic numbers, p-adic analysis and Zeta-Functions. Springer, Heidelberg (1997)
Goresky, M., Klapper, A.: Fibonacci and Galois representations of feedback-with-carry shift registers. IEEE Transactions on Information Theory 48(11), 2826–2836 (2002)
Arnault, F., Berger, T.P.: Design and Properties of a New Pseudorandom Generator Based on a Filtered FCSR Automaton. IEEE Transaction on Computers 54(11), 1374–1383 (2005)
Lauradoux, C., Röck, A.: Parallel generation of ℓ-sequences. In: Golomb, S.W., Parker, M.G., Pott, A., Winterhof, A. (eds.) SETA 2008. LNCS, vol. 5203, pp. 299–312. Springer, Heidelberg (2008)
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)
Goldberg, I., Wagner, D.: Architectural considerations for cryptanalytic hardware. Technical report, Secrets of Encryption Research, Wiretap Politics & Chip Design (1996)
Joux, A., Delaunay, P.: Galois LFSR, embedded devices and side channel weaknesses. In: Barua, R., Lange, T. (eds.) INDOCRYPT 2006. LNCS, vol. 4329, pp. 436–451. Springer, Heidelberg (2006)
Röck, A.: Stream ciphers using a random update function: Study of the entropy of the inner state. In: Vaudenay, S. (ed.) AFRICACRYPT 2008. LNCS, vol. 5023, pp. 258–275. Springer, Heidelberg (2008)
Hong, J., Kim, W.H.: TMD-Tradeoff and State Entropy Loss Considerations of Streamcipher MICKEY. In: Maitra, S., Veni Madhavan, C.E., Venkatesan, R. (eds.) INDOCRYPT 2005. LNCS, vol. 3797, pp. 169–182. Springer, Heidelberg (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Arnault, F., Berger, T., Lauradoux, C., Minier, M., Pousse, B. (2009). A New Approach for FCSRs. In: Jacobson, M.J., Rijmen, V., Safavi-Naini, R. (eds) Selected Areas in Cryptography. SAC 2009. Lecture Notes in Computer Science, vol 5867. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-05445-7_27
Download citation
DOI: https://doi.org/10.1007/978-3-642-05445-7_27
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-05443-3
Online ISBN: 978-3-642-05445-7
eBook Packages: Computer ScienceComputer Science (R0)