At Crypto 2019, Gohr first adopted the neural distinguisher for differential cryptanalysis, and since then, this work received increasing attention. However, most of the existing work focuses on improving and applying the neural distinguisher, the studies delving into the intrinsic principles of neural distinguishers are finite. At Eurocrypt 2021, Benamira et al. conducted a study on Gohr’s neural distinguisher. But for the neural distinguishers proposed later, such as the r-round neural distinguishers trained with k ciphertext pairs or ciphertext differences, denoted as NDcpk_r (Gohr’s neural distinguisher is the special NDcpk_r with K = 1) and NDcdk_r , such research is lacking. In this work, we devote ourselves to study the intrinsic principles and relationship between NDcdk_r and NDcpk_r. Firstly, we explore the working principle of NDcd1_r through a series of experiments and find that it strongly relies on the probability distribution of ciphertext differences. Its operational mechanism bears a strong resemblance to that of NDcp1_r given by Benamira et al.. Therefore, we further compare them from the perspective of differential cryptanalysis and sample features, demonstrating the superior performance of NDcp1_r can be attributed to the relationships between certain ciphertext bits, especially the significant bits. We then extend our investigation to NDcpk_r, and show that its ability to recognize samples heavily relies on the average differential probability of k ciphertext pairs and some relationships in the ciphertext itself, but the reliance between k ciphertext pairs is very weak. Finally, in light of the findings of our research, we introduce a strategy to enhance the accuracy of the neural distinguisher by using a fixed difference to generate the negative samples instead of the random one. Through the implementation of this approach, we manage to improve the accuracy of the neural distinguishers by approximately 2% to 8% for 7-round Speck32/64 and 9-round Simon32/64.

This paper introduces significant improvements over the existing cryptanalysis approaches on Salsa20 and ChaCha stream ciphers. For the first time, we reduced the attack complexity on Salsa20/8 to the lowest possible margin. We introduced an attack on ChaCha7.25. It is the first attack of its type on ChaCha7.25/20. In our approach, we studied differential cryptanalysis of the Salsa20 and ChaCha stream ciphers based on a comprehensive analysis of probabilistic neutral bits (PNBs). The existing differential cryptanalysis approaches on Salsa20 and ChaCha stream ciphers first study the differential bias at specific input and output differential positions and then search for probabilistic neutral bits. However, the differential bias and the set of PNBs obtained in this method are not always the ideal combination to conduct the attack against the ciphers. The researchers have not focused on the comprehensive analysis of the probabilistic neutrality measure of all key bits concerning all possible output difference positions at all possible internal rounds of Salsa20 and ChaCha stream ciphers. Moreover, the relationship between the neutrality measure and the number of inverse quarter rounds has not been scrutinized yet. To address these study gaps, we study the differential cryptanalysis based on the comprehensive analysis of probabilistic neutral bits on the reduced-round Salsa20 and ChaCha. At first, we comprehensively analyze the neutrality measure of 256 key bits positions. Afterward, we select the output difference bit position with the best average neutrality measure and look for the corresponding input differential with the best differential bias. Considering all aspects, we present an attack on Salsa20/8 with a time complexity of 2241.62 and data complexity of 231.5, which is the best-known single bit differential attack on Salsa20/8 and then, we introduced an attack on ChaCha7.25 rounds with a time complexity of 2254.011 and data complexity of 251.81.

In CRYPTO 2019, Gohr first introduced the deep learning method to cryptanalysis for SPECK32/64. A differential-neural distinguisher was obtained using ResNet neural network. Zhang et al. used multiple parallel convolutional layers with different kernel sizes to capture information from multiple dimensions, thus improving the accuracy or obtaining a more round of distinguisher for SPECK32/64 and SIMON32/64. Inspired by Zhang's work, we apply the network structure to other ciphers. We not only improve the accuracy of the distinguisher, but also increase the number of rounds of the distinguisher, that is, distinguish more rounds of ciphertext and random number for DES, Chaskey and PRESENT.

Integral cryptanalysis is one of the most powerful attacks on symmetric key block ciphers. Attackers preliminarily search integral characteristics of a target cipher and use them to perform the key recovery attack. Todo proposed a novel technique named the bit-based division property to find integral characteristics. Xiang et al. extended the Mixed Integer Linear Programming (MILP) method to search integral characteristics of lightweight block ciphers based on the bit-based division property. In this paper, we apply these techniques to the symmetric key block cipher KASUMI which was developed by modifying MISTY1. As a result, we found new 4.5-round characteristics of KASUMI for the first time. We show that 7-round KASUMI is attackable with 263 data and 2120 encryptions.

