nach oben

Cryptography and Communications

Erschienen in:

01.12.2012

Applying cube attacks to stream ciphers in realistic scenarios

verfasst von: Itai Dinur, Adi Shamir

Erschienen in: Cryptography and Communications | Ausgabe 3-4/2012

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Cube attacks were introduced in Dinur and Shamir (2009) as a cryptanalytic technique that requires only black box access to the underlying cryptosystem. The attack exploits the existence of low degree polynomial representation of a single output bit (as a function of the key and plaintext bits) in order to recover the secret key. Although cube attacks can be applied in principle to almost any cryptosystem, most block ciphers iteratively apply a highly non-linear round function (based on Sboxes or arithmetic operations) a large number of times which makes them resistant to cube attacks. On the other hand, many stream ciphers (such as Trivium (De Cannière and Preneel 2008)), are built using linear or low degree components and are natural targets for cube attacks. In this paper, we describe in detail how to apply cube attacks to stream ciphers in various settings with different assumptions on the target stream cipher and on the data available to the attacker.

Vorheriger Artikel High order differential attacks on stream ciphers

Nächster Artikel On the nonlinearity of maximum-length NFSR feedbacks

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nur mit Berechtigung zugänglich

Throughout this paper, we refer to all polynomials of degree 1 as linear polynomials. Thus, we do not distinguish between affine polynomials in which the value of the free coefficient is one, and polynomials of degree 1 in which the value of this coefficient is zero.

We note that although trivial equations do not give information about the secret key, they can be used in order to distinguish the cipher from a random function [1].

When considering a big cube of dimension 2^d + k and its subcubes of dimension d − 1, there are k + 1 variables which define the big cube, whose value stay constant in each subcube. The number of subcubes is \(\binom{d+k}{d-1}\), if we only consider subcubes for which the constant value for the k + 1 variables is zero.

We use the standard notion of distance between functions (which is used in many papers, such as [9]), i.e., the fraction of the domain on which the functions differ.

Analyzing how the previous choices of equations in B influence the probability that the next equation will increase the rank of B seems difficult, and thus we provide a worst-case analysis.

Aumasson, J.-P., Dinur, I., Meier, W., Shamir, A.: Cube testers and key recovery attacks on reduced-round MD6 and trivium. In: Dunkelman, O. (ed.) FSE. Lecture Notes in Computer Science, vol. 5665, pp. 1–22. Springer (2009)

Blum, M., Luby, M., Rubinfeld, R.: Self-testing/correcting with applications to numerical problems. In: STOC, pp. 73–83. ACM (1990)

Courtois, N., Klimov, A., Patarin, J., Shamir, A.: Efficient algorithms for solving overdefined systems of multivariate polynomial equations. In: Preneel, B. (ed.) EUROCRYPT. Lecture Notes in Computer Science, vol. 1807, pp. 392–407. Springer (2000)

De Cannière, C., Preneel, B.: Trivium. In: New Stream Cipher Designs. LNCS, vol. 4986, pp. 84–97. Springer (2008)

Dinur, I., Shamir, A.: Cube attacks on tweakable black box polynomials. In: Joux, A. (ed.) EUROCRYPT. Lecture Notes in Computer Science, vol. 5479, pp. 278–299. Springer (2009)

Dinur, I., Shamir, A.: Generic analysis of small cryptographic leaks. In: Breveglieri, L., Joye, M., Koren, I., Naccache, D., Verbauwhede, I. (eds.) FDTC, IEEE Computer Society, pp. 39–48 (2010)

Faugère, J.C.: A new efficient algorithm for computing Grø”bner bases without reduction to zero (F5). In: Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, ISSAC ’02, pp. 75–83. ACM, New York, NY, USA (2002)CrossRef

Gaborit, P., Ruatta, O.: Efficient erasure list-decoding of Reed-Muller codes. In: 2006 IEEE International Symposium on Information Theory, pp. 148–152 (2006)

Goldreich, O., Goldwasser, S., Lehman, E., Ron, D., Samorodnitsky, A.: Testing monotonicity. Combinatorica 20(3), 301–337 (2000)MathSciNetMATHCrossRef

10.

Kaufman, T., Litsyn, S., Xie, N.: Breaking the epsilon-soundness bound of the linearity test over GF(2). SIAM J. Comput. 39(5), 1988–2003 (2010)MathSciNetMATHCrossRef

11.

Lai, X.: Higher order derivatives and differential cryptanalysis. In: “Symposium on Communication, Coding and Cryptography” in honor of James L. Massey on the Occasion of his 60’th Birthday, pp. 227–233 (1994)

12.

Luby, M., Mitzenmacher, M., Shokrollahi, M.A., Spielman, D.A.: Efficient erasure correcting codes. IEEE Trans. Inf. Theory 47(2), 569–584 (2001)MathSciNetMATHCrossRef

13.

Reed, I.S.: A class of multiple-error-correcting codes and the decoding scheme. IEEE Trans. Inf. Theory 4(4), 38–49 (1954)

14.

Vielhaber, M.: Breaking ONE.FIVIUM by AIDA an Algebraic IV Differential Attack. Cryptology ePrint Archive, Report 2007/413 (2007)

Titel: Applying cube attacks to stream ciphers in realistic scenarios
verfasst von: Itai Dinur
Adi Shamir
Publikationsdatum: 01.12.2012
Verlag: Springer US
Erschienen in: Cryptography and Communications / Ausgabe 3-4/2012
Print ISSN: 1936-2447
Elektronische ISSN: 1936-2455
DOI: https://doi.org/10.1007/s12095-012-0068-4

Springer Professional

Abstract

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

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 3-4/2012

On the nonlinearity of maximum-length NFSR feedbacks

Guest editorial

High order differential attacks on stream ciphers

Synthetic linear analysis with applications to CubeHash and Rabbit

State cycles, initialization and the Trivium stream cipher

Cryptanalysis of WG-7: a lightweight stream cipher

Premium Partner