Differential cryptanalysis of DES-like cryptosystems

The Data Encryption Standard (DES) is the best known and most widely used cryptosystem for civilian applications. It was developed at IBM and adopted by the National Bureau of Standards in the mid 1970s, and has successfully withstood all the attacks published so far in the open literature. In this paper we develop a new type of cryptanalytic attack which can break the reduced variant of DES with eight rounds in a few minutes on a personal computer and can break any reduced variant of DES (with up to 15 rounds) using less than 2⁵⁶ operations and chosen plaintexts. The new attack can be applied to a variety of DES-like substitution/permutation cryptosystems, and demonstrates the crucial role of the (unpublished) design rules.     

Substitution-permutation networks resistant to differential and linear cryptanalysis

In this paper we examine a class of product ciphers referred to as substitution-permutation networks. We investigate the resistance of these cryptographic networks to two important attacks: differential cryptanalysis and linear cryptanalysis. In particular, we develop upper bounds on the differential characteristic probability and on the probability of a linear approximation as a function of the number of rounds of substitutions. Further, it is shown that using large S-boxes with good diffusion characteristics and replacing the permutation between rounds by an appropriate linear transformation is effective in improving the cipher security in relation to these two attacks.This work was supported by the Natural Sciences and Engineering Research Council of Canada and the Telecommunications Research Institute of Ontario, and was presented at the rump session of CRYPTO '93. Howard Heys is now with Electrical Engineering, Faculty of Engineering and Applied Science, Memorial University of Newfoundland, St. John's, Newfoundland, Canada A1B 3X5.     

差分分析中的特征概率计算问题研究

该文指出了长期以来在差分密码分析中所采用的差分特征概率计算方法与差分分析基本原理不相符合的矛盾，对这一问题进行了深入研究，给出了二者等价的充分条件，力图解决差分分析方法的理论基础问题．     

对8轮ARIA算法的差分枚举攻击

给出了ARIA算法4轮差分性质,提出了对ARIA算法的差分枚举攻击。攻击了7轮和8轮ARIA-256算法,攻击的数据复杂度是256,攻击7轮时预计算的复杂度为2238.2次加密7轮ARIA算法,恢复密钥的计算复杂度是2124.2次加密7轮ARIA算法;攻击8轮时预计算的复杂度为2238次加密8轮ARIA算法,恢复密钥的计算复杂度是2253.6次加密8轮ARIA算法。     

一种新的改进型DES密码体制——RDES

介绍了日本密码学家Nakao Y等四人新近提出的一种改进型DES密码体制——随机化DES体制(RDES)。研究了该体制与DES体制的抗差分分析和抗线性分析能力。     

多重线性密码分析的改进

本文介绍一种有助于对分组密码作线性密码分析并能减少有效攻击所数据量的算法，给出了该算法成功率的计算公式，并与现有的线性密码分析方法作了比较。     

On Probability of Success in Linear and Differential Cryptanalysis

Despite their widespread usage in block cipher security, linear and differential cryptanalysis still lack a robust treatment of their success probability, and the success chances of these attacks have commonly been estimated in a rather ad hoc fashion. In this paper, we present an analytical calculation of the success probability of linear and differential cryptanalytic attacks. The results apply to an extended sense of the term “success” where the correct key is found not necessarily as the highest-ranking candidate but within a set of high-ranking candidates. Experimental results show that the analysis provides accurate results in most cases, especially in linear cryptanalysis. In cases where the results are less accurate, as in certain cases of differential cryptanalysis, the results are useful to provide approximate estimates of the success probability and the necessary plaintext requirement. The analysis also reveals that the attacked key length in differential cryptanalysis is one of the factors that affect the success probability directly besides the signal-to-noise ratio and the available plaintext amount.     

一类动态S盒的构造与差分性质研究

该文对有限域的逆与仿射变换复合得到的动态S盒进行了研究。首先给出了动态S盒变换差分概率的刻画方法,并给出了动态S盒变换的差分对应是不可能差分对应的充分必要条件及不可能差分的个数。接着给出了动态S盒变换最大差分概率的上界及可达性。最后利用模拟实验的方法研究了由随机S盒来构造的动态S盒的差分性质。理论和实验分析都表明,这类动态S盒变换具有远好于单个S盒的差分特性。     

