Cryptology ePrint Archive: Report 2003/229

Algebraic Attacks on Summation Generators

Dong Hoon Lee and Jaeheon Kim and Jin Hong and 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.

Category / Keywords: stream ciphers, algebraic attacks, summation generators

Publication Info: Presented at Fast Software Encryption (FSE) 2004, LNCS 3017, pp.34-48

Date: received 3 Nov 2003, last revised 6 Aug 2008

Contact author: dlee at ensec re kr

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20080806:101904 (All versions of this report)

Short URL: ia.cr/2003/229

Discussion forum: Show discussion | Start new discussion