On LFSR based Stream Ciphers - analysis and design

Sammanfattning: Stream ciphers are cryptographic primitives used to ensure privacy in digital communication. In this thesis we focus on stream ciphers built using Linear Feedback Shift Registers (LFSRs). Several different stream ciphers are analysed and new attacks are presented. In addition, two new stream ciphers are presented, both based on the same design. The first attack is performed on SOBER-t16 and SOBER-t32. A new distinguishing attack is presented for simplified versions of the two ciphers, as well as for the complete version of SOBER-t16. Next, the cipher A5/1, used in the GSM standard for mobile telephones, is analysed. The resulting attack is an initial state recovery attack which recovers the secret key using approximately 5 minutes of known keystream. The attack takes roughly 5 minutes to perform on today's standard PC. Bluetooth is a well-known standard for wireless communication and the cipher responsible for the secrecy within that standard is called E0. An initial state recovery algorithm on E0 is presented, based on recently discovered correlations within the cipher. These new correlations are stronger than previously known. This attack, however, is only applicable to E0 in a theoretical perspective, since the required length of the observed keystream is longer than allowed in the Bluetooth standard. Following this, two distinguishing attacks are presented targeting clock controlled generators; the shrinking generator and the self-shrinking generator. The attack on the shrinking generator is based on a new observation that the majority bits of a block surrounding the tap positions in the LFSR output also fulfils the linear recurrence equation. The attack on the self-shrinking generator identifies two new classes of weak feedback polynomials. For the first class, both a distinguishing attack and an initial state recovery attack are presented. This distinguishing attack is remarkable in the sense that the required length of the observed keystream only grows linearly in the length of the shift register. For the second class of weak feedback polynomials a distinguishing attack is given. The final part of this thesis concerns the design of stream ciphers. Two new designs are presented, SNOW 1.0 and SNOW 2.0, the latter being an improvement on the former. These ciphers are designed to be very fast, especially in a software implementation.