- Santanu Sarkar

###### Options

# Santanu Sarkar

Loading...

Preferred name

Santanu Sarkar

Official Name

Santanu Sarkar

Alternative Name

Sarkar, Santanu

Main Affiliation

Email

ORCID

Scopus Author ID

Google Scholar ID

43 results Back to results

### Filters

##### Date

##### Author

##### Organization

##### Subject

##### Has files

##### Type

### Settings

Sort By

Results per page

Now showing 1 - 10 of 43

- PublicationSOME RESULTS ON LIGHTWEIGHT STREAM CIPHERS FOUNTAIN V1 & LIZARD(01-04-2023)
;Anand, Ravi ;Roy, DibyenduShow more 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.Show more - PublicationLatin Dances Reloaded: Improved Cryptanalysis Against Salsa and ChaCha, and the Proposal of ForrÃ³(01-07-2023)
;Coutinho, Murilo ;Passos, Iago ;VÃ¡squez, Juan C.Grados; ;de MendonÃ§a, FÃ¡bio L.L. ;de Sousa, Rafael T.Borges, FÃ¡bioShow more 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 .Show more - PublicationOn acyclic edge-coloring of complete bipartite graphs(01-03-2017)
;Venkateswarlu, Ayineedi; Ananthanarayanan, Sai MaliShow more 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.Show more - PublicationExhaustive search for various types of MDS matrices(01-01-2019)
;Kesarwani, Abhishek; Venkateswarlu, AyineediShow more 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.Show more - PublicationConditional TMDTO as a MILP Instance(01-05-2023)
;Kumar, SatyamShow more 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.Show more - PublicationProving the biases of Salsa and ChaCha in differential attack(01-09-2020)
;Dey, SabyasachiShow more 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.Show more - PublicationRevisiting Cryptanalysis on ChaCha From Crypto 2020 and Eurocrypt 2021(01-09-2022)
;Dey, Sabyasachi ;Dey, Chandan; Meier, WilliShow more 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.Show more - PublicationDifferential fault location identification by machine learning(01-03-2021)
;Baksi, Anubhab; ;Siddhanti, Akhilesh ;Anand, RaviChattopadhyay, AnupamShow more 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.Show more - PublicationA New Approach for Side Channel Analysis on Stream Ciphers and Related Constructions(01-10-2022)
;Baksi, Anubhab ;Kumar, SatyamShow more 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).Show more - PublicationSome results on Fruit(15-03-2019)
;Dey, Sabyasachi ;Roy, TapabrataShow more In FSE 2015, Armknecht et al. proposed a new technique to design stream ciphers, which involves repeated use of keybits in each round of the keystream bit generation. This technique showed the possibility to design stream ciphers where the internal state size is significantly lower than twice the key size. They proposed a new cipher based on this idea, named Sprout. But soon Sprout was proved to be insecure. In Crypto 2015, Lallemand et al. proposed an attack which was 2 10 times faster than the exhaustive search. But the new idea used in Sprout showed a new direction in the design of stream cipher, which led to the proposal of several new ciphers with small size of internal state. Fruit is a recently proposed cipher where both the key size and the state size are 80. In this paper, we attack full round Fruit by a divide-and-conquer method. Our attack is equivalent to 2 74.95 many Fruit encryptions, which is around 16.95 times faster than the average exhaustive key search. Our idea also works for the second version of Fruit.Show more