Cryptanalysis of Achterbahn-128/80

Maria Naya-Plasencia
INRIA (projet CODES), France.

Maria.Naya_Plasencia@inria.fr

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

Abstract

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 2⁶¹. The attack against Achterbahn-128 requires 2^80.58 operations and 2⁶⁰.

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.