Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Designs, Codes and Cryptography
Published in: Designs, Codes and Cryptography 12/2021

20-10-2021

An improved degree evaluation method of NFSR-based cryptosystems

Authors: Chen-Dong Ye, Tian Tian

Published in: Designs, Codes and Cryptography | Issue 12/2021

Login to get access

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In this paper, we study the algebraic degree evaluation of NFSR-based cryptosystems. The degree evaluation method based on the numeric mapping proposed by Liu at CRYPTO 2017 is very fast and could be applied to a cube of any size. The numeric degree of \(f_1(\varvec{x},\varvec{v})\times f_2(\varvec{x},\varvec{v})\) is estimated as \(D_1+D_2\), where \(D_1\) and \(D_2\) are the numeric degrees of \(f_1\) and \(f_2\) respectively and the algebraic degree of a function is no more than its numeric degree. It can be observed that some variables may be counted twice in \(D_1+D_2\) and the precise of the numerical mapping heavily depends on how many variables are counted redundantly. When applied to an iterative cryptosystem, such redundances will accumulate during iteratively computing numeric degrees. This is an important factor accounting for the difference between the numeric degree and the algebraic degree of a cryptosystem. To reduce this difference, a new framework on the degree evaluation algorithm based on the numeric mapping is proposed. The main idea is to identify variables which are repeatedly counted in the numeric mapping and eliminate the redundant degrees on these variables. As illustrations, a concrete algorithm on Trivium-like ciphers is given which is shown to be useful in correlation cube attacks and the zero-sum distinguisher search. For correlation cube attacks on 835-round Trivium, we find some more useful cubes so that we could recover about 1.5 more bits at a cost of \(2^{40.7}\). Furthermore, we find several cubes leading to zero-sum distinguishers for Kreyvium variants with from 875 to 880 initialization rounds.
previous article Bounds for flag codes
next article Pseudorandom functions in NC class from the standard LWE assumption
Appendix
Available only for authorised users
Footnotes
Literature
1.
Ågren M., Hell M., Johansson T., Meier W.: Grain-128a: a new version of grain-128 with optional authentication. Int. J. Wirel. Mob. Comput. 5(1), 48–59 (2011).CrossRef
2.
Aumasson J., Henzen L., Meier W., Naya-Plasencia M.: Quark: a lightweight hash. J. Cryptol. 26(2), 313–339 (2013).MathSciNetCrossRef
3.
Cannière C.D., Preneel B.: Trivium. In: New Stream Cipher Designs—The eSTREAM Finalists, pp. 244–266 (2008).
4.
Cannière C.D., Dunkelman O., Knezevic M.: KATAN and KTANTAN—a family of small and efficient hardware-oriented block ciphers. In: Cryptographic Hardware and Embedded Systems—CHES 2009, 11th International Workshop, Lausanne, Switzerland, September 6–9, 2009, Proceedings, pp. 272–288 (2009).
5.
Canteaut A., Carpov S., Fontaine C., Lepoint T., Naya-Plasencia M., Paillier P., Sirdey R.: Stream ciphers: a practical solution for efficient homomorphic-ciphertext compression. In: Fast Software Encryption—23rd International Conference, FSE 2016, Bochum, Germany, March 20–23, 2016, Revised Selected Papers, pp. 313–333 (2016).
6.
Canteaut A., Carpov S., Fontaine C., Lepoint T., Naya-Plasencia M., Paillier P., Sirdey R.: Stream ciphers: a practical solution for efficient homomorphic-ciphertext compression. J. Cryptol. 31(3), 885–916 (2018).MathSciNetCrossRef
7.
8.
Chakraborti A., Chattopadhyay A., Hassan M., Nandi M.: Trivia: a fast and secure authenticated encryption scheme. In: Cryptographic Hardware and Embedded Systems—CHES 2015—17th International Workshop, Saint-Malo, France, September 13–16, 2015, Proceedings, pp. 330–353 (2015).
9.
Chepyzhov V.V., Johansson T., Smeets B.J.M.: A simple algorithm for fast correlation attacks on stream ciphers. In: Schneier B. (ed.) Fast Software Encryption, 7th International Workshop, FSE 2000, New York, NY, USA, April 10–12, 2000, Proceedings. Lecture Notes in Computer Science, Vol. 1978, pp. 181–195. Springer (2000).
10.
Courtois N.: Fast algebraic attacks on stream ciphers with linear feedback. In: D. Boneh (ed.) Advances in Cryptology—CRYPTO 2003, 23rd Annual International Cryptology Conference, Santa Barbara, California, USA, August 17–21, 2003, Proceedings. Lecture Notes in Computer Science, Vol. 2729, pp. 176–194. Springer (2003).
11.
Courtois N., Meier W.: Algebraic attacks on stream ciphers with linear feedback. In: Biham E. (ed.) Advances in Cryptology—EUROCRYPT 2003, International Conference on the Theory and Applications of Cryptographic Techniques, Warsaw, Poland, May 4–8, 2003, Proceedings. Lecture Notes in Computer Science, Vol. 2656, pp. 345–359. Springer (2003).
12.
Courtois N., Pieprzyk J.: Cryptanalysis of block ciphers with overdefined systems of equations. In: Zheng Y. (ed.) Advances in Cryptology—ASIACRYPT 2002, 8th International Conference on the Theory and Application of Cryptology and Information Security, Queenstown, New Zealand, December 1–5, 2002, Proceedings. Lecture Notes in Computer Science, Vol. 2501, pp. 267–287. Springer (2002).
13.
Courtois N., Klimov A., Patarin J., Shamir A.: Efficient algorithms for solving overdefined systems of multivariate polynomial equations. In: Preneel B. (ed.) Advances in Cryptology—EUROCRYPT 2000, International Conference on the Theory and Application of Cryptographic Techniques, Bruges, Belgium, May 14–18, 2000, Proceeding. Lecture Notes in Computer Science, Vol. 1807, pp. 392–407. Springer (2000).
14.
Dinur I., Shamir A.: Cube attacks on tweakable black box polynomials. In: Advances in Cryptology—EUROCRYPT 2009, 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cologne, Germany, April 26–30, 2009. Proceedings, pp. 278–299 (2009).
15.
Dinur I., Shamir A.: Breaking grain-128 with dynamic cube attacks. In: Fast Software Encryption—18th International Workshop, FSE 2011, Lyngby, Denmark, February 13–16, 2011, Revised Selected Papers, pp. 167–187 (2011).
16.
Dinur I., Güneysu T., Paar C., Shamir A., Zimmermann R.: An experimentally verified attack on full grain-128 using dedicated reconfigurable hardware. In: D.H. Lee, X. Wang (eds.) Advances in Cryptology—ASIACRYPT 2011—17th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, South Korea, December 4–8, 2011. Proceedings. Lecture Notes in Computer Science, Vol. 7073, pp. 327–343. Springer (2011).
17.
Dinur I., Morawiecki P., Pieprzyk J., Srebrny M., Straus M.: Cube attacks and cube-attack-like cryptanalysis on the round-reduced keccak sponge function. In: Oswald E., Fischlin M. (eds.) Advances in Cryptology—EUROCRYPT 2015—34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, April 26–30, 2015, Proceedings, Part I. Lecture Notes in Computer Science, Vol. 9056, pp. 733–761. Springer (2015).
18.
Hell M., Johansson T., Maximov A., Meier W.: A stream cipher proposal: Grain-128. In: Proceedings 2006 IEEE International Symposium on Information Theory, ISIT 2006, The Westin Seattle, Seattle, Washington, USA, July 9–14, 2006, pp. 1614–1618. IEEE (2006).
19.
Hell M., Johansson T., Maximov A., Meier W.: The grain family of stream ciphers. In: New Stream Cipher Designs—The eSTREAM Finalists, pp. 179–190 (2008).
20.
Kesarwani A., Roy D., Sarkar S., Meier W.: New cube distinguishers on nfsr-based stream ciphers. Des. Codes Cryptogr. 88(1), 173–199 (2020).MathSciNetCrossRef
21.
Knudsen L.R.: Truncated and higher order differentials. In: Preneel B. (ed.) Fast Software Encryption: Second International Workshop. Leuven, Belgium, 14–16 December 1994, Proceedings. Lecture Notes in Computer Science, Vol. 1008, pp. 196–211. Springer (1994).
22.
Knudsen L.R., Wagner D.A.: Integral cryptanalysis. In: Daemen J., Rijmen V. (eds.) Fast Software Encryption, 9th International Workshop, FSE 2002, Leuven, Belgium, February 4–6, 2002, Revised Papers, Lecture Notes in Computer Science, vol. 2365, pp. 112–127. Springer (2002).
23.
Liu M.: Degree evaluation of NFSR-Based cryptosystems. In: Advances in Cryptology—CRYPTO 2017—37th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 20–24, 2017, Proceedings, Part III, pp. 227–249 (2017).
24.
Liu M., Yang J., Wang W., Lin D.: Correlation cube attacks: from weak-key distinguisher to key recovery. In: Advances in Cryptology—EUROCRYPT 2018—37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29–May 3, 2018 Proceedings, Part II, pp. 715–744 (2018).
25.
26.
Moriai S., Shimoyama T., Kaneko T.: Higher order differential attak of CAST cipher. In: Vaudenay S (ed.) Fast Software Encryption, 5th International Workshop, FSE ’98, Paris, France, March 23–25, 1998, Proceedings. Lecture Notes in Computer Science, Vol. 1372, pp. 17–31. Springer (1998).
27.
Todo Y., Isobe T., Hao Y., Meier W.: Cube attacks on non-blackbox polynomials based on division property. In: Advances in Cryptology—CRYPTO 2017—37th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 20–24, 2017, Proceedings, Part III, pp. 250–279 (2017).
28.
Todo Y., Isobe T., Hao Y., Meier W.: Cube attacks on non-blackbox polynomials based on division property. IEEE Trans. Comput. 67(12), 1720–1736 (2018).MathSciNetCrossRef
29.
Wang Q., Hao Y., Todo Y., Li C., Isobe T., Meier W.: Improved division property based cube attacks exploiting algebraic properties of superpoly. In: Advances in Cryptology—CRYPTO 2018—38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19–23, 2018, Proceedings, Part I, pp. 275–305 (2018).
30.
31.
Ye C., Tian T.: A new framework for finding nonlinear superpolies in cube attacks against trivium-like ciphers. In: Susilo W., Yang G. (eds.) Information Security and Privacy—23rd Australasian Conference, ACISP 2018, Wollongong, NSW, Australia, July 11–13, 2018, Proceedings. Lecture Notes in Computer Science, Vol. 10946, pp. 172–187. Springer (2018).
32.
Ye C., Tian T.: Algebraic method to recover superpolies in cube attacks. IET Inf. Security 14(4), 430–441 (2020).CrossRef
Metadata
Title
An improved degree evaluation method of NFSR-based cryptosystems
Authors
Chen-Dong Ye
Tian Tian
Publication date
20-10-2021
Publisher
Springer US
Published in
Designs, Codes and Cryptography / Issue 12/2021
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI
https://doi.org/10.1007/s10623-021-00954-9

Other articles of this Issue 12/2021

Designs, Codes and Cryptography 12/2021 Go to the issue

OriginalPaper

On security properties of all-or-nothing transforms

OriginalPaper

Five families of the narrow-sense primitive BCH codes over finite fields

OriginalPaper

Pseudorandom functions in NC class from the standard LWE assumption

OriginalPaper

Walsh spectrum and nega spectrum of complementary arrays

OriginalPaper

Binary signed-digit integers and the Stern diatomic sequence

OriginalPaper

Existence of primitive normal pairs with one prescribed trace over finite fields

Premium Partner

    Image Credits