Making the Impossible Possible

This paper introduces new techniques and correct complexity analyses for impossible differential cryptanalysis, a powerful block cipher attack. We show how the key schedule of a cipher impacts an impossible differential attack, and we provide a new formula for the time complexity analysis that takes this parameter into account. Further, we show, for the first time, that the technique of multiple differentials can be applied to impossible differential attacks. Then, we demonstrate how this technique can be combined in practice with multiple impossible differentials or with the so-called state-test technique. To support our proposal, we implemented the above techniques on small-scale ciphers and verified their efficiency and accuracy in practice. We apply our techniques to the cryptanalysis of ciphers including AES-128, CRYPTON-128, ARIA-128, CLEFIA-128, Camellia-256 and LBlock. All of our attacks significantly improve previous impossible differential attacks and generally achieve the best memory complexity among all previous attacks against these ciphers.     

Linearly weak keys of RC5 [private-key cipher]

The author examines the application of linear cryptanalysis to the RC5 private-key cipher and shows that there are expected to be weak keys for which the attack is applicable to many rounds. It is demonstrated that, for the 12-round nominal RC5 version with a 64 bit block size and a 128 bit key, there are 2²⁸ weak keys for which only ~2¹⁷ known plaintexts are required to break the cipher. There are 268 keys for which the cipher is theoretically breakable, requiring ~2⁵⁷ known plaintexts. The analysis highlights the sensitivity of RC5 security to its key scheduling algorithm     

FOX算法的中间相遇攻击

研究了FOX分组密码算法在中间相遇攻击下的安全性。首先,分别构造了FOX64和FOX128的3轮中间相遇区分器,实施了6轮中间相遇攻击,得到对6轮FOX64和FOX128较好的攻击结果。其次,将FOX128的中间相遇区分器扩展到4轮,并结合时间存储数据折衷的方法,攻击了7轮FOX128,与已有的攻击结果相比,攻击的时间复杂度和存储复杂度略大,而数据复杂度明显降低。     

A new method for resynchronization attack

This paper presents a new method for resynchronization attack, which is the combination of the differential cryptanalysis and algebraic attack. By using the new method one gets a system of linear equations or low-degree equations about initial keys, and the solution of the system of equations results in the recovery of the initial keys. This method has a lower computational complexity and better performance of attack in contrast to the known methods. Accordingly, the design of the resynchronization stream generators should be reconsidered to make them strong enough to avoid our attacks. When implemented to the Toyocrypt, our method gains the computational complexity of O（2^17）, and that of 0（2^67） for LILI-128.     

CIKS-128分组算法的相关密钥-差分攻击

分析研究了CIKS-128分组密码算法在相关密钥-差分攻击下的安全性.利用DDP结构和非线性函数的差分信息泄漏规律构造了一条高概率相关密钥-差分特征,并给出攻击算法,恢复出了192bit密钥;在此基础上,对剩余64bit密钥进行穷举攻击,恢复出了算法的全部256bit密钥.攻击所需的计算复杂度为2⁷⁷次CIKS-128算法加密,数据复杂度为2⁷⁷个相关密钥-选择明文,存储复杂度为2^25.4字节存储空间.分析结果表明,CIKS-128算法在相关密钥-差分攻击条件下是不安全的.     

A Practical-Time Related-Key Attack on the KASUMI Cryptosystem Used in GSM and 3G Telephony

Over the last 20 years, the privacy of most GSM phone conversations was protected by the A5/1 and A5/2 stream ciphers, which were repeatedly shown to be cryptographically weak. They are being replaced now by the new A5/3 and A5/4 algorithms, which are based on the block cipher KASUMI. In this paper we describe a new type of attack called a sandwich attack, and use it to construct a simple related-key distinguisher for 7 of the 8 rounds of KASUMI with an amazingly high probability of 2^?14. By using this distinguisher and analyzing the single remaining round, we can derive the complete 128-bit key of the full KASUMI with a related-key attack which uses only 4 related keys, 2²⁶ data, 2³⁰ bytes of memory, and 2³² time. These completely practical complexities were experimentally verified by performing the attack in less than two hours on a single-core of a PC. Interestingly, neither our technique nor any other published attack can break the original MISTY block cipher (on which KASUMI is based) significantly faster than exhaustive search. Our results thus indicate that the modifications made by ETSI’s SAGE group in moving from MISTY to KASUMI made it extremely weak when related-key attacks are allowed, but do not imply anything about its resistance to single-key attacks. Consequently, there is no indication that the way KASUMI is implemented in GSM and 3G networks is practically vulnerable in any realistic attack model.     

Cobra-H64/128算法的相关密钥-差分攻击

