IIT Madras is a public technical and research university located in Chennai, Tamil Nadu. Founded in 1959, it is recognised as an Institute of National Importance.

IIT Madras has been ranked as the top engineering institute in India for four years in a row by the National Institutional Ranking Framework of the MHRD

It currently offers undergraduate, postgraduate and research degrees across 16 disciplines in Engineering, Sciences, Humanities and Management. About 596 faculty belonging to science and engineering departments and centres of the Institute are engaged in teaching, research and industrial consultancy.

IIT Madras

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. © 2020 New York Business Global. All rights reserved.

World University root node

Department of Mathematics

Fulltext

European Journal of Pure and Applied Mathematics

A hybrid inversive congruential pseudorandom number generator with high period

It has been common knowledge that for a stream cipher to be secure against generic TMD tradeoff attacks, the size of its internal state in bits needs to be at least twice the size of the length of its secret key. In FSE 2015, Armknecht and Mikhalev however proposed the stream cipher Sprout with a Grain-like architecture, whose internal state was equal in size with its secret key and yet resistant against TMD attacks. Although Sprout had other weaknesses, it germinated a sequence of stream cipher designs like Lizard and Plantlet with short internal states. Both these designs have had cryptanalytic results reported against them. In this paper, we propose the stream cipher Atom that has an internal state of 159 bits and offers a security of 128 bits. Atom uses two key filters simultaneously to thwart certain cryptanalytic attacks that have been recently reported against keystream generators. In addition, we found that our design is one of the smallest stream ciphers that offers this security level, and we prove in this paper that Atom resists all the attacks that have been proposed against stream ciphers so far in literature. On the face of it, Atom also builds on the basic structure of the Grain family of stream ciphers. However, we try to prove that by including the additional key filter in the architecture of Atom we can make it immune to all cryptanalytic advances proposed against stream ciphers in recent cryptographic literature. © 2021, Ruhr-Universitat Bochum. All rights reserved.

IACR Transactions on Symmetric Cryptology

Atom: A stream cipher with double key filter

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. © 2021 The Authors. CAAI Transactions on Intelligence Technology published by John Wiley & Sons Ltd on behalf of The Institution of Engineering and Technology and Chongqing University of Technology.

CAAI Transactions on Intelligence Technology

Differential fault location identification by machine learning

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. © 2020, Springer Science+Business Media, LLC, part of Springer Nature.

Designs, Codes, and Cryptography

Proving the biases of Salsa and ChaCha in differential attack

In this paper, we revisit the work of Sarkar et al. (Des Codes Cryptogr 82(1–2):351–375, 2017) and Liu (Advances in cryptology—Crypto 2017, 2017) and show how both of their ideas can be tuned to find good cubes. Here we propose a new algorithm for cube generation which improves existing results on Zero- Sum distinguisher. We apply our new cube finding algorithm to three different nonlinear feedback shift register (NFSR) based stream ciphers Trivium, Kreyvium and ACORN. From the results, we can see a cube of size 39, which gives Zero- Sum for maximum 842 rounds and a significant non-randomness up to 850 rounds of Trivium. We provide some small size good cubes for Trivium, which outperform existing ones. We further investigate Kreyvium and ACORN by a similar technique and obtain cubes of size 56 and 92 which give Zero- Sum distinguisher till 875 and 738 initialization rounds of Kreyvium and ACORN respectively. To the best of our knowledge, these results are best results as compared to the existing results on distinguishing attacks of these ciphers. We also provide a table of good cubes of sizes varying from 10 to 40 for these three ciphers. © 2019, Springer Science+Business Media, LLC, part of Springer Nature.

New cube distinguishers on NFSR-based stream ciphers

