Dr Chaoyun Li

In this paper, a family of new de Bruijn sequences is proposed through the construction of maximum-length nonlinear feedback shift registers (NFSRs). Let k be a positive integer and p(0)(x), p(1)(x),..., p(k)(x) be the primitive polynomials in F-2[x] with their degrees strictly increasing and pairwise coprime. We determine the cycle structure and adjacency graphs of linear feedback shift registers (LFSRs) with characteristic polynomial q(x) = Pi(k)(i=0) p(i) (x). In the case that p(0)(x) = 1 + x, an algorithm is proposed to produce maximum-length NFSRs from these LFSRs, and it is shown that the algorithm can generate O(2((2k-1)n)) n-stage maximum-length NFSRs with memory complexity O(2kkn) and time complexity O(2(n-dk) kn), where n and d(k) are the degrees of q(x) and p(k)(x), respectively. Finally, we illustrate the proposed algorithm in the case of k = 2. In this case, we prove that for any integer n >= 8, the algorithm can produce n-stage maximum-length NFSRs with time complexity as low as O(n(loglog(n))).

Symmetric cryptographic primitives with low multiplicative complexity have been proposed to improve the performance of emerging applications such as secure Multi-Party Computation. However, primitives composed of round functions with low algebraic degree require a careful evaluation to assess their security against algebraic cryptanalysis, and in particular interpolation attacks. This paper proposes new low-memory interpolation attacks on symmetric key primitives of low degree. Moreover, we present generic attacks on block ciphers with a simple key schedule; our attacks require either constant memory or constant data complexity. The improved attack is applied to the block cipher MiMC which aims to minimize the number of multiplications in large finite fields. As a result, we can break MiMC-129/129 with 38 rounds with time and data complexity 265.5 and 260.2 respectively and with negligible memory; this attack invalidates one of the security claims of the designers. Our attack indicates that for MiMC-129/129 the full 82 rounds are necessary even with restrictions on the memory available to the attacker. For variants of MiMC with larger keys, we present new attacks with reduced complexity. Our results do not affect the security claims of the full round MiMC.

In this paper, we propose several classes of permutation polynomials with the form (x(pm) - x +delta)(s1) +(x(Pm) - x+delta)(s2) + x over finite fields. The permutation behavior of the proposed polynomials is investigated by the AGW criterion and determination of the number of solutions to certain equations over finite fields. (C) 2018 Elsevier Inc. All rights reserved.

In this paper, a class of linear feedback shift registers (LFSRs) with characteristic polynomial (1 + x 3 )p(x) is discussed, where p(x) is a primitive polynomial of degree n > 2. The cycle structure and adjacency graphs of the LFSRs are determined. A new class of de Bruijn sequences is constructed from these LFSRs, and the number of de Bruijn sequences in the class is also considered. To illustrate the efficiency of constructing de Bruijn sequences from these LFSRs, an algorithm for producing some corresponding maximum-length nonlinear feedback shift registers with time and memory complexity O(n) is also proposed.

Privacy and data confidentiality are today at the heart of many discussions. But such data protection should not be done at the detriment of other security aspects. In the context of network traffic, intrusion detection system becomes totally blind when the traffic is encrypted, making clients again vulnerable to known attacks. To reconcile security and privacy, BlindBox and BlindIDS are proposed to perform Deep Packet Inspection over an encrypted traffic, based on two different cryptographic techniques. But, on one side, even if BlindBox is quite efficient to detect an anomalous encrypted traffic, it necessitates a very high setup time for clients and servers and does not protect the know‐how of Security Editors (SEs) working on detection rules. On the other side, BlindIDS does protect SE's market and does not introduce any latency during setup time, but is definitely not enough efficient for a practical use. Herein, it is shown that the design of a fully efficient and market‐compliant intrusion detection system over an encrypted traffic is possible. The system is based on only symmetric cryptography, and permits to encrypt a packet of 1500 bytes in about 6 μs and to test such packets with 3000 rules in less than 2 μs.

