Abstract
F-FCSR-H v2 is one of the 8 final stream ciphers in the eSTREAM portfolio. However, it was broken by M. Hell and T. Johansson at ASIACRYPT 2008 by exploiting the bias in the carry cells of a Galois FCSR. In order to resist this attack, at SAC 2009 F. Arnault \(et \ al.\) proposed the new stream cipher F-FCSR-H v3 based upon a ring FCSR. M. Hell and T. Johansson only presented experimental results but no theoretical results for the success probability of their powerful attack against F-FCSR-H v2. And so far there are no analytical results of F-FCSR-H v3. This paper discusses the probability distribution of the carry cells of F-FCSR-H v2 and F-FCSR-H v3. We build the probability model for the carry cells of the two stream ciphers and prove that the consecutive output sequence of a single carry cell is a homogeneous Markov chain and the inverse chain is also a homogeneous Markov chain. We also prove that the probability of l consecutive outputs of a single carry cell to be zeros is (1/2)·(3/4)l − 1, which is a weakness of the carry cells of F-FCSR-H v2 and F-FCSR-H v3, noticing that (1/2)·(3/4)l − 1 > 2− l for l > 1. FCSR is a finite-state automata, so its distribution is stable. Based on this fact, we construct a system of equations using the law of total probability, and present a theoretical probability of breaking F-FCSR-H v2 by solving the equations. Applying this technique to F-FCSR-H v3, we obtain that the probability of all the 82 carry cells of F-FCSR-H v3 to be zeros at the same clock is at least 2− 64.29, which is much higher than 2− 82. This is another weakness of the carry cells of F-FCSR-H v3. Our results provide theoretical support to M.Hell and T.Johansson’s cryptanalysis of F-FCSR-H v2 and establish a theoretical foundation for further cryptanalysis of F-FCSR-H v3.
This work was supported by the Natural Science Foundation of China (Grant No. 60833008 and 60902024).
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
Arnault, F., Berger, T., Lauradoux, C.: Update on F-FCSR stream cipher. eSTREAM, ECRYPT Stream Cipher Project, Report 2006/025 (2006), http://www.ecrypt.eu.org/stream
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)
eSTREAM: Ecrypt stream cipher project, http://www.ecrypt.eu.org/stream/
Goresky, M., Klapper, A.: Fibonacci and Galois representations of feedback-with-carry shift registers. IEEE Transactions on Information Theory 48(11), 2826–2836 (2002)
Goresky, M., Klapper, A.: Periodicity and distribution properties of combined FCSR sequences. In: Gong, G., Helleseth, T., Song, H.-Y., Yang, K. (eds.) SETA 2006. LNCS, vol. 4086, pp. 334–341. Springer, Heidelberg (2006)
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)
Klapper, A., Goresky, M.: Feedback Shift Registers, 2-Adic Span, and Combiners with Memory. J. Cryptol. 10(2), 111–147 (1997)
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
Song, H., Fan, X., Wu, C., Feng, D. (2012). On the Probability Distribution of the Carry Cells of Stream Ciphers F-FCSR-H v2 and F-FCSR-H v3. In: Wu, CK., Yung, M., Lin, D. (eds) Information Security and Cryptology. Inscrypt 2011. Lecture Notes in Computer Science, vol 7537. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-34704-7_13
Download citation
DOI: https://doi.org/10.1007/978-3-642-34704-7_13
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-34703-0
Online ISBN: 978-3-642-34704-7
eBook Packages: Computer ScienceComputer Science (R0)