nach oben

Designs, Codes and Cryptography

Erschienen in:

31.07.2017

On data complexity of distinguishing attacks versus message recovery attacks on stream ciphers

verfasst von: Goutam Paul, Souvik Ray

Erschienen in: Designs, Codes and Cryptography | Ausgabe 6/2018

Einloggen, um Zugang zu erhalten

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Vorheriger Artikel On two-weight -codes

Nächster Artikel On some constacyclic codes over , their images, and new codes

Nur mit Berechtigung zugänglich

A family of probability distributions $\left\{ P_{\theta }\right\} $ indexed by the parameter $\theta $ is said to be identifiable w.r.t. $\theta $, if

$$\begin{aligned} \theta _1\ne \theta _2 \Rightarrow P_{\theta _1 } \ne P_{\theta _2}. \end{aligned}$$

Otherwise the family is said to be non-identifiable.

AlFardan N.J., Bernstein D.J., Paterson K.G., Poettering B., Schuldt J.C.N.: On the security of RC4 in TLS. In: King S.T. (ed.) Proceedings of the 22th USENIX Security Symposium, Washington, DC, USA, 14–16 August 2013, pp. 305–320. USENIX Association, Santa Clara (2013).

Aumasson J.-P., Fischer S., Khazaei S., Meier W., Rechberger C.: New features of latin dances: analysis of salsa, chacha, and rumba. In: Nyberg K. (ed.) Fast Software Encryption, 15th International Workshop, FSE 2008, Lausanne, Switzerland, 10–13 February 2008, Revised Selected Papers, vol. 5086. Lecture Notes in Computer Science, pp. 470–488. Springer, Berlin (2008).

Baignères T., Junod P., Vaudenay S.: How far can we go beyond linear cryptanalysis? In: Lee P.J. (ed.) Advances in Cryptology—ASIACRYPT 2004, 10th International Conference on the Theory and Application of Cryptology and Information Security, Jeju Island, Korea, 5–9 December 2004, Proceedings, vol. 3329. Lecture Notes in Computer Science, pp. 432–450. Springer, Berlin (2004).

Baignères T., Sepehrdad P., Vaudenay S.: Distinguishing distributions using Chernoff information. In: Heng S.-H., Kurosawa K. (eds.) Provable Security—4th International Conference, ProvSec 2010, Malacca, Malaysia, 13–15 October 2010, Proceedings, vol. 6402. Lecture Notes in Computer Science, pp. 144–165. Springer, Berlin (2010).

Banik S., Isobe T.: Cryptanalysis of the full Spritz stream cipher. In: Peyrin T. (ed.) Fast Software Encryption—23rd International Conference, FSE 2016, Bochum, Germany, 20–23 March 2016, Revised Selected Papers, vol. 9783. Lecture Notes in Computer Science, pp. 63–77. Springer, Berlin (2016).

Basu R., Ganguly S., Maitra S., Paul G.: A complete characterization of the evolution of RC4 pseudo random generation algorithm. J. Math. Cryptol. 2(3), 257–289 (2008).MathSciNetCrossRefMATH

Blahut R.E.: Principles and Practice of Information Theory. Addison-Wesley Longman Publishing, Boston (1987).MATH

Blondeau C., Gérard B., Tillich J.-P.: Accurate estimates of the data complexity and success probability for various cryptanalyses. Des. Codes Cryptogr. 59(1–3), 3–34 (2011).MathSciNetCrossRefMATH

Casella G., Berger R.: Statistical Inference. Duxbury Resource Center, Boston (2001).MATH

10.

Cover T.M., Thomas J.A: Elements of Information Theory. Wiley Series in Telecommunications and Signal Processing. Wiley-Interscience, Hoboken (2006).

11.

Ekdahl P., Johansson, T.: Distinguishing attacks on sober-t16 and t32. In: Daemen J., Rijmen V. (eds.) Fast Software Encryption, 9th International Workshop, FSE 2002, Leuven, Belgium, 4–6 February 2002, Revised Papers, vol. 2365. Lecture Notes in Computer Science, pp. 210–224. Springer, Berlin (2002).

