International Association for Cryptologic Research

International Association
for Cryptologic Research


Wei Wang


Accelerating the Search of Differential and Linear Characteristics with the SAT Method
Ling Su Wei Wang Meiqin Wang
The introduction of the automatic search boosts the cryptanalysis of symmetric-key primitives to some degree. However, the performance of the automatic search is not always satisfactory for the search of long trails or ciphers with large state sizes. Compared with the extensive attention on the enhancement for the search with the mixed integer linear programming (MILP) method, few works care for the acceleration of the automatic search with the Boolean satisfiability problem (SAT) or satisfiability modulo theories (SMT) method. This paper intends to fill this vacancy. Firstly, with the additional encoding variables of the sequential counter circuit for the original objective function in the standard SAT method, we put forward a new encoding method to convert the Matsui’s bounding conditions into Boolean formulas. This approach does not rely on new auxiliary variables and significantly reduces the consumption of clauses for integrating multiple bounding conditions into one SAT problem. Then, we evaluate the accelerating effect of the novel encoding method under different sets of bounding conditions. With the observations and experience in the tests, a strategy on how to create the sets of bounding conditions that probably achieve extraordinary advances is proposed. The new idea is applied to search for optimal differential and linear characteristics for multiple ciphers. For PRESENT, GIFT-64, RECTANGLE, LBlock, TWINE, and some versions in SIMON and SPECK families of block ciphers, we obtain the complete bounds (full rounds) on the number of active S-boxes, the differential probability, as well as the linear bias. The acceleration method is also employed to speed up the search of related-key differential trails for GIFT-64. Based on the newly identified 18-round distinguisher with probability 2−58, we launch a 26-round key-recovery attack with 260.96 chosen plaintexts. To our knowledge, this is the longest attack on GIFT-64. Lastly, we note that the attack result is far from threatening the security of GIFT-64 since the designers recommended users to double the number of rounds under the related-key attack setting.
Linear Cryptanalyses of Three AEADs with GIFT-128 as Underlying Primitives
This paper considers the linear cryptanalyses of Authenticated Encryptions with Associated Data (AEADs) GIFT-COFB, SUNDAE-GIFT, and HyENA. All of these proposals take GIFT-128 as underlying primitives. The automatic search with the Boolean satisfiability problem (SAT) method is implemented to search for linear approximations that match the attack settings concerning these primitives. With the newly identified approximations, we launch key-recovery attacks on GIFT-COFB, SUNDAE-GIFT, and HyENA when the underlying primitives are replaced with 16-round, 17-round, and 16-round versions of GIFT-128. The resistance of GIFT-128 against linear cryptanalysis is also evaluated. We present a 24-round key-recovery attack on GIFT-128 with a newly obtained 19-round linear approximation. We note that the attack results in this paper are far from threatening the security of GIFT-COFB, SUNDAE-GIFT, HyENA, and GIFT-128.
On the Usage of Deterministic (Related-Key) Truncated Differentials and Multidimensional Linear Approximations for SPN Ciphers 📺
Among the few works realising the search of truncated differentials (TD) and multidimensional linear approximations (MDLA) holding for sure, the optimality of the distinguisher should be confirmed via an exhaustive search over all possible input differences/masks, which cannot be afforded when the internal state of the primitive has a considerable number of words. The incomplete search is also a long-term problem in the search of optimal impossible differential (ID) and zerocorrelation linear approximation (ZCLA) since all available automatic tools operate under fixed input and output differences/masks, and testing all possible combinations of differences/masks is impracticable for now. In this paper, we start by introducing an automatic approach based on the constraint satisfaction problem for the exploration of deterministic TDs and MDLAs. Since we transform the exhaustive search into an inherent feature of the searching model, the issue of incomplete search is settled. This tool is applied to search for related-key (RK) TDs of AES-192, and a new related-key differential-linear (DL) distinguisher is identified with a TD with certainty. Due to the novel property of the distinguisher, the previous RK DL attack on AES-192 is improved. Also, the new distinguisher is explained from the viewpoint of differentiallinear connectivity table (DLCT) and thus can be regarded as the first application of DLCT in the related-key attack scenario. As the second application of the tool, we propose a method to construct (RK) IDs and ZCLAs automatically. Benefiting from the control of the nonzero fixed differential pattern and the inherent feature of exhaustive search, the new searching scheme can discover longer distinguishers and hence possesses some superiorities over the previous methods. This technique is implemented with several primitives, and the provable security bounds of SKINNY and Midori64 against impossible differential distinguishing attack are generalised.
More Accurate Differential Properties of LED64 and Midori64 📺
In differential cryptanalysis, a differential is more valuable than the single trail belonging to it in general. The traditional way to compute the probability of the differential is to sum the probabilities of all trails within it. The automatic tool for the search of differentials based on Mixed Integer Linear Programming (MILP) has been proposed and realises the task of finding multiple trails of a given differential. The problem is whether it is reliable to evaluate the probability of the differential traditionally. In this paper, we focus on two lightweight block ciphers – LED64 and Midori64 and show the more accurate estimation of differential probability considering the key schedule. Firstly, an automated tool based on Boolean Satisfiability Problem (SAT) is put forward to accomplish the automatic search of differentials for ciphers with S-boxes and is applied to LED64 and Midori64. Secondly, we provide an automatic approach to detect the right pairs following a given differential, which can be exploited to calculate the differential property. Applying this technique to the STEP function of LED64, we discover some differentials with enhanced probability. As a result, the previous attacks relying upon high probability differentials can be improved definitely. Thirdly, we present a method to compute an upper-bound of the weak-key ratio for a given differential, which is utilised to analyse 4-round differentials of Midori64. We detect two differentials whose weak-key ratios are much lower than the expected 50%. More than 78% of the keys will make these two differentials being impossible differentials. The idea of the estimation for an upper-bound of the weak-key ratio can be employed for other ciphers and allows us to launch differential attacks more reliably. Finally, we introduce how to compute the enhanced differential probability and evaluate the size of keys achieving the improved probability. Such a property may incur an efficient weak-key attack. For a 4-round differential of Midori64, we obtain an improved differential property for a portion of keys.
Impossible Differential Cryptanalysis of Pelican, MT-MAC-AES and PC-MAC-AES
In this paper, the impossible differential cryptanalysis is extended to MAC algorithms \textsc{Pelican}, MT-MAC and PC-MAC based on AES and 4-round AES. First, we collect message pairs that produce the inner near-collision with some specific differences by the birthday attack. Then the impossible differential attack on 4-round AES is implemented using a 3-round impossible differential property. For \textsc{Pelican}, our attack can recover the internal state, which is an equivalent subkey. For MT-MAC-AES, the attack turns out to be a subkey recovery attack directly. The data complexity of the two attacks is $2^{85.5}$ chosen messages, and the time complexity is about $2^{85.5}$ queries. For PC-MAC-AES, we can recover the 256-bit key with $2^{85.5}$ chosen messages and $2^{128}$ queries.
Distinguishing and Forgery Attacks on Alred and Its AES-based Instance Alpha-MAC
In this paper, we present new distinguishers of the MAC construction \textsc{Alred} and its specific instance \textsc{Alpha}-MAC based on AES, which is proposed by Daemen and Rijmen in 2005. For the \textsc{Alred} construction, we describe a general distinguishing attack which leads to a forgery attack directly. The complexity is $2^{64.5}$ chosen messages and $2^{64.5}$ queries with success probability 0.63. We also use a two-round collision differential path for \textsc{Alpha}-MAC, to construct a new distinguisher with about $2^{65.5}$ queries. The most important is that the new distinguisher can be used to recover the internal state, which is an equivalent secret subkey, and leads to a second preimage attack. Moreover, the distinguisher on \textsc{Alred} construction is also applicable to the MACs based on CBC and CFB encryption mode.
Improved Impossible Differential Cryptanalysis of CLEFIA
Wei Wang Xiaoyun Wang
This paper presents an improved impossible differential attack on the new block cipher CLEFIA which is proposed by Sony Corporation at FSE 2007. Combining some observations with new tricks, we can filter out the wrong keys more efficiently, and improve the impossible differential attack on 11-round CLEFIA-192/256, which also firstly works for CLEFIA-128. The complexity is about $2^{98.1}$ encryptions and $2^{103.1}$ chosen plaintexts. By putting more constraint conditions on plaintext pairs, we give the first attack on 12-round CLEFIA for all three key lengths with $2^{114.3}$ encryptions and $2^{119.3}$ chosen plaintexts. For CLEFIA-192/256, our attack is applicable to 13-round variant, of which the time complexity is about $2^{181}$, and the data complexity is $2^{120}$. We also extend our attack to 14-round CLEFIA-256, with about $2^{245.4}$ encryptions and $2^{120.4}$ chosen plaintexts. Moreover, a birthday sieve method is introduced to decrease the complexity of the core precomputation.