Summation generator

The summation generator, created in 1985, by Rainer Rueppel, was a cryptography and security front-runner in the late 1980s. It operates by taking the output of two LFSR's through an adder with carry. The operation's strength is that it is nonlinear. However, through the early 1990s various attacks against the summation generator eventually led to its fall to a correlation attack. In 1995 Klapper and Goresky were able to determine the summation generator's sequence in only 2¹⁹ bits.

An improved summation generator with 2-bit memory was then proposed by cryptographers Lee and Moon. In the new generator scheme an extra bit of memory is added to the nonlinear combining function. The objective in the modification was to make the summation generator immune to correlation attack.

However, in June 2005 an algebraic attack against the improved summation generator was developed. Using this attack a PC can calculate the initial state of the summation generator within 3 minutes even with 256 bit LFSR's

References

* R. A. Rueppel, "Correlation immunity and the Summation Generator," Advances in Cryptography-EUROCRYPT '85 proceedings, Berlin: Springer-Verlag, 1986, pp. 260-272.

* W.Meier and O. Staffelbach, "Correlation properties of Combiners with Memory in Stream Ciphers," Advances in Cryptography-EUROCRYPT '90 proceedings, Berlin: Springer-Verlag, 1991, pp. 204-213.

* Bruce Schneir, "Applied Cryptography," pg. 364, Summation Generator

* "An algebraic attack on the improved summation generator with 2-bit memory" Information Processing Letters, Volume 93 , Issue 1, (January 2005) Pages: 43 - 46 ISSN:0020-0190

External links

* [http://dsns.csie.nctu.edu.tw/research/crypto/HTML/PDF/C85/260.PDF Correlation Immunity and the Summation Generator]

* [http://ciphersbyritter.com/RES/COMBCORR.HTM The story of combiner correlation]

* [http://citeseer.ist.psu.edu/cache/papers/cs/31398/http:zSzzSzeprint.iacr.orgzSz2003zSz229.pdf/lee03algebraic.pdf Algebraic Attacks on Summation Generators]