Paper 2009/412

Distinguishing Attacks on Stream Ciphers Based on Arrays of Pseudo-random Words

Nathan Keller and Stephen D. Miller


In numerous modern stream ciphers, the internal state consists of a large array of pseudo-random words, and the output key-stream is a relatively simple function of the state. In [Paul-Preneel], it was heuristically shown that in various cases this structure may lead to distinguishing attacks on the cipher. In this paper we further investigate this structural attack. We present a rigorous proof of the main probabilistic claim used in the attack in the basic cases, and demonstrate by examining a concrete example (the cipher SN3) that the heuristic assumptions of the attack are remarkably precise in more complicated cases. Furthermore, we use the general technique to devise a distinguishing attack on the stream cipher MV3 requiring $2^{82}$ words of key-stream. Unlike the attacks in [Paul-Preneel], our attack does not concentrate on the least significant bits of the words, thus allowing to handle the combination of more operations (XORs, modular additions and multiplications, and rotations by a fixed number of bits) in the update and output rules of the cipher.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
stream cipherscryptanalysis
Contact author(s)
miller @ math rutgers edu
2009-09-01: received
Short URL
Creative Commons Attribution


      author = {Nathan Keller and Stephen D.  Miller},
      title = {Distinguishing Attacks on Stream Ciphers Based on Arrays of Pseudo-random Words},
      howpublished = {Cryptology ePrint Archive, Paper 2009/412},
      year = {2009},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.