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.

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).