对ABC算法的差分错误攻击

Differential Fault Analysis of ABC

2002年Klimov和Shamir提出了一类新的非线性函数——T函数,2005年Anashin等人利用一类单字单圈T函数作为主要驱动部件,设计了面向软件实现的ABC流密码算法参与e STREAM计划的征集.根据对ABC算法已有的攻击结果,在弱密钥情况下,可以利用快速相关攻击获得组件A的状态,所以本文主要研究了在已知组件A状态的前提下,组件B与C对差分错误攻击的安全性.攻击利用面向比特的错误模型,在不同时刻向组件B的输出状态注入单比特错误.然后根据正确的输出密钥字与错误的输出密钥字,结合差分分析技术,通过组件C建立起不同时刻组件B状态之间的关系.分析结果显示通过192个错误密钥字和160个正确密钥字可以建立含5个状态方程的方程组;然后根据单圈T函数的性质,本文设计了逐比特求解该方程组的算法,平均得到192组候选解;最后利用正确密钥字对候选解进行筛选.从而使恢复组件B和C的数据复杂度从2^(17.5)降为2^(8.46),计算复杂度从2^(32.84)降为2^(16.32),本文结论显示ABC对于差分错误攻击是不安全的.

In 2002 Klimov and Shamir proposed a new class of nonlinear function called T-functions. Then in 2005, Anashin et al. submitted ABC algorithm to the e STREAM Project. ABC is a software-oriented stream cipher which uses a class of single cycle T-functions as its driving part. According to the attack results of ABC, we can apply fast correlation attack to recover the state of component A under the condition of weak keys. Assuming that the state of component A is already known, we analyze the resistance of components B and C against differential fault attack. Bit based fault model is built to inject single bit faults to the output states of component B in different moments. According to the correct and errorous keystream words, we make use of differential analysis techniques to obtain the relationship of component B in different moments by means of component C. The analysis results show that 5 state equations can be established by 192 errorous keystream words and 160 correct keystream words. After that, an algorithm based on the properties of single cycle T-function is designed to solve the equations bit by bit. At last the correct keystream words are used to select the average 192 candidate solutions obtained by the algorithm. The data complexity recovering component B and C reduces from 2^(17.5) to 2^(8.46), and the computational complexity reduces from 2^(32.84) to 2^(16.32). The result shows that ABC stream cipher is not safe against differential fault analysis.