With the expansion of wireless technology, vehicular ad-hoc networks (VANETs) are emerging as a promising approach for realizing smart cities and addressing many serious traffic problems, such as road safety, convenience, and efficiency. To avoid any possible rancorous attacks, employing lightweight ciphers is most effective for implementing encryption/decryption, message authentication, and digital signatures for the security of the VANETs. Light encryption device (LED) is a lightweight block cipher with two basic keysize variants: LED-64 and LED-128. Since its inception, many fault analysis techniques have focused on provoking faults in the last four rounds to derive the 64-bit and 128-bit secret keys. It is vital to investigate whether injecting faults into a prior round enables breakage of the LED. This study presents a novel impossible meet-in-the-middle fault analysis on a prior round. A detailed analysis of the expected number of faults is used to uniquely determine the secret key. It is based on the propagation of truncated differentials and is surprisingly reminiscent of the computation of the complexity of a rectangle attack. It shows that the impossible meet-in-the-middle fault analysis could successfully break the LED by fault injections.

In this paper, we propose several classes of complete permutation polynomials over a finite field based on certain polynomials over its subfields or subsets. In addition, a class of complete permutation trinomials with Niho exponents is studied, and the number of these complete permutation trinomials is also determined. (C) 2018 Elsevier Inc. All rights reserved.

With the development of wireless technology, the ubiquitous sensor networks have a profound effect on the way human interacts with computers, devices and environment. In order to reduce the potentially serious risks in the interaction, applying lightweight ciphers is effective to balance security, efficiency and convenience. Simeck is such a lightweight cipher that provides data confidentiality, authentication and integrity. It is significant to explore whether Simeck remains robust security. Up to now, the attacking assumptions of the previous security analysis of Simeck focus on the known-plaintext attack and the chosen-plaintext attack. There is no literature about Simeck against the ciphertext-only attack, which represents the weakest attacking capability of the attackers. On the assumption of the ciphertext-only attack, this paper proposes the security analysis of Simeck against the statistical fault analysis with a series of novel distinguishers of KDE, MME and MME-GF. The experimental results show that the proposed distinguishers can recover the secret key of Simeck in both decreasing faults and increasing reliability and accuracy. Thus, Simeck cannot resist against the statistical fault analysis with the proposed distinguishers. Furthermore, the good performance of these novel distinguishers can be applied on the PRESENT lightweight cipher. It offers the valuable reference for the design and analysis of the lightweight ciphers in the ubiquitous sensor networks.

A theoretically reliable key-recovery attack should evaluate not only the non-randomness for the correct key guess but also the randomness for the wrong ones as well. The former has always been the main focus but the absence of the latter can also cause self-contradicted results. In fact, the theoretic discussion of wrong key guesses is overlooked in quite some existing key-recovery attacks, especially the previous cube attack variants based on pure experiments. In this paper, we draw links between the division property and several variants of the cube attack. In addition to the zero-sum property, we further prove that the bias phenomenon, the non-randomness widely utilized in dynamic cube attacks and cube testers, can also be reflected by the division property. Based on such links, we are able to provide several results: Firstly, we give a dynamic cube key-recovery attack on full Grain-128. Compared with Dinur et al.’s original one, this attack is supported by a theoretical analysis of the bias based on a more elaborate assumption. Our attack can recover 3 key bits with a complexity 297.86 and evaluated success probability 99.83%. Thus, the overall complexity for recovering full 128 key bits is 2125. Secondly, now that the bias phenomenon can be efficiently and elaborately evaluated, we further derive new secure bounds for Grain-like primitives (namely Grain-128, Grain-128a, Grain-V1, Plantlet) against both the zero-sum and bias cube testers. Our secure bounds indicate that 256 initialization rounds are not able to guarantee Grain-128 to resist bias-based cube testers. This is an efficient tool for newly designed stream ciphers for determining the number of initialization rounds. Thirdly, we improve Wang et al.’s relaxed term enumeration technique proposed in CRYPTO 2018 and extend their results on Kreyvium and ACORN by 1 and 13 rounds (reaching 892 and 763 rounds) with complexities 2121.19 and 2125.54 respectively. To our knowledge, our results are the current best key-recovery attacks on these two primitives.

With the enlargement of wireless technology, Internet of Things (IoT) is emerging as a promising approach to realize smart cities and address lots of serious problems such as safety, convenience and efficiency. In order to avoid any possible rancorous attacks, employing lightweight cryptosystems is most effective to implement encryption/decryption, message authentication and digital signature for security of the IoT. LED is such a lightweight cipher with two flexible keysize variants in the IoT. Since its designing, a multitude of fault analysis techniques in chosen plaintext attacks focus on provoking faults on LED to derive the 64-bit and 128-bit secret keys. It is vital to investigate whether injecting faults allows breaking LED while the attackers have the weakest ciphertext-only attacking ability. This study presents ciphertext-only fault analysis with six different distinguishers on LED. The simulating experiments show that our analysis can recover its 64-bit and 128-bit secret keys with over 99 percent probability using the SEI, GF, GF-SEI, ML, HW and MAP distinguishers. The attack can not only improve the attacking efficiency, but also decrease the number of faults. The fault locations can be injected into the deeper round. It provides vital reference for security analysis of other lightweight ciphers in the IoT.

