Santanu Sarkar

Rasta and Dasta are two fully homomorphic encryption friendly symmetric-key primitives proposed at CRYPTO 2018 and ToSC 2020, respectively. We point out that the designers of Rasta and Dasta neglected an important property of the χ operation. Combined with the special structure of Rasta and Dasta, this property directly leads to significantly improved algebraic cryptanalysis. Especially, it enables us to theoretically break 2 out of 3 instances of full Agrasta, which is the aggressive version of Rasta with the block size only slightly larger than the security level in bits. We further reveal that Dasta is more vulnerable against our attacks than Rasta for its usage of a linear layer composed of an ever-changing bit permutation and a deterministic linear transform. Based on our cryptanalysis, the security margins of Dasta and Rasta parameterized with (n, κ, r) ∈ { (327, 80, 4 ), (1877, 128, 4 ), (3545, 256, 5 ) } are reduced to only 1 round, where n, κ and r denote the block size, the claimed security level and the number of rounds, respectively. These parameters are of particular interest as the corresponding ANDdepth is the lowest among those that can be implemented in reasonable time and target the same claimed security level.

In this paper, we provide several improvements over the existing differential-linear attacks on ChaCha. ChaCha is a stream cipher which has 20 rounds. At CRYPTO 2020, Beierle et al. observed a differential in the 3.5-th round if the right pairs are chosen. They produced an improved attack using this, but showed that to achieve a right pair, we need 2 5 iterations on average. In this direction, we provide a technique to find the right pairs with the help of listing. Also, we provide a strategical improvement in PNB construction, modification of complexity calculation and an alternative attack method using two input-output pairs. Using these, we improve the time complexity, reducing it to 2 221.95 from 2 230.86 reported by Beierle et al. for 256 bit version of ChaCha. Also, after a decade, we improve existing complexity (Shi et al. ICISC 2012) for a 6-round of 128 bit version of ChaCha by more than 11 million times and produce the first-ever attack on 6.5-round ChaCha128 with time complexity 2 123.04.

The hash function RIPEMD-160 is an ISO/IEC standard and is being used to generate the bitcoin address together with SHA-256. Despite the fact that many hash functions in the MD-SHA hash family have been broken, RIPEMD-160 remains secure and the best collision attack could only reach up to 34 out of 80 rounds, which was published at CRYPTO 2019. In this paper, we propose a new collision attack on RIPEMD-160 that can reach up to 36 rounds with time complexity 2 64.5. This new attack is facilitated by a new strategy to choose the message differences and new techniques to simultaneously handle the differential conditions on both branches. Moreover, different from all the previous work on RIPEMD-160, we utilize a MILP-based method to search for differential characteristics, where we construct a model to accurately describe the signed difference transitions through its round function. As far as we know, this is the first model targeting the signed difference transitions for the MD-SHA hash family. Indeed, we are more motivated to design this model by the fact that many automatic tools to search for such differential characteristics are not publicly available and implementing them from scratch is too time-consuming and difficult. Hence, we expect that this can be an alternative easy tool for future research, which only requires to write down some simple linear inequalities.

Let (N, e) be an RSA public key, where N= pq is the product of equal bitsize primes p, q. Let dp, dq be the corresponding secret CRT-RSA exponents. Using a Coppersmith-type attack, Takayasu, Lu and Peng (TLP) recently showed that one obtains the factorization of N in polynomial time, provided that dp, dq≤ N0.122. Building on the TLP attack, we show the first Partial Key Exposure attack on short secret exponent CRT-RSA. Namely, let N0.122≤ dp, dq≤ N0.5. Then we show that a constant known fraction of the least significant bits (LSBs) of both dp, dq suffices to factor N in polynomial time. Naturally, the larger dp, dq, the more LSBs are required. E.g. if dp, dq are of size N0.13, then we have to know roughly a 15 -fraction of their LSBs, whereas for dp, dq of size N0.2 we require already knowledge of a 23 -LSB fraction. Eventually, if dp, dq are of full size N0.5, we have to know all of their bits. Notice that as a side-product of our result we obtain a heuristic deterministic polynomial time factorization algorithm on input (N, e, dp, dq).

