Cryptanalysis of Achterbahn-Version 1 and -Version 2

Achterbahn is one ofthe candidate stream ciphers submitted to the eSTREAM, which is theECRYPT Stream Cipher Project. The cipher Achterbahn uses a newstructure which is based on several nonlinear feedback shiftregisters (NLFSR) and a nonlinear combining output Boolean function.This paper proposes distinguishing attacks on Achterbahn-Version 1and -Version 2 on the reduced mode and the full mode. Thesedistinguishing attacks are based on linear approximations of theoutput functions. On the basis of these linear approximations and theperiods of the registers, parity checks with noticeable biases arefound. Then distinguishing attacks can be achieved through thesebiased parity checks. As to Achterbahn-Version 1, three cases that theoutput function has three possibilities are analyzed. Achterbahn-Version2, the modification version of Achterbahn-Version 1, is designed toavert attacks based on approximations of the output Boolean function. Ourattack with even much lower complexities on Achterbahn-Version 2 showsthat Achterbahn-Version 2 cannot prevent attacks based on linearapproximations.