构造Feistel-SP结构高阶差分区分器的新方法

Abstract

著名的分组密码算法DES所采用的Feistel结构一直活跃在对称密码领域, 它的安全性分析也是密码学的热点之一. AES的问世, 并没有减弱Feistel结构的吸引力, 反而给了很多分组密码与杂凑函数的设计者启发, 许多新出现的对称密码算法整体采用Feistel结构, 而轮函数采用SP结构, 一般称它们为Feistel-SP类算法. 本文对这类结构的代数次数增加情况进行研究, 利用Feistel结构的迭代特点与SP结构的积分性质, 改进了Feistel-SP类算法代数次数上界的估计方法. 利用这一方法可以构造此类算法更多轮数的高阶差分区分器与已知密钥高阶差分区分器. 此外, 我们利用这一技术得到了四种常用参数下Feistel-SP结构的高阶差分区分器, 其中两个为现在此类结构轮数最长的已知密钥区分器. 最后, 我们将这一技术用于分析LBlock分组密码, 得到它15轮的非随机性结果.

Alternate abstract:

The Feistel structure, used by the famous block cipher DES, has been active in the field of symmetric ciphers, and the cryptanalysis on the structure is one of the hot topics in cryptology. The appearance of AES does not diminish the appeal of the Feistel structure. On the contrary, it inspired many researchers to design new block ciphers and hash functions. Many new symmetric algorithms utilize the Feistel structure on the whole, and its round functions use the so-called SP network. They are generally known as the “Feistel-SP-like algorithms”. In this paper, we study the growth of the algebraic degrees of the Feistel-SP scheme. Utilizing the characteristic of the Feistel structure and the integral properties of the SP network, we improve the method of estimating the upper bounds of algebraic degrees for Feistel-SP-like algorithms. This method can be used to construct the (known-key) higher-order differential distinguisher with more rounds. Furthermore, we obtain higher-order differential distinguishers of the Feistel-SP network within four common parameters by using the new technique, and two of them have the maximum number of rounds in all exiting known-key distinguishers of this scheme. Finally, we apply the technique to the block cipher LBlock, and get its 15-round non-pseudo-random result.