Abstract Small-state stream ciphers (SSCs) idea is based on using key bits not only in the initialization but also continuously in the keystream generation phase. A time-memory-data tradeoff (TMDTO) distinguishing attack was successfully applied against all SSCs in 2017 by Hamann et al. They suggested using not only key bits but also initial value (IV) bits continuously in the keystream generation phase to strengthen SSCs against TMDTO attacks. Then, Hamann and Krause proposed a construction based on using only IV bits continuously in the packet mode. They suggested an instantiation of an SSC and claimed that it is resistant to TMDTO attacks. We point out that accessing IV bits imposes an overhead on cryptosystems that might be unacceptable in some applications. More importantly, we show that the proposed SSC remains vulnerable to TMDTO attacks 1. To resolve this security threat, the current paper proposes constructions based on storing key or IV bits that are the first to provide full security against TMDTO attacks. Five constructions are proposed for different applications by considering efficiency. Designers can obtain each construction’s minimum volatile state length according to the desirable keystream, key and IV lengths.