Search

Linear cryptanalysis is one of the most classical cryptanalysis methods for block ciphers. Some critical techniques of the key-recovery phase are developed for enhancing linear cryptanalysis. Collard et al. improved the time complexity for last-round key-recovery attacks by using FWT. A generalized key-recovery algorithm for an arbitrary number of rounds with an associated time complexity formula is further provided by Flórez-Gutiérrez and Naya-Plasencia based on FWT in Eurocrypt 2020. However, the previous generalized algorithms are mainly applied to block ciphers with SPN structures, where the round-keys in the first and last round XORed to the state can be easily defined as outer keys. In Asiacrypt 2021, Leurent et al. applied the algorithm by Flórez-Gutiérrez et al. to Feistel structure ciphers. However, for other structures, such as NLFSR-based, the outer keys can not be directly deduced to utilize the previous algorithms. This paper extends the algorithm by Flórez-Gutiérrez et al. for more complicated structures, including but not limited to NLFSR-based, Feistel, ARX, and SPN. We also use the dependency relationships between ciphertext, plaintext and key information bits to eliminate the redundancy calculation and the improve analysis phase. We apply the algorithm with the improved analysis phase to KATAN (NLFSR-based) and SPARX (ARX). We obtain significantly improved results. The linear results we find for SPARX-128/128 beat other cryptanalytic techniques, becoming the best key recovery attacks on this cipher. The previous best linear attacks on KATAN32, KATAN48 and KATAN64 are improved by 9, 4, and 14 rounds, respectively. [ABSTRACT FROM AUTHOR]

The cipher T-310 was developed by the Central Cipher Authority of the German Democratic Republic in the 1970s and widely used for protection of teletype communication up to security level secret. After publication of the cipher algorithm in 2006, several articles appeared aiming at the cryptographic properties of the cipher T-310. The cryptographic strength of the cipher T-310 must be assessed as a combination of both the cipher algorithm and the approved long-term keys. This article provides a rationale of the design decisions and the selection of approved long-term keys for T-310. We demonstrate that the attacks involving fundamental equations, linear characteristics, and some of their generalizations do not work if historical approved long-term keys are used. The results are also valid for the cipher SKS and block ciphers, whose groups of round functions are the alternating groups over the blocks. [ABSTRACT FROM AUTHOR]

In this paper, we perform linear cryptanalysis of the stream cipher SNOW 5G, which is recommended by the international standardization group (SAGE) as one standard algorithm for 5G confidentiality and integrity protection over the wireless channel. SNOW 5G can be regarded as one member of the SNOW-V family, as it is modified from SNOW-Vi by SAGE with a slight improvement. As an overall contribution, we provide a comprehensive and elaborate theoretical analysis of linear approximations of SNOW 5G and provide the best public cryptanalysis result by far. Specifically, we first theoretically analyze the formats of linear masks of SNOW5G that can introduce high correlations, and then search for high-quality linear masks using a divide-and-conquer method based on the different cases of a critical intermediate linear mask. We find a linear approximation of SNOW 5G with correlation −2−67.67 and further launch a correlation attack against it with complexity 2279.8, improving the existing best correlation attack by a factor of 232.4. Our results are mainly from theoretical analysis, which involve little computation overhead and help to better understand the security of SNOW 5G.

CHAM is a family of lightweight block ciphers with block sizes of 64 bits and 128 bits. CHAM performs very well in lightweight environments and is known to be one of the block ciphers that can be implemented with the smallest hardware area. In this paper, we evaluate the security of CHAM against linear cryptanalysis. Linear cryptanalysis is a cryptanalytic attack technique used to analyze the security of block ciphers by exploiting linear approximations of the cipher’s operations to deduce information about the secret key. We present a 36-round linear trail with correlation 2−31 of CHAM with 64-bit blocks and a 50-round linear trail with correlation 2−63 of CHAM with 128-bit blocks. Up to now, they are the best linear trails of CHAM. Furthermore, we present a 42-round linear hull with potential greater than 2−61.793 of CHAM with 64-bit blocks and a 54-round linear hull with potential greater than 2−126.394 of CHAM with 128-bit blocks. To the best of our knowledge, they are the first known linear hulls of CHAM.

