Time-memory-data (TMD) tradeoff attacks limit the security level of classical stream ciphers to the birthday bound. Recently, a new field of research has emerged, which searches for so-called small-state stream ciphers that try to overcome this imitation.

In a first part, generic distinguishers for recently proposed small-state stream ciphers are derived whose complexity is significantly smaller than that of exhaustive key search.A new design idea for small-state stream ciphers is presented, which might allow to achieve full security against TMD tradeoff attacks.

In a second part, a fast correlation attack is proposed on Grain-like small-state stream ciphers. This attack is shown to be quite efficient for a recently designed small-state stream cipher.

This is joint work with Matthias Hamann, Matthias Krause and Bin Zhang.