×

Optimising Gröbner bases on Bivium. (English) Zbl 1205.94081

Summary: Bivium is a reduced version of the stream cipher Trivium. In this paper we investigate how fast a key recovery attack on Bivium using Gröbner bases is. First we explain the attack scenario and the cryptographic background. Then we identify the factors that have impact on the computation time and show how to optimise them. As a side effect these experiments benchmark several Gröbner basis implementations. The optimised version of the Gröbner attack has an expected running time of \(2^{39.12}\) s, beating the attack time of our previous SAT solver attack by a factor of more than 330. Furthermore this approach is faster than an attack based on BDDs, an exhaustive key search, a generic time-memory trade-off attack and a guess-and-determine strategy.

MSC:

94A60 Cryptography
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
13-04 Software, source code, etc. for problems pertaining to commutative algebra
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Maximov, A., Khovratovich, D.: New state recovery attack on RC4. Cryptology ePrint Archive, Report 2008/017. http://eprint.iacr.org/2008/017 (2008) · Zbl 1183.94041
[2] Lu, Y., Meier, W., Vaudenay, S.: The conditional correlation attack: a practical attack on bluetooth encryption. CRYPTO 2005 (2005) · Zbl 1145.94446
[3] Maximov, A., Johansson, T., Babbage, S.: An improved correlation attack on A5/1. Select. Areas Cryptogr. vol. 3357, 1–18 (2004) · Zbl 1117.94327
[4] eSTREAM: eSTREAM–The ECRYPT Stream Cipher Project. http://www.ecrypt.eu.org/stream/ (2008). Accessed 9 Jan 2008 · Zbl 1259.94006
[5] eSTREAM: Call for Stream Cipher Primitives, version 1.3. http://www.ecrypt.eu.org/stream/call/ (2005). Accessed 9 Jan 2008
[6] Babbage, S., De Cannière, C., Canteaut, A., Cid, C., Gilbert, H., Johansson, T., Parker, M., Preneel, B., Rijmen, V., Robshaw, M.: The eSTREAM Portfolio, eSTREAM. http://www.ecrypt.eu.org/stream/portfolio.pdf (2008). Accessed 9 Jan 2008
[7] De Cannière, C., Preneel, B.: TRIVIUM–a stream cipher construction inspired by block cipher design principles. eSTREAM, ECRYPT Stream Cipher Project, Report 2006/021. http://www.ecrypt.eu.org/stream/trivium.html (2005)
[8] Raddum, H.: Cryptanalytic results on TRIVIUM, eSTREAM, ECRYPT Stream Cipher Project, Report 2006/039. http://www.ecrypt.eu.org/stream/ (2006)
[9] Dinur, I., Shamir, A.: Cube attacks on tweakable black box polynomials. EUROCRYPT 2009. LNCS, vol. 5479, pp. 278–299 (2009) · Zbl 1239.94045
[10] Aumasson, J-P., Dinur, I., Meier, W., Shamir, A.: Cube testers and key recovery attacks on reduced-round MD6 and trivium. FSE 2009. LNCS, vol. 5665, pp. 1–22 (2009) · Zbl 1291.94051
[11] Bardet, M., Faugère, J-C., Salvy, B., Yang, B-Y.: Asymptotic behaviour of the degree of regularity of semi-regular polynomial systems. MEGA 2005 (2005)
[12] Buchberger, B.: Gröbner Bases: A short introduction for system theorists. Computer Aided Systems Theory–EUROCAST 2001. LNCS, vol. 2178, pp. 1–14 (2001) · Zbl 1023.68882
[13] Stein, W.: Sage Mathematics Software (Version 2.9.2), The SAGE Group. http://www.sagemath.org (2007). Accessed 9 Jan 2008
[14] Greuel, G-M., Pfister, G., Schönemann, H.: Singular 3.0.4. A computer algebra system for polynomial computations. Centre for Computer Algebra, University of Kaiserslautern. http://www.singular.uni-kl.de/ (2007). Accessed 9 Jan 2008 · Zbl 1344.13002
[15] Wolfram Research, Inc.: Mathematica Edition: Version 6.0.1. http://www.wolfram.com/ (2007). Accessed 9 Jan 2008
[16] Grayson, D., Stillman, M.: Macaulay 2, a software system for research in algebraic geometry. Version 1.1 AMD64. http://www.math.uiuc.edu/Macaulay2/ (2007)
[17] Bosma, W., Cannon, J., Playoust, C.: MAGMA computational algebra system. Vers. 2.14–10. http://magma.maths.usyd.edu.au/magma/ (2008) · Zbl 0898.68039
[18] Brickenstein, M., Dreyer, A.: PolyBoRi: A framework for Gröbner basis computations with Boolean polynomials. In: Electronic Proceedings of the MEGA 2007–Effective Methods in Algebraic Geometry (2007) · Zbl 1186.68571
[19] Eibach, T., Pilz, E., Völkel, G.: Attacking bivium using SAT solvers. SAT’08–Theory and Applications of Satisfiability Testing. LNCS, vol. 4996, pp. 63–76. Springer (2008) · Zbl 1138.68536
[20] Eibach, T., Pilz, E., Steck, S.: Comparing and optimising two generic attacks on bivium. Proceedings of SASC’08–The State of the Art of Stream Ciphers, pp. 57–68, ECRYPT (2008)
[21] Maximov, A., Biryukov, A.: Two trivial attacks on trivium. Select. Areas Cryptogr. vol. 4876, 36–55 (2007) · Zbl 1154.94418
[22] Biryukov, A., Shamir, A.: Cryptoanalytic time/memory/data tradeoffs for stream ciphers. ASIACRYPT 2000. LNCS, vol. 1976, pp. 1–13 (2000) · Zbl 0980.94013
[23] Eibach, T., Völkel, G.: Optimising Gröbner bases on bivium. Proceedings of SCC’08–First International Conference on Symbolic Computation and Cryptography, pp. 83–94. LMIB Beihang University (2008)
[24] Cox D.A., Little J., O’Shea D.B.: Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. Springer, New York (2007) · Zbl 1118.13001
[25] Faugère J-C.: A new efficient algorithm for computing Gröbner bases (F 4). J. Pure Appl. Algebra 139, 61–88 (1999) · Zbl 0930.68174 · doi:10.1016/S0022-4049(99)00005-5
[26] Faugère, J-C.: A new efficient algorithm for computing Gröbner bases without reduction to zero (F 5). Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, ACM Special Interest Group on Symbolic and Algebraic Manipulation, pp. 75–83 (2002) · Zbl 1072.68664
[27] Brickenstein, M.: Slimgb: Gröbner bases with slim polynomials. Reports on Computer Algebra 35, ZCA, University of Kaiserslautern (2005) · Zbl 1200.13044
[28] Courtois, N., Bard, G.: Algebraic cryptanalysis of the data encryption standard. Cryptology ePrint Archive, Report 2006/402 (2006)
[29] Krause, M.: BDD-Based cryptanalysis of keystream generators. EUROCRYPT 2002. LNCS, vol. 2332, pp. 239–237 (2002) · Zbl 1055.94018
[30] Bard, G., Courtois, N., Jefferson, C.: Efficient methods for conversion and solution of sparse systems of low-degree multivariate polynomials over GF(2) via SAT-solvers. Cryptology ePrint Archive, Report 2007/024 (2007)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.