Mixed-integer linear programming (MILP) techniques are widely used in cryptanalysis, aiding in the discovery of optimal linear and differential characteristics. This paper delves into the analysis of block ciphers KLEIN and PRINCE using MILP, specifically calculating the best linear and differential characteristics for reduced-round versions. Both ciphers employ matrix multiplication in their diffusion layers, which we model using multiple XOR operations. To this end, we propose two novel MILP models for multiple XOR operations, which use fewer variables and constraints, proving to be more efficient than standard methods for XOR modeling. For differential cryptanalysis, we identify characteristics with a probability of 2-59 for 7 rounds of KLEIN and a probability of 2-56 for 7 rounds of PRINCE. In linear cryptanalysis, we identify characteristics with a bias of 2-27 for 6 rounds of KLEIN and a bias of 2-29 for 7 rounds of PRINCE. These results establish the best single-key differential and linear distinguishers for these ciphers in the literature. [ABSTRACT FROM AUTHOR]

In recent years, Mixed-Integer Linear Programming (MILP)-based automatic tools have played a significant role in providing security evaluations of symmetric-key primitives. Differential and linear cryptanalysis are the two most important cryptographic techniques. Although some methods have conducted a great effort in exploiting MILP-aided tools in searching for differential (linear) characteristics, traditional methods still suffer from primitives with strong diffusion layers and large sizes, such as NOEKEON. Typically, searching for differential (linear) characteristics of such primitives is difficult, and the corresponding MILP models are too heavy to be solved efficiently. To this end, we propose a simple yet efficient approach to employ MILP to evaluate the security against differential and linear cryptanalysis of such primitives. The core of our approach is to reduce the complex problem to a set of simpler subproblems and obtain the optimal solution of the complex problem by combining all the subproblems. A subproblem is equivalent to searching for all differential (linear) characteristics with a fixed number of active S-boxes in each round. Furthermore, we design an elaborate algorithm consisting of three MILP-aided methods to solve various subproblems and adopt some techniques to improve efficiency further. Applying our new algorithm to three SPN primitives Serpent, NOEKEON and ASCON, we obtain the tightest security bounds against differential and linear cryptanalysis for all three primitives so far and find improved differential and linear characteristics for Serpent and NOEKEON. For Serpent, we improve the upper bound of the maximum probability of 7-round differential characteristics from |$2^{-71}$| to |$2^{-76}$| and find for the first time 7-round differential characteristics. For NOEKEON, our results show that there is no 9-round (10-round) differential (linear) characteristic with a probability (correlation) higher than |$2^{-128}$| (⁠|$2^{-64}$|⁠), whereas it needs 10 rounds (11 rounds) according to the previous results. In addition, we find an 8-round (9-round) differential (linear) characteristic with a probability (correlation) of |$2^{-127}$| (⁠|$2^{-60}$|⁠). For ASCON permutation, we provide for the first time an upper bound of the maximum probability (correlation) of 5-round differential (linear) characteristics as |$2^{-70}$| (⁠|$2^{-33}$|⁠). [ABSTRACT FROM AUTHOR]

BORON is a lightweight substitution–permutation network cipher proposed in 2017. We reduce the number of guessed key bits by key-bridging technology and first utilize Fast Walsh Transform on BORON to minimize the time complexity. Finally, this paper gives the better key-recovery attack against block cipher BORON than previously proposed by 2 rounds: we realize a 11-round key-recovery attack on BORON-80 and 13-round key-recovery attack on BORON-128. The attacks proposed in this paper are the best attacks against BORON-80/128 to date. [ABSTRACT FROM AUTHOR]

