Santanu Sarkar

In this paper, we propose cryptanalytic results on two lightweight stream ciphers: Fountain v1 and Lizard. The main results of this paper are the followings:-We propose a zero-sum distinguisher on reduced round Fountain v1. In this context, we study the non-randomness of the cipher with a careful selection of cube variables. Our obtained cube provides a zero-sum on Fountain v1 till 188 initialization rounds and significant non-randomness till 189 rounds. This results in a distinguishing attack on Fountain v1 with 189 initialization rounds.-Further, we find that the same cipher has a weakness against conditional Time-Memory-Data-Tradeoff (TMDTO). We show that TMDTO attack using sampling resistance has online complexity 2110 and offline complexity 2146.-Finally, we revisit the Time-Memory-Data-Tradeoff attack on Lizard by Maitra et al. (IEEE Transactions on Computers, 2018) and provide our observations on their work. We show that instead of choosing any random string, some particular strings would provide better results in their proposed attack technique.

In this paper, we present 4 major contributions to ARX ciphers and in particular, to the Salsa/ChaCha family of stream ciphers: (a)We propose an improved differential-linear distinguisher against ChaCha. To do so, we propose a new way to approach the derivation of linear approximations by viewing the algorithm in terms of simpler subrounds. Using this idea, we show that it is possible to derive almost all linear approximations from previous works from just 3 simple rules. Furthermore, we show that with one extra rule, it is possible to improve the linear approximations proposed by Coutinho and Souza at Eurocrypt 2021 (Coutinho and Neto, in: Canteaut, Standaert (eds) Advances in cryptology—EUROCRYPT 2021—40th annual international conference on the theory and applications of cryptographic techniques, Zagreb, Croatia, October 17–21, 2021, proceedings, Part I. Lecture notes in computer science, vol 12696, Springer, 2021).(b)We propose a technique called Bidirectional Linear Expansions (BLE) to improve attacks against Salsa. While previous works only considered linear expansions moving forward into the rounds, BLE explores the expansion of a single bit in both forward and backward directions. Applying BLE, we propose the first differential-linear distinguishers reaching 7 and 8 rounds of Salsa and we improve Probabilistic Neutral Bit (PNB) key-recovery attacks against 8 rounds of Salsa.(c)At Eurocrypt 2022 (Dey et al in Revamped differential-linear cryptanalysis on reduced round chacha, Springer, 2022), Dey et al. proposed a technique to combine two input–output positions in a PNB attack. In this paper, we generalize this technique for an arbitrary number of input–output positions. Combining this approach with BLE, we are able to improve key recovery attacks against 7 rounds of Salsa.(d)Using all the knowledge acquired studying the cryptanalysis of these ciphers, we propose some modifications in order to provide better diffusion per round and higher resistance to cryptanalysis, leading to a new stream cipher named Forró. We show that Forró has higher security margin; this allows us to reduce the total number of rounds while maintaining the security level, thus creating a faster cipher in many platforms, especially in constrained devices.(e)Finally, we developed CryptDances, a new tool for the cryptanalysis of Salsa, ChaCha, and Forró designed to be used in high performance environments with several GPUs. With CryptDances it is possible to compute differential correlations, to derive new linear approximations for ChaCha automatically, to automate the computation of the complexity of PNB attacks, among other features. We make CryptDances available for the community at https://github.com/murcoutinho/cryptDances .

Conditional Time-Memory-Data Trade-off (TMDTO) attack given by Biryukov and Shamir can be reduced to the following problem: 'Find the minimum number of state bits that should be fixed in order to recover the maximum number of state bits by utilizing the keystream bits and value of rest of the state bits'. As per our literature survey, existing algorithms search for state bits that should be fixed (as minimum as possible) in order to recover the maximum possible state bits directly through the keystream bits. However, those algorithms are cipher specific and require extensive manual effort in analyzing the keystream bit equations. In this manuscript, we have constructed an automated framework that is easy to implement and solves the above problem (for the case when bits are fixed to 0) for any NLFSR based stream cipher with better complexity, thereby reducing manual efforts. However, we do not claim any global optimum for fixed bits. We tried to reduce the number of fixed bits as much as possible. To show that our algorithm is applicable to a majority of NLFSR based stream ciphers, we implement it on three different stream ciphers: LIZARD, GRAIN-128a and ESPRESSO. It improves all existing TMDTO results on these ciphers. The framework involves modelling keystream bit equations into a set of linear constraints, which is then solved by using a Mixed Integer Linear Programming (MILP) solver, Gurobi. The advantages of our automated framework over other methods are that we can achieve better results with far less effort, and it can be applied to any stream cipher of a similar structure with very ease. To the best of our knowledge, our MILP model is the first work that converts the conditional TMDTO of a stream cipher into a linear optimization problem. As a consequence, for LIZARD cipher, we reduce the number of fixed bits by 20 bits from the previous best result when the number of recovered bits is 18. In the case of GRAIN-128a, the highest reduction in the number of fixed bits is by 34 bits when the number of recovered bits is 35. Lastly, for ESPRESSO cipher, the reduction is by 7 bits when the number of recovered bits is 35.

