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