New Conditional Differential Cryptanalysis for NLFSR-based Stream Ciphers and Application to Grain v1
Yuhei Watanabe, Yosuke Todo, Masakatu Morii · 2016
Grain v1 is an NLFSR-based stream cipher designed by Hell, Johansson, and Meier in 2005. This algorithm was selected in the eSTREAM hardware profile. At Asiacrypt 2010, Knellwolf, Meier, and Naya-Plasencia showed a conditional differential cryptanalysis and applied it to Grain v1. They showed distinguishing and key-recovery attacks on Grain v1 with 104 rounds by using 235 chosen IVs. Sarkar then extended the distinguisher up to 106 rounds. Knellwolf et al. also showed a conditional differential cryptanalysis for the related-key setting, where they analyzed both forward and inverse key initializations. Since differences quickly spread to the whole of the state, this technique works in the related-key setting because the key is loaded directly into the state in the NLFSR-based stream ciphers. In this paper, we propose a new method to find conditional differential characteristics on NLFSR-based stream ciphers. Our method is similar to the previous one on the related-key setting, but we look for conditional differential characteristics so as to prevent differences from spreading to the key. Therefore, we can efficiently find characteristics without the related-key setting. On the other hand, since the found characteristic has many conditions, it generally works in the weak-key setting. We apply our technique to Grain v1. We show the conditional differential distinguisher on Grain v1 up to 114 rounds and have 240 weak keys. Our distinguisher can be executed in a practical time by using 232 chosen IVs. Moreover, we propose a key recovery attack. We distinguish the weak key from the randomly chosen key by using our distinguisher. After distinguishing the weak key, we obtain the 1-bit key from the condition on both key and IV.