In PKC 2017, the elliptic curve hidden number problem (EC-HNP) was revisited in order to rigorously assess the bit security of the elliptic curve Diffie–Hellman key exchange protocol. In this paper, we solve EC-HNP by using the Coppersmith technique which combines the idea behind the second lattice method of Boneh, Halevi and Howgrave-Graham for solving the modular inversion hidden number problem. We show that the hidden point in EC-HNP can be recovered asymptotically if about half of the most significant bits of the x-coordinates of the corresponding points are given. A similar result is also obtained for the least significant bits. We provide better bounds than the one in the work of PKC 2017, which needs about 5/6 of the bits as a result of a rigorous algorithm. However, our solution is based on a heuristic assumption. We verify the validity of our heuristic algorithm by computer experiments. © 2019, Springer Science+Business Media, LLC, part of Springer Nature.

Cryptanalysis of elliptic curve hidden number problem from PKC 2017

The Modular Inversion Hidden Number Problem (MIHNP), introduced by Boneh, Halevi and Howgrave-Graham in Asiacrypt 2001, is briefly described as follows: Let$${\mathrm {MSB}}_{\delta }(z)$$ refer to the$$\delta $$ most significant bits of z. Given many samples$$\left(t_{i}, {\mathrm {MSB}}_{\delta }((\alpha + t_{i})^{-1} \bmod {p})\right) $$ for random$$t:i \in \mathbb {Z}_p$$, the goal is to recover the hidden number$$\alpha \in \mathbb {Z}_p$$. MIHNP is an important class of Hidden Number Problem. In this paper, we revisit the Coppersmith technique for solving a class of modular polynomial equations, which is respectively derived from the recovering problem of the hidden number$$\alpha $$ in MIHNP. For any positive integer constant d, let integer$$n=d^{3+o(1)}$$. Given a sufficiently large modulus p,$$n+1$$ samples of MIHNP, we present a heuristic algorithm to recover the hidden number$$\alpha $$ with a probability close to 1 when$$\delta /\log _2 p>\frac{1}{d\,+\,1}+o(\frac{1}{d})$$. The overall time complexity of attack is polynomial in$$\log _2 p$$, where the complexity of the LLL algorithm grows as$$d^{\mathcal {O}(d)}$$ and the complexity of the Gröbner basis computation grows as$$(2d)^{\mathcal {O}(n^2)}$$. When$$d> 2$$, this asymptotic bound outperforms$$\delta /\log _2 p>\frac{1}{3}$$ which is the asymptotic bound proposed by Boneh, Halevi and Howgrave-Graham in Asiacrypt 2001. It is the first time that a better bound for solving MIHNP is given, which implies that the conjecture that MIHNP is hard whenever$$\delta /\log _2 p<\frac{1}{3}$$ is broken. Moreover, we also get the best result for attacking the Inversive Congruential Generator (ICG) up to now. © 2019, International Association for Cryptologic Research.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

New Results on Modular Inversion Hidden Number Problem and Inversive Congruential Generator

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. © 2019 IEEE.

2019 International Conference on Ubiquitous and Emerging Concepts on Sensors and Transducers, UEMCOS 2019

Coverage Problem of sensor network in Continuous Region

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. © 2018, Springer Science+Business Media, LLC, part of Springer Nature.

Some results on Fruit

Salsa and ChaCha are well known names in the family of stream ciphers. In this paper, we first revisit the existing attacks on these ciphers. We first perform an accurate computation of the attack complexities of the existing technique instead of the estimation used in previous works. This improves the complexity by some margin. The differential attacks using probabilistic neutral bits against ChaCha and Salsa involve two probability biases: Forward probability bias (ϵd) and backward probability bias (ϵa). In the second part of the paper, we suggest a method to increase the backward probability bias, which helps reduce the attack complexity. Finally, we focus on the design principle of ChaCha. We suggest a slight modification in the design of this cipher as a countermeasure of the differential attacks against it. We show that the key recovery attacks proposed against ChaCha will not be effective on this modified version. © 2019 AIMS.

Advances in Mathematics of Communications

Revisiting design principles of Salsa and Chacha

