A time--memory trade-off approach for the solution of nonlinear equation systems

We propose a memory-based method for the solution of a specific type of nonlinear equation systems. We observe that when the equations in a system can be separated into 2 parts, where each subset contains fewer parameters than the whole set of equations, the system can be solved faster with a preprocessing phase. We show that reduced rounds of AES produce such a system under a chosen plaintext scenario. This observation enables us to solve that system within a practically applicable complexity of 237 operations where a brute force approach requires 272 trials. The method can be used for the solution of other equation systems of the same structure. In the optimal case where we can divide the equations into 2, a problem that contains n binary variables can be solved at time O(n/2. 2n/2) operations and using O(2n/2) units of memory rather than O(2n) trials of the equation system.

Anahtar Kelimeler:

Key words: Time-memory trade-off, solution of nonlinear equations, AES, cryptanalysis

A time--memory trade-off approach for the solution of nonlinear equation systems

Keywords:

Key words: Time-memory trade-off, solution of nonlinear equations, AES, cryptanalysis,

PDF

___

A. Kipnis, A. Shamir, “Cryptanalysis of the HFE public key crypto system by relinearization”, In CRYPTO 99, LNCS, Vol. 1666, pp. 19–30, Springer-Verlag, 1999.
N. Courtois, A. Klimov, J. Patarin, A. Shamir, “Eﬃcient algorithms for solving overdeﬁned systems of multivariate polynomial equations”, In EUROCRYPT 2000, LNCS, Vol. 1807, pp. 392–407, Springer-Verlag, 2000.
N.T. Courtois, J. Pieprzyk, “Cryptanalysis of block ciphers with overdeﬁned systems of equations”, In ASIACRYPT 2002, LNCS, Vol. 2501, pp. 267–287, Springer-Verlag, 2002.
M.H. Hellman, “A cryptanalytic time-memory trade-oﬀ”, IEEE Transactions in Information Theory, Vol. IT-26, pp. 401–406, 1980.
A. Biryukov, A. Shamir, “Cryptanalytic time/memory/data trade-oﬀs for stream ciphers”, In ASIACRYPT 2000, LNCS, Vol. 1976, pp. 1–13, Springer-Verlag, 2000.
A. Biryukov, A. Shamir, D. Wagner, “Real time cryptanalysis of A5/1 on a PC”, In FSE 2000, LNCS, Vol. 1978, pp. 37–44, Springer-Verlag, 2001.
P. Oechslin, “Making a faster cryptanalytic time-memory trade-oﬀ”, In CRYPTO 2003, LNCS, Vol. 2729, pp. 617–630, Springer-Verlag, 2003.
S.H. Babbage, “Improved exhaustive search attacks on stream ciphers”, In European Convention on Security and Detection, IEE Conference publication, Vol. 408, pp. 161–166, IEE, 1995.
J.Dj. Goli´ c, “Cryptanalysis of alleged A5 stream cipher”, In EUROCRYPT 97, LNCS, Vol. 1233, pp. 239–255, Springer-Verlag, 1997.
D.E. Denning, In Cryptography and Data Security, page 100, Addison-Wesley, 1982.
W. Diﬃe, M.E. Hellman, “Exhaustive cryptanalysis of the NBS data encryption standard”, Computer, Vol. 10, 74–84, 1977.
H. Morita, K. Ohta, K. Miyaguchi, “A switching closure test to analyze cryptosystems”, In CRYPTO 1991, LNCS, Vol. 576, pp. 183–193, Springer-Verlag, 1992.
M. Matsui, A. Yamagishi, “A new method for known plaintext attack of FEAL cipher”, In EUROCRYPT 1992, LNCS, Vol. 658, pp. 81–91, Springer-Verlag, 1993.
D. Khovratovich, I. Nikoli´ c, R.P. Weinmann, “Meet-in-the-middle attacks on SHA-3 candidates”, In FSE 2009, LNCS, Vol. 5665, pp. 228–245, Springer-Verlag, 2009.
H. Gilbert, M. Minier, “A collision attack on 7 rounds of Rijndael”, In The Third AES Candidate Conference, 2000.
H. Demirci, A.A. Sel¸cuk, “A meet in the middle attack on 8-round AES”, In FSE 2008, LNCS, Vol. 5086, pp. 116–126, Springer-Verlag, 2008.
K. Nyberg, L.R. Knudsen, “Provable security against a diﬀerential attack”, Journal of Cryptology, Vol. 8(1), pp. 27–38, 1995.
“Fips-197: Advanced Encryption Standard”, November 2001, available at http://csrc.nist.gov/publications/ﬁps/ﬁps197/ﬁps-197.pdf.
J. Daemen, L. Knudsen, V. Rijmen, “The block cipher SQUARE”. In FSE 1997, LNCS, Vol. 1267, pp. 149–165, Springer-Verlag, 1997.
N. Ferguson, J. Kelsey, S. Lucks, B. Schneier, M. Stay, D. Wagner, D. Whiting, “Improved cryptanalysis of Rijndael”, In FSE 2000, LNCS, Vol. 1978, pp. 213–230, Springer-Verlag, 2001.
S. Lucks, “Attacking seven rounds of Rijndael under 192-bit and 256-bit keys”, In The Third AES Candidate Conference, 2000.
E. Biham, N. Keller, “Cryptanalysis of reduced variants of Rijndael”, In The Third AES Candidate Conference, 2000.
J.H. Cheon, M.J. Kim, K. Kim, J. Lee, S. Kang, “Improved impossible diﬀerential cryptanalysis of Rijndael”, In ICISC ’2001, LNCS, Vol. 2288, pp. 39–49, Springer-Verlag, 2001.
R.C.W. Phan, M.U. Siddiqi, “Generalized impossible diﬀerentials of Advanced Encryption Standard”, IEE Electronics Letters, Vol. 37(14), pp. 896–898, 2001.
R.C.W. Phan, “Classes of impossible diﬀerentials of Advanced Encryption Standard”, IEE Electronics Letters, Vol. 38(11), pp. 508–510, 2002.
R.C.W. Phan, “Impossible diﬀerential cryptanalysis of 7-round Advanced Encryption Standard AES”, Information Processing Letters, Vol. 91, pp. 33–38, 2004.
B. Bahrak, M.R. Aref, “Impossible diﬀerential attack on seven-round AES-128”, In IET Information Security Journal, Vol. 2, pp. 28–32, 2008.
B. Bahrak, M.R. Aref, “A novel impossible diﬀerential cryptanalysis of AES”, In Proceedings of the Western European Workshop on Research in Cryptology, Bochum Germany, 2007.
W. Zhang, W. Wun, D. Feng, “New results on impossible diﬀerential cryptanalysis of reduced AES”, In Proceedings of ICISC 2007, LNCS, Vol. 4817, pp. 239–250, Springer-Verlag, 2007.
J. Lu, O. Dunkelman, N. Keller, J. Kim, “New impossible diﬀerential attacks on AES”, In INDOCRYPT ’2008, LNCS, Vol. 5365, pp. 279–293, Springer-Verlag, 2008.
A. Biryukov, “Boomerang attack on 5 and 6-round AES”, In The Fourth Conference on Advanced Encryption Standard, 2004.
A. Biryukov, O. Dunkelman, N. Keller, D. Khovratovich, A. Shamir, “Key recovery attacks of practical complexity on AES variants with up to 10 rounds”, 2009. available at http://eprint.iacr.org/2009/374.pdf.
A. Biryukov, D. Khovratovich, I. Nikoli´ c, “Distinguisher and related-key attack on the full AES-256 (extended version)”, In CRYPTO 2009, LNCS, Vol. 5677, pp. 231–249, Springer-Verlag, 2009.
A. Biryukov, D. Khovratovich, “Related-key cryptanalysis of the full AES-192 and AES-256”, 2009. available at http://eprint.iacr.org/2009/317.pdf.
D.J. Bernstein, “Cache-timing attacks on AES”, 2005. URL: http://cr.yp.to/antiforgery/cachetiming-20050414.pdf. A. Cabezon, H.P. Wynn, “Mincut ideals of two-terminal networks”, Applicable Algebra in Engineering, Communication and Computing, Vol. 21, pp. 443–457, 2010.