Salsa and ChaCha are two of the most famous stream ciphers in recent times. Most of the attacks available so far against these two ciphers are differential attacks, where a difference is given as an input in the initial state of the cipher and in the output some correlation is investigated. This correlation works as a distinguisher. All the key recovery attacks against these ciphers are based on these observed distinguishers. However, the distinguisher in the differential attack was purely an experimental observation, and the reason for this bias was unknown so far. In this paper, we provide a full theoretical proof of both the observed distinguishers for Salsa and ChaCha. In the key recovery attack, the idea of probabilistically neutral bit also plays a vital role. Here, we also theoretically explain the reason of a particular key bit of Salsa to be probabilistically neutral. This is the first attempt to provide a theoretical justification of the idea of differential key recovery attack against these two ciphers.

ChaCha has been one of the most prominent ARX designs of the last few years because of its use in several systems. The cryptanalysis of ChaCha involves a differential attack that exploits the idea of Probabilistic Neutral Bits (PNBs). For a long period, the single-bit distinguisher in this differential attack was found up to 3rd round. At Crypto 2020, Beierle et al. introduced for the first time the single bit distinguishers for 3.5th round, which contributed significantly to regaining the flow of the research work in this direction. This discovery became the primary factor behind the huge improvement in the key recovery attack complexity in that work. This was followed by another work at Eurocrypt 2021, where a single bit distinguisher at 3.5th round helped to produce a 7th round distinguisher of ChaCha and a further improvement in the key recovery. In this paper, first, we provide the theoretical framework for the distinguisher given by Beierle et al. We mathematically derive the observed differential correlation for the particular position where the output difference is observed at 3.5th round. Also, Beierle et al. mentioned the issue of the availability of proper IVs to produce such distinguishers, and pointed out that not all keys have such IVs available. Here we provide a theoretical insight of this issue. Next, we revisit the work of Coutinho et al. (Eurocrypt 2021). Using Differential-Linear attacks against ChaCha, they claimed the distinguisher and the key recovery with complexities 2218 and $2^{228.51}$ respectively. We show that the differential correlation for the 3.5th round is much smaller than the claim of Coutinho et al. This makes the attack complexities much higher than their claim.

As the fault-based attacks are becoming a more pertinent threat in today's era of edge computing/internet-of-things, there is a need to streamline the existing tools for better accuracy and ease of use, so that we can gauge the attacker's power and a proper countermeasure can be devised in the long run. In this regard, we propose a machine learning (ML) assisted tool that can be used in the context of a differential fault attack. In particular, finding the exact fault location by analysing the output difference (typically the XOR of the nonfaulty and the faulty ciphertexts) is somewhat nontrivial. During the literature survey, we notice that the Pearson's correlation coefficient dominantly is used for this purpose, and has almost become the defacto standard. While this method can yield good accuracy for certain cases, we argue that an ML-based method is more powerful in all the situations we experiment with. We substantiate our claim by showing the relative performances (we choose the commonly used multilayer perceptron as our ML tool) with two variants of Grain-128a (a stream cipher, and a stream cipher with authentication), the lightweight stream cipher LIZARD and the lightweight block cipher SIMON-32 (where the faults are injected at the fifth last rounds). Our results demonstrate that a common ML tool can outperform the correlation with the same training/testing data. We believe that our work extends the state-of-the-art by showing how traditional cryptographic methods can be replaced by a more powerful ML tool.

