Simple power analysis applied to nonlinear feedback shift registers

Linear feedback shift registers (LFSRs) and nonlinear feedback shift register (NLFSRs) are major components of stream ciphers. It has been shown that, under certain idealised assumptions, LFSRs and LFSR-based stream ciphers are susceptible to cryptanalysis using simple power analysis (SPA). In this study, the authors show that SPA can be practically applied to a CMOS digital hardware circuit to determine the bit values of an NLFSR and SPA therefore has applicability to NLFSR-based stream ciphers. A new approach is used with the cryptanalyst collecting power consumption information from the system on both edges (triggering and non-triggering) of the clock in the digital hardware circuit. The method is applied using simulated power measurements from an 80-bit NLFSR targeted to an 180 nm CMOS implementation. To overcome inaccuracies associated with mapping power measurements to the cipher data, the authors offer novel analytical techniques which help the analysis to find the bit values of the NLFSR. Using the obtained results, the authors analyse the complexity of the analysis on the NLFSR and show that SPA is able to successfully determine the NLFSR bits with modest computational complexity and a small number of power measurement samples.