An Improvement of Linearization-Based Algebraic Attacks
An Improvement of Linearization-Based Algebraic Attacks
复制标题
DOI：
10.1007/978-3-642-24586-2_14
复制
发表时间：
2011-10
期刊：
影响因子：
--
通讯作者：
Satrajit Ghosh;Abhijit Das
中科院分区：
文献类型：
--
作者：
Satrajit Ghosh;Abhijit Das
In an algebraic attack on a cipher, one expresses the encryption function as a system (usually overdefined) of multivariate polynomial equations in the bits of the plaintext, the ciphertext and the key, and subsequently solves the system for the unknown key bits from the knowledge of one or more plaintext/ciphertext pairs. The standard eXtended Linearization algorithm (XL) expands the initial system of equations by monomial multiplications. The expanded system is treated as a linear system in the monomials. For most block ciphers (like the Advanced Encryption Standard (AES)), the size of the linearized system turns out to be very large, and consequently, the complexity to solve the system often exceeds the complexity of brute-force search. In this paper, we propose a heuristic strategy XL_SGE to reduce the number of linearized equations. This reduction is achieved by applying structured Gaussian elimination before each stage of monomial multiplication. Experimentation on small random systems indicates that XL_SGE has the potential to improve the performance of the XL algorithm in terms of the size of the final solvable system. This performance gain is exhibited by our heuristic also in the case of a toy version of AES.
