DONG Li-hua1, ZENG Yong2, WANG Chun-hong3, HU Yu-pu1
1. National ISN Key Laboratory, Xidian University, Xi'an, Shaanxi 710071, China;
2. School of Cyber Engineering, Xidian University, Xi'an, Shaanxi 710071, China;
3. No. 722 Research Institute of CSIC, Wuhan, Hubei 430205, China
Abstract：We propose a novel FCSR-based cryptographic primitive for efficiently resisting M.Hell and T.Johansson's real-time crypt-analysis on FCSR-based stream ciphers.With this proposed primitive in the application,we simply need to xor the bit in the carry unit with the corresponding state bit in a LFSR.Then just perform the original operation of the FCSR.Analysis and experimental results show that:the transition function of the proposed primitive is still quadratic,thus it provides an intrinsic resistance to algebraic attacks and correlation attacks;and it is very important that all the sequences generated by the carry cells are independent,unbiased and have good statistical properties,thus can prevent the attack of Hell and Johansson and other similar attacks on FCSR-based stream ciphers.
[1] Dj Golic,J Menicocci,R.Edit probability correlation attacks on stop/go clocked keystream generators[J].J Cryptology,2003,16(1):41-68.
[2] Zhang B,Wu H,Feng D,Bao F.A fast correlation attack on the shrinking generator[A].Topics in Cryptology-CT-RSA 2005.CT-RSA 2005[C].Springer,Berlin,Heidelberg.2005.LNCS 3376:72-86.
[3] Martin Hell,Thomas Johansson.Two new attacks on the self-shrinking generator[J].IEEE Transactions on Information Theory,2006,52(8):3837-3843.
[4] Faheem Masoodi,Shadab Alam and M U Bokhari.An analysis of linear feedback shift registers in stream ciphers[J].International Journal of Computer Applications,2012,46(17):46-49.
[5] Zhong X,Wang M,Zhang B,Wu S.A guess-then-algebraic attack on LFSR-based stream ciphers with nonlinear filter[A].Information and Communications Security.ICICS 2014[C].Springer,Cham.2015.LNCS 8958:132-142.
[6] Goli'c,J,Menicocci,R.A new statistical distinguisher for the shrinking generator[OL].http://eprint.iacr.org/2003/041.
[7] Debraize B,Goubin L.Guess-and-determine algebraic attack on the self-shrinking generator[A].Fast Software Encryption.FSE 2008[C].Springer,Berlin,Heidelberg,2008.LNCS 5086:235-252.
[8] 冯登国.NESSIE工程简介[J].信息安全与通信保密,2001,(3):36-39.
[9] Robshaw M.The eSTREAM project[A].New Stream Cipher Designs[C].Springer,Berlin,Heidelberg,2008.LNCS 4986:1-6.
[10] Elena Dubrova.An equivalence preserving transformation from the Fibonacci to the Galois NLFSRs[OL].2008,http://arxiv.org/PS_cache/arxiv/pdf/0801/0801.4079v2.pdf.
[11] Deb S.,Biswas B.,Kar N.(2015) Study of NLFSR and reasonable security improvement on trivium cipher[A].Information Systems Design and Intelligent Applications.Advances in Intelligent Systems and Computing[C].Springer,New Delhi,2015.339:731-739.
[12] Shi T,Anashin V,Lin D.Linear weaknesses in t-functions[A].Sequences and Their Applications-SETA 2012.SETA 2012[C].Springer,Berlin,Heidelberg,2012.LNCS 7280:279-290.
[13] Vladimir Anashin,Andrei Khrennikov,Ekaterina Yurova.T-functions revisited:new criteria for bijectivity/transitivity[J].Des.Codes Cryptogr,2014,71(3):383-407.
[14] Francois Arnault,Thierry P.Berger and Benjamin Pousse.A matrix approach for FCSR automata.Cryptography and Communications,2011[OL].www.springerlink.com/index/J16174424270X56G.pdf.
[15] Paul Stankovski,Martin Hell,Thomas Johansson.An efficient state secovery attack on the X-FCSR family of stream ciphers[J].J Cryptol,2014,27(1):1-22.
[16] Klapper A,Goresky M.2-Adic shift registers[A].Fast Software Encryption.FSE 1993[C].Springer,Berlin,Heidelberg.1994.LNCS 809:174-178.
[17] Arnault F,Berger T P.(2005) F-FCSR:Design of a new class of stream ciphers[A].Fast Software Encryption.FSE 2005[C].Springer,Berlin,Heidelberg.2005.LNCS 3557:83-97.
[18] Hell M,Johansson T.(2008) Breaking the F-FCSR-H stream cipher in real time[A].Advances in Cryptology-ASIACRYPT 2008.ASIACRYPT 2008[C].Springer,Berlin,Heidelberg.2008.LNCS 5350:557-569.
[19] Song H,Fan X,Wu C,Feng D.On the probability distribution of the carry cells of stream ciphers F-FCSR-H v2 and F-FCSR-H v3[A].Information Security and Cryptology.Inscrypt 2011[C].Springer,Berlin,Heidelberg,2012.LNCS 7537:160-178.
[20] Arnault F,Berger T,Lauradoux C,Minier M,Pousse B.A new approach for FCSRs[A].Selected Areas in Cryptography.SAC 2009[C].Springer,Berlin,Heidelberg,2009.LNCS 5867:433-448.
[21] Marjane A,Allailou B.Vectorial conception of FCSR[A].Sequences and Their Applications-SETA 2010.SETA 2010[C].Springer,Berlin,Heidelberg,2010.LNCS 6338:240-252.
[22] Allailou B,Marjane A,Mokrane A.Design of a novel pseudo-random generator based on vectorial FCSRs[A].Information Security Applications.WISA 2010[C].Springer,Berlin,Heidelberg,2011.LNCS 6513:76-91.
[23] Berger T P,Minier M,Pousse B.Software oriented stream ciphers based upon FCSRs in diversified mode[A].Progress in Cryptology-INDOCRYPT 2009.INDOCRYPT 2009[C].Springer,Berlin,Heidelberg,2009.5922:119-135.
[24] Stankovski P,Hell M,Johansson T.An efficient state recovery attack on the X-FCSR family of stream ciphers[J].Journal of Cryptology,2014,27(1):1-22.
[25] Wang H,Stankovski P,Johansson T.A generalized birthday approach for efficiently finding linear relations inl-sequences[J].Designs Codes & Cryptography,2015,74(1):41-57.
[26] Pei D,Lin Z,Zhang X.Construction of transition matrices for ternary ring feedback with carry shift registers[J].IEEE Transactions on Information Theory,2015,61(5):2942-2951.
[27] 刘鑫,田甜,戚文峰.一类LFSR序列簇的2-adic复杂度[J].系统科学与数学,2015,35(9):999-1007. Liu xin,Tian tian,Qi wenfeng.The 2-adic complexity of a class of LFSR sequence families[J].Journal of Systems Scieme and Mathematical Sciences,2015,35(9):999-1007.(in Chinese)
[28] Lin Z,Lin D,Pei D.Practical construction of ring LFSRs and ring FCSRs with low diffusion delay for hardware cryptographic applications[J].Cryptography & Communications,2017,9(4):431-443.
[29] M.Goresky,A Klapper.Fibonacci and galois representations of feedback-with-carry shift registers[J].IEEE Transaction on Information Theory,2002,48(11):2826-2836.
2018, Vol. 46 
