A generalized birthday approach for efficiently finding linear relations in \(\ell \) -sequences

详细信息    查看全文

• 作者：Hui Wang (1)
  Paul Stankovski (2)
  Thomas Johansson (2)
  
• 关键词：FCSR ; Linear relations ; Generalized birthday attack ; Distinguisher ; 94A60
• 刊名：Designs, Codes and Cryptography
• 出版年：2015
• 出版时间：January 2015
• 年：2015
• 卷：74
• 期：1
• 页码：41-57
• 全文大小：338 KB
• 参考文献：1. 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/p3ciphers/ffcsr/ffcsr_p3.pdf. Accessed 16 June 2013.
  2. Arnault F., Berger T., Lauradoux C., Minier M., Pousse B.: A new approach for F-FCSRs. In: Jacobson M.J., Jr., Rijmen V., Safavi-Naini R. (eds.) Selected Areas in Cryptography: SAC 2009. Lecture Notes in Computer Science, vol. 5867, pp. 433鈥?48. Springer, Berlin (2009). doi:10.1007/978-3-642-05445-7_27 .
  3. Arnault F., Berger T., Pousse B.: A matrix approach for FCSR automata. Cryptogr. Commun. 3, 109鈥?39 (2011). doi:10.1007/s12095-010-0041-z .
  4. Cover T., Thomas J.A.: Elements of Information Theory. Wiley Series in Telecommunication, Wiley (1991). http://eu.wiley.com/WileyCDA/WileyTitle/productCd-0471241954.html. Accessed 16 June 2013.
  5. Goresky M., Klapper A.: Arithmetic cross-correlations of FCSR sequences. IEEE Trans. Inf. Theory 43, 1342鈥?346 (1997).
  6. Goresky M., Klapper A.: Fibonacci and Galois representations of feedback-with-carry shift registers. IEEE Trans. Inf. Theory 48(11), 2826鈥?836 (2002). doi:10.1109/TIT.2002.804048 .
  7. Hell M., Johansson T.: Breaking the stream ciphers F-FCSR-H and F-FCSR-16 in real time. J. Cryptol. 24(3), 427鈥?45 (2009). doi:10.1007/s00145-009-9053-2 .
  8. Hell M., Johansson T., Brynielsson L.: An overview of distinguishing attacks on stream ciphers. Cryptogr. Commun. 1(1), 71鈥?4 (2009). doi:10.1007/s12095-008-0006-7 .
  9. Hogg R.V., Tanis E.A.: Probability and Statistical Inference. MacMillan, New York (1993).
  10. Klapper A., Goresky M.: 2-adic shift registers. In: Anderson R.J. (ed.) Fast Software Encryption鈥?3. Lecture Notes in Computer Science, vol. 809, pp. 174鈥?78. Springer, Berlin (1994). doi:10.1007/3-540-58108-1_21 .
  11. Klapper A., Goresky M.: Feedback shift registers, 2-adic span, and combiners with memory. J. Cryptol. 10(2), 111鈥?47 (1997). doi:10.1007/s001459900024 .
  12. Matsui M.: Linear cryptanalysis method for DES cipher. In: Helleseth T. (ed.) Advances in Cryptology鈥揈UROCRYPT鈥?3. Lecture Notes in Computer Science, vol. 765, pp. 386鈥?97. Springer, Berlin (1994). doi:10.1007/3-540-48285-7_33 .
  13. Pagh R., Rodler F.F.: Cuckoo hashing. J. Algorithms 51, 122鈥?44 (2004). doi:10.1016/j.jalgor.2003.12.002 .
  14. Tian T., Qi W.F.: Linearity properties of binary FCSR sequences. Des. Codes Cryptogr. 52, 249鈥?62 (2009). doi:10.1007/s10623-009-9280-4 .
  15. Wagner D.: A generalized birthday problem. In: Yung M. (ed.) Advances in Cryptology鈥揅RYPTO 2002. Lecture Notes in Computer Science, vol. 2442, pp. 288鈥?04. Springer, Berlin (2002). doi:10.1007/3-540-45708-9_19 .
  16. Wikipedia: Birthday problem: Wikipedia, the free encyclopedia. http://en.wikipedia.org/wiki/Birthday_problem. Accessed 17 Feb 2012.
  
• 作者单位：Hui Wang (1)
  Paul Stankovski (2)
  Thomas Johansson (2)
  
  1. Shanghai Key Lab of Intelligent Information Processing, School of Computer Science, Fudan University, Shanghai, 200433, People鈥檚 Republic of China
  2. Deptartment of Electrical and Information Technology, Lund University, Box 118, Lund, 221 00, Sweden
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Coding and Information Theory
  Data Structures, Cryptology and Information Theory
  Data Encryption
  Discrete Mathematics in Computer Science
  Information, Communication and Circuits
  
• 出版者：Springer Netherlands
• ISSN：1573-7586

文摘

Feedback with carry shift registers (FCSRs) have previously been available in two configurations, the Fibonacci and Galois architectures. Recently, a generalized and unifying FCSR structure and theory was presented. The new ring FCSR model repairs some weaknesses of the older architectures. Most notably, the carry cell bias property that was exploited for an attack on the eSTREAM final portfolio cipher F-FCSR-H v2 is no longer possible for the updated (and unbroken) F-FCSR-H v3 stream cipher. In this paper we show how to exploit a particular set of linear relations in ring FCSR sequences. We show what biases can be expected, and we also present a generalized birthday algorithm for actually realizing these relations. As all prerequisites of a distinguishing attack are present, we explicitly show a new such attack on F-FCSR-H v3 with an online time complexity of only \(2^{37.2}\) . The offline time complexity (for finding a linear relation) is \(2^{56.2}\) . This is the first successful attack on F-FCSR-H v3, the first attack to breach the exhaustive search complexity limit. Note that this attack is completely different from that of F-FCSR-H v2. We focus on this particular application in the paper, but the presented algorithm is actually very general. The algorithm can be applied to any FCSR automaton, so linearly filtered FCSRs and FCSR combiners may be particularly interesting targets for cryptanalysis.