An Improved Framework of Massive Superpoly Recovery in Cube Attacks Against NFSR-Based Stream Ciphers

A critical problem in the cube attack is how to recover superpolies efficiently.As the targeting number of rounds of an iterative stream cipher increases,the scale of its superpolies becomes larger and larger.Recently,to recover massive superpolies,the nested monomial prediction technique,the algorithm based on the divide-and-conquer strategy,and stretching cube attacks were proposed,which have been used to recover a superpoly with over ten million monomials for the NFSR-based stream ciphers such as Trivium and Grain-128AEAD.Nevertheless,when these methods are used to recover superpolies,many invalid calculations are performed,which makes recovering superpolies more difficult.This study finds an interesting observation that can be used to improve the above methods.Based on the observation,a new method is proposed to avoid a part of invalid calculations during the process of recovering superpolies.Then,the new method is applied to the nested monomial prediction technique and an improved superpoly recovery framework is presented.To verify the effectiveness of the proposed scheme,the improved framework is applied to 844-and 846-round Trivium and the exact ANFs of the superpolies is obtained with over one hundred million monomials,showing the improved superpoly recovery technique is powerful.Besides,extensive experiments on other scaled-down variants of NFSR-based stream ciphers show that the proposed scheme indeed could be more efficient on the superpoly recovery against NFSR-based stream ciphers.

General Method of Combining Grover and Simon for Attacking Block Ciphers

The compatibility of different quantum algorithms should be considered when these algorithms are combined.In this paper,the method of combining Grover and Simon is studied for the first time,under some preconditions or assumptions.First,we give two preconditions of applying Grover’s algorithm,which ensure that the success probability of finding the marked element is close to 1.Then,based on these two preconditions,it is found out that the success probability of the quantum algorithm for FXconstruction is far less than 1.Furthermore,we give the design method of the Oracle function,and then present the general method of combining Grover and Simon algorithm for attacking block ciphers,with success probability close to 1.

Automatic Search of Impossible Differentials and Zero-Correlation Linear Hulls for ARX Ciphers

In lightweight cryptographic primitives, round functions with only simple operations XOR, modular addition and rotation are widely used nowadays. This kind of ciphers is called ARX ciphers. For ARX ciphers, impossible differential cryptanalysis and zero-correlation linear cryptanalysis are among the most powerful attacks, and the key problems for these two attacks are discovering more and longer impossible differentials(IDs) and zero-correlation linear hulls(ZCLHs). However, finding new IDs and ZCLHs for ARX ciphers has been a manual work for a long time, which has been an obstacle in improving these two attacks. This paper proposes an automatic search method to improve the efficiency of finding new IDs and ZCLHs for ARX ciphers. In order to prove the efficiency of this new tool, we take HIGHT, LEA, SPECK three typical ARX algorithms as examples to explore their longer and new impossible differentials and zero-correlation linear hulls. To the best of our knowledge, this is the first application of automatic search method for ARX ciphers on finding new IDs and ZCLHs. For HIGHT, we find more 17 round IDs and multiple 17 round ZCLHs. This is the first discovery of 17 round ZCLHs for HIGHT. For LEA, we find extra four 10 round IDs and several 9 round ZCLHs. In the specification of LEA, the designers just identified three 10 round IDs and one 7round ZCLH. For SPECK, we find thousands of 6 round IDs and forty-four 6 round ZCLHs. Neither IDs nor ZCLHs of SPECK has been proposed before. The successful application of our new tool shows great potential in improving the impossible differential cryptanalysis and zero-correlation linear cryptanalysis on ARX ciphers..

Further Analysis of Block Ciphers against Timing Attacks

Timing attacks break a cryptosystem by time measurement to recover keys. Most available countermeasures protect block ciphers based on the safety of modules. This paper gives a complete definition of timing attacks and studies the vulnerability of operations and modules on timing attacks. We present a method to transfer the security of the algorithm to that of secure operations by reduction. As a result, we hopefully tend to reconcile the provable security notions and modem cryptography with real-world implementations of block ciphers.

