This paper deals with the phase-shift fault analysis of stream cipher Grain v1. We assume that the attacker is able to desynchronize the linear and nonlinear registers of the cipher during the keystream generation phase by either forcing one of the registers to clock one more time, while the other register is not clocked, or by preventing one of the registers from clocking, while the other register is clocked. Using this technique, we are able to obtain the full inner state of the cipher in reasonable time (under 12 hours on a single PC) by using 150 bits of unfaulted keystream, 600 bits of faulted keystreams and by correctly guessing 28 bits of the linear register.

A desirable property of iterated cryptographic algorithms, such as stream ciphers or pseudo-random generators, is the lack of short cycles. Many of the previously mentioned algorithms are based on the use of linear feedback shift registers (LFSR) and nonlinear feedback shift registers (NLFSR) and their combination. It is currently known how to construct LFSR to generate a bit sequence with a maximum period, but there is no such knowledge in the case of NLFSR. The latter would be useful in cryptography application (to have a few taps and relatively low algebraic degree). In this article, we propose a simple method based on the generation of algebraic equations to describe iterated cryptographic algorithms and find their solutions using an SAT solver to exclude short cycles in algorithms such as stream ciphers or nonlinear feedback shift register (NLFSR). Thanks to the use of AIG graphs, it is also possible to fully automate our algorithm, and the results of its operation are comparable to the results obtained by manual generation of equations. We present also the results of experiments in which we successfully found short cycles in the NLFSRs used in Grain-80, Grain-128 and Grain-128a stream ciphers and also in stream ciphers Bivium and Trivium (without constants used in the initialization step).