Physical attacks against cryptographic devices and their countermeasures have been studied for over a decade. Physical attacks on block-cipher algorithms usually target a few rounds near the input or the output of cryptographic algorithms. Therefore, in order to reduce the implementation cost or increase the performance, countermeasures tend to be applied to the rounds that can be targeted by physical attacks. For example, for AES, the conventional physical attacks have practical complexity when the target leakage is as deep as 4 rounds. In general, the deeper rounds are targeted, the greater the cost required for attackers. In this paper, we focus on the physical attack that uses the leakage as deep as 5 rounds. Specifically, we consider the recently proposed 5-round mixture differential cryptanalysis, which is not physical attack, into the physical attack scenarios, and propose the corresponding physical attack. The proposed attack can break AES-128 with data complexity and time complexity of 225.31. As a result, it is clear that the rounds as deep as 5 must be protected for AES. Furthermore, we evaluated the proposed attack when the information extracted from side-channel leakage contains noise. In the means of theoretical analysis and simulated attacks, the relationship between the accuracy of information leakage and the complexity of the attack is evaluated.

We revisit the design of Lesamnta-LW, which is one of the three lightweight hash functions specified in ISO/IEC 29192-5:2016. Firstly, we present some updates on the bounds of the number of active S-boxes for the underlying 64-round block cipher. While the designers showed that the Viterbi algorithm ensured 24 active S-boxes after 24 rounds, our tool based on Mixed Integer Linear Programming (MILP) in the framework of Mouha et al. ensures the same number of active S-boxes only after 18 rounds. The tool completely evaluates the tight bound of the number of active S-boxes, and it shows that the bound is 103 for full (64) rounds. We also analyze security of the Shuffle operation in the round function and resistance against linear cryptanalysis. Secondly, we present a new mode for a pseudorandom function (PRF) based on Lesamnta-LW. It is twice as efficient as the previous PRF modes based on Lesamnta-LW. We prove its security both in the standard model and the ideal cipher model.

Sieve algorithms are regarded as the best algorithms to solve the shortest vector problem (SVP) on account of its good asymptotical quality, which could make it outperform enumeration algorithms in solving SVP of high dimension. However, due to its large memory requirement, sieve algorithms are not practical as expected, especially on high dimension lattice. To overcome this bottleneck, TupleSieve algorithm was proposed to reduce memory consumption by a trade-off between time and memory. In this work, aiming to make TupleSieve algorithm more practical, we combine TupleSieve algorithm with SubSieve technique and obtain a sub-exponential gain in running time. For 2-tuple sieve, 3-tuple sieve and arbitrary k-tuple sieve, when selecting projection index d appropriately, the time complexity of our algorithm is O(20.415(n-d)), O(20.566(n-d)) and $O(2^{rac{kmathrm{log}_2p}{1-k}(n-d)})$ respectively. In practice, we propose a practical variant of our algorithm based on GaussSieve algorithm. Experimental results show that our algorithm implementation is about two order of magnitude faster than FPLLL's GuassSieve algorithm. Moreover, techniques such as XOR-POPCNT trick, progressive sieving and appropriate projection index selection can be exploited to obtain a further acceleration.

We address the security issue of RSA with implicitly related keys in this paper. Informally, we investigate under what condition is it possible to efficiently factorize RSA moduli in polynomial time given implicit relation of the related private keys that certain portions of bit pattern are the same. We formulate concrete attack scenarios and propose lattice-based cryptanalysis by using lattice reduction algorithms. A subtle lattice technique is adapted to represent an unknown private key with the help of known implicit relation. We analyze a simple case when given two RSA instances with the known amount of shared most significant bits (MSBs) and least significant bits (LSBs) of the private keys. We further extend to a generic lattice-based attack for given more RSA instances with implicitly related keys. Our theoretical results indicate that RSA with implicitly related keys is more insecure and better asymptotic results can be achieved as the number of RSA instances increases. Furthermore, we conduct numerical experiments to verify the validity of the proposed attacks.

The boomerang connectivity table (BCT) was introduced by C. Cid et al. Using the BCT, for SPN block cipher, the dependency between sub-ciphers in boomerang structure can be computed more precisely. However, the existing method to generate BCT is difficult to be applied to the ARX-based cipher, because of the huge domain size. In this paper, we show a method to compute the dependency between sub-ciphers in boomerang structure for modular addition. Using bit relation in modular addition, we compute the dependency sequentially in bitwise. And using this method, we find boomerang characteristics and amplified boomerang characteristics for the ARX-based ciphers LEA and SPECK. For LEA-128, we find a reduced 15-round boomerang characteristic and reduced 16-round amplified boomerang characteristic which is two rounds longer than previous boomerang characteristic. Also for SPECK64/128, we find a reduced 13-round amplified boomerang characteristic which is one round longer than previous rectangle characteristic.