LiCi分组密码算法的不可能差分分析

LiCi是由Patil等人(2017)提出的轻量级分组密码算法。由于采用新型的设计理念,该算法具有结构紧凑、能耗低、占用芯片面积小等优点,特别适用于资源受限的环境。目前该算法的安全性备受关注,Patil等人声称：16轮简化算法足以抵抗经典的差分攻击及线性攻击。该文基于S盒的差分特征,结合中间相遇思想,构造了一个10轮的不可能差分区分器。基于此区分器,向前后各扩展3轮,并利用密钥编排方案,给出了LiCi的一个16轮的不可能差分分析方法。该攻击需要时间复杂度约为2^83.08次16轮加密,数据复杂度约为2^59.76选择明文,存储复杂度约为2^76.76数据块,这说明16轮简化的LiCi算法无法抵抗不可能差分攻击。     

模2n数乘运算的差分性质研究

模2n数乘运算y=cx mod 2n是一个常用的密码算法编码环节,在许多密码算法中有广泛的应用,如Sosemanuk, RC6, MARS等。当常数c取奇数时,该运算环节是一个具有很强的非线性性质和良好实现效率的非线性置换。目前没有公开文献对此环节进行差分分析。该文对y=cx mod 2n(c是任意固定的正整数)的差分性质进行了研究,给出了差分转移概率为1时,输入差、输出差及常数c的结构,并给出计数公式。然后该文给出了其进位计数之间的递归关系,基于这种递归关系给出了计算该运算的差分转移概率的平均复杂度为O(n)的算法。     

一类Feistel密码的线性分析

该文提出一种新的求取分组密码线性偏差上界的方法，特别适用于密钥线性作用的Feistel密码．该分析方法的思路是，首先对密码体制线性偏差进行严格的数学描述，分别给出密码线性偏差与轮函数F及S盒的线性偏差的数学关系；然后通过求取线性方程组最小重量解，确定密码线性偏差的上界．     

Improved impossible differential and biclique cryptanalysis of HIGHT

HIGHT is a lightweight block cipher introduced in CHES 2006 by Hong et al as a block cipher suitable for low‐resource applications. In this paper, we propose improved impossible differential and biclique attacks on HIGHT block cipher both exploiting the permutation‐based property of the cipher's key schedule algorithm as well as its low diffusion. For impossible differential attack, we found a new 17‐round impossible differential characteristic that enables us to propose a new 27‐round impossible differential attack. The total time complexity of the attack is 2^120.4 where an amount of 2^59.3 chosen plaintext‐ciphertext pairs and 2^107.4 memory are required. We also instantiate a new biclique cryptanalysis of HIGHT, which is based on the new idea of splitting each of the forward and backward keys into 2 parts where the computations associated to each one are performed independently. The time complexity and data complexity of this attack are 2^125.7 and 2⁴², respectively. To the best of our knowledge, this is the fastest biclique attack on full‐round HIGHT.     

截断差分概率的上界估计与应用

截断差分分析是差分分析的一个变形。为说明一个密码算法能够抵抗截断差分分析,需要给出截断差分概率的上界。Masayuki Kanda等人就密码算法中S盒为GF(256)上的乘法逆变换和仿射双射变换复合而成时,提出了截断差分概率的上界一个猜想。该文就一般双射S盒给出了该概率上界问题的一个估计,Masayuki Kanda的猜想是该估计所考虑问题的一个特例,在一些情况下,该估计给出的上界与Masayuki Kanda的猜想接近。利用该结论可以衡量密码算法截断差分传递链概率的上界。该结论为分组密码抗截断差分分析的可证明安全性提供了理论依据。     

Biclique cryptanalysis on lightweight block ciphers I-PRESENT-80 and I-PRESENT-128

