Cryptanalysis of Achterbahn-Version 1 and -Version 2

摘要

Achterbahn is one of the candidate stream ciphers submitted to the eSTREAM, which is the ECRYPT Stream Cipher Project. The cipher Achterbahn uses a new structure which is based on several nonlinear feedback shift registers (NLFSR) and a nonlinear combining output Boolean function. This paper proposes distinguishing attacks on Achterbahn-Version 1 and -Version 2 on the reduced mode and the full mode. These distinguishing attacks are based on linear approximations of the output functions. On the basis of these linear approximations and the periods of the registers, parity checks with noticeable biases are found. Then distinguishing attacks can be achieved through these biased parity checks. As to Achterbahn-Version 1, three cases that the output function has three possibilities are analyzed. Achterbahn-Version 2, the modification version of Achterbahn-Version 1, is designed to avert attacks based on approximations of the output Boolean function. Our attack with even much lower complexities on Achterbahn-Version 2 shows that Achterbahn-Version 2 cannot prevent attacks based on linear approximations.