Title: On the algebraic attack against summation type keystream generators

Authors: Md. Iftekhar Salam; Hoon-Jae Lee

Addresses: Department of Ubiquitous IT, Graduate School of Design and IT, Dongseo University, San 69-1 Jurye-2-dong, Sasang-gu, Busan 617-716, Korea ' Division of Information Network Engineering, School of Internet Engineering, Dongseo University, San 69-1 Jurye-2-dong, Sasang-gu, Busan 617-716, Korea

Abstract: The recently proposed algebraic attack has been proved to be very powerful against certain type of structure dependent cryptographic schemes especially LFSR-based stream ciphers. In this paper, we have investigated the algebraic attack against summation type of keystream generators. We have analysed the algebraic attack for three particular summation type generators: Rueppel's summation generator, LM generator and PingPong keystream generator. The efficiency of the algebraic attack against these generators are compared in terms of time, data and memory complexity. It will be shown that the, Rueppel's summation generator and the LM generator can be broken down with much less complexity compare to the exhaustive key search. However, for the case of PingPong stream cipher, we have found that it is infeasible to recover the secret key based on algebraic attack, mainly due to the irregular clock controlling function employed in the PingPong keystream generator.

Keywords: stream ciphers; nonlinearity; algebraic attacks; linearisation; cryptography; keystream generators.

DOI: 10.1504/IJICS.2012.051778

International Journal of Information and Computer Security, 2012 Vol.5 No.2, pp.132 - 149

Published online: 29 Jan 2013 *

Full-text access for editors Access for subscribers Purchase this article Comment on this article