12.

Fluhrer S.R., McGrew, D.A.: Statistical analysis of the alleged RC4 keystream generator. In: Schneier B. (ed.) Fast Software Encryption, 7th International Workshop, FSE 2000, New York, NY, USA, 10–12 April 2000, Proceedings, vol. 1978. Lecture Notes in Computer Science, pp. 19–30. Springer, Berlin (2000).

13.

Garman C., Paterson K.G., Van der Merwe, T.: Attacks only get better: password recovery attacks against RC4 in TLS. In: Jung J., Holz T. (eds.) 24th USENIX Security Symposium, USENIX Security 15, Washington, D.C., USA, 12–14 August 2015, pp. 113–128. USENIX Association, Santa Clara (2015).

14.

Gupta S.S., Maitra S., Paul G., Sarkar S.: (Non-)random sequences from (non-)random permutations–analysis of RC4 stream cipher. J. Cryptol. 27(1), 67–108 (2014).CrossRefMATH

15.

Gut A.: Probability: A Graduate Course, 2nd edn. Springer, New York (2013).CrossRefMATH

16.

Hardy G.H., Littlewood J.E., Pólya G.: Inequalities. Cambridge Mathematical Library. Cambridge University Press, Cambridge (1952).

17.

Kullback S., Leibler R.A.: On information and sufficiency. Ann. Math. Stat. 22, 49–86 (1951).MathSciNetCrossRefMATH

18.

Maitra S., Paul G., Raizada S., Sen S., Sengupta R.: Some observations on HC-128. Des. Codes Cryptogr. 59(1–3), 231–245 (2011).MathSciNetCrossRefMATH

19.

Mantin I.: Predicting and distinguishing attacks on RC4 keystream generator. In: Cramer R. (ed.) Advances in Cryptology—EUROCRYPT 2005, 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Aarhus, Denmark, 22–26 May 2005, Proceedings, vol. 3494. Lecture Notes in Computer Science, pp. 491–506. Springer, Berlin (2005)

20.

Mantin I., Shamir A.: A practical attack on broadcast RC4. In: Matsui M. (ed.) Fast Software Encryption, 8th International Workshop, FSE 2001 Yokohama, Japan, April 2-4, 2001, Revised Papers, vol. 2355. Lecture Notes in Computer Science, pp. 152–164. Springer, Berlin (2001)

21.

Neyman, J., Pearson, E.S.: On the problem of the most efficient tests of statistical hypotheses. Philos. Trans. R. Soc. Lond. Ser. A 231, 289–337 (1933).

22.

Samajder S., Sarkar P.: Another look at normal approximations in cryptanalysis. IACR Cryptology. ePrint Archive 2015, 679 (2015).

23.

Samajder S., Sarkar P.: Rigorous upper bounds on data complexities of block cipher cryptanalysis. IACR Cryptology. ePrint Archive 2015, 916 (2015).

24.

Stankovski P., Ruj S., Hell M., Johansson T.: Improved distinguishers for HC-128. Des. Codes Cryptogr. 63(2), 225–240 (2012).MathSciNetCrossRefMATH

25.

Wu H.: The stream cipher HC-128. In: Robshaw M.J.B., Billet O. (eds.) New Stream Cipher Designs—The eSTREAM Finalists, vol. 4986. Lecture Notes in Computer Science, pp. 39–47. Springer, Berlin (2008).

Titel: On data complexity of distinguishing attacks versus message recovery attacks on stream ciphers
verfasst von: Goutam Paul
Souvik Ray
Publikationsdatum: 31.07.2017
Verlag: Springer US
Erschienen in: Designs, Codes and Cryptography / Ausgabe 6/2018
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-017-0391-z

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Weitere Artikel der Ausgabe 6/2018

On self-dual double circulant codes

Leakage-resilient attribute based encryption in prime-order groups via predicate encodings

New optimal binary sequences with period 4p via interleaving Ding–Helleseth–Lam sequences

A recursive construction for simple t-designs using resolutions

On some constacyclic codes over , their images, and new codes

A framework for constructing partial geometric difference sets