To evaluate the security of a cryptographic primitive, investigating its resistance against differential and linear cryptanalysis is required. Many modern cryptographic primitives repeatedly apply similar round functions alternated with the addition of round keys or constants. A round function usually consists of a non-linear mapping and a number of linear mappings. The non-linear mapping χ is used in different cryptographic primitives such as Keccak and Subterranean. An alternative version of χ is used in Ascon and the non-linear layer of Simon has the same differential and linear properties of χ . The mapping χ can be applied to strings with different lengths. For instance, it can be parallelly applied to small-length strings as in Keccak, where it works on 5-bit strings, or it can be applied to big-length strings as in Subterranean, where it works on a string of length 257. Investigating the differential and linear properties of χ working on alternative lengths of strings, provides useful information to designers to make a better choice for the non-linear layer. Some differential properties of χ have been analyzed in [8] and in this work we provide a revised presentation of them. We then extend this study and we analyze linear propagation properties of χ . Thanks to these additional results, we extend the comparison between the application of parallel instances of χ on small-length strings and the application of a single instance of χ on a big-length string. We show how we can apply the results of this study also to the non-linear layers of Ascon and Simon thanks to their affine-equivalence with χ . [ABSTRACT FROM AUTHOR]

In the context of linear cryptanalysis of block ciphers, let p 0 (resp. p 1 ) be the probability that a particular linear approximation holds for the right (resp. a wrong) key choice. The standard right key randomisation hypothesis states that p 0 is a constant p ≠ 1 / 2 and the standard wrong key randomisation hypothesis states that p 1 = 1 / 2 . Using these hypotheses, the success probability P S of the attack can be expressed in terms of the data complexity N. The resulting expression for P S is a monotone increasing function of N. Building on earlier work by O'Connor (In: Preneel B (ed) Fast Software Encryption: Second International Workshop. Leuven, Belgium, 14–16 December 1994, Proceedings, volume 1008 of Lecture Notes in Computer Science, pp. 131–136. Springer, 1994) and Daemen and Rijmen (J Math Cryptol 1(3):221–242, 2007), Bogdanov and Tischhauser (In: Moriai S (ed) Fast Software Encryption—20th International Workshop, FSE 2013, Singapore, March 11–13, 2013. Revised Selected Papers, volume 8424 of Lecture Notes in Computer Science, pp. 19–38. Springer, 2013) argued that p 1 should be considered to be a random variable. They postulated the adjusted wrong key randomisation hypothesis which states that p 1 follows a normal distribution. A non-intuitive consequence is that the resulting expression for P S is no longer a monotone increasing function of N. A later work by Blondeau and Nyberg (Des Codes Cryptogr 82(1–2):319–349, 2017) argued that p 0 should also be considered to be a random variable and they postulated the adjusted right key randomisation hypothesis which states that p 0 follows a normal distribution. In this work, we revisit the key randomisation hypotheses. While the argument that p 0 and p 1 should be considered to be random variables is indeed valid, we show that if p 0 and p 1 follow any distributions with supports which are subsets of [0, 1], and E [ p 0 ] = p and E [ p 1 ] = 1 / 2 , then the expression for P S that is obtained is exactly the same as the one obtained using the standard key randomisation hypotheses. Consequently, P S is a monotone increasing function of N even when p 0 and p 1 are considered to be random variables. [ABSTRACT FROM AUTHOR]

As the first generic method for finding the optimal differentialand linear characteristics, Matsui's branch and bound search algorithm has played an important role in evaluating the security of symmetric ciphers. By combining Matsui's bounding conditions with automatic search models, search efficiency can be improved. In this paper, by studying the properties of Matsui's bounding conditions, we give the general form of bounding conditions that can eliminate all the impossible solutions determined by Matsui's bounding conditions. Then, a new method of combining bounding conditions with sequential encoding method is proposed. With the help of some small size Mixed Integer Linear Programming (MILP) models, we can use fewer variables and clauses to build Satisfiability Problem (SAT) models. As applications, we use our new method to search for the optimal differential and linear characteristics of some SPN, Feistel, and ARX block ciphers. The number of variables and clauses and the solving time of the SAT models are decreased significantly. In addition, we find some new differential and linear characteristics covering more rounds. [ABSTRACT FROM AUTHOR]