Improved Feistel-based ciphers for wireless sensor network security

Wireless sensor networks (WSNs) are exposed to a variety of attacks. The quality and complexity of attacks are rising day by day. The proposed work aims at showing how the complexity of modern attacks is growing accordingly, leading to a similar rise in methods of resistance. Limitations in computational and battery power in sensor nodes are constraints on the diversity of security mechanisms. We must apply only suitable mechanisms to WSN where our approach was motivated by the application of an improved Feistel scheme. The modified accelerated-cipher design uses data-dependent permutations, and can be used for fast hardware, firmware, software and WSN encryption systems. The approach presented showed that ciphers using this approach are less likely to suffer intrusion of differential cryptanalysis than currently used popular WSN ciphers like DES, Camellia and so on.

A survey on the Metaheuristics for Cryptanalysis of Substitution and Transposition Ciphers

This paper presents state-of-art cryptanalysis studies on attacks of the substitution and transposition ciphers using various metaheuristic algorithms.Traditional cryptanalysis methods employ an exhaustive search,which is computationally expensive.Therefore,metaheuristics have attracted the interest of researchers in the cryptanalysis field.Metaheuristic algorithms are known for improving the search for the optimum solution and include Genetic Algorithm,Simulated Annealing,Tabu Search,Particle Swarm Optimization,Differential Evolution,Ant Colony,the Artificial Bee Colony,Cuckoo Search,and Firefly algorithms.The most important part of these various applications is deciding the fitness function to guide the search.This review presents how these algorithms have been implemented for cryptanalysis purposes.The paper highlights the results and findings of the studies and determines the gaps in the literature.

STUDY ON STREAM CIPHERS USING GENERATING FUNCTIONS

Several kinds of stream ciphers—complementary sequences of period sequences,partial sum of period sequences,inverse order sequences and finitely generated sequences,arestudied by using techniques of generating functions.Their minimal polynomials,periods,as wellas generating functions are given.As to finitely generated sequences,the change of their linearcomplexity profiles as well as the relationship between the two generated sequences usder thecase in which the degree of connected polynomials are fixed,are discussed.

Randomized Stream Ciphers with Enhanced Security Based on Nonlinear Random Coding

We propose a framework for designing randomized stream ciphers with enhanced security. The key attribute of this framework is using of nonlinear bijective mappings or keyless hash functions for random coding. We investigate the computational security of the proposed ciphers against chosen-plaintext-chosen-initialization-vector attacks and show that it is based on the hardness of solving some systems of random nonlinear Boolean equations. We also provide guidelines for choosing components to design randomizers for specified ciphers.

Improved deep learning aided key recovery framework:applications to large-state block ciphers

At the Annual International Cryptology Conference in 2019,Gohr introduced a deep learning based cryptanalysis technique applicable to the reduced-round lightweight block ciphers with a short block of SPECK32/64.One significant challenge left unstudied by Gohr's work is the implementation of key recovery attacks on large-state block ciphers based on deep learning.The purpose of this paper is to present an improved deep learning based framework for recovering keys for large-state block ciphers.First,we propose a key bit sensitivity test(KBST)based on deep learning to divide the key space objectively.Second,we propose a new method for constructing neural distinguisher combinations to improve a deep learning based key recovery framework for large-state block ciphers and demonstrate its rationality and effectiveness from the perspective of cryptanalysis.Under the improved key recovery framework,we train an efficient neural distinguisher combination for each large-state member of SIMON and SPECK and finally carry out a practical key recovery attack on the large-state members of SIMON and SPECK.Furthermore,we propose that the 13-round SIMON64 attack is the most effective approach for practical key recovery to date.Noteworthly,this is the first attempt to propose deep learning based practical key recovery attacks on18-round SIMON128,19-round SIMON128,14-round SIMON96,and 14-round SIMON64.Additionally,we enhance the outcomes of the practical key recovery attack on SPECK large-state members,which amplifies the success rate of the key recovery attack in comparison to existing results.

Continuously non-malleable codes from block ciphers in split-state model

