paper
title
Reduced Complexity Attacks on the Alternating Step Generator.
authors
Shahram Khazaei, Simon Fischer, and Willi Meier.
publication
In C. Adams, A. Miri, and M. Wiener, editors, Selected Areas in Cryptography - SAC 2007, 14th International Workshop, Ottawa, Canada, August 16-17, 2007. Proceedings, volume 4876 of Lecture Notes in Computer Science, pages 1-16. Springer-Verlag, 2007.
abstract
In this paper, we present some reduced complexity attacks on the Alternating Step Generator (ASG). The attacks are based on a quite general framework and mostly benefit from the low sampling resistance of the ASG, and of an abnormal behavior related to the distribution of the initial states of the stop/go LFSR's which produce a given segment of the output sequence. Our results compare well with previous results as they show a greater flexibility with regard to known output of the ASG, which amounts in reduced complexity. We will also give a closed form for the complexity of attacks on ASG (and SG) as presented in [Joh98].