Algebraic Attacks on Summation Generators

Dong Hoon Lee; Jaeheon Kim; Jin Hong; Jae Woo Han; Dukjae Moon

Paper 2003/229

Algebraic Attacks on Summation Generators

Dong Hoon Lee, Jaeheon Kim, Jin Hong, Jae Woo Han, and Dukjae Moon

Abstract

We apply the algebraic attacks on stream ciphers with memories to the summation generator. For a summation generator that uses $n$ LFSRs, the algebraic equation relating the key stream bits and LFSR output bits can be made to be of degree less than or equal to $2^{\lceil\log_2 n \rceil}$, using $\lceil\log_2 n \rceil + 1$ consecutive key stream bits. This is much lower than the upper bound given by previous general results.

Metadata

Available format(s): PDF PS
Publication info: Published elsewhere. Presented at Fast Software Encryption (FSE) 2004, LNCS 3017, pp.34-48
Keywords: stream ciphers algebraic attacks summation generators
Contact author(s): dlee @ ensec re kr
History: 2008-08-06: last of 8 revisions; 2003-11-06: received; See all versions
Short URL: https://ia.cr/2003/229
License: CC BY

BibTeX

@misc{cryptoeprint:2003/229,
      author = {Dong Hoon Lee and Jaeheon Kim and Jin Hong and Jae Woo Han and Dukjae Moon},
      title = {Algebraic Attacks on Summation Generators},
      howpublished = {Cryptology {ePrint} Archive, Paper 2003/229},
      year = {2003},
      url = {https://eprint.iacr.org/2003/229}
}