On the Role of the Inner State Size in Stream Ciphers

Many modern stream ciphers consist of a keystream generator and an initialisation function. In fielded systems, security of the keystream generator is often based on a large inner state rather than an inherently secure design. As a consequence, an increasing number of attacks on stream ciphers exploit the (re-)initialisation of large inner states by a weak initialisation function. In this paper, we propose a strict separation of keystream generator and initialisation function in stream cipher design. After giving lower bounds on the necessary inner state size, we show how a secure stream cipher can be constructed from a weak keystream generator. We introduce the notion of inner state size efficiency and compare it for a number of fielded stream ciphers, indicating that a secure cipher can be based on reasonable inner state sizes. Concluding, we ask a number of open questions that may give rise to a new field of research that is concerned with the security of initialisation functions.