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 regi...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.展开更多
基金This work was supported by tile National Natural Science Foundation of China under Grant No.60673068the National Grand Fundamental Research 973 Program of China under Grant No.2004CB318004.
文摘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.
