Stream Cipher Algorithm Abc Analysis

ECRYPT (European Network of Excellence for Cryptology) was launched by IST on February 1st, 2004, under the globalization of cryptography research. And the Estream project which was carried into execution by ECRYPT in October, 2004, aimed to choose the standard algorithm of stream cipher for Europe through public appraisal in several years and put them into practice. Estream project published 34 candidates in June, 2005, and the first evaluation phase which began from that time planned to be ended in February, 2006. The second phase started in July and the evaluation reports will be published in January, 2008.ABC is a synchronous stream cipher which is designed by Anashin, Bogdanov, Kizhvatov and Kumarb. It has three versions, which are v1, v2 and v3. The designers have already applied patent and claimed that v3 is the final version.H.J.Wu and B.Preneel find weak keys through analyzing the possible probability advantage in the process of carry, which is similar to our method, and break the scheme using fast relate attack. In order to prevent against such kind of attack, the designer fixed the key expansion, and release the third version of the scheme.This paper makes use of the property of LFSR and the flaw in key part of ABC. We analyzed ABC.v2 and ABC.v3 using linear syndrome. When m =0,1,2 theprobability of F(y,m)(?)(F(c,m)(?)F(x,m)) = 0 is not 1/2 ,then we found thatABC.v2 has large amount of weak keys, at least 2⁸⁶ + 2⁸¹ keys can be recovered. The number of weak keys account for 2^-43 of the key space at least and recovering the internal state of a weak key requires about 2⁵⁴ keystream bytes and 2⁶⁵ operation. Besides, if the computation complexity was restricted under that of birthday attack, the number of weak keys will increase when the computation complexity and the data amount increase. A similar attack can be applied to break ABC.v3.