on the probability distribution of the carry cells of stream ciphers f-fcsr-h v2 and f-fcsr-h v3

ISCAS OpenIR

	on the probability distribution of the carry cells of stream ciphers f-fcsr-h v2 and f-fcsr-h v3
	Song Haixin; Fan Xiubin; Wu Chuankun; Feng Dengguo
	2012
会议名称	7th China International Conference on Information Security and Cryptography, Inscrypt 2011
会议录名称	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
页码	160-178
会议日期	November 30, 2011 - December 3, 2011
会议地点	Beijing, China
收录类别	EI
ISSN	0302-9743
ISBN	9783642347030
部门归属	(1) State Key Laboratory of Information Security Institute of Software Chinese Academy of Sciences Beijing 100190 China; (2) Graduate University of Chinese Academy of Sciences Beijing 100049 China
摘要	F-FCSR-H v2 is one of the 8 final stream ciphers in the eSTREAM portfolio. However, it was broken by M. Hell and T. Johansson at ASIACRYPT 2008 by exploiting the bias in the carry cells of a Galois FCSR. In order to resist this attack, at SAC 2009 F. Arnault proposed the new stream cipher F-FCSR-H v3 based upon a ring FCSR. M. Hell and T. Johansson only presented experimental results but no theoretical results for the success probability of their powerful attack against F-FCSR-H v2. And so far there are no analytical results of F-FCSR-H v3. This paper discusses the probability distribution of the carry cells of F-FCSR-H v2 and F-FCSR-H v3. We build the probability model for the carry cells of the two stream ciphers and prove that the consecutive output sequence of a single carry cell is a homogeneous Markov chain and the inverse chain is also a homogeneous Markov chain. We also prove that the probability of l consecutive outputs of a single carry cell to be zeros is (1/2)·(3/4) ^l∈-∈1, which is a weakness of the carry cells of F-FCSR-H v2 and F-FCSR-H v3, noticing that (1/2)·(3/4) ^l∈-∈1∈>∈2^-∈l for l∈>∈1. FCSR is a finite-state automata, so its distribution is stable. Based on this fact, we construct a system of equations using the law of total probability, and present a theoretical probability of breaking F-FCSR-H v2 by solving the equations. Applying this technique to F-FCSR-H v3, we obtain that the probability of all the 82 carry cells of F-FCSR-H v3 to be zeros at the same clock is at least 2^-∈64.29, which is much higher than 2^-∈82. This is another weakness of the carry cells of F-FCSR-H v3. Our results provide theoretical support to M.Hell and T.Johansson's cryptanalysis of F-FCSR-H v2 and establish a theoretical foundation for further cryptanalysis of F-FCSR-H v3. © 2012 Springer-Verlag Berlin Heidelberg.; F-FCSR-H v2 is one of the 8 final stream ciphers in the eSTREAM portfolio. However, it was broken by M. Hell and T. Johansson at ASIACRYPT 2008 by exploiting the bias in the carry cells of a Galois FCSR. In order to resist this attack, at SAC 2009 F. Arnault proposed the new stream cipher F-FCSR-H v3 based upon a ring FCSR. M. Hell and T. Johansson only presented experimental results but no theoretical results for the success probability of their powerful attack against F-FCSR-H v2. And so far there are no analytical results of F-FCSR-H v3. This paper discusses the probability distribution of the carry cells of F-FCSR-H v2 and F-FCSR-H v3. We build the probability model for the carry cells of the two stream ciphers and prove that the consecutive output sequence of a single carry cell is a homogeneous Markov chain and the inverse chain is also a homogeneous Markov chain. We also prove that the probability of l consecutive outputs of a single carry cell to be zeros is (1/2)·(3/4) ^l∈-∈1, which is a weakness of the carry cells of F-FCSR-H v2 and F-FCSR-H v3, noticing that (1/2)·(3/4) ^l∈-∈1∈>∈2^-∈l for l∈>∈1. FCSR is a finite-state automata, so its distribution is stable. Based on this fact, we construct a system of equations using the law of total probability, and present a theoretical probability of breaking F-FCSR-H v2 by solving the equations. Applying this technique to F-FCSR-H v3, we obtain that the probability of all the 82 carry cells of F-FCSR-H v3 to be zeros at the same clock is at least 2^-∈64.29, which is much higher than 2^-∈82. This is another weakness of the carry cells of F-FCSR-H v3. Our results provide theoretical support to M.Hell and T.Johansson's cryptanalysis of F-FCSR-H v2 and establish a theoretical foundation for further cryptanalysis of F-FCSR-H v3. © 2012 Springer-Verlag Berlin Heidelberg.
关键词	Automata Theory Cryptography Cytology Markov Processes Probability Distributions Security Of Data
语种	英语
内容类型	会议论文
URI标识	http://ir.iscas.ac.cn/handle/311060/15827
专题	中国科学院软件研究所
推荐引用方式 GB/T 7714	Song Haixin,Fan Xiubin,Wu Chuankun,et al. on the probability distribution of the carry cells of stream ciphers f-fcsr-h v2 and f-fcsr-h v3[C],2012:160-178.