Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Current Challenges in Developing Open Source Computer Algebra Systems Read chapter Read first chapter

2016 | OriginalPaper | Chapter

Advanced Algebraic Attack on Trivium

Authors : Frank-M. Quedenfeld, Christopher Wolf

Published in: Mathematical Aspects of Computer and Information Sciences

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

This paper presents an algebraic attack against Trivium that breaks 625 rounds using only 4096 bits of output in an overall time complexity of \(2^{42.2}\) Trivium computations. While other attacks can do better in terms of rounds (799), this is a practical attack with a very low data usage (down from \(2^{40}\) output bits) and low computation time (down from \(2^{62}\)).
From another angle, our attack can be seen as a proof of concept: how far can algebraic attacks can be pushed when several known techniques are combined into one implementation? All attacks have been fully implemented and tested; our figures are therefore not the result of any potentially error-prone extrapolation, but results of practical experiments.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
previous chapter Solving Extended Ideal Membership Problems in Rings of Convergent Power Series via Gröbner Bases
next chapter Compressing Big Data: When the Rate of Convergence to the Entropy Matters
Literature
1.
Abbott, T., Albrecht, M., Bard, G., Bodrato, M., Brickenstein, M., Dreyer, A., Dumas, J.G., Hart, W., Harvey, D., James, J., Kirkby, D., Pernet, C., Said, W., Wood, C.: M4RI(e)–Linear Algebra over \(F_2\) (and \(F_2^e\)). http://​m4ri.​sagemath.​org/​
2.
Albrecht, M.: Algorithmic Algebraic Techniques and their Application to Block Cipher Cryptanalysis. Ph.D. thesis, Royal Holloway, University of London (2010)
3.
Armknecht, F., Krause, M.: Algebraic attacks on combiners with memory. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 162–175. Springer, Heidelberg (2003)CrossRef
4.
Ars, G., Faugère, J.-C., Imai, H., Kawazoe, M., Sugita, M.: Comparison between XL and Gröbner basis algorithms. In: Lee, P.J. (ed.) ASIACRYPT 2004. LNCS, vol. 3329, pp. 338–353. Springer, Heidelberg (2004)CrossRef
5.
Biryukov, A., De Cannière, C.: Block ciphers and systems of quadratic equations. In: Johansson, T. (ed.) FSE 2003. LNCS, vol. 2887, pp. 274–289. Springer, Heidelberg (2003)CrossRef
6.
7.
De Cannière, C., Preneel, B.: Trivium. In: Robshaw, M., Billet, O. (eds.) New Stream Cipher Designs. LNCS, vol. 4986, pp. 244–266. Springer, Heidelberg (2008)
8.
Courtois, N.T., Bard, G.V.: Algebraic cryptanalysis of the data encryption standard. In: Galbraith, S.D. (ed.) Cryptography and Coding 2007. LNCS, vol. 4887, pp. 152–169. Springer, Heidelberg (2007)CrossRef
9.
Courtois, N.T., Klimov, A.B., Patarin, J., Shamir, A.: Efficient algorithms for solving overdefined systems of multivariate polynomial equations. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 392–407. Springer, Heidelberg (2000)CrossRef
10.
Courtois, N.T., Meier, W.: Algebraic attacks on stream ciphers with linear feedback. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 345–359. Springer, Heidelberg (2003)CrossRef
11.
Courtois, N.T., Pieprzyk, J.: Cryptanalysis of Block ciphers with overdefined systems of equations. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol. 2501, pp. 267–287. Springer, Heidelberg (2002)CrossRef
12.
Courtois, N.T., Sepehrdad, P., Sušil, P., Vaudenay, S.: \({\sf ElimLin}\) algorithm revisited. In: Canteaut, A. (ed.) FSE 2012. LNCS, vol. 7549, pp. 306–325. Springer, Heidelberg (2012)CrossRef
13.
Diem, C.: The XL-algorithm and a conjecture from commutative algebra. In: Lee, P.J. (ed.) ASIACRYPT 2004. LNCS, vol. 3329, pp. 323–337. Springer, Heidelberg (2004)CrossRef
14.
Dinur, I., Shamir, A.: Cube attacks on tweakable black box polynomials. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 278–299. Springer, Heidelberg (2009)CrossRef
15.
Faugère, J.C.: A new efficient algorithm for computing gröbner bases (F4). In: Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, ISSAC 2002, pp. 75–83. Springer (2002)
16.
Faugère, J.C.: A new efficient algorithm for computing Gröbner bases without reduction to zero (\(F_5\)). In: International Symposium on Symbolic and Algebraic Computation, ISSAC 2002, pp. 75–83. ACM Press, July 2002
17.
18.
Faugère, J.-C., Joux, A.: Algebraic cryptanalysis of hidden field equation (HFE) cryptosystems using Gröbner bases. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 44–60. Springer, Heidelberg (2003)CrossRef
19.
Faugère, J.-C., Otmani, A., Perret, L., Tillich, J.-P.: Algebraic cryptanalysis of Mceliece variants with compact keys. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 279–298. Springer, Heidelberg (2010)CrossRef
20.
Fouque, P.-A., Vannet, T.: Improving key recovery to 784 and 799 rounds of trivium using optimized cube attacks. In: Moriai, S. (ed.) FSE 2013. LNCS, vol. 8424, pp. 502–517. Springer, Heidelberg (2014)
21.
22.
23.
24.
25.
Schilling, T.E., Raddum, H.: Analysis of trivium using compressed right hand side equations. In: Kim, H. (ed.) ICISC 2011. LNCS, vol. 7259, pp. 18–32. Springer, Heidelberg (2012)CrossRef
26.
27.
28.
Sugita, M., Kawazoe, M., Perret, L., Imai, H.: Algebraic cryptanalysis of 58-Round SHA-1. In: Biryukov, A. (ed.) FSE 2007. LNCS, vol. 4593, pp. 349–365. Springer, Heidelberg (2007)CrossRef
29.
30.
Yang, B.-Y., Chen, J.-M.: All in the XL family: theory and practice. In: Park, C., Chee, S. (eds.) ICISC 2004. LNCS, vol. 3506, pp. 67–86. Springer, Heidelberg (2005)CrossRef
31.
Yang, B.-Y., Chen, J.-M.: Theoretical analysis of XL over small fields. In: Wang, H., Pieprzyk, J., Varadharajan, V. (eds.) ACISP 2004. LNCS, vol. 3108, pp. 277–288. Springer, Heidelberg (2004)CrossRef
Metadata
Title
Advanced Algebraic Attack on Trivium
Authors
Frank-M. Quedenfeld
Christopher Wolf
Copyright Year
2016
Book
Mathematical Aspects of Computer and Information Sciences

Print ISBN: 978-3-319-32858-4

Electronic ISBN: 978-3-319-32859-1

Copyright Year: 2016

DOI
https://doi.org/10.1007/978-3-319-32859-1_23

Premium Partner

    Image Credits