Fast correlation attacks on certain stream ciphers
Fast correlation attacks on certain stream ciphers
复制标题
DOI：
10.1007/bf02252874
复制
发表时间：
1989-01
影响因子：
3
通讯作者：
W. Meier;O. Staffelbach
中科院分区：
文献类型：
--
作者：
W. Meier;O. Staffelbach
假设流密码中采用的运行密钥生成器的输出与线性反馈移位寄存器序列（LFSR序列）a相关，相关概率p>0.5。然后提出两种新的相关攻击（算法A和B）来确定a的初始数字，前提是反馈抽头的数量t<10，如果p≤0.75。算法A的计算复杂度为O(2ck)量级，其中k表示LFSR的长度并且c<1取决于攻击的输入参数，而算法B对于LFSR的长度k是多项式的（事实上，甚至是线性的）。这些算法比对 LFSR 所有阶段的穷举搜索要快得多，并且被证明能够成功地对抗相当长度 k（通常 k=1000）的移位寄存器。另一方面，对于相关概率 p≤0.75，如果长 LFSR 具有更多的抽头（大约 k≥100 且 t≥10），则攻击被证明是不可行的。
Suppose that the output of a running key generator employed in a stream cipher is correlated to a linear feedback shift register sequence (LFSR sequence) a with correlation probabilityp>0.5. Then two new correlation attacks (Algorithms A and B) are presented to determine the initial digits of a, provided that the numbertof feedback taps is small (t<10 ifp≤0.75). The computational complexity of Algorithm A is of orderO(2ck), wherekdenotes the length of the LFSR andc<1 depends on the input parameters of the attack, and Algorithm B is polynomial (in fact, even linear) in the lengthkof the LFSR. These algorithms are much faster than an exhaustive search over all phases of the LFSR, and are demonstrated to be successful against shift registers of considerable lengthk(typically,k=1000). On the other hand, for correlation probabilitiesp≤0.75 the attacks are proven to be infeasible against long LFSRs if they have a greater number of taps (roughlyk≥100 andt≥10).