## CryptoDB

### Lei Hu

#### Affiliation: Chinese Academy of Sciences

#### Publications

**Year**

**Venue**

**Title**

2020

TOSC

Lightweight Iterative MDS Matrices: How Small Can We Go?
📺
Abstract

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.

2020

TOSC

Differential Attacks on CRAFT Exploiting the Involutory S-boxes and Tweak Additions
📺
Abstract

CRAFT is a lightweight tweakable block cipher proposed at FSE 2019, which allows countermeasures against Differential Fault Attacks to be integrated into the cipher at the algorithmic level with ease. CRAFT employs a lightweight and involutory S-box and linear layer, such that the encryption function can be turned into decryption at a low cost. Besides, the tweakey schedule algorithm of CRAFT is extremely simple, where four 64-bit round tweakeys are generated and repeatedly used. Due to a combination of these features which makes CRAFT exceedingly lightweight, we find that some input difference at a particular position can be preserved through any number of rounds if the input pair follows certain truncated differential trails. Interestingly, in contrast to traditional differential analysis, the validity of this invariant property is affected by the positions where the constant additions take place. We use this property to construct “weak-tweakey” truncated differential distinguishers of CRAFT in the single-key model. Subsequently, we show how the tweak additions allow us to convert these weak-tweakey distinguishers into ordinary secret-key distinguishers based on which key-recovery attacks can be performed. Moreover, we show how to construct MILP models to search for truncated differential distinguishers exploiting this invariant property. As a result, we find a 15-round truncated differential distinguisher of CRAFT and extend it to a 19-round key-recovery attack with 260.99 data, 268 memory, 294.59 time complexity, and success probability 80.66%. Also, we find a 14-round distinguisher with probability 2−43 (experimentally verified), a 16-round distinguisher with probability 2−55, and a 20-round weak-key distinguisher (2118 weak keys) with probability 2−63. Experiments on round-reduced versions of the distinguishers show that the experimental probabilities are sometimes higher than predicted. Finally, we note that our result is far from threatening the security of the full CRAFT.

2020

ASIACRYPT

Quantum Collision Attacks on AES-like Hashing with Low Quantum Random Access Memories
📺
Abstract

At EUROCRYPT 2020, Hosoyamada and Sasaki proposed the first dedicated quantum attack on hash functions -- a quantum version of the rebound attack exploiting differentials whose probabilities are too low to be useful in the classical setting. This work opens up a new perspective toward the security of hash functions against quantum attacks. In particular, it tells us that the search for differentials should not stop at the classical birthday bound. Despite these interesting and promising implications, the concrete attacks described by Hosoyamada and Sasaki make use of large quantum random access memories (qRAMs), a resource whose availability in the foreseeable future is controversial even in the quantum computation community. Without large qRAMs, these attacks incur significant increases in time complexities. In this work, we reduce or even avoid the use of qRAMs by performing a quantum rebound attack based on differentials with non-full-active super S-boxes. Along the way, an MILP-based method is proposed to systematically explore the search space of useful truncated differentials with respect to rebound attacks. As a result, we obtain improved attacks on \aes-\texttt{MMO}, \aes-\texttt{MP}, and the first classical collision attacks on 4- and 5-round \grostl-\texttt{512}.
Interestingly, the use of non-full-active super S-box differentials in the analysis of \aes-\texttt{MMO} gives rise to new difficulties in collecting enough starting points. To overcome this issue, we consider attacks involving two message blocks to gain more degrees of freedom, and we successfully compress the qRAM demand of the collision attacks on \texttt{AES}-\texttt{MMO} and \texttt{AES}-\texttt{MP} (EUROCRYPT 2020) from $2^{48}$ to a range from $2^{16}$ to $0$, while still maintaining a comparable time complexity.
To the best of our knowledge, these are the first dedicated quantum attacks on hash functions that slightly outperform Chailloux, Naya-Plasencia, and Schrottenloher's generic quantum collision attack (ASIACRYPT 2017) in a model where large qRAMs are not available. This work demonstrates again how a clever combination of classical cryptanalytic technique and quantum computation leads to improved attacks, and shows that the direction pointed out by Hosoyamada and Sasaki deserves further investigation.

