×

An improved degree evaluation method of NFSR-based cryptosystems. (English) Zbl 1477.94064

Summary: In this paper, we study the algebraic degree evaluation of NFSR-based cryptosystems. The degree evaluation method based on the numeric mapping proposed by M. Liu [Lect. Notes Comput. Sci. 10403, 227–249 (2017; Zbl 1406.94073)] is very fast and could be applied to a cube of any size. The numeric degree of \(f_1(x,v)\times f_2(x,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.

MSC:

94A60 Cryptography
94A55 Shift register sequences and sequences over finite alphabets in information and communication theory

Citations:

Zbl 1406.94073
PDF BibTeX XML Cite
Full Text: DOI

References:

[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)
[2] Aumasson, J.; Henzen, L.; Meier, W.; Naya-Plasencia, M., Quark: a lightweight hash, J. Cryptol., 26, 2, 313-339 (2013) · Zbl 1279.94053
[3] Cannière C.D., Preneel B.: Trivium. In: New Stream Cipher Designs—The eSTREAM Finalists, pp. 244-266 (2008). · Zbl 1285.94054
[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). · Zbl 1290.94060
[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). · Zbl 1387.94071
[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) · Zbl 1400.94132
[7] Chakraborti A., Nandi M.: Trivia-ck-v2. http://competitions.cr.yp.to/round2/triviackv2.pdf (2015). Accessed 26 August 2020.
[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). · Zbl 1380.94077
[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). · Zbl 0999.94542
[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). · Zbl 1122.94365
[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). · Zbl 1038.94525
[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). · Zbl 1065.94543
[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). · Zbl 1082.94514
[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). · Zbl 1239.94045
[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). · Zbl 1282.94042
[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). · Zbl 1227.94042
[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). · Zbl 1370.94506
[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) · Zbl 1428.94080
[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). · Zbl 0939.94556
[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). · Zbl 1045.94527
[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). · Zbl 1406.94073
[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). · Zbl 1428.94086
[25] Meier, W.; Staffelbach, O., Fast correlation attacks on certain stream ciphers, J. Cryptol., 1, 3, 159-176 (1989) · Zbl 0673.94010
[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). · Zbl 1385.94063
[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). · Zbl 1406.94081
[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) · Zbl 07033435
[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). · Zbl 1444.94103
[30] Wu H.: Acorn: A Lightweight Authenticated Cipher (v3) (2016). http://competitions.cr.yp.to/round3/acornv3.pdf. Accessed 26 August 2020.
[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). · Zbl 1444.94110
[32] Ye, C.; Tian, T., Algebraic method to recover superpolies in cube attacks, IET Inf. Security, 14, 4, 430-441 (2020)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.