Abstract
In this paper, we revisit the work of Sarkar et al. (Des Codes Cryptogr 82(1–2):351–375, 2017) and Liu (Advances in cryptology—Crypto 2017, 2017) and show how both of their ideas can be tuned to find good cubes. Here we propose a new algorithm for cube generation which improves existing results on \({\texttt {Zero-Sum}}\) distinguisher. We apply our new cube finding algorithm to three different nonlinear feedback shift register (NFSR) based stream ciphers \({\textsf {Trivium}}\), \(\textsf {Kreyvium}\) and \(\textsf {ACORN}\). From the results, we can see a cube of size 39, which gives \({\texttt {Zero-Sum}}\) for maximum 842 rounds and a significant non-randomness up to 850 rounds of \({\textsf {Trivium}}\). We provide some small size good cubes for \({\textsf {Trivium}}\), which outperform existing ones. We further investigate \(\textsf {Kreyvium}\) and \(\textsf {ACORN}\) by a similar technique and obtain cubes of size 56 and 92 which give \({\texttt {Zero-Sum}}\) distinguisher till 875 and 738 initialization rounds of \(\textsf {Kreyvium}\) and \(\textsf {ACORN}\) respectively. To the best of our knowledge, these results are best results as compared to the existing results on distinguishing attacks of these ciphers. We also provide a table of good cubes of sizes varying from 10 to 40 for these three ciphers.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
Note that indices of \(k_{i}\) and \(x_{i}\) for \(\textsf {ACORN}\) are from 0 to 127.
References
Å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).
Aumasson J.-P., Dinur I., Henzen L., Meier W., Shamir A.: Efficient FPGA implementations of high-dimensional cube Testers on the stream cipher Grain-128. In: SHARCS’09 Special-purpose Hardware for Attacking Cryptographic Systems, p. 147 (2009).
Aumasson J.-P., Dinur I., Meier W., Shamir A.: Cube testers and key recovery attacks on reduced-round MD6 and Trivium. In: Fast Software Encryption, pp. 1–22 (2009).
CAESAR: competition for authenticated encryption: security, applicability, and robustness. http://competitions.cr.yp.to/caesar.html.
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: International Workshop on Fast Software Encryption, pp. 502–517 (2016).
De Cannière C., Preneel B.: Trivium specification (2005).
Dinur I., Shamir A.: Cube attacks on tweakable black box polynomials. Adv. Cryptol. 2009, 278–299 (2009).
eSTREAM: Stream cipher project for ECrypt 2005. http://www.ecrypt.eu.org/stream/.
Fischer S., Khazaei S., Meier W.: Chosen IV statistical analysis for key recovery attacks on stream ciphers. In: International Conference on Cryptology in Africa, pp. 236–245 (2008).
Fouque P.-A., Vannet T.: Improving key recovery to 784 and 799 rounds of Trivium using optimized cube attacks. In: International Workshop on Fast Software Encryption, pp. 502–517 (2013).
Fu X., Wang X., Dong X., Meier W.: A Key-recovery attack on 855-round Trivium. In: Advances in Cryptology—CRYPTO 2018, pp. 160–184 (2018).
Ghafari V.A., Hu H.: A new chosen IV statistical distinguishing framework to attack symmetric ciphers, and its application to ACORN-v3 and Grain-128a. J. Ambient Intell. Humaniz. Comput. 1–8, (2018).
Hao Y., Jiao L., Li C., Meier W., Todo Y., Wang Q.: Observations on the dynamic cube attack of 855-round Trivium from Crypto’18. Cryptology Report 2018/972 (2018).
Hongjun W.: ACORN: a lightweight authenticated cipher (v3). In: Candidate for the CAESAR competition. https://competitions.cr.yp.to/round3/acornv3.pdf.
Knellwolf S., Meier W., Naya-Plasencia M.: Conditional differential cryptanalysis of Trivium and Katan. In: International Workshop on Selected Areas in Cryptography, pp. 200–212 (2011).
Liu M.: Degree evaluation of NFSR-based cryptosystems. Advances in Cryptology-Crypto 2017, 227–249 (2017).
Liu M., Lin D., Wang W.: Searching cubes for Testing Boolean function and its application to Trivium. In: IEEE International Symposium on Information Theory (ISIT), pp. 496–500 (2015).
Liu M., Yang J., Wang W., Lin D.: Correlation cube attacks: from weak-key distinguisher to key recovery. In: Advances in Cryptology—EUROCRYPT 2018, pp. 715–744 (2018).
Michael V.: Breaking ONE.FIVIUM by AIDA an algebraic IV differential attack. In: IACR Cryptology 2007, p. 413 (2007).
SAGE: The Sage mathematics software system. http://www.sagemath.org/.
Salam MdI, Bartlett H., Dawson E., Pieprzyk J., Simpson L., Wong K.K.H.: Investigating cube attacks on the authenticated encryption stream cipher ACORN. ATIS 2016, 15–26 (2016).
Sarkar S., Maitra S., Baksi A.: Observing biases in the state: case studies with Trivium and Trivia-sc. Des. Codes Cryptogr. 82(1–2), 351–375 (2017).
Stankovski P.: Greedy distinguishers and nonrandomness detectors. In: International Conference on Cryptology in India, pp. 210–226 (2010).
Stinson D.R.: Cryptography: Theory and Practice. CRC Press, Boca Raton (2005).
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).
Wang Q., Hao Y., Todo Y., Li C., Isobe T., Meier W.: Improved division property based cube attacks exploiting algebraic properties of superpoly (full version). Advances in Cryptology-Crypto 2018, 275–305 (2018).
Watanabe Y., Isobe T., Morii M.: Conditional differential cryptanalysis for Kreyvium. In: Australasian Conference on Information Security and Privacy, pp. 421–434 (2017).
Ye C., Tian T.: A new framework for finding nonlinear superpolies in cube attacks against trivium-like ciphers. In: Australasian Conference on Information Security and Privacy, pp. 172–187 (2018).
Acknowledgements
We are very grateful to the anonymous reviewers for their valuable suggestions/comments. We would also like to thank the High Performance Computing Environment (HPCE) at the P. G. Senapathy Center for computing resources, IIT Madras, Chennai for providing Virgo supercluster to carry out the experiments. The first author thanks University Grants Commission (UGC), New Delhi, India for financial support.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by L. Knudsen.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Appendices
Appendix A: Some best cubes for Trivium
Appendix B: Some best cubes for \(\textsf {Kreyvium}\)
Appendix C: Some best cubes for ACORN
Rights and permissions
About this article
Cite this article
Kesarwani, A., Roy, D., Sarkar, S. et al. New cube distinguishers on NFSR-based stream ciphers. Des. Codes Cryptogr. 88, 173–199 (2020). https://doi.org/10.1007/s10623-019-00674-1
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10623-019-00674-1
Keywords
- Stream cipher
- \({\textsf {Trivium}}\)
- \(\textsf {Kreyvium}\)
- \(\textsf {ACORN}\)
- Distinguishing attack