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
-
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},
url = {https://eprint.iacr.org/2015/1174}
}
