Generalization of Roos bias in RC4 and some results on key-keystream relations

Journal of mathematical cryptology

article

Sabyasachi Dey¹  Santanu Sarkar¹ 

[1] Indian Institute of Technology

关键词: Cryptanalysis;    keystream;    RC4;    Roos bias;    stream cipher;   

DOI  :  10.1515/jmc-2016-0061

学科分类：社会科学、人文和艺术（综合）

来源: De Gruyter

【 摘 要 】

RC4 has attracted many cryptologists due to its simple structure. In [9], Paterson, Poettering and Schuldt reported the results of a large scale computation of RC4 biases. Among the biases reported by them, we try to theoretically analyze a few which show very interesting visual patterns. We first study the bias which relates the key stream byte zi{z_{i}} with i-k⁢[0]{i-k[0]}, where k⁢[0]{k[0]} is the first byte of the secret key. We then present a generalization of the Roos bias. In 1995, Roos observed the bias of initial bytes S⁢[i]{S[i]} of the permutation after KSA towards fi=∑r=1ir+∑r=0iK⁢[r]{f_{i}=\sum_{r=1}^{i}r+\sum_{r=0}^{i}K[r]}. Here we study the probability of S⁢[i]{S[i]} equaling fy=∑r=1yr+∑r=0yK⁢[r]{f_{y}=\sum_{r=1}^{y}r+\sum_{r=0}^{y}K[r]} for i≠y{i\neq y}. Our generalization provides a complete correlation between zi{z_{i}} and i-fy{i-f_{y}}. We also analyze the key-keystream relation zi=fi-1{z_{i}=f_{i-1}} which was studied by Maitra and Paul [6] in FSE 2008. We provide more accurate formulas for the probability of both zi=i-fi{z_{i}=i-f_{i}} and zi=fi-1{z_{i}=f_{i-1}} for different i ’s than the existing works.

【 授权许可】

CC BY|CC BY-NC-ND