Santanu Sarkar

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.

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.

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.

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.

In Crypto 2010, Kiltz, O’Neill and Smith used m -prime RSA modulus N with m ≥ 3 for constructing lossy RSA. The security of the proposal is based on the Multi-Prime Φ -Hiding Assumption. In this paper, we propose a heuristic algorithm based on the Herrmann-May lat- tice method (Asiacrypt 2008) to solve the Multi-Prime Φ -Hiding Problem when prime e > N2/3M. Further, by combining with mixed lattice tech- niques, we give an improved heuristic algorithm to solve this problem when prime e > N2/3M-1/4m2. These two results are verified by our experiments. Our bounds are better than the existing works.

In Asiacrypt 2010, Knellwolf, Meier and Naya-Plasencia pro-posed distinguishing attacks on Grain v1 when (i) Key Scheduling process is reduced to 97 rounds using 227chosen IVs and (ii) Key Scheduling process is reduced to 104 rounds using 235 chosen IVs. Using similar idea, Banik obtained a new distinguisher for 105 rounds. In this paper, we show similar approach can work for 106 rounds. We present a new distinguisher on Grain v1 for 106 rounds with success probability 63%.

Differential Fault Attack (DFA) is a very well known technique to evaluate security of a stream cipher. This considers that the stream cipher can be weakened by injection of the fault. In this paper we study DFA on three ciphers, namely Grain v1, Lizard and ACORN v3. We show that Grain v1 (an eStream cipher) can be attacked with injection of only 5 faults instead of 10 that has been reported in 2012. For the first time, we have mounted the fault attack on Lizard, a very recent design and show that one requires only 5 faults to obtain the state. ACORN v3 is a third round candidate of CAESAR and there is only one hard fault attack on an earlier version of this cipher. However, the ‘hard fault’ model requires a lot more assumption than the generic DFA. In this paper, we mount a DFA on ACORN v3 that requires 9 faults to obtain the state. In case of Grain v1 and ACORN v3, we can obtain the secret key once the state is known. However, that is not immediate in case of Lizard. While we have used the basic framework of DFA that appears in literature quite frequently, specific tweaks have to be explored to mount the actual attacks that were not used earlier. To the best of our knowledge, these are the best known DFAs on these three ciphers.

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.