Kreyvium is a NLFSR-based stream cipher which is oriented to homomorphic-ciphertext compression. This is a variant of Trivium with 128-bit security. Designers have evaluated the security of Kreyvium and concluded that the resistance of Kreyvium to the conditional differential cryptanalysis is at least the resistance of Trivium, and even better. However, we consider that this attack is effective for reduced Kreyvium due to the structure of it. This paper shows the conditional differential cryptanalysis for Kreyvium, and we propose distinguishing and key recovery attacks. We show how to arrange differences and conditions to obtain good higher-order conditional differential characteristics. We use two types of higher-order conditional differential characteristics to find a distinguisher, e.g. the bias of higher-order conditional differential characteristics of a keystream and the probabilistic bias of them. In the first one, we obtain the distinguisher on Kreyvium with 730 rounds from 20-th order characteristics. In the second one, we obtain the distinguisher on Kreyvium with 899 rounds from 25-th order conditional differential characteristics. Moreover, we show the key recovery attack on Kreyvium with 736 rounds from 20-th order characteristics. We experimentally confirm all our attacks. The second distinguisher shows that we can obtain the distinguisher on Kreyvium with more rounds than the distinguisher on Trivium. Therefore, Kreyvium has a smaller security margin than Trivium for the conditional differential cryptanalysis.

Bel-T is the national block cipher encryption standard of the Republic of Belarus. It operates on 128-bit blocks and uses either 128, 192 or 256-bit keys. Bel-T combines a Feistel network with a Lai-Massey scheme and it has a complex round function with 7 S-box layers. In this work, we use a Mixed Integer Linear Programming (MILP) approach to find a a related-key differential characteristic that extends for 4 rounds and 5 S-box layers ($4 rac{5}{7}$ rounds) with probability higher than 2-128. To build an MILP model of Bel-T that a solver can practically handle, we use a partial Difference Distribution Table (DDT) based on the Hamming weight of the input and output differences. The identified differential characteristic is used to mount a key recovery attack on 5 rounds and 6 S-box layers ($5 rac{6}{7}$ out of 8 rounds) of Bel-T-256 with 2123.28 chosen plaintexts and 2228.4 encryptions. According to the best of our knowledge, this is the first public cryptanalysis of Bel-T in the black-box attack model.

At FSE 2014, Grosso et al. proposed LS-designs which are a family of bitslice ciphers aiming at efficient masked implementations against side-channel analysis. They also presented two specific LS-designs, namely the non-involutive cipher Fantomas and the involutive cipher Robin. The designers claimed that the longest impossible differentials of these two ciphers only span 3 rounds. In this paper, for the two ciphers, we construct 4-round impossible differentials which are one round more than the longest impossible differentials found by the designers. Furthermore, with the 4-round impossible differentials, we propose impossible differential attacks on Fantomas and Robin reduced to 6 rounds (out of the full 12/16 rounds). Both of the attacks need 2119 chosen plaintexts and 2101.81 6-round encryptions.

SPARX-128/256 is one of the two versions of the SPARX-128 block cipher family. It has 128-bit block size and 256-bit key size. SPARX has been developed using ARX-based S-boxes with the aim of achieving provable security against single-trail differential and linear cryptanalysis. In this letter, we propose 20-round impossible differential distinguishers for SPARX-128. Then, we utilize these distinguishers to attack 24 rounds (out of 40 rounds) of SPARX-128/256. Our attack has time complexity of 2232 memory accesses, memory complexity of 2160.81 128-bit blocks, and data complexity of 2104 chosen plaintexts.

Midori128 is a lightweight block cipher proposed at ASIACRYPT 2015 to achieve low energy consumption per bit. Currently, the best published impossible differential attack on Midori128 covers 10 rounds without the pre-whitening key. By exploiting the special structure of the S-boxes and the binary linear transformation layer in Midori128, we present impossible differential distinguishers that cover 7 full rounds including the mix column operations. Then, we exploit four of these distinguishers to launch multiple impossible differential attack against 11 rounds of the cipher with the pre-whitening and post-whitening keys.

