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

Improving algebraic attacks on stream ciphers based on linear feedback shift register over \(\mathbb {F}_{2^k}\)

  • Published:
Designs, Codes and Cryptography Aims and scope Submit manuscript

Abstract

In this paper we investigate univariate algebraic attacks on filter generators over extension fields \(\mathbb {F}_q=\mathbb {F}_{2^n}\) with focus on the Welch–Gong (WG) family of stream ciphers. Our main contribution is to reduce the general algebraic attack complexity on such cipher by proving new and lower bounds for the spectral immunity of such ciphers. The spectral immunity is the univariate analog of algebraic immunity and instead of measuring degree of multiples of a multivariate polynomial, it measures the minimum number of nonzero coefficients of a multiple of a univariate polynomial. In particular, there is an algebraic degeneracy in these constructions, which, when combined with attacks based on low-weight multiples over \(\mathbb {F}_q\), provides much more efficient attacks than over \(\mathbb {F}_2\). With negligible computational complexity, our best attack breaks the primitive WG-5 if given access to 4 kilobytes of keystream, break WG-7 if given access to 16 kilobytes of keystream and break WG-8 if given access to half a megabyte of keystream. Our best attack on WG-16 targeted at 4G-LTE is less practical, and requires \(2^{103}\) computational complexity and \(2^{61}\) bits of keystream. In all instances, we significantly lower both keystream and computational complexity in comparison to previous estimates. On a side note, we resolve an open problem regarding the rank of a type of equation systems used in algebraic attacks.

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