In this paper, using a matrix, at first we revisit the work of Mantin on finding the probability distribution of the RC4 permutation after the completion of the KSA. After that, we extend the same idea to analyse the probabilities during any iteration of the Pseudo Random Generation Algorithm. Next, we study the bias of Zr = r (where Zr is the r-th output keystream byte), which is one of the significant biases observed in the RC4 output keystream. This bias has played an important role in the plaintext recovery attack proposed by Isobe et al. in FSE 2013. However, the accurate theoretical explanation of the bias of Zr = r is still a mystery. Though several attempts have been made to prove this bias, none of those provides an accurate justification. Here, using the results found with the help of the probability transition matrix we justify this bias of Zr = r accurately and settle this issue. The bias obtained from our proof matches the experimental observations perfectly. © 2018, Springer Science+Business Media, LLC, part of Springer Nature.

Cryptography and Communications

Settling the mystery of Zr = r in RC4

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&lt;&gt;2&lt;&gt;8 such that S&lt;&gt;8&lt;&gt; is MDS. © 2019, Ruhr-Universitat Bochum. All rights reserved.

Exhaustive search for various types of MDS matrices

In this paper, we present a polynomial lattice method to solve the approximate polynomial common divisor problem. This problem is the polynomial version of the well known approximate integer common divisor problem introduced by Howgrave-Graham (Calc 2001). Our idea can be applied directly to solve the noisy multipolynomial reconstruction problem in the field of error-correcting codes. Compared to the method proposed by Devet, Goldberg and Heninger in USENIX 2012, our approach is faster. © 2019, Springer Nature Switzerland AG.

Revisiting Approximate Polynomial Common Divisor Problem and Noisy Multipolynomial Reconstruction

In this paper, we study TRIAD-AE, which is submitted in the on-going NIST Lightweight competition. We first estimate an upper bound of the algebraic degree of internal state and key-stream bit seen as multivariate Boolean polynomials. Using this estimation, we find good cubes to analyze reduced round TRIAD-AE. We get a cube of size 32 which gives zero-sum up to 540 rounds, and a cube of size 34 which can distinguish TRIAD-AE up to 550 rounds with a confidence level around $$95 \%$$. Further, we also obtained some small size good cubes which distinguishes TRIAD-AE from a random generator. We believe that our analysis can help to understand the security of the cipher better. © 2019, Springer Nature Switzerland AG.

Some Cryptanalytic Results on TRIAD

RC4 has attracted many cryptologists due to its simple structure. In [<a href="https://www.degruyter.com/document/doi/10.1515/jmc-2016-0061/html#j_jmc-2016-0061_ref_009_w2aab3b7b2b1b6b1ab1b5b9Aa">9</a>], Paterson, Poettering and Schuldt reported the results of a large scale computation of RC4 biases. Among the biases reported by them, we try to theoretically analyze a few which show very interesting visual patterns. We first study the bias which relates the key stream byte zi with i−k[0], where k[0] is the first byte of the secret key. We then present a generalization of the Roos bias. In 1995, Roos observed the bias of initial bytes S[i] of the permutation after KSA towards fi=∑ir=1r+∑ir=0K[r]. Here we study the probability of S[i] equaling fy=∑yr=1r+∑yr=0K[r] for i≠y. Our generalization provides a complete correlation between zi and i−fy. We also analyze the key-keystream relation zi=fi−1 which was studied by Maitra and Paul [<a href="https://www.degruyter.com/document/doi/10.1515/jmc-2016-0061/html#j_jmc-2016-0061_ref_006_w2aab3b7b2b1b6b1ab1b5b6Aa">6</a>] in FSE 2008. We provide more accurate formulas for the probability of both zi=i−fi and zi=fi−1 for different i’s than the existing works.

Journal of Mathematical Cryptology

Generalization of Roos bias in RC4 and some results on key-keystream relations

