Paper 2015/1174

On Data Complexity of Distinguishing Attacks vs. Message Recovery Attacks on Stream Ciphers

Goutam Paul and Souvik Ray


We revisit the different approaches used in the literature to estimate the data complexity of distinguishing attacks on stream ciphers and analyze their inter-relationships. In the process, we formally argue which approach is applicable (or not applicable) in what scenario. To our knowledge, this is the first kind of such an exposition. We also perform a rigorous statistical analysis of the message recovery attack that exploits a distinguisher and show that in practice there is a significant gap between the data complexities of a message recovery attack and the underlying distinguishing attack. This gap is not necessarily determined by a constant factor as a function of the false positive and negative rate, as one would expect. Rather this gap is also a function of the number of samples of the distinguishing attack. We perform a case study on RC4 stream cipher to demonstrate that the typical complexities for message recovery attack inferred in the literature are but under-estimates and the actual estimates are quite larger.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. Designs, Codes and Cryptography (2017)
Data ComplexityDistinguisherDistinguishing AttackMessage RecoveryStream Cipher
Contact author(s)
goutam paul @ isical ac in
2017-08-18: last of 2 revisions
2015-12-08: received
See all versions
Short URL
Creative Commons Attribution


      author = {Goutam Paul and Souvik Ray},
      title = {On Data Complexity of Distinguishing Attacks vs. Message Recovery Attacks on Stream Ciphers},
      howpublished = {Cryptology ePrint Archive, Paper 2015/1174},
      year = {2015},
      doi = {10.1007/s10623-017-0391-z},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.