International Association
for Cryptologic Research

Lattice reduction algorithms have been proved to be one of the most powerful and versatile tools in public key cryptanalysis. In this work, we primarily concentrate on lattice attacks against (EC)DSA with nonce leakage via some sidechannel analysis. Previous works relying on lattice reduction algorithms such as LLL and BKZ will finally lead to the “lattice barrier”: lattice algorithms become infeasible when only fewer nonce is known. Recently, Albrecht and Heninger introduced lattice algorithms augmented with a predicate and broke the lattice barrier (Eurocrypt 2021). We improve their work in several aspects.We first propose a more efficient predicate algorithm which aims to search for the target lattice vector in a large database. Then, we combine sieving with predicate algorithm with the “dimensions for free” and “progressive sieving” techniques to further improve the performance of our attacks. Furthermore, we give a theoretic analysis on how to choose the optimal Kannan embedding factor.As a result, our algorithm outperforms the state-of-the-art lattice attacks for existing records such as 3-bit nonce leakage for a 256-bit curve and 2-bit nonce leakage for a 160-bit curve in terms of running time, sample numbers and success probability. We also break the lattice records on the 384-bit curve with 3-bit nonce leakage and the 256-bit curve with 2-bit nonce leakage which are thought infeasible previously. Finally, we give the first lattice attack against ECDSA with a single-bit nonce leakage, which enables us to break a 112-bit curve with 1-bit nonce leakage in practical time.

In this paper, we improve the cube attack by exploiting low-degree factors of the superpoly w.r.t. certain \textit{"special" } index set of cube (\textit{ISoC}). This can be viewed as a special case of the correlation cube attack proposed at Eurocrypt 2018, but under our framework more beneficial equations on the key variables can be obtained in the key-recovery phase. To mount our attack, one has two challenging problems: (1) effectively recover algebraic normal form of the superpoly and extract out its low-degree factors; and (2) efficiently search a large quantity of good \textit{ISoC}s. We bring in new techniques to solve both of them. First, we propose the \textit{variable substitution technique} for middle rounds of a cipher, in which polynomials on the key variables in the algebraic expressions of internal states are substituted by new variables. This will improve computational complexity of the superpoly recovery and promise more compact superpolys that can be easily decomposed with respect to the new variables. Second, we propose the \textit{vector numeric mapping technique}, which seeks out a tradeoff between efficiency of the numeric mapping technique (Crypto 2019) and accuracy of the monomial prediction technique (Asiacrypt 2020) in degree evaluation of superpolys. Combining with this technique, a fast pruning method is given and modeled by MILP to filter good \textit{ISoC}s of which the algebraic degree satisfies some fixed threshold. Thanks to automated MILP solvers, it becomes practical to comprehensively search for good cubes across the entire search space. To illustrate the power of our techniques, we apply all of them to Trivium stream cipher. As a result, we have recovered the superpolys of three cubes given by Kesarwani et al. in 2020, only to find they do not have \texttt{zero-sum} property up to 842 rounds as claimed in their paper. To our knowledge, the previous best practical key recovery attack was on 820-round Trivium with complexity $2^{53.17}$. We put forward 820-, 825- and 830-round practical key-recovery attacks, in which there are $\mathbf{2^{80}\times 87.8\%}$, $\mathbf{2^{80}\times 83\%}$ and $\mathbf{2^{80}\times 65.7\%}$ keys that could be practically recovered, respectively, if we consider $\mathbf{2^{60}}$ as the upper bound for practical computational complexity. Besides, even for computers with computational power not exceeding $\mathbf{2^{52}}$ (resp. $\mathbf{2^{55}}$), we can still recover $\mathbf{58\%}$ (resp. $\mathbf{46.6\%}$) of the keys in the key space for 820 rounds (resp. 830 rounds). Our attacks have led 10 rounds more than the previous best practical attack. \keywords{Correlation cube attack \and Variable substitution \and Vector numeric mapping \and MILP \and Trivium.}

Many block ciphers use permutations defined over the finite field F22k with low differential uniformity, high nonlinearity, and high algebraic degree to provide confusion. Due to the lack of knowledge about the existence of almost perfect nonlinear (APN) permutations over F22k, which have lowest possible differential uniformity, when k > 3, constructions of differentially 4-uniform permutations are usually considered. However, it is also very difficult to construct such permutations together with high nonlinearity; there are very few known families of such functions, which can have the best known nonlinearity and a high algebraic degree. At Crypto’16, Perrin et al. introduced a structure named butterfly, which leads to permutations over F22k with differential uniformity at most 4 and very high algebraic degree when k is odd. It is posed as an open problem in Perrin et al.’s paper and solved by Canteaut et al. that the nonlinearity is equal to 22k−1−2k. In this paper, we extend Perrin et al.’s work and study the functions constructed from butterflies with exponent e = 2i + 1. It turns out that these functions over F22k with odd k have differential uniformity at most 4 and algebraic degree k +1. Moreover, we prove that for any integer i and odd k such that gcd(i, k) = 1, the nonlinearity equality holds, which also gives another solution to the open problem proposed by Perrin et al. This greatly expands the list of differentially 4-uniform permutations with good nonlinearity and hence provides more candidates for the design of block ciphers.