New cube distinguishers on NFSR-based stream ciphers
Authors:
Kesarwani, Abhishek and Roy, Dibyendu and Sarkar, Santanu and Meier, Willi
Journal:
Designs, Codes and Cryptography
year:
2019
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 $}{\$\\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.
