### 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.

Available format(s)
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
See all versions
Short URL
https://ia.cr/2015/1174

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.