MDS matrices are important building blocks providing diffusion functionality for the design of many symmetric-key primitives. In recent years, continuous efforts are made on the construction of MDS matrices with small area footprints in the context of lightweight cryptography. Just recently, Duval and Leurent (ToSC 2018/FSE 2019) reported some 32 x 32 binary MDS matrices with branch number 5, which can be implemented with only 67 XOR gates, whereas the previously known lightest ones of the same size cost 72 XOR gates. In this article, we focus on the construction of lightweight involutory MDS matrices, which are even more desirable than ordinary MDS matrices, since the same circuit can be reused when the inverse is required. In particular, we identify some involutory MDS matrices which can be realized with only 78 XOR gates with depth 4, whereas the previously known lightest involutory MDS matrices cost 84 XOR gates with the same depth. Notably, the involutory MDS matrix we find is much smaller than the AES MixColumns operation, which requires 97 XOR gates with depth 8 when implemented as a block of combinatorial logic that can be computed in one clock cycle. However, with respect to latency, the AES MixColumns operation is superior to our 78-XOR involutory matrices, since the AES MixColumns can be implemented with depth 3 by using more XOR gates. We prove that the depth of a 32 x 32 MDS matrix with branch number 5 (e.g., the AES MixColumns operation) is at least 3. Then, we enhance Boyar's SLP-heuristic algorithm with circuit depth awareness, such that the depth of its output circuit is limited. Along the way, we give a formula for computing the minimum achievable depth of a circuit implementing the summation of a set of signals with given depths, which is of independent interest. We apply the new SLP heuristic to a large set of lightweight involutory MDS matrices, and we identify a depth 3 involutory MDS matrix whose implementation costs 88 XOR gates, which is superior to the AES MixColumns operation with respect to both lightweightness and latency, and enjoys the extra involution property.

The cube attack is an important technique for the cryptanalysis of symmetric key primitives, especially for stream ciphers. Aiming at recovering some secret key bits, the adversary reconstructs a superpoly with the secret key bits involved, by summing over a set of the plaintexts/IV which is called a cube. Traditional cube attack only exploits linear/quadratic superpolies. Moreover, for a long time after its proposal, the size of the cubes has been largely confined to an experimental range, e.g., typically 40. These limits were first overcome by the division property based cube attacks proposed by Todo et al. at CRYPTO 2017. Based on MILP modelled division property, for a cube (index set) I, they identify the small (index) subset J of the secret key bits involved in the resultant superpoly. During the precomputation phase which dominates the complexity of the cube attacks, 2(vertical bar I vertical bar+vertical bar J vertical bar) encryptions are required to recover the superpoly. Therefore, their attacks can only be available when the restriction vertical bar I vertical bar+vertical bar J vertical bar < n is met. In this paper, we introduced several techniques to improve the division property based cube attacks by exploiting various algebraic properties of the superpoly. 1. We propose the "flag" technique to enhance the preciseness of MILP models so that the proper non-cube IV assignments can be identified to obtain a non-constant superpoly. 2. A degree evaluation algorithm is presented to upper bound the degree of the superpoly. With the knowledge of its degree, the superpoly can be recovered without constructing its whole truth table. This enables us to explore larger cubes I's even if vertical bar I vertical bar + vertical bar J vertical bar >= n. 3. We provide a term enumeration algorithm for finding the monomials of the superpoly, so that the complexity of many attacks can be further reduced. As an illustration, we apply our techniques to attack the initialization of several ciphers. To be specific, our key recovery attacks have mounted to 839-round TRIVIUM, 891-round Kreyvium, 184-round Grain-128a and 750-round ACORN respectively.

In this paper, periodic sequences with period N and nonlinear complexity N -2 are investigated. A necessary and sufficient condition for characterizing such sequences is established, and a recursive method is proposed to generate all possible binary sequences with period N and nonlinear complexity N -2. The exact number of such sequences is also determined.