Determining bounds on the differential probability of differential trails and the squared correlation contribution of linear trails forms an important part of the security evaluation of a permutation. For Xoodoo, such bounds were proven using the trail core tree search technique, with a dedicated tool (XooTools) that scans the space of all r-round trails with weight below a given threshold Tr. The search space grows exponentially with the value of Tr and XooTools appeared to have reached its limit, requiring huge amounts of CPU time to push the bounds a little further. The bottleneck was the phase called trail extension where short trails are extended to more rounds, especially in the backward direction. In this work, we present a number of techniques that allowed us to make extension much more efficient and as such to increase the bounds significantly. Notably, we prove that the minimum weight of any 4-round trail is 80, the minimum weight of any 6-round trail is at least 132 and the minimum weight of any 12-round trail is at least 264, both for differential and linear trails. As a byproduct we found families of trails that have predictable weight once extended to more rounds and use them to compute upper bounds for the minimum weight of trails for arbitrary numbers of rounds.

This paper mainly studies mixed integer linear programming (MILP)‐based cryptanalysis on round‐reduced NBC algorithm with generalized Feistel structure. First, each component of the algorithm is equivalently described by linear inequality equations, and the propagation rules of differential characteristics and linear approximation are described, and an automatic search algorithm model of differential mode and linear mask mode based on MILP is established, and the minimum number of active S‐boxes and the corresponding differential mode and linear mask mode paths are obtained. Second, according to the NBC algorithm's 16‐bit block pull‐wire position permutation characteristics, the optimal full diffusion rounds of NBC‐128 algorithm and NBC‐256 algorithm are obtained by using approximate matrix multiplication theory to be six and eight respectively. Finally, based on the optimal number of full diffusion rounds of the algorithm, an automatic search algorithm model of impossible differential cryptanalysis is established, and the set of input differential patterns is traversed to obtain 11‐round impossible differential distinguishers of NBC‐128 algorithm and 14‐round impossible differential distinguishers of NBC‐256 algorithm respectively. [ABSTRACT FROM AUTHOR]

Copyright of Journal of Cryptologic Research (2095-7025) is the property of Editorial Board of Journal of Cryptologic Research and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

A quantum version of the linear cryptanalysis technique is presented in this paper. So far, only a certain part of some classical cryptanalysis techniques was converted for quantum processing to gain speed-up while analysing a symmetric primitive. However, none of the quantum version of these attacks, including linear cryptanalysis, completely uses quantum computing for all the steps. We developed a quantum version for all the steps of the linear cryptanalysis. The proposed quantum linear cryptanalysis is applied on the quantum version of a toy cipher. Performance analysis shows that the quantum version of the linear cryptanalysis offers quadratic speed-up in different steps of the attack. It can be used to attack any cipher that is vulnerable against linear cryptanalysis. [ABSTRACT FROM AUTHOR]

In practice, when the security of a block cipher implementation is considered, the leakages related to the outer rounds encryptions can be used by side channel attacks (SCA) to recover the secret key. Therefore, the outer rounds of block cipher implementations should be protected. However, in order to lower the implementation price, the inner rounds of block cipher implementations may be unprotected. In light of this, the security of an outer rounds protected DES implementation is considered. In detail, template attack (TA), which is information theoretically the strongest SCA style, can be used to obtain the inner round output. Then, linear cryptanalysis (LC) can be used to recover the secret key. Finally, the optimal key enumeration algorithm can be used to optimize the efficiency of TA assisted LC. We evaluate the efficiency of TA assisted LC in simulated scenarios where a three outer rounds protected DES implementation is targeted. The evaluation results show that when 800 correct samples are available and the number of key enumeration is |$2^{10}$|⁠ , the efficiency of TA assisted LC can reach 83% of success rate. Overall, an efficient combination attack style that can be used to accurately evaluate the security of an outer rounds protected DES implementation is proposed. [ABSTRACT FROM AUTHOR]

