The main concern in the design philosophy is to decrease the internal state size without compromising the security against TMD tradeoff attacks. If the number of equivalence classes is more than the cardinality of the key space, then the cipher is expected to be resistant against TMD tradeoff attacks even though the internal state (except the fixed key) is of fairly small length. Moreover, Armknecht and Mikhalev presented a new design, which they call Sprout, to embody their philosophy.
In this work, ironically, we mount a TMD tradeoff attack on Sprout within practical limits using $2^d$ output bits in $2^{71-d}$ encryptions of Sprout along with $2^{d}$ table lookups. The memory complexity is $2^{86-d}$ where $d\leq 40$. In one instance, it is possible to recover the key in $2^{31}$ encryptions and $2^{40}$ table lookups 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^{41.3}$ systems of linear equations with 20 unknowns and an effort of about $2^{35}$ encryptions. Furthermore, we mount a guess-and-determine attack having a complexity about $2^{68}$ encryptions with negligible data and memory. We have verified our attacks by conducting several experiments. Our results show that Sprout can be practically broken.
Category / Keywords: Stream ciphers, Cryptanalysis, Time-Memory-Data Tradeoff, Sprout Original Publication (in the same form): Selected Areas in Cryptography (SAC) 2015 Date: received 27 Mar 2015, last revised 28 Sep 2015 Contact author: muhammedgs at gmail com Available format(s): PDF | BibTeX Citation Version: 20150928:061848 (All versions of this report) Short URL: ia.cr/2015/289 Discussion forum: Show discussion | Start new discussion