Misplaced Pages

Summation generator

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. Please help improve this article by introducing more precise citations. (November 2013) (Learn how and when to remove this message)

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

Category: