Title:  on the probability distribution of the carry cells of stream ciphers ffcsrh v2 and ffcsrh v3 
Author:  Song Haixin
; Fan Xiubin
; Wu Chuankun
; Feng Dengguo

Source:  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Conference Name:  7th China International Conference on Information Security and Cryptography, Inscrypt 2011

Conference Date:  November 30, 2011  December 3, 2011

Issued Date:  2012

Conference Place:  Beijing, China

Keyword:  Automata theory
; Cryptography
; Cytology
; Markov processes
; Probability distributions
; Security of data

Indexed Type:  EI

ISSN:  03029743

ISBN:  9783642347030

Department:  (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

Abstract:  FFCSRH 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 FFCSRH 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 FFCSRH v2. And so far there are no analytical results of FFCSRH v3. This paper discusses the probability distribution of the carry cells of FFCSRH v2 and FFCSRH 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 FFCSRH v2 and FFCSRH v3, noticing that (1/2)·(3/4) ^{l∈∈1}∈>∈2^{∈l} for l∈>∈1. FCSR is a finitestate 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 FFCSRH v2 by solving the equations. Applying this technique to FFCSRH v3, we obtain that the probability of all the 82 carry cells of FFCSRH 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 FFCSRH v3. Our results provide theoretical support to M.Hell and T.Johansson's cryptanalysis of FFCSRH v2 and establish a theoretical foundation for further cryptanalysis of FFCSRH v3. © 2012 SpringerVerlag Berlin Heidelberg. 
English Abstract:  FFCSRH 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 FFCSRH 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 FFCSRH v2. And so far there are no analytical results of FFCSRH v3. This paper discusses the probability distribution of the carry cells of FFCSRH v2 and FFCSRH 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 FFCSRH v2 and FFCSRH v3, noticing that (1/2)·(3/4) ^{l∈∈1}∈>∈2^{∈l} for l∈>∈1. FCSR is a finitestate 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 FFCSRH v2 by solving the equations. Applying this technique to FFCSRH v3, we obtain that the probability of all the 82 carry cells of FFCSRH 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 FFCSRH v3. Our results provide theoretical support to M.Hell and T.Johansson's cryptanalysis of FFCSRH v2 and establish a theoretical foundation for further cryptanalysis of FFCSRH v3. © 2012 SpringerVerlag Berlin Heidelberg. 
Language:  英语

Content Type:  会议论文

URI:  http://ir.iscas.ac.cn/handle/311060/15827

Appears in Collections:  软件所图书馆_会议论文

There are no files associated with this item.

Recommended Citation: 
Song Haixin,Fan Xiubin,Wu Chuankun,et al. on the probability distribution of the carry cells of stream ciphers ffcsrh v2 and ffcsrh v3[C]. 见:7th China International Conference on Information Security and Cryptography, Inscrypt 2011. Beijing, China. November 30, 2011  December 3, 2011.


