基于故障信息的SOSEMANUK猜测确定攻击

Fault-based guess-and-determine attack on SOSEMANUK

针对SOSEMANUK流密码已有攻击方法复杂度过高的不足,提出并讨论了一种基于故障信息的猜测确定攻击方法.首先利用代数方法构建密码在比特层面的等效代数方程组,然后向密码注入随机单字故障,在深入分析故障传播特征的基础上,将故障信息表示成代数方程组并猜测密码部分内部状态,使用CryptoMinisat解析器求解代数方程组恢复密码初始内部状态.实验结果表明:对密码首轮加密进行攻击,恢复密码全部初始内部状态所需的故障注入次数为20次,计算复杂度为O(296),对密码前两轮加密进行攻击,无须猜测密码内部状态,仅注入10个单字故障即可恢复密码全部初始内部状态.与已有结果相比,新方法攻击复杂度显著降低.

The SOSEMANUK stream cipher is a member of the finalists of the eSTREAM project.In this paper,the previous known attacks against SOSEMANUK was presented and discussed.Firstly,SOSEMANUK was described as a set of equations involving the public and key variables at bit level.Secondly,the attacker was assumed to be able to fault a random inner state word and the faults were described as a set of equations by analyzing the propagation of faults.Thirdly,the CryptoMinisat solver was adapted to recover the secret inner state by guessing certain inner state words and solving the combined equations.The results show that the first round attack recovers the secret internal states,requires 20 faults and the computational complexity is dramatically reduced to O（296）.The first two rounds attack recovers the whole states,requires 10 faults without guessing any inner state word,which is better than the previous known cryptanalytic results.