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 LFSRs 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.

An attack against the improved summation generator was reported by Mex-Perera and Shepherd in 2002 by exploiting linear relations. Besides, in June 2005 an algebraic attack was developed. Using this attack a PC can calculate the initial state of the summation generator within 3 minutes even with 256 bit LFSRs.

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 Schneier, "Applied Cryptography," pg. 364, Summation Generator
• Mex-Perera, J. C. and Shepherd, S. J. 2002. "Cryptanalysis of a summation generator with 2-bit memory". Signal Process. 82, 12 (Dec. 2002), 2025–2028.
• "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

• Correlation Immunity and the Summation Generator
• The story of combiner correlation
• Algebraic Attacks on Summation Generators