In this paper we present proofs for the new biases in RC4 which were experimentally found and listed out (without theoretical justifications and proofs) in a paper by Vanhoef et al. in USENIX 2015. Their purpose was to exploit the vulnerabilities of RC4 in TLS using the set of new biases found by them. We also show (and prove) new results on couple of very strong biases residing in the joint distribution of three consecutive output bytes of the RC4 stream cipher. These biases provides completely new distinguisher for RC4 taking roughly O(224) samples to distinguish streams of RC4 from a uniformly random stream. We also provide a list of newresults with proofs relating to some conditional biases in the keystreams of the RC4 stream cipher. © 2018 The Institute of Electronics, Information and Communication Engineers.

IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

Theoretical understanding of some conditional and joint biases in RC4 stream cipher

In this paper we revisit the modular inversion hidden number problem (MIHNP) and the inversive congruential generator (ICG) and consider how to attack them more efficiently. We consider systems of modular polynomial equations of the form aij+bijxi+cijxj+xixj=0(modp) and show the relation between solving such equations and attacking MIHNP and ICG. We present three heuristic strategies using Coppersmith’s lattice-based root-finding technique for solving the above modular equations. In the first strategy, we use the polynomial number of samples and get the same asymptotic bound on attacking ICG proposed in PKC 2012, which is the best result so far. However, exponential number of samples is required in the work of PKC 2012. In the second strategy, a part of polynomials chosen for the involved lattice are linear combinations of some polynomials and this enables us to achieve a larger upper bound for the desired root. Corresponding to the analysis of MIHNP we give an explicit lattice construction of the second attack method proposed by Boneh, Halevi and Howgrave-Graham in Asiacrypt 2001. We provide better bound than that in the work of PKC 2012 for attacking ICG. Moreover, we propose the third strategy in order to give a further improvement in the involved lattice construction in the sense of requiring fewer samples. © 2017, Springer Science+Business Media, LLC.

Solving a class of modular polynomial equations and its relation to modular inversion hidden number problem and inversive congruential generator

Salsa20 and ChaCha20 are two of the most promising ciphers in recent days. The most significant step in the cryptanalysis of Salsa and ChaCha is the idea of Probabilistic Neutral Bits, which was introduced by Aumasson et al. (FSE 2008). After that, no significant improvement is achieved in the procedure of choosing Probabilistic Neutral Bits. The works in this direction mostly were concerned about forward probabilities. In this paper, we give a new algorithm to construct Probabilistic Neutral Bits. We use this algorithm to improve the existing attacks for reduced rounds of both Salsa and ChaCha. Our attacks on Salsa and Chacha are respectively around 2.27 and 5.39 times faster than the existing works of Choudhuri and Maitra (accepted in FSE 2017). © 2017 Elsevier B.V.

Discrete Applied Mathematics

Improved analysis for reduced round Salsa and Chacha

In this paper we study an RSA variant with moduli of the form N = prql (r &gt; l ≥ 2). This variant was mentioned by Boneh, Durfee and Howgrave-Graham [2]. Later Lim, Kim, Yie and Lee [11] showed that this variant is much faster than the standard RSA moduli in the step of decryption procedure. There are two proposals of RSA variants when N = prql. In the first proposal, the encryption exponent e and the decryption exponent d satisfy ed = 1 mod pr-1ql-1(p-1)(q-1),whereas in the second proposal ed = 1 mod (p-1)(q-1). We prove that for the first case if d &lt; N1-(3r+l)(r+l)-2, one can factor N in polynomial time. We also show that polynomial time factorization is possible if d &lt; N(7-2¶7)/(3(r+l)) for the second case. Finally, we study the case when few bits of one prime are known to the attacker for this variant of RSA. We show that given min( l r+l , 2(r-l) r+l ) log2 p least significant bits of one prime, one can factor N in polynomial time. © 2017 Walter de Gruyter GmbH, Berlin/Boston.

Cryptanalysis of an RSA variant with moduli N=prql

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. © 2016 Elsevier B.V.