Internal state recovery of Grain v1 employing guess-and-determine attack
The well-known stream cipher Grain v1 is one of the finalists of European eSTREAM project. In this study, a novel guess-and-determine attack on Grain v1 is introduced. The attack primarily employs a new conditional BSW sampling technique and the main creative idea is that the conditions are set not only on state bits but also on the updates of the registers for the BSW sampling technique. It is shown that using this technique we can further reduce the sampling resistance of Grain v1 to which is the best result so far. The attack leads to an efficient internal state recovery of Grain v1 with only online time employing a memory of , requiring keystreams each of length and preprocessing time. It is shown that these figures are obviously better compared with the previous results. This is also the first attempt to control the updates of the registers of Grain v1 in the guess-and-determine attack and hopefully this provides new insights for cryptanalysis on such compact stream ciphers.