本文研究了Cobra-H64/128分组密码算法在相关密钥-差分攻击下的安全性.针对Cobra-H64算法,利用新构造的相关密钥-差分路径和CP逆变换存在的信息泄露规律给出攻击算法1,恢复出了全部128bit密钥,相应的计算复杂度为2^40.5次Cobra-H64算法加密,数据复杂度为2^40.5个选择明文,存储复杂度为2^22bit,成功率约为1;针对Cobra-H128算法,利用新构造的相关密钥-差分路径给出攻击算法2,恢复出了全部256bit密钥,相应的计算复杂度为2^76次Cobra-H128算法加密,数据复杂度为2^76个选择明文,存储复杂度为2^16.2bit.分析结果表明,Cobra-H64/128算法在相关密钥-差分攻击条件下是不安全的.     

A cryptanalytic time-memory trade-off

A probabilistic method is presented which cryptanalyzes anyNkey cryptosystem inN^{2/3}operational withN^{2/3}words of memory (average values) after a precomputation which requiresNoperations. If the precomputation can be performed in a reasonable time period (e.g, several years), the additional computation required to recover each key compares very favorably with theNoperations required by an exhaustive search and theNwords of memory required by table lookup. When applied to the Data Encryption Standard (DES) used in block mode, it indicates that solutions should cost between1 and100 each. The method works in a chosen plaintext attack and, if cipher block chaining is not used, can also be used in a ciphertext-only attack.     

Information leakage of Feistel ciphers

We examine the information leakage between sets of plaintext and ciphertext bits in symmetric-key block ciphers. The paper demonstrates the effectiveness of information leakage as a measure of cipher security by relating information leakage to linear cryptanalysis and by determining a lower bound on the amount of data required in an attack from an upper bound on information leakage. As well, a model is developed which is used to estimate the upper bound on the information leakage of a general Feistel (1975) block cipher. For a cipher that fits the model well, the results of the analysis can be used as a measure in determining the number of rounds required for security against attacks based on information leakage. It is conjectured that the CAST-128 cipher fits the model well and using the model it is predicted that information leaked from 20 or fewer plaintext bits is small enough to make an attack on CAST-128 infeasible     

减轮LEA密码算法的积分攻击

LEA密码算法是一类ARX型轻量级分组密码,广泛适用于资源严格受限的环境.本文使用中间相错技术找到LEA算法的86条8轮和6条9轮零相关区分器,进一步利用零相关区分器和积分区分器的关系,构造出5条8轮和1条9轮积分区分器.在8轮积分区分器的基础上,利用密钥扩展算法的性质和部分和技术,首次实现了对LEA-128的10轮积分攻击,攻击的计算复杂度为2¹²⁰次10轮LEA-128加密.进一步,实现了对LEA-192的11轮积分攻击以及对LEA-256的11轮积分攻击,计算复杂度分别为2^185.02次11轮LEA-192加密和2²⁴⁸次11轮LEA-256加密.     

低轮FOX分组密码的差分碰撞攻击

This paper presents a method for differential collision attack of reduced FOX block cipher based on 4-round distinguishing property. It can be used to attack 5, 6 and 7-round FOX64 and 5-round FOX128. Our attack has a precomputation phase, but it can be obtained before attack and computed once for all. This attack on the reduced to 4-round FOX64 requires only 7 chosen plaintexts, and performs 242 .84-round FOX64 encryptions. It could be extended to 5 (6, 7)-round FOX64 by a key exhaustive search behind the fourth round. The time complexities of 5, 6 and 7-round FOX64 are approximate to 2106 .8, 2170 .8and 2234 .8, respectively. The attack on reduced FOX128 demands 11 chosen plain-texts, requires 2192one round encryptions in precomputation, performs approximately 276 .5 one round encryptions on 4-round FOX128, and is 2204 .5against 5-round FOX128.     

On the security of the Yi-Tan-Siew chaotic cipher

This paper presents a comprehensive analysis on the security of the Yi-Tan-Siew chaotic cipher. A differential chosen-plaintext attack and a differential chosen-ciphertext attack are suggested to break the sub-key K, under the assumption that the time stamp can be altered by the attacker, which is reasonable in such attacks. Also, some security problems about the sub-keys /spl alpha/ and /spl beta/ are clarified, from both theoretical and experimental points of view. Further analysis shows that the security of this cipher is independent of the use of the chaotic tent map, once the sub-key K is removed via the proposed suggested differential chosen-plaintext attack.     

Cryptanalysis of the parameterized improved fast encryption algorithm for multimedia

The Parameterized Improved Fast Encryption Algorithm for Multimedia (PIFEA-M) is a fast cipher recently proposed by Chefranov (IEEE communications letters, Vol. 12, No. 6, June 2008) to resist an implementation dependent differential attack on earlier versions of the cipher. In this paper we show that a similar differential style attack can still break PIFEA-M with a very low data and computational complexity.     

数字视频广播通用加扰算法的不可能差分分析

