A Variation on Knellwolf and Meier's Attack on the Knapsack Generator

Pseudo-random generators are deterministic algorithms that take as input a random secret seed and output a flow of random-looking numbers. The Knapsack Generator, presented by Rueppel and Massey in 1985, is one of the many attempts at designing a pseudo-random number generator that is cryptographically secure. It is based on the subset-sum problem, a variant of the knapsack optimization problem, which is considered computationally hard. At FSE 2011, Knellwolf and Meier found a way to go around this hard problem and exhibited a weakness of this generator. In addition to be able to distinguish the outputs from the uniform distribution, they designed an algorithm that retrieves a large portion of the secret. We present here an alternative version of the attack with similar costs retrieving an even larger portion of the secret on a larger range of parameters.