Cryptanalysis of Achterbahn-128/80

Maria Naya-Plasencia

INRIA (projet CODES), France.

To appear in the Proceedings of Fast Software Encryption -- FSE 2007.


This paper presents two key-recovery attacks against Achterbahn-128/80, the last version of one of the stream cipher proposals in the eSTREAM project.

The attack against the 80-bit variant, Achterbahn-80, has complexity 261. The attack against Achterbahn-128 requires 280.58 operations and 260.

These attacks are based on an improvement of the attack due to Hell and Johansson against Achterbahn version 2. They mainly rely on an algorithm

that makes profit of the short lengths of the constituent registers.

Keywords : stream cipher, eSTREAM, Achterbahn, cryptanalysis, correlation attack, linear approximation, parity check, key-recovery attack.