Research on Feedback with Carry (2-Adic) Shift Registers

This major project is in the area of Stream Ciphers. This is a method of encryption in which a binary sequence (a ``key'') is added to a message bit by bit to hide it from an eavesdropper. A legitimate receiver who knows the key can subtract it out to recover the message, but a hostile eavesdropper who does not know the key cannot. The goal of the study of stream ciphers is to design key generators that are fast and whose keys resist attack. Conversely, we want to design attacks on existing key generators to expose their weaknesses. These attacks are generally of the form ``given a few bits of the key, try to discover the remainder of the key.''

In joint work with Mark Goresky, I am studying a new type of binary sequence generator, Feedback with Carry Shift Registers or FCSRs which we invented in 1993. This construction is based on division in the 2-adic numbers. Many of the algebraic properties of linear feedback shift registers have parallels for FCSRs. We have developed a method of synthesizing FCSRs from short subsequences of their output. This provides us with a new measure for cryptologic security of stream ciphers, the 2-adic span. Future designers of stream cipher will have to show that their sequences have large 2-adic span. We have used these ideas to give an attack on a well known and commercially used stream cipher, the summation combiner. We have also extended our initial construction to more general registers based on division in ramified and unramified extensions of the 2-adic numbers. We are currently studying methods of modifying FCSRs so the resulting sequences have large 2-adic span, as well as resistance to other cryptologic attacks. These results have caused excitement in the cryptography community. I first presented them at the Cambridge Algorithms Workshop in Cambridge, England, December 1993, and an abstract appears in the Springer LNCS volume number 809 ("Fast Software Encryption"). I described extensions at several conferences in 1994 and 1995: Midwest Theory Day; Eurocrypt 1994; and The IEEE International Symposium on Information Theory. Further results were presented at the Leuven Algorithms Workshop in December 1994. Results relating to statistical properties were presented at Eurocrypt 1995 (Springer LNCS volume 921). The FCSR synthesis algorithm was presented at Crypto 1995 (Springer LNCS volume 963).

This material is based upon work supported by the National Science Foundation under Grant No. 9400762