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 .

Tiaoxin and AEGIS are two second round candidates of the ongoing CAESAR competition for authenticated encryption. In 2014, Brice Minaud proposed a distinguisher for AEGIS-256 that can be used to recover bits of a partially known message, encrypted 2188 times, regardless of the keys used. Also he reported a correlation between AEGIS-128 ciphertexts at rounds i and i + 2, although the biases would require 2140 data to be detected. Apart from that, to the best of our knowledge, there is no known cryptanalysis of AEGIS or Tiaoxin. In this paper we propose differential fault analyses of Tiaoxin and AEGIS family of ciphers in a nonce reuse setting. Analysis shows that the secret key of Tiaoxin can be recovered with 384 single bit faults and the states of AEGIS-128, AEGIS-256 and AEGIS-128L can be recovered respectively with 384, 512 and 512 single bit faults. Considering multi byte fault, the number of required faults and re-keying reduces 128 times.

An acyclic edge-coloring of a graph is a proper edge-coloring without bichromatic (2-colored) cycles. The acyclic chromatic index of a graph G, denoted by a′(G), is the least integer k such that G admits an acyclic edge-coloring using k colors. Let Δ=Δ(G) denote the maximum degree of a vertex in a graph G. A complete bipartite graph with n vertices on each side is denoted by Kn,n. Basavaraju, Chandran and Kummini proved that a′(Kn,n)≥n+2=Δ+2 when n is odd. Basavaraju and Chandran provided an acyclic edge-coloring of Kp,p using p+2 colors and thus establishing a′(Kp,p)=p+2=Δ+2 when p is an odd prime. The main tool in their approach is perfect 1-factorization of Kp,p. Recently, following their approach, Venkateswarlu and Sarkar have shown that K2p−1,2p−1 admits an acyclic edge-coloring using 2p+1 colors which implies that a′(K2p−1,2p−1)=2p+1=Δ+2, where p is an odd prime. In this paper, we generalize this approach and present a general framework to possibly get an acyclic edge-coloring of Kn,n which possesses a perfect 1-factorization using n+2=Δ+2 colors. In this general framework, using number theoretic techniques, we show that Kp2,p2 admits an acyclic edge-coloring with p2+2 colors and thus establishing a′(Kp2,p2)=p2+2=Δ+2 when p is an odd prime.

MDS matrices are used in the design of diffusion layers in many block ciphers and hash functions due to their optimal branch number. But MDS matrices, in general, have costly implementations. So in search for efficiently implementable MDS matrices, there have been many proposals. In particular, circulant, Hadamard, and recursive MDS matrices from companion matrices have been widely studied. In a recent work, recursive MDS matrices from sparse DSI matrices are studied, which are of interest due to their low fixed cost in hardware implementation. In this paper, we present results on the exhaustive search for (recursive) MDS matrices over GL(4, F2). Specifically, circulant MDS matrices of order 4, 5, 6, 7, 8; Hadamard MDS matrices of order 4, 8; recursive MDS matrices from companion matrices of order 4; recursive MDS matrices from sparse DSI matrices of order 4, 5, 6, 7, 8 are considered. It is to be noted that the exhaustive search is impractical with a naive approach. We first use some linear algebra tools to restrict the search to a smaller domain and then apply some space-time trade-off techniques to get the solutions. From the set of solutions in the restricted domain, one can easily generate all the solutions in the full domain. From the experimental results, we can see the (non) existence of (involutory) MDS matrices for the choices mentioned above. In particular, over GL(4, F2), we provide companion matrices of order 4 that yield involutory MDS matrices, circulant MDS matrices of order 8, and establish the nonexistence of involutory circulant MDS matrices of order 6, 8, circulant MDS matrices of order 7, sparse DSI matrices of order 4 that yield involutory MDS matrices, and sparse DSI matrices of order 5, 6, 7, 8 that yield MDS matrices. To the best of our knowledge, these results were not known before. For the choices mentioned above, if such MDS matrices exist, we provide base sets of MDS matrices, from which all the MDS matrices with the least cost (with respect to d-XOR and s-XOR counts) can be obtained. We also take this opportunity to present some results on the search for sparse DSI matrices over finite fields that yield MDS matrices. We establish that there is no sparse DSI matrix S of order 8 over F<>2<>8 such that S<>8<> is MDS.

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.

In this paper, we consider well known 'coverage problem' in Wireless Sensor Networks (WSNs) in continuous domain. Here, we discuss optimal placement of sensors and coverage criteria in Rn with special emphasis on R2. Coverage is essential in WSNs, which are two-or three-dimensional systems. When sensors are deployed from air on some previously fixed points (vertices) in the Region of Interest (ROI), they may not fall on the target vertices. So, some part of the ROI may be uncovered by the sensors. In this paper, we consider the problem, how one reduced the uncovered area? To reduce the uncovered area, extra sensors are usually deployed on some randomly chosen vertices. We develop a new strategy for deployment of extra sensors and compare the uncovered areas for these two strategies and for different number of extra sensors, using simulation.

In this paper, we analyze the security of two variants of the RSA public key cryptosystem where multiple encryption and decryption exponents are used with a common modulus. For the most well known variant, CRT-RSA, assume that n encryption and decryption exponents (el, dpl, dql), where l = 1, …, n, are used with a common CRT-RSA modulus N. By utilizing a Minkowski sum based lattice construction and combining several modular equations which share a common variable, we prove that one can factor N when (Formula presented) for all l = 1, …, n. We further improve this bound to (Formula presented) for all l = 1, …, n. Moreover, our experiments do better than previous works by Jochemsz-May (Crypto 2007) and Herrmann-May (PKC 2010) when multiple exponents are used. For Takagi’s variant of RSA, assume that n key pairs (el, dl) for l = 1, …, n are available for a common modulus N = prq where r ≥ 2. By solving several simultaneous modular univariate linear equations, we show that when (Formula presented), for all l = 1, …, n, one can factor the common modulus N.