In 1999, Boneh and Durfee introduced the small inverse problem, which solves the bivariate modular equation x(N+y)≡1(mod e. Absolute values of solutions for x and y are bounded above by X=Nδ and Y=Nβ, respectively. They solved the problem for β=1/2 in the context of small secret exponent attacks on RSA and proposed a polynomial time algorithm that works when δ<(7-2√7)/6≈0.284. In the same work, the bound was further improved to δ<1-1/≈2≈0.292. Thus far, the small inverse problem has also been analyzed for an arbitrary β. Generalizations of Boneh and Durfee's lattices to obtain the stronger bound yielded the bound δ<1-≈β. However, the algorithm works only when β≥1/4. When 0<β<1/4, there have been several works where the authors claimed their results are the best. In this paper, we revisit the problem for an arbitrary β. At first, we summarize the previous results for 0<β<1/4. We reveal that there are some results that are not valid and show that Weger's algorithms provide the best bounds. Next, we propose an improved algorithm to solve the problem for 0<β<1/4. Our algorithm works when δ<1-2(≈β(3+4β)-β)/3. Our algorithm construction is based on the combinations of Boneh and Durfee's two forms of lattices and it is more natural compared with previous works. For the cryptographic application, we introduce small secret exponent attacks on Multi-Prime RSA with small prime differences.

In this paper, we present several cryptanalyses of Hierocrypt-L1 block cipher, which was selected as one of the CRYPTREC recommended ciphers in Japan in 2003. We present a differential attack and an impossible differential attack on 8 S-function layers in a related-key setting. We first show that there exist the key scheduling differential characteristics which always hold, then we search for differential paths for the data randomizing part with the minimum active S-boxes using the above key differentials. We also show that our impossible differential attack is a new type.

Kiasu-BC is a recently proposed tweakable variant of the AES-128 block cipher. The designers of Kiasu-BC claim that no more than 7-round Meet-in-the-Middle (MitM) attack can be launched against it. In this letter, we present a MitM attack, utilizing the differential enumeration technique, on the 8-round reduced cipher. The attack has time complexity of 2116 encryptions, memory complexity of 286 128-bit blocks, and data complexity of 2116 plaintext-tweak combinations.

In this letter, we present a meet-in-the-middle attack on the 7-round reduced block cipher Kalyna-b/2b, which has been approved as the new encryption standard of Ukraine (DSTU 7624:2014) in 2015. According to its designers, the cipher provides strength to several cryptanalytic methods after the fifth and sixth rounds of the versions with block length of 128 and 256 bits, respectively. Our attack is based on the differential enumeration approach, where we carefully deploy a four-round distinguisher in the first four rounds to bypass the effect of the carry bits resulting from the prewhitening modular key addition. We also exploit the linear relation between consecutive odd and even indexed round keys, which enables us to attack seven rounds and recover all the round keys incrementally. The attack on Kalyna with 128-bit block has a data complexity of 289 chosen plaintexts, time complexity of 2230.2 and a memory complexity of 2202.64. The data, time and memory complexities of our attack on Kalyna with 256-bit block are 2233, 2502.2 and 2170, respectively.

This paper deals with the security of chaos-based “true” random number generators (RNG)s. An attack method is proposed to analyze the security weaknesses of chaos-based RNGs and its convergence is proved using a master slave synchronization scheme. Attack on a RNG based on a double-scroll attractor is also presented as an example. All secret parameters of the RNG are revealed where the only information available is the structure of the RNG and a scalar time series observed from the double-scroll attractor. Simulation and numerical results of the proposed attack method are given such that the RNG doesn't fulfill NIST-800-22 statistical test suite, not only the next bit but also the same output bit stream of the RNG can be reproduced.

Linear cryptanalysis proposed by Matsui is one of the most effective attacks on block ciphers. Some attempts to improve linear cryptanalysis have been made since Matsui introduced. We focus on how to optimize linear cryptanalysis with such techniques, and we apply the optimized linear cryptanalysis on FEAL-8X. First, we evaluate two existing implementation methods so as to optimize the computation time of linear cryptanalysis. Method 1 removes redundant round function computations and optimizes the other computation of linear cryptanalysis by transforming it into bitwise operations. Method 2 transforms the computation of linear cryptanalysis into a matrix multiplication and reduces the time complexity of the multiplication using the fast Fourier transform (FFT). We implement both methods optimized for modern microprocessors and compare their computation time to clarify the appropriate method for practical cryptanalysis. From the result, we show that the superior implementation depends on the number of given known plaintexts (KPs) and that of guessed key bits. Furthermore, we show that these results enable us to select the superior method to implement linear cryptanalysis without another comparative experiment. By using the superior method, we implement the multiple linear cryptanalysis (MLC) on FEAL-8X. Our implementation can recover the secret key of FEAL-8X with 210KPs in practical computation time with non-negligible probability, and it is the best attack on FEAL-8X in data complexity.