FASER流密码的安全性分析  

Cryptanalysis of FASER Stream Cipher

作　　者：徐超[1] 张斌[1,2] Willi Meier 

机构地区：[1]可信计算与信息保障实验室中国科学院软件研究所,北京100190 [2]计算机科学国家重点实验室中国科学院软件研究所,北京100190 [3]瑞士西北高等专业学院

出　　处：《密码学报》2014年第4期358-367,共10页Journal of Cryptologic Research

基　　金：国家重点基础研究发展项目(973计划)(2013CB338002);国家自然科学基金项目(60833008;60603018;61173134;91118006;61272476)

摘　　要：FASER是一个由Chaza等人设计的认证加密方案并提交到CAESAR竞赛.FASER使用两个具有相同长度的状态寄存器,一个用来加密另一个用来认证.FASER的状态寄存器可以分成两个部分,一部分由线性FSR更新另一部分由非线性FSR进行更新.一个滤波布尔函数用来产生密钥流,这个滤波布尔函数是由MAJ和MIX两个函数组成.我们主要评估了FASER加密过程的安全性,也就是密钥流生成阶段.我们指出FASER的最大缺陷就是线性FSR和非线性FSR直接不相互影响.因此通过线性逼近MAJ函数,可能寻找到只包含密钥流比特和线性FSR状态比特的线性关系式.对于FASER128和FASER256我们寻找到了许多这样的线性逼近等式,这些逼近等式的相关系数都是2-1.利用这个缺陷我们利用相关攻击来恢复线性FSR的内部状态,在预计算阶段寻找低重量倍式的时间复杂度是2-36,在线的复杂度是可以忽略不计的,它是线性FSR长度的多项式.攻击所需的数据量不超过2-36.此外,利用MAJ函数的性质,我们利用连续两步密钥流之间的关系构造了许多区分器,对于FASER128和FASER256这些区分器都具有2-2的相关系数.因此我们分别只需要16个FASER128或者FASER256的密钥流就可区分出密钥流和随机序列.这些区分器都没有利用MIX函数的设计缺陷,即使FASER的设计者修改了MIX函数的缺陷,我们的区分攻击依然起作用.我们还给出了在假设线性逼近中包含一个非线性FSR的状态比特的条件下如何恢复的内部状态的方法.FASER is an authenticated encryption scheme designed by Chaza et al. and submitted to the CAESAR competition. FASER uses two state registers of the same size, one for encryption and the other for authentication. The state registers used in FASER are divided into two parts: updating with linear FSRs and updating with non-linear FSRs. A filtering Boolean function composed of MAJ and MIX, is used to derive each keystream word from the internal state. We evaluate the security of the FASER encryption process, i.e., the process of keystream generation. We found that the biggest weakness of FASER is that the linear FSR and nonlinear FSR parts do not interact with each other. By linear approximations of the MAJ function, it is possible to derive linear approximation equations involving the keystream and the linear FSR initial states. We found some specific linear approximations with correlation coefficient 2-1 for both FASER128 and FASER256. This weakness leads to a correlation attack to recover the initial state of the linear FSR parts with off-line time complexity 2-36 to compute a low weight multiple polynomial, and the online time complexity can be ignored, which is the polynomial time of the total length of linear FSRs and needs 2-36 keystream words. Moreover, with the poor correlation property of the MAJ function, we constructed many distinguishers involving two consecutive steps of keystream words, with correlation coefficient of 2-2 for FASER128 and FASER256. So we only need 16 keystream words of FASER128 and FASER256 to distinguish a keystream with a random sequence, respectively. These distinguishers do not use the weakness of the MIX operation, so our distinguishing attack still works even when the designer of FASER modify the MIX function. Furthermore, we also give the idea to recover the initial state even if the linear approximations have one input bit coming from a nonlinear FSR.

关 键 词：流密码 CAESAR FASER 相关攻击 区分器 

分 类 号：TN918.4[电子电信—通信与信息系统]