on guess and determine analysis of rabbit

ISCAS OpenIR

	on guess and determine analysis of rabbit
	Feng Xiutao; Shi Zhenqing; Wu Chuankun; Feng Dengguo
	2011
发表期刊	INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE
ISSN	0129-0541
卷号	22 期号:6 页码:1283-1296
摘要	Rabbit is a stream cipher proposed by M. Boesgaard et al., and has been selected into the final portfolio after three evaluation phases of the ECRYPT Stream Cipher Project (eSTREAM). So far only a few papers studied its security besides a series of white papers by the designers of Rabbit. Recently we presented a new idea to evaluate the security of a word-oriented stream cipher algorithm from a smaller data granularity instead of its original data granularity and applied it successfully to the stream cipher SOSEMANUK. In this work we apply the same idea to the Rabbit algorithm and analyze its security in resistance against the guess and determine attack from the view point of byte units. As a result, we present two new approaches of solving all x(j,t)+1's and g(j,t)'s from the next-state function and the extraction scheme of Rabbit, whose complexities are 2(166) and 2(140.68) respectively, which are dramatically lower than those proposed by Lu et al. (2(192) and 2(174) resp.) at ISC 2008. Finally based on the above new results we propose a byte-based guess and determine attack on Rabbit, which only needs a small segment of known key stream to recover the whole internal state of Rabbit with time complexity 2(242). Though the complexity of our attack is far higher than that of a brute force (2(128)), we believe that some new techniques adopted in this paper are of interest for future work on Rabbit.; Rabbit is a stream cipher proposed by M. Boesgaard et al., and has been selected into the final portfolio after three evaluation phases of the ECRYPT Stream Cipher Project (eSTREAM). So far only a few papers studied its security besides a series of white papers by the designers of Rabbit. Recently we presented a new idea to evaluate the security of a word-oriented stream cipher algorithm from a smaller data granularity instead of its original data granularity and applied it successfully to the stream cipher SOSEMANUK. In this work we apply the same idea to the Rabbit algorithm and analyze its security in resistance against the guess and determine attack from the view point of byte units. As a result, we present two new approaches of solving all x(j,t)+1's and g(j,t)'s from the next-state function and the extraction scheme of Rabbit, whose complexities are 2(166) and 2(140.68) respectively, which are dramatically lower than those proposed by Lu et al. (2(192) and 2(174) resp.) at ISC 2008. Finally based on the above new results we propose a byte-based guess and determine attack on Rabbit, which only needs a small segment of known key stream to recover the whole internal state of Rabbit with time complexity 2(242). Though the complexity of our attack is far higher than that of a brute force (2(128)), we believe that some new techniques adopted in this paper are of interest for future work on Rabbit.
收录类别	SCI
关键词	Stream Cipher Rabbit Guess And Determine Attack
部门归属	Feng Xiutao; Shi Zhenqing; Wu Chuankun; Feng Dengguo Chinese Acad Sci Inst Software State Key Lab Informat Secur Beijing 100190 Peoples R China.
学科领域	Computer Science
资助者	Natural Science Foundation of China60833008, 60902024; National 973 Program2007CB807902
语种	英语
WOS记录号	WOS:000294809400005
引用统计
内容类型	期刊论文
URI标识	http://ir.iscas.ac.cn/handle/311060/16075
专题	中国科学院软件研究所
推荐引用方式 GB/T 7714	Feng Xiutao,Shi Zhenqing,Wu Chuankun,et al. on guess and determine analysis of rabbit[J]. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE,2011,22(6):1283-1296.
APA	Feng Xiutao,Shi Zhenqing,Wu Chuankun,&Feng Dengguo.(2011).on guess and determine analysis of rabbit.INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE,22(6),1283-1296.
MLA	Feng Xiutao,et al."on guess and determine analysis of rabbit".INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 22.6(2011):1283-1296.