Cryptanalysis Of Light-Weight And Large Non-surjective S-box Block Ciphers

Over the past few decades, following the tremendous challenges and opportunities in communication security brought about by computer technology, cryptography has been taking greater role in information security. In cryptography, a block cipher, as one type of the symmetric ciphers, is a very basic cryptographic primitive, which can be used to devise stream ciphers, hash functions and message authentication codes. It is such an one-key-dependent permutation that firstly breaking up the message into small plaintext blocks, then transforming them into ciphertext blocks of the same size respec-tively. It is widely applied in security protocols such as SSL, IPSec etc. and security applications. Until now, both the design and security evaluation of block ciphers have been research hot topic.DES designed by IBM, is proposed as the first encryption standard for block ci-pher in1977. Its key size is56bits, block size is64bits. The encryption is composed of an initial permutation,16iterative round functions in Feistel network, and an invert-ible permutation at the end. From then on, lots of block ciphers have been designed in Feistel networks, such as the well-known block ciphers CAMELLIA, CAST-128, ICE, LOKI97, LUCIFER. At the same time, a series of cryptanalytic methods have been put forward, such as differential cryptanalysis, linear cryptanalysis and alge-braic cryptanalysis, etc. Due to the development of computer technology, key size of56bits is not sufficient for the security requirements. In order to find a replacement of DES, in1997, National Institute of Standards and Technology (NIST) collected block ciphers for the Advanced Encryption Standard (AES). In2000, Rijndael, which is de- signed by Joan Daemen and Vincent Rijmen, was finally proposed as AES and U.S. FIPS PUB197(FIPS197) one year later. AES is based on substitution-permutation network, termed SPN, which is more efficient than Feistel Structure. In order to achieve strong confusion and diffusion property, SPN is much easier to apply in the paralleliza-tion architecture compared to Feistel network.Substitution box, termed S-box, is an important component in block cipher and it is a boolean mapping{0,1}m→{0,1}n. Its non-linear property provides the confusion property for block cipher. In order to resist the differential cryptanalysis, S-box with large number of output bits is often used in block ciphers such as CAST-128, CAST-256, Blowfish etc. If the number of input bits and output bits are m and n respec-tively, the S-box can be implemented as an2m size of table. For large S-box, n will be larger than m, so the S-box must be non-surjective mapping. Linear cryptanalysis is a known-plaintext or a ciphertext-only attack, introduced by Matsui in1993. In order to resist linear cryptanalysis, the large S-box will be designed with the bent function with the upper bound degree2m-1-22/m-1. Identifying the best linear approximation with zero input mask and nonzero output mask for the round function for such large S-boxes is valuable for the linear cryptanalysis. However, it is quite difficult because searching both S-box table and all the output mask values are very time-consuming. Therefore, the previous works only searched limited linear approximation for the round function with the large non-surjective S-boxes.For example, in block cipher CAST-128and CAST-256there are three kinds of round function named F1, F2and F3. Each of them consists of four8x32non-surjective S-boxes and mixed operations with module addition, module subtraction and XOR, which results in the linear approximation table being difficult to be con-structed. Because of its Feistel structure, we need search the linear approximation pattern0→Γ. In [63], Nakahara et al. think the best linear approximation should be00000000x->00000001x and the corresponding bias is2-17because they believe the carry bits or borrow bits will reduce the bias. Based on it, they constructed two rounds of iterative linear approximation, finally they presented a cryptanalytic result of12-round CAST-256, which requires2101known plaintexts and210112-round CAST-256 encryptions. Soon afterwards, Meiqin Wang et al. presented the linear cryptanalysis for CAST-128and CAST-256, they pointed that carry bits and borrow bits do not always reduce the bias, so due to the high time complexity, they searched no more than three nonzero bits for output mask values for round function F1and F3, and they ac-counted the special property for the round function F2, as a result they can search no more than six nonzero bits for output mask values. Finally, they found the best linear approximation is00000000x→03400000x for F2, the corresponding bias is2-12.91, they can attack24-round CAST-256, which needs2124.1plaintexts and2156.224-round CAST-256encryptions. However, the number of output bits for round function F1, F2and F3is32. So there are a large number of linear approximations which have not been computed. Whether there are still some linear approximations with larger bias than the one identified by Meiqin Wang et al. is unknown.In this paper, we will propose a practical method to search all the linear approx-imations0→Γ for large non-surjective S-boxes. Our algorithm makes full use of the hardware properties in the64-bit high-performance parallel computers and can be used to cryptanalyze all the block ciphers with large non-surjective S-boxes. In order to describe our method clearly, we will take CAST-256as an example. As a result, we identify the best linear approximation for CAST-256which is better than the previous linear approximation. We mainly describe our computing method to search over all232output mask values to find out the highest linear relation0→Γ for round function F2of CAST-256, which can be done in85.3hours in our parallel environment consisted of64CPU cores with clock speed2.4GHz and3MB L2caches (IBM X3950M2). It should be noted that our searching algorithm is not just to be implemented in parallel, it makes full use of some hardware properties to improve computational complexity ob-viously. Without our improvements, the task should be done in256days in our parallel environment. Using our computing method, we identify the best linear approximation for the round function F2of CAST-256is00000000x→8021c53ax, the correspond-ing bias is2-12.63which is larger than the previous results2-12.91. Moreover, we give a general computing method which can be used to search all the linear approximations for the round function F1, F2and F3only within47.72hours in our environment. In recent years, due to the development of Internat, more and more tiny terminal equipments have been pervasively adopted, which are in charge of handy computing or communication for individuals, such as RFID tags and sensor networks. However, the present popular cryptographic algorithm AES can not be directly used in such a low-cost environment with limited resources. So block ciphers suitable for such resource constrained environment have been designed, which are often called light-weight block ciphers, such as DESL, mCRYPTON, HEIGHT, ICEBERG, PRESENT, PUFFIN etc.PUFFIN is such a light-weight block cipher proposed by Cheng, Heys and Wang in DSD2008. It is a32-round SP-network block cipher with block size64bits and key size128bits. As the light-weight block cipher ICEBERG, the most significant characteristic for PUFFIN is that it is an involutional SPN structure, which requires the low hardware implementation requirements. At CCECE2009, Wang and Heys proposed the block cipher PUFFIN2which is similar to PUFFIN but includes34rounds and tiny different key schedule.The original PUFFIN proposal presented the probability of the differential char-acteristic for the31-round PUFFIN is less than2-62. The proposers claimed that262chosen plaintext pairs would be required to attack the cipher and the complexity for the attack approaches the dictionary attack. They claimed that the key size for the block cipher PUFFIN is128-bit and the block size is64-bit, with the whole dictionary for an ideal cipher, the key can not be recovered. So they claimed that32-round PUF-FIN is resistant to differential cryptanalysis. However, we think, if the key can be recovered with the whole dictionary and the time complexity is less than the time of exhaustive search, the attack is valuable. In this paper, we will recover the128-bit key for the32-round PUFFIN using the whole codebook with the differential cryptanalysis. Moreover, we can recover the128-bit key for the32-round PUFFIN with262known plaintexts and293.732-round encryptions. Furthermore, our cryptanalytic results can be used to32-round PUFFIN2.Differential cryptanalysis is one of the classic cryptanalytic methods for block ciphers. It is introduced by Biham and Shamir in, and it is a chosen-plaintext attack to identify the secret key of an iterated block cipher. It identifies the advanced probability of the given input difference and the special output difference in the iter-ated cipher, and uses the differential characteristic as a distinguisher from a random permutation. Resistance against differential cryptanalysis is a typical design criterion for new block ciphers. Algebraic cryptanalysis is a general method for ciphers. It has been widely used in many ciphers such as stream ciphers, multivariate cryp-tosystems and in particular block ciphers. The basic idea of the algebraic cryptanalysis is to express the block cipher as the large multivariate polynomial sys-tem of equations. The secret information of the cipher is the solution of this system of equations. Generally, the time complexity of solving multivariate polynomial system with more variables and more non-linear equations is higher, such as solving a system of4000multivariate quadratic equations given one known plaintext on AES. How-ever, still there are several multivariate polynomial systems arisen from ciphers are easily solvable since some reasons. Until now, researchers have been research-ing the properties of easily solvable multivariate polynomial system. In general, if the system is very sparse, overdefined or structured, it may be solved faster than a generic non-linear system of equations. There are several methods to solve these systems of equations such as computing a Grobner Basis or using a SAT Solver, such as Magma, Singular, PolyBori, MiniSat2etc. To compute a Grobner Basis, PolyBoRi can be used. MiniSat is a fast SAT Solver. If the system of equations for the block cipher can be solved, the key can be recovered with only a few plaintext-ciphertext pairs.In recent years, the attack combining algebraic and differential cryptanalysis is on focus. At FSE2009, Albrecht et al. proposed a new cryptanalytic method that com-bines algebraic and differential cryptanalysis[47]. They introduced three new attacks, namely Attack A, Attack B and Attack C. For Attack A, they explain that the time com-plexity is difficult to determine. The goal of Attacks B and C is to filter out the wrong pairs that do not follow the differential characteristic or differential, and then to use the remained pairs to recover the key. Based on them, they finally give the cryptanalytic results on16-round PRESENT-80and17,18,19-round PRESENT-128. In this paper, we show that Attacks B and C do not work for PRESENT, because they cannot be used to filter out most of the wrong pairs that satisfy the ciphertext differences. Furthermore, we explain why Attack C cannot work for commonly used block ciphers. We verify our results for PRESENT experimentally, using both PolyBori and MiniSat2. Based on our findings, we present two new differential-algebraic attacks. Using the first method, our attack on16-round PRESENT-80requires263chosen plaintexts and has a worst-case time complexity of279.4equivalent encryptions. Although this attack has a higher time complexity than the differential attack, its data complexity is lower.In this paper, at first we present the method of searching linear approximation for large non-surjective S-box, then we give the differential cryptanalysis and linear crypt-analysis of full round PUFFIN, and we revisit the attack that combines algebraic and differential cryptanalysis proposed by Albrecht et al. The section about the attack com-bining algebraic and differential cryptanalysis is worked together with Meiqin Wang, she proposed the idea and proof and I did the massive data tests.(1) Algorithm of searching linear approxmation for large non-surjective S-box●Improvement with hardware propertiesWe dispatch the counter addition module to64child processes and the compu-tation module in charge of computing the biases to parent process. In order to reduce the massive memory requirement for counters, we adopt a time-memory trade off method to store counter values. Finally, We make use of the property of64-bit CPU and operating system to obtain two S-box elements once memory read.●Optimize Dot-Multiply operation Enlightened by the idea of "Binary Search", we decrease Dot-Multiply oper-ation from32times of XOR operation,33times of AND operation and31times of Right Shift to6times of XOR operation,8times of AND operation and6times of Right Shift.●S-box reordering and counter addition optimization Here we take the round function F2of CAST-256as an example. Because the input mask is always zero, the order of the elements in S-box does not affect the bias computation. We reorder the elements in the large non-surjective S-box by the rule. After this step, we can see the regrouped S-box consists of new64groups, each of whom includes40000x elements. Now the new S-box can be evenly split up to64pieces and distributed to64child processes. Each group consists of at most three kinds of block:B1, B2and B3. The ele-ments in B1or B2have the same six least significant bits.The child process will proceed at most three kinds of block in different ways. In this way, for the64successive output mask values, Dot Multiply will execute at most two times and the counter-adding operation only manipulates two counters.●Finally, we put forward a more efficient general algorithm to search large non-surjective S-box such as the round function F1and F3of CAST-256based on the one for round function F2。The computing time is only242.81times of memory write and the memory requirement is228bytes. In practice, this algorithm can be done in47.72hours in our environment. However, if we directly use the algorithm for round function F1of CAST-256, the time will be251.58times of memory write and the memory requirement is228bytes.(2) Differential cryptanalysis and Linear cryptanalysis of32-round PUFFINWe searched for the iterative differential characteristics of2-round PUFFIN, and the corresponding highest probability is2-4. There are totally four such iterative dif-ferential characteristics. The best differential characteristic has only one active S-box in each round of PUFFIN. With any of the four2-round iterative differential character-istics, we can construct the differential characteristic for more rounds. One of the four differential characteristics with the probability2-60for30-round of PUFFIN is listed as follows, where the notation (?) means an30rounds transformation,(00000000x,00004000x)(?)(00000000x,00004000x). We use the first differential characteristic from round2to round31. We deduce that the difference of four bits in pairs of plaintexts and the difference of four bits in pairs of ciphertexts should be in the set described below. So we choose264plaintexts to produce260structures. In each structure there are56plaintext pairs whose difference may be1only in bit14,22,38and55.(ΔP55,ΔP38, ΔP22,ΔP14)⊿{(1,1,0,0),(0,0,0,1),(0,1,0,1),(1,0,1,0),(1,0,1,1),(0,1,1,1),(1,1,1,1)},(ΔC48,ΔC46,ΔC,8,ΔC0)∈{(1,0,0,1),(0,1,0,0),(1,1,0,0),(0,0,1,1),(0,1,1,1),(1,1,1,0),(1,1,1,1)}.Then we recover the subkey bits for round0and round32. We use the other3differential characteristics to recover other subkey bits in round0and round32in the same way. In all, we can recover the128-bit master key with264plaintexts and the corresponding ciphertexts,211232-round PUFFIN encryptions and286-bit counters. The success rate is99.99999999996%.We identified142-round iterative linear relations with the bias2-3, and we list one of them as follows,(0000000000000010)(?)(0004000000000000)(?)(0000000000000010)x. We iterate the linear approximation to28rounds, the overall bias is2-29. With the28-round linear approximation, we recover the full32-round key for PUFFIN. We use the linear approximation for round3to round30. During the key-recovery process, the number of guessed subkey bits is41bits. According to the key schedule, we can easily deduce that the41bits are derived from35bits of the master key. The remained93-bit master key is recovered by exhaustive search. Therefore, we can recover all128-bit key for the full32-round PUFFIN encryptions under the linear attack with262known plaintexts, about293.732-round encryptions and23564-bit counters, and the success rate is about91%.(3)Algebraic techniques in differential cryptanalysis revisitedFirstly, we show Attack C typically cannot be used to filter out the wrong pairs not satisfying the difference values of the ciphertexts. Secondly, we verify using PolyBori and MiniSat2that Attack B does not result in an attack for the PRESENT block cipher. The reason is that there are too few usable equations in the system of equations to derive an inconsistency for wrong pairs or to find a solution for the right pairs. Based on our findings, we present two methods that can more reliably use the right pairs to solve the right key within an acceptable time, but no solutions will be produced for wrong pairs. One is to fix certain key bits in the system of equations. This will allow an inconsistency in the system of equations to be derived faster. Another method is to use more than one plaintext-ciphertext pair to construct the system of equations.We apply our attack methods to a reduced-round PRESENT-80block cipher. With the first method, we attack16-round PRESENT-80with263chosen plaintexts and279.4equivalent encryptions in the worst case. The differential attack on16-round PRESENT-80has a data complexity of264and a time complexity of262mem-ory accesses. Therefore, the time complexity of the differential-algebraic attack for PRESENT-80is much larger than that of the differential attack, but the data complex-ity is lower.With the second method, the time complexity will be larger than the280required for an exhaustive key search on16-round PRESENT-80. It is an open question whether the second method can offer an improvement for other block ciphers.