×

zbMATH — the first resource for mathematics

Obtaining and solving systems of equations in key variables only for the small variants of AES. (English) Zbl 1205.94076
Summary: This work is devoted to attacking the small scale variants of the Advanced Encryption Standard (AES) via systems that contain only the initial key variables. To this end, we investigate a system of equations that naturally arises in the AES, and then introduce an elimination of all the intermediate variables via normal form reductions. The resulting system in key variables only is solved then. We also consider a possibility to apply our method in the meet-in-the-middle scenario especially with several plaintext/ciphertext pairs. We elaborate on the method further by looking for subsystems which contain fewer variables and are overdetermined, thus facilitating solving the large system.

MSC:
94A60 Cryptography
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
13P15 Solving polynomial systems; resultants
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Albrecht, M., Cid, C.: Algebraic Techniques in Differential Cryptanalysis. http://eprint.iacr.org/2008/177.pdf (2008) · Zbl 1291.94043
[2] Albrecht, M., Cid, C.: Algebraic techniques in differential cryptanalysis. In: Proceedings of the First International Conference on Symbolic Computation and Cryptography, Beijing, China, pp. 55–60 (2008) · Zbl 1291.94043
[3] Albrecht, M., Bard, G., The M4RI Team.: The M4RI Library–Version 20080901. http://m4ri.sagemath.org (2008)
[4] Bardet, M., Faugére, J.-C., Salvy, B.: On the complexity of Gröbner basis computation of semi-regular overdetermined algebraic equations. In: ICPSS Paris, pp. 71–75, November (2004)
[5] Barkan, E., Biham, E.: How many ways can you write Rijndael? In: ASIACRYPT 2002, Lecture Notes in Computer Science, vol. 2501, pp. 160–175 (2002) · Zbl 1065.68529
[6] Billet, O., Patain, J., Seurin, Y.: Analysis of intermediate field systems. In: Proceedings of the First International Conference on Symbolic Computation and Cryptography, Beijing, China, pp. 110–117 (2008)
[7] Biryukov, A., Khovratovich, D.: Related-key cryptanalysis of the full AES-192 and AES-256. In: Asiacrypt’09 (in press) · Zbl 1267.94041
[8] Bogdanov, A., Kizhvatov, I., Pyshkin, A.: Algebraic methods in side-channel collision attacks and practical collision detection. In: INDOCRYPT 2008, Lecture Notes in Computer Science, vol. 5365, pp. 251–265 (2008) · Zbl 1203.94095
[9] Brickenstein, M.: Slimgb: Gröbner bases with slim polynomials. In: Zentrum für Computeralgebra, Kaiserslautern, September (2005) · Zbl 1200.13044
[10] Brickenstein, M., Bulygin, S.: Attacking AES via solving systems in the key variables only. In: Proceedings of the First International Conference on Symbolic Computation and Cryptography, Beijing, China, pp. 118–123 (2008)
[11] Brickenstein M., Dreyer A.: PolyBoRi: a framework for Gröbner basis computation with Boolean polynomials. Special Issue Effect. Methods Algebraic Geom. J. Symb. Comput. 44(9), 1326–1345 (2009) · Zbl 1186.68571
[12] Brickenstein, M., Dreyer, A.: PolyBoRi: a framework for Gröbner basis computation with Boolean polynomials. In: MEGA’2007 (2007) · Zbl 1186.68571
[13] Brickenstein, M., Dreyer, A., Greuel, G., Wedler, M., Wienand, O.: New developments in the theory of Gröbner bases and applications to formal verification. http://arxiv.org/abs/0801.1177 . Preprint (2008) · Zbl 1164.68019
[14] Buchberger, B.: Ein Algorithmus zum Auffinden der Basiselemente des Restklassenrings nach einem nulldimensionalen Polynomideal. Universität Innsbruck, Dissertation (1965) · Zbl 1245.13020
[15] Buchmann, J., Pyshkin, A., Weinmann, R.-P.: A zero-dimensional Groebner basis for AES-128. In: FSE 2006, Lecture Notes in Computer Science, vol. 4047, pp. 78–88 (2006) · Zbl 1234.94032
[16] Buchmann, J., Pyshkin, A., Weinmann, R.-P.: Block ciphers sensitive to Groebner basis attacks. In: CT-RSA 2006, Lecture Notes in Computer Science, vol. 3860, pp. 313–331. Springer, New York (2006) · Zbl 1125.94013
[17] Cannon, J.J., Bosma, W. (eds.): Handbook of Magma Functions, Edition 2.14 (2007)
[18] Cid, C., Leurent, G.: An analysis of the XSL algorithm. In: Roy, B. (ed.) Advances in Cryptology–ASIACRYPT 2005, Lecture Notes in Computer Science, vol. 3788, pp. 333–352 (2005) · Zbl 1154.94384
[19] Cid C., Murphy S., Robshaw M.J.B.: Algebraic Aspects of the Advanced Encryption Standard. Springer, New York (2006) · Zbl 1130.68047
[20] Cid, C., Murphy, S., Robshaw, M.: An algebraic framework for cipher embeddings. In: Proceedings of the 10th IMA International Conference on Coding and Cryptography, Lecture Notes in Computer Science, vol. 3796, pp. 278–289 (2005) · Zbl 1122.94033
[21] Cid, C., Murphy, S., Robshaw, M.: Computational and algebraic aspects of the advanced encryption standard. In: Seventh International Workshop on Computer Algebra in Scientific Computing, CASC 2004, pp. 93–103, St. Petersburg, Russia (2004) · Zbl 1130.68047
[22] Cid, C., Murphy, S., Robshaw, M.: Small scale variants of the AES. In: Fast Software Encryption–FSE2005, Lecture Notes in Computer Science, vol. 3557, pp. 145–162 (2005) · Zbl 1140.94330
[23] Clegg, M., Edmonds, J., Impagliazzo, R.: Using the Groebner basis algorithm to find proofs of unsatisfiability. In: Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, pp. 174–183 (1996) · Zbl 0938.68825
[24] Courtois, N., Pieprzyk, J.: Cryptanalysis of block ciphers with overdefined systems of equations. In: Asiacrypt 2002, Lecture Notes in Computer Science, vol. 2501, pp. 267–287. Springer, New York (2002) · Zbl 1065.94543
[25] Condrat, C., Kalla, P.: A Gröbner basis approach to CNF-formulae preprocessing. In: Tools and Algorithms for the Construction and Analysis of Systems, Lecture Notes in Computer Science, vol. 4424, pp. 618–631. Springer, New York (2007) · Zbl 1186.68576
[26] Dubois, V., Founque, P.-A., Shamir, A., Stern, J.: Practical cryptanalysis of SFLASH. In: Advances in Cryptology–CRYPTO 2007
[27] Faugére J.-C.: A new efficient algorithm for computing Groöbner bases (F4). J. Pure Appl. Algebra 139, 61–88 (1999) · Zbl 0930.68174 · doi:10.1016/S0022-4049(99)00005-5
[28] Faugére J.-C., Gianni P., Lazard D., Mora T.: Efficient computation of zero-dimensional Gröbner bases by change of ordering. J. Symb. Comput. 16(4), 329–344 (1993) · Zbl 0805.13007 · doi:10.1006/jsco.1993.1051
[29] Faugére, J.-C., Joux, A.: Algebraic cryptanalysis of hidden field equation (HFE) cryptosystem using Gröbner bases. In: Boneh, D. (ed.) Advances in Cryptology–EUROCRYPTO 2003, Lecture Notes in Computer Science, vol. 2729, pp. 44–60 (2003) · Zbl 1122.94371
[30] Faugére, J.-C., Perret, L.: On the security of UOV. In: Proceedings of the First International Conference on Symbolic Computation and Cryptography, Beijing, China, pp. 103–109 (2008)
[31] Greuel, G.-M., Pfister, G.: A SINGULAR Introduction to Commutative Algebra. Springer, New York (2008) · Zbl 1344.13002
[32] Greuel, G.-M., Pfister, G., Schönemann, H.: Singular 3.0. A Computer Algebra System for Polynomial Computations. Centre for Computer Algebra, University of Kaiserslautern. http://www.singular.uni-kl.de (2005) · Zbl 1344.13002
[33] Lim, C.-W., Khoo, K.: An analysis of XSL applied to BES. In: FSE 2007, Lecture Notes in Computer Science, vol. 4593, pp. 242–253. Springer, New York (2007) · Zbl 1186.94459
[34] Miolane, C.V., Knudsen, L.R.: Block cipher analysis. Academic dissertation, in series: (ISBN), p. 176, 200902
[35] Murphy, S., Robshaw, M.: Essential algebraic structure within the AES. In: Yung, M. (ed.) Advances in Cryptology–CRYPTO 2002, Lecture Notes in Computer Science, vol. 2442, pp. 1–16. Springer, Berlin (2002) · Zbl 1026.94537
[36] National Institute of Standards and Technology. Advanced Encryption Standard. FIPS 197, 26 November (2001)
[37] Raddum, H.: MRHS equation systems. In: Lecture Notes in Computer Science, vol. 4876, pp. 232–245 (2007) · Zbl 1154.94429
[38] Toli, I., Zanoni, A.: An algebraic interpretation of AES-128. In: Dobbertin, H., Rijmen, V., Sowa, A. (eds.) Advanced Encryption Standard AES: 4th International Conference, AES 2004, Revised Selected and Invited Papers. Lecture Notes in Computer Science, vol. 3373, pp. 84–97 (2004). doi: 10.1007/11506447_8 · Zbl 1117.94337
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.