Access this article

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

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Aagaard M.D., Gong G., Mota, R.K.: Hardware implementations of the WG-5 cipher for passive RFID tags, In: IEEE International Symposium on Hardware-Oriented Security and Trust (HOST), 2013 pp. 29–34 (June 2013).

  2. Armknecht F.: Improving fast algebraic attacks. In: Proceedings of Fast Software Encryption 2004. Lecture Notes in Computer Science, vol. 3017, pp. 65–82, Springer, Berlin (2004).

  3. Armknecht F., Ars G.: Introducing a new variant of fast algebraic attacks and minimizing their successive data complexity. In: Dawson E., Vaudenay S. (eds.) Mycrypt 2005 (International Conference on Cryptology in Malaysia). Lecture Notes in Computer Science, vol. 3715, pp. 16–32 (2005).

  4. Armknecht F., Krause M.: Algebraic attacks on combiners with memory. In: Advances in Cryptology-CRYPTO 2003. Lecture Notes in Computer Science, vol. 2729, pp. 162–176. Springer, Berlin (2003).

  5. Brynielsson L.: On the linear complexity of combined shift register sequences. In: William H.C (ed.) EUROCRYPT85, pp. 156–160. Springer, Berlin (1985).

  6. Canteaut A.: Open problems related to algebraic attacks on stream ciphers. In: Coding and Cryptography, Lecture Notes in Computer Science, vol. 3969, pp. 120–134, Springer, Berlin (2006).

  7. Courtois N.: Fast algebraic attacks on stream ciphers with linear feedback. In: Advances in Cryptology-Crypto’2003. Lecture Notes in Computer Science, vol. 2729, pp. 176–194, Springer, Berlin (2003).

  8. Courtois N., Meier W.: Algebraic attacks on stream ciphers with linear feedback. In: Advances in Cryptology—-Eurocrypt’2003. Lecture Notes in Computer Science, vol. 2656, pp. 345–359. Springer, Berlin (2003).

  9. Ding L., Jin C.: Cryptanalysis of lightweight WG-8 stream cipher. IEEE Trans. Inf. Forensics Secur. 9(4), 645–652 (2014).

  10. ETSI/SAGE. Specification of the 3GPP Confidentiality and Integrity Algorithms UEA & UIA2 Document 2: Snow 3G Specification (version 1.1) (September 2006), http://www.3gpp.org/ftp

  11. Fan X., Gong G.: Specification of the stream cipher WG-16 based confidentiality and integrity algorithms, Technical Report CACR 2013-06 at University of Waterloo, http://cacr.uwaterloo.ca/techreports/2013/cacr2013-06.pdf.

  12. Fan X., Mandal K., Gong G.: WG-8: A lightweight Stream cipher for resource-constrained smart devices, In: Singh K., Awasthi AK (eds.) Quality, Reliability, Security and Robustness in Heterogeneous Networks. Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering. Springer, Berlin.

  13. Golomb S.W.: Shift Register Sequences. Holden-Day Inc, San Francisco (1967) (Revised edn, Aegean Park Press, Laguna Hills 1982).

  14. Golomb S.W., Gong G.: Signal Design for Good Correlation: For Wireless Communication, Cryptography, and Radar. Cambridge University Press, New York (2004).

  15. Gong G., Rønjom S., Helleseth T., Hu H.: Fast discrete Fourier spectra attacks on stream ciphers. IEEE Trans. Inf. Theory, 57(8), 5555–5565 (2011).

  16. Helleseth T., Rønjom S.: Simplifying algebraic attacks with univariate analysis. Information Theory and Applications Workshop (ITA) 2011, 1–7 (2011).

  17. Lidl R., Niederreiter H.: Finite Fields In Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge (1997).

  18. Luo Y., Chai Q., Gong G., Lai X.: A Lightweight Stream Cipher, WG-7 for RFID Encryption and Authentication, In: IEEE Global Telecommunications Conference (GLOBECOM), Dec 2010, pp. 1–6 (2010).

  19. Meier W., Pasalic E., Carlet C.: Algebraic attacks and decomposition of Boolean functions. In: Cachin C., Camenisch J (eds.) Advances in Cryptology - EUROCRYPT 2004. Lecture Notes in Computer Science, vol. 3027, pp. 474–491.Springer, Berlin (2004).

  20. Nawaz Y., Gong G.: The WG Stream Cipher. EU ECRYPT eSTREAM competition, http://www.ecrypt.eu.org/stream/.

  21. Orumiehchiha M.A., Pieprzyk J., Steinfeld R.: Cryptanalysis of WG-7: a lightweight stream cipher. In: Cryptography and Communications, vol. 4, pp. 3–4, Springer, Berlin (2012).

  22. Philip H., Rose G.G. In: Advances in Cryptology—CRYPTO 2004: Proceedings of 24th Annual International Cryptology Conference, Santa Barbara, California, USA, Aug 15–19, 2004. Lecture Notes in Computer Science. Rewriting variables: The complexity of fast algebraic attacks on stream ciphers. Springer, Berlin (2004).

  23. Rønjom S., Helleseth T.: A New attack on the filter generator. IEEE Trans. Inf. Theory 53(5), 17520–17558 (2007).

  24. Rønjom S., Helleseth T.: Attacking the filter generator over \(GF(2^m)\), Arithmetic of Finite Fields, First International Workshop, WAIFA 2007, Madrid, Spain, June 2007. Lecture Notes in Computer Science, vol. 4547, pp. 264–275 (2007).

  25. Shparlinski I.E. : On the singularity of generalised Vandermonde matrices over finite fields. In: Finite Fields and Applications, vol. 11, no. 2, pp. 193–199. Elsevier Science Publishers B. V., North-Holland, (2005).

Download references

Author information

Authors and Affiliations

  1. Nasjonal sikkerhetsmyndighet, Oslo, Norway

    Sondre Rønjom

Authors
  1. Sondre Rønjom
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Sondre Rønjom.

Additional information

This is one of several papers published in Designs, Codes and Cryptography comprising the “Special Issue on Coding and Cryptography”.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Rønjom, S. Improving algebraic attacks on stream ciphers based on linear feedback shift register over \(\mathbb {F}_{2^k}\) . Des. Codes Cryptogr. 82, 27–41 (2017). https://doi.org/10.1007/s10623-016-0212-9

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10623-016-0212-9

Keywords

Mathematics Subject Classification

Search

Navigation