Information Security and Cryptology - ICISC 2003

Alpha1 is a stream cipher with a key size of 128 bits. It was proposed as a replacement algorithm for the stream cipher A5 to supply confidentiality over mobile communication systems. Alpha1 consists of four binary linear feedback shift registers. Previous attacks on Alpha1 only recover the initial state of the shortest register. In this paper we present a complete divide and conquer attack, starting with an improved attack on the shortest register, and continuing the attack to recover the remaining three registers. Although Alpha1 is a 128-bit stream cipher, the key can be recovered through this divide and conquer attack with complexity 261, using 35,000 bits of known plaintext