数字视频广播通用加扰算法(DVB-CSA)是一种混合对称加密算法,由分组密码加密和流密码加密两部分组成。该算法通常用于保护视讯压缩标准(MPEG-2)中的信号流。主要研究DVB-CSA分组加密算法(DVB-CSA-Block Cipher, CSA-BC)的不可能差分性质。通过利用S盒的具体信息,该文构造了CSA-BC的22轮不可能差分区分器,该区分器的长度比已有最好结果长2轮。进一步,利用构造的22轮不可能差分区分器,攻击了缩减的25轮CSA-BC,该攻击可以恢复24 bit种子密钥。攻击的数据复杂度、时间复杂度和存储复杂度分别为253.3个选择明文、232.5次加密和224个存储单元。对于CSA-BC的不可能差分分析,目前已知最好结果能够攻击21轮的CSA-BC并恢复16 bit的种子密钥量。就攻击的长度和恢复的密钥量而言,该文的攻击结果大大改进了已有最好结果。     

Two-Key Triple Encryption

In this paper we consider multiple encryption schemes built from conventional cryptosystems such as DES. The existing schemes are either vulnerable to variants of meet-in-the-middle attacks, i.e., they do not provide security corresponding to the full key length used or there is no proof that the schemes are as secure as the underlying cipher. We propose a variant of two-key triple encryption with a new method of generating three keys from two. Our scheme is not vulnerable to the meet-in-the-middle attack and, under an appropriate assumption, we can show that our scheme is at least about as hard to break as the underlying block cipher. Received 22 June 1995 and revised 11 October 1996     

A Single-Key Attack on the Full GOST Block Cipher

The GOST block cipher is the Russian encryption standard published in 1989. In spite of considerable cryptanalytic efforts over the past 20 years, a key recovery attack on the full GOST block cipher without any key conditions (e.g., weak keys and related keys) has not been published yet. In this paper, we show the first single-key attack, which works for all key classes, on the full GOST block cipher. To begin, we develop a new attack framework called Reflection-Meet-in-the-Middle Attack. This approach combines techniques of the reflection attack and the meet-in-the-middle (MITM) attack. Then we apply it to the GOST block cipher employing bijective S-boxes. In order to construct the full-round attack, we use additional novel techniques which are the effective MITM techniques using equivalent keys on a small number of rounds. As a result, a key can be recovered with a time complexity of 2²²⁵ encryptions and 2³² known plaintexts. Moreover, we show that our attack is applicable to the full GOST block cipher using any S-boxes, including non-bijective S-boxes.     

KeeLoq密码Courtois攻击方法的分析和修正

KeeLoq密码是由Willem Smit设计的分组密码算法,广泛应用于汽车的无线门锁装置。Courtois等人在2007年提出了破译KeeLoq的4种滑动-代数攻击方法,其中第4种滑动-代数攻击方法的计算复杂性最小。本文证明了Courtois的第4种滑动-代数攻击方法的攻击原理是错误的,因而无法实现对KeeLoq的破译。此外,本文还对该方法进行了修正,提出了改进的攻击方法,利用232个已知明文能够以O(248) 次加密的计算复杂性求出KeeLoq密码的密钥,成功率为1。对于KeeLoq密码26％的密钥,其连续64圈圈函数形成的复合函数至少具有两个不动点,此时改进的攻击方法的计算复杂性还可降至O(248) 次加密。     

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.     

Differential Fault Attack on GIFT

GIFT,a lightweight block cipher proposed at CHES2017,has been widely cryptanalyzed this years.This paper studies the differential diffusion characteristics of round function of GIFT at first,and proposes a random nibble-based differential fault attack.The key recovery scheme is developed on the statistical properties we found for the differential distribution table of the S-box.A lot of experiments had been done and experimental results show that one round key can be retrieved with an average of 20.24 and 44.96 fault injections for GIFT-64 and GIFT-128 respectively.Further analysis shows that a certain number of fault injections recover most key bits.So we demonstrate an improved fault attack combined with the method of exhaustive search,which shows that the master key can be recovered by performing 216 and 217 computations and injecting 31 and 32 faults on an average for GIFT-64 and GIFT-128 respectively.     

Differential fault attack on FeW

In order to evaluate the security of the lightweight block cipher FeW,a differential fault attack method was proposed and discussed using a single byte random fault model.In this method,a single byte random fault was introduced on the right side of the last round of FeW to recover the key based on the statistical characteristics of S-box difference distribution,and the difference information was obtained using the characteristics of the linear diffusion function.The experiment results show that the complete key recovery can be achieved with an average of 47.73 and 79.55 fault injections for FeW-64-80 and FeW-64-128 respectively.If 2¹⁰exhaustive calculations are added to the key recovery process,the number of average fault injections required can be reduced to 24.90 and 41.50.This attack is effective on FeW.