Side Channel Analysis (SCA) is among the newly emerged threats to small scale devices performing a cryptographic operation. While such analysis is well studied against the block ciphers, we observe that the stream cipher counterpart is not that much explored. We propose novel modelling that can work with a number of stream ciphers and related constructions. We show practical state/key recovery attacks on the lightweight ciphers, LIZARD, PLANTLET and GRAIN-128-AEAD. We consider the software platform (where the Hamming weight leakage is available) as well as the hardware platform (where the Hamming distance leakage is available). Through the modelling of Satisfiability Modulo Theory (SMT), we show that the solution can be obtained in a matter of seconds in most cases. In a handful of cases, however, the entire state/key recovery is not feasible in a practical amount of time. For those cases, we show full recovery is possible when a small number of bits are guessed. We also study the effect of increasing/decreasing the number of keystream bits on the solution time. Following a number of literature, we initially assume the traces that are obtained are noiseless. Later, we show how an extension of our model can deal with the noisy traces (which is a more general assumption).

Rasta and Dasta are two fully homomorphic encryption friendly symmetric-key primitives proposed at CRYPTO 2018 and ToSC 2020, respectively. It can be found from the designers’ analysis that the security of the two ciphers highly relies on the high algebraic degree of the inverse of the n-bit χ operation denoted by χn-1, while surprisingly the explicit formula of χn-1 has never been given in the literature. As the first contribution, for the first time, we give a very simple formula of χn-1 that can be written down in only one line and we prove its correctness in a rigorous way. Based on this formula of χn-1, an obvious yet important weakness of the two ciphers can be identified, which shows that their security against the algebraic attack cannot be solely based on the high degree of χn-1. Specifically, this weakness enables us to theoretically break two out of three 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 because of 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.

The security of the post-quantum signature scheme Picnic is highly related to the difficulty of recovering the secret key of LowMC from a single plaintext-ciphertext pair. Since Picnic is one of the alternate third-round candidates in NIST post-quantum cryptography standardization process, it has become urgent and important to evaluate the security of LowMC in the Picnic setting. The best attacks on LowMC with full S-box layers used in Picnic3 were achieved with Dinur’s algorithm. For LowMC with partial nonlinear layers, e.g. 10 S-boxes per round adopted in Picnic2, the best attacks on LowMC were published by Banik et al. with the meet-in-the-middle (MITM) method. In this paper, we improve the attacks on LowMC in a model where memory consumption is costly. First, a new attack on 3-round LowMC with full S-box layers with negligible memory complexity is found, which can outperform Bouillaguet et al.’s fast exhaustive search attack and can achieve better time-memory tradeoffs than Dinur’s algorithm. Second, we extend the 3-round attack to 4 rounds to significantly reduce the memory complexity of Dinur’s algorithm at the sacrifice of a small factor of time complexity. For LowMC instances with 1 S-box per round, our attacks are shown to be much faster than the MITM attacks. For LowMC instances with 10 S-boxes per round, we can reduce the memory complexity from 32GB (238 bits) to only 256KB (221 bits) using our new algebraic attacks rather than the MITM attacks, while the time complexity of our attacks is about 23.2 ∼ 25 times higher than that of the MITM attacks. A notable feature of our new attacks (apart from the 4-round attack) is their simplicity. Specifically, only some basic linear algebra is required to understand them and they can be easily implemented.

Though generating a sequence of pseudorandom numbers by linear methods (Lehmer generator) displays acceptable behavior under some conditions of the parameters, it also has undesirable features, which makes the sequence unusable for various stochastic simulations. An extension which showed promise for such applications is a generator obtained by using a first-order recurrence based upon the inverse modulo a prime or a prime power, called inversive congruential generator (ICG). A lot of work has been dedicated to investigate the periods (under some conditions of the parameters), the lattice test passing, discrepancy and other statistical properties of such a generator. Here, we propose a new method, which we call hybrid inversive congruential generator (HICG), based upon a second order recurrence using the inverse modulo M, a power of 2. We investigate the period of this pseudorandom numbers generator (PRNG) and give necessary and sufficient conditions for our PRNG to have periods M (thereby doubling the period of the classical ICG) and M=2 (matching the one of the ICG). Moreover, we show that the lattice test complexity for a binary sequence associated to (a full period) HICG is precisely M=2.