Cryptanalysls Of Twine And NTRU

As the foundation stone of information security, Cryptology plays a very impor-tant role in modern world. The encryption algorithms in cryptology includes symmetric encryption algorithms and asymmetric encryption algorithms. As the study subjects of this dissertation, TWINE is a symmetric encryption algorithm and NTRU is an asym-metric encryption algorithm.Symmetric cryptosystem includes block cipher, stream cipher and hash func-tion. With the development of RFID and handheld devices etc, block cipher used in low resource devices attracts widely attention and is developing very fast. And the lightweight block cipher TWINE is proposed in this background. TWINE was proposed by Suzaki et. al. at the ECRYPT (European Network of Excellence in Cryp-tology) Workshop on Lightweight Cryptography in2011, and then published at the SAC conference in2012. It is a64-bit lightweight block cipher consisting of36round-s with80-bit or128-bit keys. The global structure of TWINE is a variant of Type-2generalized Feistel structure with16nibbles.NTRU cryptosystem, proposed at CRYPTO in1996by Hoffstein et. al., is based on the algebraic structures of polynomial ring R=Z[x]/(xN-1). Although there is no rigorous reduction from NTRU to some hard problem, breaking NTRU could be expressed as a hard problem over Euclidean lattice. Therefore, it is believed that NTRU can resist quantum computers. Besides, its encryption and decryption operations are much faster than those of RSA and elliptic curve cryptosystems with the same level of security. Due to its high security and efficient operations, many security assessment arose in the last few years.In the development of cryptography, cryptographic design and cryptanalysis are on the opposite sides while they improve each other at the same time. After Cryp-tographers designing some cryptographic algorithms using all kinds of mathematical methods, many researchers try to find the weakness of these algorithms and then fix the problem to obtain better cryptographic algorithms. For example, a competition to develop the Advanced Encryption Standard (AES) as a replacement of DES which was hold by the National Institute of Standards and Technology (NIST), the European NESSIE project, Japanese CRYPTREC project etc have been promoting the fast devel-opment of the design and cryptanalysis of block cipher. This dissertation shows some attacks against two important cryptographic algorithms to help the understanding of their security level.The security analysis of cryptographic algorithms includes theoretical analysis and practical implementation analysis. This dissertation gives theoretical analysis of TWINE and practical implementation analysis of NTRU. For the theoretical analysis of block cipher, many techniques such as differential cryptanalysis, linear cryptanalysis, impossible differential cryptanalysis, algebraic cryptanalysis etc. are used. The technique of analyzing TWINE in this dissertation is impossible differential cryptanalysis. From the aspect of security assessment of cryptographic chips, side channel attack is the most powerful tool which chips are threatened by. Since the appearance of timing attack given by Kocher on CRYPTO in1996, side channel attack has been developing very fast. Power analysis which is the most common method and easiest to amount among all kinds of side channel attacks, contains Simple Power Analysis, Differential Power Analysis, High Order Differential Power Analysis, Collision Attack etc. Meanwhile, countermeasures which are designed to resist these attacks are developed due to the practical threaten to the cryptographic chip systems. The technique used in our security assessment of NTRU is collision attack.·Impossible Differential Attack on Reduced-Round TWINE We obtain some important properties about the round subkeys of TWINE accord-ing to the Key Schedule. Those subkey relations affect attackers’choice of impossible differential and the key recovery algorithm. During the selection of best impossible d-ifferential among the longest ones, an attacker pick the longest impossible differentials, and then the best one is chosen according to these subkeys relations for the sake of less time complexity in the key recovery step.In former works of impossible differential attacks, an attacker selects all the sub-keys that satisfy the head truncated differential and the tail truncated differential sepa-rately, and then the two parts of subkeys are combined directly to be filtered as wrong keys. Since the subkeys considered in their attacks has no more bits than the master key, it is feasible to directly discard these subkeys. However, the subkeys involved in the truncated differentials have more bits than the master key in our attack, which means there are some information redundance among the subkeys. Therefore, we give a new algorithm that can deal with the redundance at the same time when selecting subkeys satisfying the truncated differentials.Besides some precomputation to obtain the time-memory balance, the order of using subkey relations are optimized. What’s more, a more precise description of the plaintext/ciphertext difference is obtained by using the differential characteristic of TWINE s box. Therefore, a right plaintext/ciphertext pair can be picked more quickly. The time, data and memory complexity of attacking23-round TWINE-80are279.0923-round encryptions,257.85chosen plaintexts and278.04blocks respectively. Besides, the impossible differential attack on24-round TWINE-128needs258.1chosen plaintexts,2126.7824-round encryptions and2125.61blocks of memory.·First-order collision attack on protected NTRU cryptosystemLee et al. gave several power analysis attacks on the most common used soft-ware implementation of NTRU and three countermeasures in2010, where they argued that only second-order power analysis can break their first countermeasure, and the combination of the first and third countermeasure is secure. The first countermeasure is random initialization of registers t, which is aim to prevent their Simple Power Analysis (SPA) attack. To be more specific, every register ti(i=0,...,2N-2) is added by some random number r, at the beginning of decryption algorithm. After the decryption algorithm is done, these ri are subtracted from the cor-responding register ti. Hence there is no operation like x+0in the modified algorithm, and their SPA attack does not work.The second countermeasure is blinding ciphertext c using random values, which is designed to resist their Correlation Power Analysis (CPA) attack. For the original input values Ci(i=0,...,N-1), the countermeasure is to replace them by ci+r, where r is a random integer. And then every value in the register ti is subtracted by dr mod q at the end of the algorithm.The third countermeasure is randomization of b. The randomized order of b[i] disables the statistical analysis of b[i]-b[i-1] in their attack.For these countermeasures, we give efficient first-order collision attacks in HW model and HD model respectively. Although the first countermeasure eliminates the adding operation of zero and non-zero and avoids the SPA attack, the initialization of the register t may make t the attack target. The second countermeasure masks the value of ci which can help resist CPA attack. However, SPA can easily break the algorithm if it is protected only by the second countermeasure. As for the third countermeasure, we admit that the order of b[i](i=0,..., d-1) is disturbed. Denote the new ordered secret key as b’[i](i=0,..., d-1). One important observation on the third countermeasure is that the equality b[0]=b [0] holds with probability1/d. Using these observations, we propose the first-order collision attack on NTRU protected by Lee’s countermeasures.For the first countermeasure, our experimental data shows that our attack has a gain of108.4%and78%in efficiency compared to Lee’s second-order power analysis in HW model and HD model respectively. Besides, the designers of these counter-measures argued that their combined countermeasure is secure, while our attack is successful given enough power traces.