Paper 2015/1174

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

Goutam Paul and Souvik Ray

Abstract

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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Designs, Codes and Cryptography (2017)
DOI
10.1007/s10623-017-0391-z
Keywords
Data ComplexityDistinguisherDistinguishing AttackMessage RecoveryStream Cipher
Contact author(s)
goutam paul @ isical ac in
History
2017-08-18: last of 2 revisions
2015-12-08: received
See all versions
Short URL
https://ia.cr/2015/1174
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/1174,
      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{https://eprint.iacr.org/2015/1174}},
      url = {https://eprint.iacr.org/2015/1174}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.