SPEEDY is a family of ultra low latency block ciphers proposed by Leander, Moos, Moradi and Rasoolzadeh at TCHES 2021. Although the designers gave some differential/linear distinguishers for reduced rounds, a concrete cryptanalysis considering key recovery attacks on SPEEDY was completely missing. The latter is crucial to understand the security margin of designs like SPEEDY which typically use low number of rounds to have low latency. In this work, we present the first third-party cryptanalysis of SPEEDY-r-192, where r∈ { 5, 6, 7 } is the number of rounds and 192 is block and key size in bits. We identify cube distinguishers for 2 rounds with data complexities 2 14 and 2 13, while the differential/linear distinguishers provided by designers has a complexity of 2 39. Notably, we show that there are several such cube distinguishers, and thus, we then provide a generic description of them. We also investigate the structural properties of 13-dimensional cubes and give experimental evidence that the partial algebraic normal form of certain state bits after two rounds is always the same. Next, we utilize the 2 rounds distinguishers to mount a key recovery attack on 3 rounds SPEEDY. Our attack require 2 17.6 data, 2 25.5 bits of memory and 2 52.5 time. Our results show that the practical variant of SPEEDY, i.e., SPEEDY-5-192 has a security margin of only 2 rounds. We believe our work will bring new insights in understanding the security of SPEEDY.

We address Partial Key Exposure attacks on CRT-RSA on secret exponents dp, dq with small public exponent e. For constant e it is known that the knowledge of half of the bits of one of dp, dq suffices to factor the RSA modulus N by Coppersmith’s famous factoring with a hint result. We extend this setting to non-constant e. Somewhat surprisingly, our attack shows that RSA with e of size N112 is most vulnerable to Partial Key Exposure, since in this case only a third of the bits of both dp, dq suffices to factor N in polynomial time, knowing either most significant bits (MSB) or least significant bits (LSB). Let edp= 1 + k(p- 1 ) and edq= 1 + ℓ(q- 1 ). On the technical side, we find the factorization of N in a novel two-step approach. In a first step we recover k and ℓ in polynomial time, in the MSB case completely elementary and in the LSB case using Coppersmith’s lattice-based method. We then obtain the prime factorization of N by computing the root of a univariate polynomial modulo kp for our known k. This can be seen as an extension of Howgrave-Graham’s approximate divisor algorithm to the case of approximate divisor multiples for some known multiple k of an unknown divisor p of N. The point of approximate divisor multiples is that the unknown that is recoverable in polynomial time grows linearly with the size of the multiple k. Our resulting Partial Key Exposure attack with known MSBs is completely rigorous, whereas in the LSB case we rely on a standard Coppersmith-type heuristic. We experimentally verify our heuristic, thereby showing that in practice we reach our asymptotic bounds already using small lattice dimensions. Thus, our attack is highly efficient.

By exploiting the feature of partial nonlinear layers, we propose a new technique called algebraic meet-in-the-middle (MITM) attack to analyze the security of LowMC, which can reduce the memory complexity of the simple difference enumeration attack over the state-of-the-art. Moreover, while an efficient algebraic technique to retrieve the full key from a differential trail of LowMC has been proposed at CRYPTO 2021, its time complexity is still exponential in the key size. In this work, we show how to reduce it to constant time when there are a sufficiently large number of active S-boxes in the trail. With the above new techniques, the attacks on LowMC and LowMC-M published at CRYPTO 2021 are further improved, and some LowMC instances could be broken for the first time. Our results seem to indicate that partial nonlinear layers are still not well-understood.

Elliptic Curve Hidden Number Problem (EC-HNP) was first introduced by Boneh, Halevi and Howgrave-Graham at Asiacrypt 2001. To rigorously assess the bit security of the Diffie–Hellman key exchange with elliptic curves (ECDH), the Diffie–Hellman variant of EC-HNP, regarded as an elliptic curve analogy of the Hidden Number Problem (HNP), was presented at PKC 2017. This variant can also be used for practical cryptanalysis of ECDH key exchange in the situation of side-channel attacks. In this paper, we revisit the Coppersmith method for solving the involved modular multivariate polynomials in the Diffie–Hellman variant of EC-HNP and demonstrate that, for any given positive integer d, a given sufficiently large prime p, and a fixed elliptic curve over the prime field Fp, if there is an oracle that outputs about 1d+1 of the most (least) significant bits of the x-coordinate of the ECDH key, then one can give a heuristic algorithm to compute all the bits within polynomial time in log 2p. When d> 1, the heuristic result 1d+1 significantly outperforms both the rigorous bound 56 and heuristic bound 12. Due to the heuristics involved in the Coppersmith method, we do not get the ECDH bit security on a fixed curve. However, we experimentally verify the effectiveness of the heuristics on NIST curves for small dimension lattices.