Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Distinguishing Attacks on Linearly Filtered NFSRs with Decimated Output

  • Conference paper
  • First Online:
Applications and Techniques in Information Security (ATIS 2020)

Part of the book series: Communications in Computer and Information Science ((CCIS,volume 1338))

  • 364 Accesses

Abstract

This paper presents an investigation into the resistance of linearly filtered nonlinear feedback shift registers (LF-NFSRs) against distinguishing attacks. We formalise the method described by Orumiehchiha, Pieprzyk, Steinfeld and Bartlett and then extend it to develop a more efficient, systematic framework for accurately distinguishing an arbitrary LF-NFSR. Our method is then generalised to distinguish arbitrary LF-NFSRs with regularly decimated output sequences. The proposed method is demonstrated through application to the example LF-NFSR used by Orumiehchiha et al. with improved results. Additionally, our new method can be accurately applied to much larger registers and can predict how much output is needed to find the strongest bias. To demonstrate this, we derive time and keystream requirement estimates for our attacks on each variant of the Grain family of stream ciphers under weak key-IV pairs.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Afzal, M., Masood, A.: Algebraic cryptanalysis of a NLFSR based stream cipher. In: 2008 3rd International Conference on Information and Communication Technologies: From Theory to Applications, pp. 1–6. IEEE (2008)

    Google Scholar 

  2. Amin Ghafari, V., Hu, H.: Fruit-80: a secure ultra-lightweight stream cipher for constrained environments. Entropy 20(3), 180 (2018)

    Article  Google Scholar 

  3. Armknecht, F., Mikhalev, V.: On lightweight stream ciphers with shorter internal states. In: Leander, G. (ed.) FSE 2015. LNCS, vol. 9054, pp. 451–470. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48116-5_22

    Chapter  Google Scholar 

  4. Berbain, C., Gilbert, H., Joux, A.: Algebraic and correlation attacks against linearly filtered non linear feedback shift registers. In: Avanzi, R.M., Keliher, L., Sica, F. (eds.) SAC 2008. LNCS, vol. 5381, pp. 184–198. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-04159-4_12

    Chapter  Google Scholar 

  5. Berbain, C., Gilbert, H., Maximov, A.: Cryptanalysis of grain. In: Robshaw, M. (ed.) FSE 2006. LNCS, vol. 4047, pp. 15–29. Springer, Heidelberg (2006). https://doi.org/10.1007/11799313_2

    Chapter  Google Scholar 

  6. Coppersmith, D., Krawczyk, H., Mansour, Y.: The shrinking generator. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 22–39. Springer, Heidelberg (1994). https://doi.org/10.1007/3-540-48329-2_3

    Chapter  Google Scholar 

  7. Courtois, N.T.: Fast algebraic attacks on stream ciphers with linear feedback. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 176–194. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-45146-4_11

    Chapter  Google Scholar 

  8. Courtois, N.T., Meier, W.: Algebraic attacks on stream ciphers with linear feedback. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 345–359. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-39200-9_21

    Chapter  Google Scholar 

  9. De Canniere, C., Preneel, B.: Trivium specifications. In eSTREAM, ECRYPT Stream Cipher Project. Citeseer (2005)

    Google Scholar 

  10. De Cannière, C., Küçük, Ö., Preneel, B.: Analysis of grain’s initialization algorithm. In: Vaudenay, S. (ed.) AFRICACRYPT 2008. LNCS, vol. 5023, pp. 276–289. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-68164-9_19

    Chapter  Google Scholar 

  11. Ding, C., Xiao, G., Shan, W. (eds.): The Stability Theory of Stream Ciphers. LNCS, vol. 561. Springer, Heidelberg (1991). https://doi.org/10.1007/3-540-54973-0

    Book  MATH  Google Scholar 

  12. Dinur, I., Shamir, A.: Breaking Grain-128 with dynamic cube attacks. In: Joux, A. (ed.) FSE 2011. LNCS, vol. 6733, pp. 167–187. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-21702-9_10

    Chapter  Google Scholar 

  13. Englund, H., Johansson, T.: A new simple technique to attack filter generators and related ciphers. In: Handschuh, H., Hasan, M.A. (eds.) SAC 2004. LNCS, vol. 3357, pp. 39–53. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-30564-4_3

    Chapter  Google Scholar 

  14. Faugere, J.-C., Ars, G.: An algebraic cryptanalysis of nonlinear filter generators using Gröbner bases. Report, INRIA (2003)

    Google Scholar 

  15. Forrié, R.: The strict avalanche criterion: spectral properties of Boolean functions and an extended definition. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol. 403, pp. 450–468. Springer, New York (1990). https://doi.org/10.1007/0-387-34799-2_31

    Chapter  Google Scholar 

  16. Forré, R.: A fast correlation attack on nonlinearly feedforward filtered shift-register sequences. In: Quisquater, J.-J., Vandewalle, J. (eds.) EUROCRYPT 1989. LNCS, vol. 434, pp. 586–595. Springer, Heidelberg (1990). https://doi.org/10.1007/3-540-46885-4_56

    Chapter  Google Scholar 

  17. Gammel, B.M., Göttfert, R.: Linear filtering of nonlinear shift-register sequences. In: Ytrehus, Ø. (ed.) WCC 2005. LNCS, vol. 3969, pp. 354–370. Springer, Heidelberg (2006). https://doi.org/10.1007/11779360_28

    Chapter  Google Scholar 

  18. Golić, J.D., Salmasizadeh, M., Simpson, L., Dawson, E.: Fast correlation attacks on nonlinear filter generators. Inf. Process. Lett. 64(1), 37–42 (1997)

    Article  MathSciNet  Google Scholar 

  19. Hell, M., Johansson, T., Brynielsson, L.: An overview of distinguishing attacks on stream ciphers. Cryptogr. Commun. 1(1), 71–94 (2009). https://doi.org/10.1007/s12095-008-0006-7

    Article  MathSciNet  MATH  Google Scholar 

  20. Hell, M., Johansson, T., Maximov, A., Meier, W.: A stream cipher proposal: Grain-128. In: 2006 IEEE International Symposium on Information Theory, pp. 1614–1618. IEEE (2006)

    Google Scholar 

  21. Hell, M., Johansson, T., Meier, W.: Grain: a stream cipher for constrained environments. Int. J. Wirel. Mobile Comput. 2(1), 86–93 (2007)

    Article  Google Scholar 

  22. Hell, M., Johansson, T., Meier, W.: Grain-128a: a new version of Grain-128 with optional authentication. Int. J. Wirel. Mob. Comput. 5, 48–59 (2011)

    Article  Google Scholar 

  23. Hell, M., Johansson, T., Meier, W., Sönnerup, J., Yoshida, H.: Grain-128AEAD - a lightweight AEAD stream cipher. NIST Lightweight Crypt. Compet. 1 (2019)

    Google Scholar 

  24. Katz, J., Menezes, A.J., Van Oorschot, P.C., Vanstone, S.A.: Handbook of Applied Cryptography. CRC Press, Boca Raton (1996)

    MATH  Google Scholar 

  25. Khazaei, S., Hassanzadeh, M., Kiaei, M.: Distinguishing attack on grain. ECRYPT Stream Cipher Proj. Rep. 71, 2005 (2005)

    Google Scholar 

  26. Küçük, O.: Slide resynchronization attack on the initialization of Grain 1.0. eSTREAM, ECRYPT Stream Cipher Proj. Rep. 44, 2006 (2006)

    Google Scholar 

  27. Lee, Y., Jeong, K., Sung, J., Hong, S.: Related-key chosen IV attacks on Grain-v1 and Grain-128. In: Mu, Y., Susilo, W., Seberry, J. (eds.) ACISP 2008. LNCS, vol. 5107, pp. 321–335. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-70500-0_24

    Chapter  Google Scholar 

  28. Massey, J.: Shift-register synthesis and BCH decoding. IEEE Trans. Inf. Theory 15(1), 122–127 (1969)

    Article  MathSciNet  Google Scholar 

  29. Meier, W., Staffelbach, O.: Fast correlation attacks on certain stream ciphers. J. Cryptol. 1(3), 159–176 (1988). https://doi.org/10.1007/BF02252874

    Article  MathSciNet  MATH  Google Scholar 

  30. Mikhalev, V., Armknecht, F., Müller, C.: On ciphers that continuously access the non-volatile key. IACR Trans. Symmetric Cryptol. 52–79 (2016)

    Google Scholar 

  31. Millan, W.: Analysis and Design of Boolean Functions for Cryptographic Applications. Doctorate (1997)

    Google Scholar 

  32. Orumiehchiha, M.A., Pieprzyk, J., Steinfeld, R., Bartlett, H.: Security analysis of linearly filtered NLFSRs. J. Math. Cryptol. 7(4), 313–332 (2013)

    Article  MathSciNet  Google Scholar 

  33. Rose, G.G., Hawkes, P.: On the applicability of distinguishing attacks against stream ciphers. IACR Cryptol. ePrint Arch. 2002, 142 (2002)

    Google Scholar 

  34. Rueppel, R.A.: Analysis and Design of Stream Ciphers. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-82865-2

    Book  MATH  Google Scholar 

  35. Siegenthaler, T.: Cryptanalysts representation of nonlinearly filtered ML-sequences. In: Pichler, F. (ed.) EUROCRYPT 1985. LNCS, vol. 219, pp. 103–110. Springer, Heidelberg (1986). https://doi.org/10.1007/3-540-39805-8_12

    Chapter  Google Scholar 

  36. Todo, Y., Isobe, T., Meier, W., Aoki, K., Zhang, B.: Fast correlation attack revisited. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10992, pp. 129–159. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96881-0_5

    Chapter  Google Scholar 

  37. Zhang, H., Wang, X.: Cryptanalysis of stream cipher grain family. IACR Cryptol. ePrint Arch. 2009, 109 (2009)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Queensland University of Technology, Brisbane, QLD, Australia

    Matthew Beighton, Harry Bartlett, Leonie Simpson & Kenneth Koon-Ho Wong

Authors
  1. Matthew Beighton
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Harry Bartlett
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Leonie Simpson
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Kenneth Koon-Ho Wong
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Matthew Beighton .

Editor information

Editors and Affiliations

  1. Radboud University, Nijmegen, The Netherlands

    Lejla Batina

  2. Deakin University, Geelong, VIC, Australia

    Gang Li

Rights and permissions

Reprints and permissions

Copyright information

© 2020 Springer Nature Singapore Pte Ltd.

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Beighton, M., Bartlett, H., Simpson, L., Wong, K.KH. (2020). Distinguishing Attacks on Linearly Filtered NFSRs with Decimated Output. In: Batina, L., Li, G. (eds) Applications and Techniques in Information Security. ATIS 2020. Communications in Computer and Information Science, vol 1338. Springer, Singapore. https://doi.org/10.1007/978-981-33-4706-9_4

Download citation

  • DOI: https://doi.org/10.1007/978-981-33-4706-9_4

  • Published:

  • Publisher Name: Springer, Singapore

  • Print ISBN: 978-981-33-4705-2

  • Online ISBN: 978-981-33-4706-9

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics