International Association
for Cryptologic Research

A new lightweight stream cipher, Sprout, has been presented at FSE 2015. The main concern in the design philosophy of the cipher is to decrease the internal state size without compromising the security against Time-Memory-Data (TMD) tradeoff attacks. In this work, we have mounted a TMD tradeoff attack to Sprout using $2^d$ output bits in $2^{71.7-d}$ encryptions of Sprout along with $2^{d}$ table lookups. The memory complexity is $2^{85-d}$ where $d\\leq 40$. In one instance, it is possible to recover the key in faster than $2^{33}$ encryption time if we have $2^{40}$ bits of keystream output by using tables of 770 Terabytes in total. The offline phase of preparing the tables consists of solving roughly $2^{42}$ system of linear equations with 20 unknowns.