2019

TOSC

Constructing Low-latency Involutory MDS Matrices with Lightweight Circuits
📺
Abstract

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 × 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 × 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.

2019

TOSC

Boomerang Connectivity Table Revisited. Application to SKINNY and AES
📺
Abstract

The boomerang attack is a variant of differential cryptanalysis which regards a block cipher E as the composition of two sub-ciphers, i.e., E = E1 o E0, and which constructs distinguishers for E with probability p2q2 by combining differential trails for E0 and E1 with probability p and q respectively. However, the validity of this attack relies on the dependency between the two differential trails. Murphy has shown cases where probabilities calculated by p2q2 turn out to be zero, while techniques such as boomerang switches proposed by Biryukov and Khovratovich give rise to probabilities greater than p2q2. To formalize such dependency to obtain a more accurate estimation of the probability of the distinguisher, Dunkelman et al. proposed the sandwich framework that regards E as Ẽ1 o Em o Ẽ0, where the dependency between the two differential trails is handled by a careful analysis of the probability of the middle part Em. Recently, Cid et al. proposed the Boomerang Connectivity Table (BCT) which unifies the previous switch techniques and incompatibility together and evaluates the probability of Em theoretically when Em is composed of a single S-box layer. In this paper, we revisit the BCT and propose a generalized framework which is able to identify the actual boundaries of Em which contains dependency of the two differential trails and systematically evaluate the probability of Em with any number of rounds. To demonstrate the power of this new framework, we apply it to two block ciphers SKINNY and AES. In the application to SKINNY, the probabilities of four boomerang distinguishers are re-evaluated. It turns out that Em involves5 or 6 rounds and the probabilities of the full distinguishers are much higher than previously evaluated. In the application to AES, the new framework is used to exclude incompatibility and find high probability distinguishers of AES-128 under the related-subkey setting. As a result, a 6-round distinguisher with probability 2−109.42 is constructed. Lastly, we discuss the relation between the dependency of two differential trails in boomerang distinguishers and the properties of components of the cipher.

2019

CRYPTO

New Results on Modular Inversion Hidden Number Problem and Inversive Congruential Generator
📺
Abstract

The Modular Inversion Hidden Number Problem (MIHNP), introduced by Boneh, Halevi and Howgrave-Graham in Asiacrypt 2001, is briefly described as follows: Let $${\mathrm {MSB}}_{\delta }(z)$$ refer to the $$\delta $$ most significant bits of z. Given many samples $$\left( t_{i}, {\mathrm {MSB}}_{\delta }((\alpha + t_{i})^{-1} \bmod {p})\right) $$ for random $$t_i \in \mathbb {Z}_p$$, the goal is to recover the hidden number $$\alpha \in \mathbb {Z}_p$$. MIHNP is an important class of Hidden Number Problem.In this paper, we revisit the Coppersmith technique for solving a class of modular polynomial equations, which is respectively derived from the recovering problem of the hidden number $$\alpha $$ in MIHNP. For any positive integer constant d, let integer $$n=d^{3+o(1)}$$. Given a sufficiently large modulus p, $$n+1$$ samples of MIHNP, we present a heuristic algorithm to recover the hidden number $$\alpha $$ with a probability close to 1 when $$\delta /\log _2 p>\frac{1}{d\,+\,1}+o(\frac{1}{d})$$. The overall time complexity of attack is polynomial in $$\log _2 p$$, where the complexity of the LLL algorithm grows as $$d^{\mathcal {O}(d)}$$ and the complexity of the Gröbner basis computation grows as $$(2d)^{\mathcal {O}(n^2)}$$. When $$d> 2$$, this asymptotic bound outperforms $$\delta /\log _2 p>\frac{1}{3}$$ which is the asymptotic bound proposed by Boneh, Halevi and Howgrave-Graham in Asiacrypt 2001. It is the first time that a better bound for solving MIHNP is given, which implies that the conjecture that MIHNP is hard whenever $$\delta /\log _2 p<\frac{1}{3}$$ is broken. Moreover, we also get the best result for attacking the Inversive Congruential Generator (ICG) up to now.

