Title: Three ways to mount distinguishing attacks on irregularly clocked stream ciphers

Authors: Hakan Englund, Thomas Johansson

Addresses: Department of Information Technology, Lund University, Lund, Sweden. ' Department of Information Technology, Lund University, Lund, Sweden

Abstract: Many stream ciphers use irregular clocking to introduce non-linearity to the keystream. We present three distinguishers on irregularly clocked linear feedback shift registers. The general idea used is to find suitable linear combinations of keystream bits, here called samples, that are drawn from a biased distribution. We describe how to place windows around the estimated positions around members of the linear combinations, and very efficiently create many samples with low computational complexity. We also describe ideas based on constructing samples consisting of vectors of bits (words) instead of single binary samples. These vectors based methods can distinguish the cipher using fewer keystream bits but sometimes require a higher computational complexity.

Keywords: cryptanalysis; distinguishing attacks; irregularly clocked LFSRs; linear feedback shift registers; keystream generators; low weight linear relations; pseudo-random number generators; security; step-one-step-two generators; stream ciphers; vector based attacks; networks; irregular clocking.

DOI: 10.1504/IJSN.2006.010826

International Journal of Security and Networks, 2006 Vol.1 No.1/2, pp.95 - 102

Published online: 06 Sep 2006 *

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