I-PRESENT was a lightweight SPN block cipher for resource-constraint environments such as RFID tags and sensor networks.The biclique structures of I-PRESENT with sieve-in-the-middle technique was an constracted.The biclique cryptanalysis schemes on full-round I-PRESENT-80 and I-PRESENT-128 were proposed for the first time.The results show that the data complexity of the biclique cryptanalysis on I-PRESENT-80 and I-PRESENT-128 is 2 ²⁶ and 2³⁶ chosen ciphertexts respectively，and the time complexity on them is 2 ^79.48 and 2 ^127.33 encryptions respectively.The time and data complexity are better than that of the exhaustive attack.In addition,the time complexity on them can be reduced to 2 ^78.61 and 2^126.48 encryptions by using related-key technology of I-PRESENT.     

Trivium流密码的基于自动推导的差分分析

Trivium是欧洲eSTREAM工程评选出的7个最终胜出的流密码算法之一.本文提出了针对Trivium的基于自动推导的差分分析技术,利用该技术可以得到任意轮Trivium算法的差分传递链.将该技术应用于轮数为288的简化版Trivium算法,提出了一个有效的区分攻击,仅需226个选择IV,区分优势为0.999665,攻击结果远优于已有的线性密码分析和多线性密码分析.将该技术应用于更多轮的Trivium算法和由Turan和Kara提出的修改Trivium算法,结果表明,初始化轮数低于359的Trivium算法不能抵抗差分分析,修改Trivium算法在抵抗差分分析方面优于原Trivium算法.     

线性分析法和差分分析法几个问题的研究

对DES—型密码体制的线性分析和差分分析法进行了研究,给出了差分分析法成功率与所需明文量之间的关系式,计算出了成功率公式。进而,提出了两种分组密码的分析方法并严格或举例证明了本文所提出方法的优越性。     

抗差分攻击的一些措施

本文在简要介绍差分攻击的基本原理的基础上,提出了一些抗击差分攻击的有效措施。     

Gimli/Xoodoo密码算法的不可能差分分析

大状态轻量级分组密码Gimli和Xoodoo具备逻辑门较少﹑低功耗和快速加密等诸多优点,备受业界关注。Gimli和Xoodoo算法均基于384 bit置换,大状态增加了对其安全性分析的困难性。该文通过引入AND、OR操作与S盒之间的等价表示,构建了Gimli和Xoodoo不可能差分区分器自动化搜索模型。进一步,为了验证不可能差分区分器的正确性,提出基于“二分法”的不可能差分区分器矛盾点检测新方法。结果表明：该文搜索并验证得到Gimli算法10轮不可能差分区分器以及Xoodoo算法4轮不可能差分区分器。特别地,Gimli算法不可能差分区分器轮数较已有结果提高了3轮。     

一类广义Feistel密码的安全性评估

该文评估一类广义Feistel密码(GFC)抵抗差分和线性密码分析的能力:如果轮函数是双射且它的最大差分和线性特征的概率分别是p和q,则16轮GFC的差分和线性特征的概率的上界为p7和q7;如果轮函数采用SP结构且是双射,S盒的最大差分和线性特征的概率是ps和qs,P变换的分支数为Pd,则16轮GFC的差分和线性特征的概率的上界为(ps)3Pd+1和(qs)3Pd+1。     

On the distribution of characteristics in bijective mappings

Differential cryptanalysis is a method of attacking iterated mappings based on differences known as characteristics. The probability of a given characteristic is derived from the XOR tables associated with the iterated mapping. If is a mapping : Z ₂ ^m , then for each , X, Y Z ₂ ^m the XOR table for gives the number of input pairs of difference X=X+X for which gp(X)+(X)=Y.The complexity of a differential attack depends upon two properties of the XOR tables: the density of zero entries in the table, and the size of the largest entry in the table. In this paper we present the first results on the expected values of these properties for a general class of mappings . We prove that if : Z ₂ ^m Z ₂ ^m is a bijective mapping, then the expected size of the largest entry in the XOR table for is bounded by 2m, while the fraction of the XOR table that is zero approaches e ^–1/2=0.60653. We are then able to demonstrate that there are easily constructed classes of iterated mappings for which the probability of a differential-like attack succeeding is very small.The author is presently employed by the Distributed System Technology Center, Brisbane, Australia.