Cryptology ePrint Archive: Report 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.

Category / Keywords: secret-key cryptography / Data Complexity, Distinguisher, Distinguishing Attack, Message Recovery, Stream Cipher

Date: received 6 Dec 2015

Contact author: goutam paul at isical ac in

Available format(s): PDF | BibTeX Citation

Version: 20151208:215947 (All versions of this report)

Short URL: ia.cr/2015/1174

Discussion forum: Show discussion | Start new discussion