Data Encryption Standard (DES) is a symmetric key cryptosystem that is applied in different cryptosystems of recent times. However, researchers found defects in the main assembling of the DES and declared it insecure against linear and differential cryptanalysis. In this paper, we have studied the faults and made improvements in their internal structure and get the new algorithm for Improved DES. The improvement is being made in the substitution step, which is the only nonlinear component of the algorithm. This alteration provided us with great outcomes and increase the strength of DES. Accordingly, a novel 6 × 6 good quality S-box construction scheme has been hired in the substitution phase of the DES. The construction involves the Galois field method and generates robust S-boxes that are used to secure the scheme against linear and differential attacks. Then again, the key space of the improved DES has been enhanced against the brute force attack. The outcomes of different performance analyses depict the strength of our proposed substitution boxes which also guarantees the strength of the overall DES. [ABSTRACT FROM AUTHOR]

To solve the problem of fast calculation of the minimum number of active S-boxes in cryptographic design, the difference and mask propagation of the diffusion layer were investigated, and a method was proposed to compute the difference (resp.mask) pattern distribution table of MDS (maximum distance separable) matrices and binary matrices.A lower bound on the computation complexity of the proposed method was also given.Based on the difference (resp.mask) pattern distribution table of diffusion matrix, a fast algorithm to search for the minimum number of active S-boxes of block cipher was proposed.The proposed algorithm is applied to some SPN (substitution permutation network) block ciphers, and finds the minimum number of active S-boxes for the full round of LED, SKINNY, CRAFT and FIDES.

The Simeck family of lightweight block ciphers was proposed by Yang et al. in 2015, which combines the design features of the NSA-designed block ciphers Simon and Speck. Previously, we proposed the use of linear cryptanalysis using super-rounds to increase the efficiency of implementing Matsui's second algorithm and achieved good results on all variants of Simon. The improved linear attacks result from the observation that, after four rounds of encryption, one bit of the left half of the state of the cipher depends on only 17 key bits (19 key bits for the larger variants of the cipher). We were able to follow a similar approach, in all variants of Simeck, with an improvement in Simeck 32 and Simeck 48 by relaxing the previous constraint of a single active bit, using multiple active bits instead. In this paper we present improved linear attacks against all variants of Simeck: attacks on 19-rounds of Simeck 32/64, 28-rounds of Simeck 48/96, and 34-rounds of Simeck 64/128, often with the direct recovery of the full master key without repeating the attack over multiple rounds. We also verified the results of linear cryptanalysis on 8, 10, and 12 rounds for Simeck 32/64. [ABSTRACT FROM AUTHOR]

In this paper, we study a new flexible method to extend linearly the graph of a nonlinear, and usually not bijective, function so that the resulting extension is a bijection. Our motivation comes from cryptography. Examples from symmetric cryptography are given as how the extension was used implicitly in the construction of some well-known block ciphers. The method heavily relies on ideas brought from linear coding theory and secret sharing. We are interested in the behavior of the composition of many extensions, and especially the space of parameters that defines a family of equations based on finite differences or linear forms. For any linear extension, we characterize entirely the space of parameters for which such equations are solvable in terms of the space of parameters that render those equations for the corresponding nonlinear extended functions solvable. Conditions are derived to assess the solvability of those kind of equations in terms of the number of compositions or iterations. We prove a relation between the number of compositions and the dimensions of vector spaces that appear in our results. The proofs of those properties rely mostly on tools from linear algebra. [ABSTRACT FROM AUTHOR]

To solve the problem of fast calculation of the minimum number of active S-boxes in cryptographic design, the difference and mask propagation of the diffusion layer were investigated, and a method was proposed to compute the difference (resp. mask) pattern distribution table of MDS (maximum distance separable) matrices and binary matrices. A lower bound on the computation complexity of the proposed method was also given. Based on the difference (resp. mask) pattern distribution table of diffusion matrix, a fast algorithm to search for the minimum number of active S-boxes of block cipher was proposed. The proposed algorithm is applied to some SPN (substitution permutation network) block ciphers, and finds the minimum number of active S-boxes for the full round of LED, SKINNY, CRAFT and FIDES. [ABSTRACT FROM AUTHOR]