In this paper, the cycle structure and adjacency graphs of a class of linear feedback shift registers (LFSRs) are determined. By recursively applying the D-morphism to the maximum-length LFSRs and representing the cycles by generating functions, a new family of maximum-length nonlinear feedback shift registers (NFSRs) are proposed based on the properties of these LFSRs. The number of NFSRs in the proposed family is also considered.

As perfect building blocks for the diffusion layers of many symmetric-key primitives, the construction of MDS matrices with lightweight circuits has received much attention from the symmetric-key community. One promising way of realizing low-cost MDS matrices is based on the iterative construction: a low-cost matrix becomes MDS after rising it to a certain power. To be more specific, if At is MDS, then one can implement A instead of At to achieve the MDS property at the expense of an increased latency with t clock cycles. In this work, we identify the exact lower bound of the number of nonzero blocks for a 4 × 4 block matrix to be potentially iterative-MDS. Subsequently, we show that the theoretically lightest 4 × 4 iterative MDS block matrix (whose entries or blocks are 4 × 4 binary matrices) with minimal nonzero blocks costs at least 3 XOR gates, and a concrete example achieving the 3-XOR bound is provided. Moreover, we prove that there is no hope for previous constructions (GFS, LFS, DSI, and spares DSI) to beat this bound. Since the circuit latency is another important factor, we also consider the lower bound of the number of iterations for certain iterative MDS matrices. Guided by these bounds and based on the ideas employed to identify them, we explore the design space of lightweight iterative MDS matrices with other dimensions and report on improved results. Whenever we are unable to find better results, we try to determine the bound of the optimal solution. As a result, the optimality of some previous results is proved.

We show that the correlation of any quadratic Boolean function can be read out from its so-called disjoint quadratic form. We further propose a polynomial-time algorithm that can transform an arbitrary quadratic Boolean function into its disjoint quadratic form. With this algorithm, the exact correlation of quadratic Boolean functions can be computed efficiently. We apply this method to analyze the linear trails of MORUS (one of the seven finalists of the CAESAR competition), which are found with the help of a generic model for linear trails of MORUS-like key-stream generators. In our model, any tool for finding linear trails of block ciphers can be used to search for trails of MORUS-like key-stream generators. As a result, a set of trails with correlation 2(-38) is identified for all versions of full MORUS, while the correlations of previously published best trails for MORUS-640 and MORUS-1280 are 2(-73) and 2(-76) respectively (ASIACRYPT 2018). This significantly improves the complexity of the attack on MORUS-1280-256 from 2(152) to 2(76). These new trails also lead to the first distinguishing and message-recovery attacks on MORUS-640-128 and MORUS-1280-128 with surprisingly low complexities around 2(76). Moreover, we observe that the condition for exploiting these trails in an attack can be more relaxed than previously thought, which shows that the new trails are superior to previously published ones in terms of both correlation and the number of ciphertext blocks involved.

Near-MDS matrices provide better trade-offs between security and efficiency compared to constructions based on MDS matrices, which are favored for hardware-oriented designs. We present new designs of lightweight linear diffusion layers by constructing lightweight near-MDS matrices. Firstly generic n x n near-MDS circulant matrices are found for 5

At CRYPTO 2017 and IEEE Transactions on Computers in 2018, Todo et al. proposed the division property based cube attack method making it possible to launch cube attacks with cubes of dimensions far beyond practical reach. However, assumptions are made to validate their attacks. In this paper, we further formulate the algebraic properties of the superpoly in one framework to facilitate cube attacks in more successful applications: we propose the “flag” technique to enhance the precision of MILP models, which enable us to identify proper non-cube IV assignments; a degree evaluation algorithm is presented to upper bound the degree of the superpoly s.t. the superpoly can be recovered without constructing its whole truth table and overall complexity of the attack can be largely reduced; we provide a divide-and-conquer strategy to Trivium-like stream ciphers namely Trivium, Kreyvium, TriviA-SC1/2 so that the large scale MILP models can be split into several small solvable ones enabling us to analyze Trivium-like primitives with more than 1000 initialization rounds; finally, we provide a term enumeration algorithm for finding the monomials of the superpoly, so that the complexity of many attacks can be further reduced. We apply our techniques to attack the initialization of several ciphers namely 839-round Trivium, 891-round Kreyvium, 1009-round TriviA-SC1, 1004-round TriviA-SC2, 184-round Grain-128a and 750-round Acorn respectively.