Department of Mathematics

Indian Institute Of Technology Madras , Chennai


New cube distinguishers on NFSR-based stream ciphers


Kesarwani, Abhishek and Roy, Dibyendu and Sarkar, Santanu and Meier, Willi


Designs, Codes and Cryptography




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 $}{\$\\backslashtexttt \Zero-Sum\\$}{\$Zero-Sumdistinguisher. We apply our new cube finding algorithm to three different nonlinear feedback shift register (NFSR) based stream ciphers $}{\$\\backslashtextsf \Trivium\\$}{\$Trivium, $}{\$\backslashtextsf \Kreyvium\$}{\$Kreyviumand $}{\$\backslashtextsf \ACORN\$}{\$ACORN. From the results, we can see a cube of size 39, which gives $}{\$\\backslashtexttt \Zero-Sum\\$}{\$Zero-Sumfor maximum 842 rounds and a significant non-randomness up to 850 rounds of $}{\$\\backslashtextsf \Trivium\\$}{\$Trivium. We provide some small size good cubes for $}{\$\\backslashtextsf \Trivium\\$}{\$Trivium, which outperform existing ones. We further investigate $}{\$\backslashtextsf \Kreyvium\$}{\$Kreyviumand $}{\$\backslashtextsf \ACORN\$}{\$ACORNby a similar technique and obtain cubes of size 56 and 92 which give $}{\$\\backslashtexttt \Zero-Sum\\$}{\$Zero-Sumdistinguisher till 875 and 738 initialization rounds of $}{\$\backslashtextsf \Kreyvium\$}{\$Kreyviumand $}{\$\backslashtextsf \ACORN\$}{\$ACORNrespectively. 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.