Non-malleable code is an encoding scheme that is useful in situations where traditional error correction or detection is impossible to achieve.It ensures with high probability that decoded message is either completely unrelated or the original one,when tampering has no effect.Usually,standard version of non-malleable codes provide security against one time tampering attack.Block ciphers are successfully employed in the construction of non-malleable codes.Such construction fails to provide security when an adversary tampers the codeword more than once.Continuously non-malleable codes further allow an attacker to tamper the message for polynomial number of times.In this work,we propose continuous version of non-malleable codes from block ciphers in split-state model.Our construction provides security against polynomial number of tampering attacks and it preserves non-malleability.When the tam-pering experiment triggers self-destruct,the security of continuously non-malleable code reduces to security of the underlying leakage resilient storage.

A CHARACTERISTIC SET METHOD FOR SOLVING BOOLEAN EQUATIONS AND APPLICATIONS IN CRYPTANALYSIS OF STREAM CIPHERS

This paper presents a characteristic more efficient and has better properties than the set method for solving Boolean equations, which is general characteristic set method. In particular, the authors give a disjoint and monic zero decomposition algorithm for the zero set of a Boolean equation system and an explicit formula for the number of solutions of a Boolean equation system. The authors also prove that a characteristic set can be computed with a polynomial number of multiplications of Boolean polynomials in terms of the number of variables. As experiments, the proposed method is used to solve equations from cryptanalysis of a class of stream ciphers based on nonlinear filter generators. Extensive experiments show that the method is quite effective.

A resynchronization attack on stream ciphers filtered by Maiorana-McFarland functions

A resynchronization attack is proposed on stream ciphers filtered by Maiorana-McFarland （M-M） functions and equipped with a linear resynchronization mechanism. The proposed attack utilizes the linear weakness of the resynchronization mechanism, the partial linearity of M-M functions, and applies the linear consistency test method to recover the secret key. It is shown that an M-M function should not be implemented by itself but rather in combination with other nonlinear components in stream ciphers using linear mechanisms to prevent the proposed attack. It is also shown that the use of linear resynchronization mechanisms should be avoided despite their high efficiency in stream ciphers filtered by M-M functions.

ON THE CRITERIA AND ENUMERATION OFBOOLEAN FUNCTIONS USEDIN STREAM CIPHERS

In this paper, we discuss the criteria of boolean functions used in streamciphers, and enumerate boolean functions which satisfy some criteria.

Multidimensional linear cryptanalysis with key difference invariant bias for block ciphers

For block ciphers,Bogdanov et al.found that there are some linear approximations satisfying that their biases are deterministically invariant under key difference.This property is called key difference invariant bias.Based on this property,Bogdanov et al.proposed a related-key statistical distinguisher and turned it into key-recovery attacks on LBlock and TWINE-128.In this paper,we propose a new related-key model by combining multidimensional linear cryptanalysis with key difference invariant bias.The main theoretical advantage is that our new model does not depend on statistical independence of linear approximations.We demonstrate our cryptanalysis technique by performing key recovery attacks on LBlock and TWINE-128.By using the relations of the involved round keys to reduce the number of guessed subkey bits.Moreover,the partial-compression technique is used to reduce the time complexity.We can recover the master key of LBlock up to 25 rounds with about 260.4 distinct known plaintexts,278.85 time complexity and 261 bytes of memory requirements.Our attack can recover the master key of TWINE-128 up to 28 rounds with about 261.5 distinct known plaintexts,2126.15 time complexity and 261 bytes of memory requirements.The results are the currently best ones on cryptanalysis of LBlock and TWINE-128.

Key-Recovery Attacks on LED-Like Block Ciphers