2019

CRYPTO

Correlation of Quadratic Boolean Functions: Cryptanalysis of All Versions of Full $\mathsf {MORUS}$
📺
Abstract

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 $$\mathsf {MORUS}$$ (one of the seven finalists of the CAESAR competition), which are found with the help of a generic model for linear trails of $$\mathsf {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 $$\mathsf {MORUS}$$-like key-stream generators. As a result, a set of trails with correlation $$2^{-38}$$ is identified for all versions of full $$\mathsf {MORUS}$$, while the correlations of previously published best trails for $$\mathsf {MORUS}$$-640 and $$\mathsf {MORUS}$$-1280 are $$2^{-73}$$ and $$2^{-76}$$ respectively (ASIACRYPT 2018). This significantly improves the complexity of the attack on $$\mathsf {MORUS}$$-1280-256 from $$2^{152}$$ to $$2^{76}$$. These new trails also lead to the first distinguishing and message-recovery attacks on $$\mathsf {MORUS}$$-640-128 and $$\mathsf {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.

2018

ASIACRYPT

Programming the Demirci-Selçuk Meet-in-the-Middle Attack with Constraints
Abstract

Cryptanalysis with SAT/SMT, MILP and CP has increased in popularity among symmetric-key cryptanalysts and designers due to its high degree of automation. So far, this approach covers differential, linear, impossible differential, zero-correlation, and integral cryptanalysis. However, the Demirci-Selçuk meet-in-the-middle ($$\mathcal {DS}$$-$$\mathsf {MITM}$$) attack is one of the most sophisticated techniques that has not been automated with this approach. By an in-depth study of Derbez and Fouque’s work on $$\mathcal {DS}$$-$$\mathsf {MITM}$$ analysis with dedicated search algorithms, we identify the crux of the problem and present a method for automatic $$\mathcal {DS}$$-$$\mathsf {MITM}$$ attack based on general constraint programming, which allows the cryptanalysts to state the problem at a high level without having to say how it should be solved. Our method is not only able to enumerate distinguishers but can also partly automate the key-recovery process. This approach makes the $$\mathcal {DS}$$-$$\mathsf {MITM}$$ cryptanalysis more straightforward and easier to follow, since the resolution of the problem is delegated to off-the-shelf constraint solvers and therefore decoupled from its formulation. We apply the method to SKINNY, TWINE, and LBlock, and we get the currently known best $$\mathcal {DS}$$-$$\mathsf {MITM}$$ attacks on these ciphers. Moreover, to demonstrate the usefulness of our tool for the block cipher designers, we exhaustively evaluate the security of $$8! = 40320$$ versions of LBlock instantiated with different words permutations in the F functions. It turns out that the permutation used in the original LBlock is one of the 64 permutations showing the strongest resistance against the $$\mathcal {DS}$$-$$\mathsf {MITM}$$ attack. The whole process is accomplished on a PC in less than 2 h. The same process is applied to TWINE, and similar results are obtained.

2017

TOSC

Analysis of AES, SKINNY, and Others with Constraint Programming
Abstract

Search for different types of distinguishers are common tasks in symmetrickey cryptanalysis. In this work, we employ the constraint programming (CP) technique to tackle such problems. First, we show that a simple application of the CP approach proposed by Gerault et al. leads to the solution of the open problem of determining the exact lower bound of the number of active S-boxes for 6-round AES-128 in the related-key model. Subsequently, we show that the same approach can be applied in searching for integral distinguishers, impossible differentials, zero-correlation linear approximations, in both the single-key and related-(twea)key model. We implement the method using the open source constraint solver Choco and apply it to the block ciphers PRESENT, SKINNY, and HIGHT (ARX construction). As a result, we find 16 related-tweakey impossible differentials for 12-round SKINNY-64-128 based on which we construct an 18-round attack on SKINNY-64-128 (one target version for the crypto competition https://sites.google.com/site/skinnycipher announced at ASK 2016). Moreover, we show that in some cases, when equipped with proper strategies (ordering heuristic, restart and dynamic branching strategy), the CP approach can be very efficient. Therefore, we suggest that the constraint programming technique should become a convenient tool at hand of the symmetric-key cryptanalysts.

2010

EPRINT

On Exponential Sums, Nowton identities and Dickson Polynomials over Finite Fields
Abstract

Let $\mathbb{F}_{q}$ be a finite field, $\mathbb{F}_{q^s}$ be an extension of $\mathbb{F}_q$, let $f(x)\in \mathbb{F}_q[x]$ be a polynomial of degree $n$ with $\gcd(n,q)=1$. We present a recursive formula for evaluating the exponential sum $\sum_{c\in \mathbb{F}_{q^s}}\chi^{(s)}(f(x))$. Let $a$ and $b$ be two elements in $\mathbb{F}_q$ with $a\neq 0$, $u$ be a positive integer. We obtain an estimate of the exponential sum $\sum_{c\in \mathbb{F}^*_{q^s}}\chi^{(s)}(ac^u+bc^{-1})$, where $\chi^{(s)}$ is the lifting of an additive character $\chi$ of $\mathbb{F}_q$. Some properties of the sequences constructed from these exponential sums are provided also.

2010

EPRINT

Balanced Boolean Functions with (Almost) Optimal Algebraic Immunity and Very High Nonlinearity
Abstract

In this paper, we present a class of $2k$-variable balanced Boolean
functions and a class of $2k$-variable $1$-resilient Boolean functions for an integer $k\ge 2$, which both have the maximal algebraic degree and very high nonlinearity. Based on a newly proposed conjecture by Tu and Deng, it is shown that the proposed balanced Boolean functions have optimal algebraic immunity and the $1$-resilient Boolean functions have almost optimal algebraic immunity. Among all the known results of balanced Boolean
functions and $1$-resilient Boolean functions, our new functions possess the highest nonlinearity. Based on the fact that the conjecture has been verified for all $k\le 29$ by computer,
at least we have constructed a class of balanced Boolean functions and a class of $1$-resilient Boolean functions with the even number of variables $\le 58$, which are cryptographically optimal or almost
optimal in terms of balancedness, algebraic degree, nonlinearity, and algebraic immunity.

2007

EPRINT

Kipnis-Shamir's Attack on HFE Revisited
Abstract

In this paper, we show that the claims in the original
Kipnis-Shamir's attack on the HFE cryptosystems and the improved
attack by Courtois that the complexity of the attacks is polynomial
in terms of the number of variables are invalid. We present computer
experiments and a theoretical argument using basic algebraic
geometry to explain why it is so. Furthermore we show that even with
the help of the powerful new Gr\"{o}bner basis algorithm like $F_4$,
the Kipnis-Shamir's attack still should be exponential not
polynomial. This again is supported by our theoretical argument.

2007

EPRINT

FURTHER PROPERTIES OF SEVERAL CLASSES OF BOOLEAN FUNCTIONS WITH OPTIMUM ALGEBRAIC IMMUNITY
Abstract

Thanks to a method proposed by Carlet, several classes of balanced
Boolean functions with optimum algebraic immunity are obtained. By
choosing suitable parameters, for even $n\geq 8$, the balanced
$n$-variable functions can have nonlinearity
$2^{n-1}-{n-1\choose\frac{n}{2}-1}+2{n-2\choose\frac{n}{2}-2}/(n-2)$,
and for odd $n$, the functions can have nonlinearity
$2^{n-1}-{n-1\choose\frac{n-1}{2}}+\Delta(n)$, where the function
$\Delta(n)$ is describled in Theorem 4.4. The algebraic
degree of some constructed functions is also discussed.

2007

EPRINT

On The Inequivalence Of Ness-Helleseth APN Functions
Abstract

In this paper, the Ness-Helleseth functions over $F_{p^n}$ defined
by the form $f(x)=ux^{\frac{p^n-1}{2}-1}+x^{p^n-2}$ are proven to be
a new class of almost perfect nonlinear (APN) functions and they are
CCZ-inequivalent with all other known APN functions when $p\geq 7$.
The original method of Ness and Helleseth showing the functions are
APN for $p=3$ and odd $n\geq 3$ is also suitable for showing their
APN property for any prime $p\geq 7$ with $p\equiv 3\,({\rm
mod}\,4)$ and odd $n$.

2007

EPRINT

Cryptanalysis of Two New Instances of TTM Cryptosystem
Abstract

In 2006, Nie et al proposed an attack to break an instance of TTM
cryptosystems. However, the inventor of TTM disputed this attack and
he proposed two new instances of TTM to support his viewpoint. At
this time, he did not give the detail of key construction
--- the construction of the lock polynomials in these instances
which would be used in decryption. The two instances are claimed to
achieve a security of $2^{109}$ against Nie et al attack. In this
paper, we show that these instances are both still insecure, and in
fact, they do not achieve a better design in the sense that we can
find a ciphertext-only attack utilizing the First Order
Linearization Equations while for the previous version of TTM, only
Second Order Linearization Equations can be used in the beginning
stage of the previous attack. Different from previous attacks, we
use an iterated linearization method to break these two instances.
For any given valid ciphertext, we can find its corresponding
plaintext within $2^{31}$ $\mathbb{F}_{2^8}$-computations after
performing once for any public key a computation of complexity less
than $2^{44}$. Our experiment result shows we have unlocked the lock
polynomials after several iterations, though we do not know the
detailed construction of lock polynomials.

2006

EPRINT

Note on Design Criteria for Rainbow-Type Multivariates
Abstract

This was a short note that deals with the design of Rainbow or
``stagewise unbalanced oil-and-vinegar'' multivariate signature
schemes. We exhibit new cryptanalysis for current schemes that
relates to flawed choices of system parameters in current schemes.
These can be ameliorated according to an updated list of security
design criteria.

2006

EPRINT

High Order Linearization Equation (HOLE) Attack on Multivariate Public Key Cryptosystems
Abstract

In the CT-track of the 2006 RSA conference, a new multivariate
public key cryptosystem, which is called the Medium Field Equation
(MFE) multivariate public key cryptosystem, is proposed by Wang,
Yang, Hu and Lai. We use the second order linearization equation
attack method by Patarin to break MFE. Given a ciphertext, we can
derive the plaintext within $2^{23}$ $\F_{2^{16}}$-operations,
after performing once for any public key a computation of
complexity less than $2^{52}$. We also propose a high order
linearization equation (HOLE) attack on multivariate public key
cryptosystems, which is a further generalization of the (first and
second order) linearization equation (LE). This method can be used
to attack extensions of the current MFE.

#### Coauthors

- Xiwang Cao (1)
- Claude Carlet (1)
- Jiun-Ming Chen (1)
- Patrick Derbez (1)
- Jintai Ding (5)
- Xiaoyang Dong (1)
- Kai Fu (2)
- Fei Gao (1)
- David Gerault (1)
- Yinghua Guo (1)
- Hao Guo (1)
- Xin Jiang (2)
- Wenfeng Jiang (1)
- Pascal Lafourcade (1)
- Jianyu Li (2)
- Chaoyun Li (3)
- Chunlei Li (1)
- Shun Li (2)
- Xiaoshuang Ma (2)
- Xuyun Nie (3)
- Yanbin Pan (1)
- Kexin Qiao (4)
- Xianrui Qin (1)
- Santanu Sarkar (1)
- Yu Sasaki (1)
- Danping Shi (7)
- Ling Song (5)
- Bing Sun (1)
- Ling Sun (1)
- Siwei Sun (13)
- Yao Sun (1)
- Xiaohu Tang (1)
- Deng Tang (1)
- Yosuke Todo (2)
- John Wagner (2)
- Huaxiong Wang (1)
- Xiaoyun Wang (1)
- Peng Wang (2)
- Meiqin Wang (3)
- Zihao Wei (1)
- Jun Xu (1)
- Yang Yang (1)
- Qianqian Yang (2)
- Bo-Yin Yang (1)
- Xiangyong Zeng (3)