AES的插值攻击方法

由Jakobsen和Knudsen提出的插值攻击, 是对具有简单代数函数作为S盒的分组密码十分有效的一种密码分析方法. 本文分析了AES(Advanced Encryption Standard)算法中的代数表达式, 得出三轮AES加密后的明密文代数表达式具有次数较低(低于255次）的特点. 由于此特点, 通过拉格郎日插值公式, 利用255个函数值可唯一地求出254次多项式的表示, 把插值攻击应用到了低轮AES的密码分析中, 并给出了相应的结论及证明. 利用此攻击方法, 通过选取256对明密文, 即可还原4轮AES的密钥, 利用2048对明密文, 可成功地破译5轮AES密码, 并可把此攻击扩展到6轮的AES密码.

The Interpolation Attack of the AES

The method of the interpolation attack on block ciphers, proposed by Jakobsen and Knudsen, is very effective for attacking ciphers which use simple algebraic functions as S-boxes. The algebraic representation of the AES(Advanced Encryption Standard) cipher is studied in this paper. A conclusion is given that the 3-round AES ciphertexts have a polynomial expression of a low degree on the plaintexts(less than 255). Using 255 values, the polynomial of degree 254 can be obtain by interpolation formula,. Hence, the interpolation attack is introduced into the cryptanalysis of the round-reduced AES, and the relevant results and the corresponding proofs are given. By this attack method, the key of 4-round AES cipher is found using only 256 chosen plaintexts, and the 5-round AES cipher is broken successfully using 2048 chosen plaintexts. This attack can also be extended to the 6-round AES cipher.