Asymmetric cryptographic schemes, represe nted by RSA, have bee n show n to be in secure un der quantum computing conditions. Correspondingly, there is a need to study whether the symmetric cryptosystem can still guarantee high security with the advent of quantum computers. In this paper, based on the basic principles of classical slide attacks and Simon's algorithm, we take LED-like lightweight block ciphers as research objects to present a security analysis under both classical and quantum attacks, fully considering the influence on the security of the ciphers of adding the round constants. By analyzing the information leakage of round constants, we can introduce the differential of the round constants to propose a classical slide attack on full-round LED-64 with a probability of 1. The analysis result shows that LED-64 is unable to resist this kind of classical slide attack, but that attack method is not applicable to LED-128. As for quantum attacks, by improving on existing quantum attack methods we dem on strate a qua ntum single-key slide attack on LED-64 and a quantum related-key attack on LED- 128, and indicators of the two attack algorithms are analyzed in detail. The attack results show that adding round consta nts does not completely improve the security of the ciphers, and quantum attacks can provide an exp on ential speed-up over the same attacks in the classical model. It further illustrates that the block cipher that is proved to be safe under classical settings is not necessarily secure under quantum conditions.

New AES Dual Ciphers Based on Rotation of Columns

Based on the different representations of the finite field GF(256), there are different Advanced Encryption Standard(AES) implementations, which is called dual ciphers. They have the same encryption process as AES, but with parameters modified. The research of dual ciphers initially aims to find more efficient AES implementations, and later it is found that they can be used to resist side-channel attacks and for white box ciphers. In this paper, based on the rotation of columns, we propose new AES dual ciphers, which use AES directly, but with the input matrices(plaintexts and keys) and output matrix rotated. The key expansion algorithm only needs some change on the computation sequence. Because of these features, there is almost no extra cost in implementing dual ciphers and it is easy for new dual ciphers to work with other side-channel protection methods to protect AES in more dimensions.

Multidimensional linear cryptanalysis with key difference invariant bias for block ciphers

For block ciphers,Bogdanov et al.found that there are some linear approximations satisfying that their biases are deterministically invariant under key difference.This property is called key difference invariant bias.Based on this property,Bogdanov et al.proposed a related-key statistical distinguisher and turned it into key-recovery attacks on LBlock and TWINE-128.In this paper,we propose a new related-key model by combining multidimensional linear cryptanalysis with key difference invariant bias.The main theoretical advantage is that our new model does not depend on statistical independence of linear approximations.We demonstrate our cryptanalysis technique by performing key recovery attacks on LBlock and TWINE-128.By using the relations of the involved round keys to reduce the number of guessed subkey bits.Moreover,the partial-compression technique is used to reduce the time complexity.We can recover the master key of LBlock up to 25 rounds with about 2^(60.4)distinct known plaintexts,2^(78.85)time complexity and 2^(61)bytes of memory requirements.Our attack can recover the master key of TWINE-128 up to 28 rounds with about 2^(61.5)distinct known plaintexts,2^(126.15)time complexity and 261 bytes of memory requirements.The results are the currently best ones on cryptanalysis of LBlock and TWINE-128.

Scan-Based Attack on Stream Ciphers: A Case Study on eSTREAM Finalists

Scan-based design for test （DFT） is a powerful and the most popular testing technique. However, while scan-based DFT improves test efficiency, it also leaves a side channel to the privacy information stored in the chip. This paper investigates the side channel and proposes a simple but powerful scan-based attack that can reveal the key and/or state stored in the chips that implement the state-of-the-art stream ciphers with less than 85 scan-out vectors.

A New Black Box Analysis of Hash Functions Based on Block Ciphers

For the 64 most basic ways to construct a hash function H:{0,1} → {0,1}n from a block cipher E:{0,1}n × {0,1}n → {0,1}n, Black et al.provided a formal and quantitative treatment of the 64 constructions, and proved that 20 schemes are collision resistant.This paper improves the upper and lower bounds and make contrast with a hash constructed from a random oracle.These 20 schemes have only one kind of collision resistance upper and lower bounds.In addition, we present new advantages for finding second preimages.

ANALYSIS OF MINIMUM NUMBERS OF LINEARLY ACTIVE S-BOXES OF A CLASS OF GENERALIZED FEISTEL BLOCK CIPHERS

For a class of generalized Feistel block ciphers, an explicit formula for the minimum numbers of linearly active S-boxes of any round r is presented.