A5/1的 故 障 分 析

左 平, 申延成, 华宏图,3, 陈守东

(1. 吉林大学 商学院, 长春 130012; 2. 空军航空大学 基础部, 长春 130022; 3. 吉林大学 数学学院, 长春 130012)

A5/1算法是欧洲数字蜂窝移动电话系统GSM中采用的流密码加密算法, 用于手机到基站线路上的数据和话音加密. 由于A5/1算法在GSM通信中应用广泛, 因此受到密码专家的广泛关注[1-10]. Golic[2]提出了对A5/1的两种攻击方法： Guess-determine攻击和Time-memory tradeoff攻击. 之后, Biryukov等[3]对Golic提出的第二种攻击方法进行了改进, 但该攻击需要很大的存储空间(约300 Gb)和很长的预计算. Biham等[4]提出一种不同的攻击方法, 该攻击需要获知几十秒的密钥流, 时间复杂度约为240. Keller等[5]基于Guess-determine攻击提出了A5/1的基于硬件攻击方法, 采用特殊的硬件实现其对A5/1的攻击, 攻击复杂度为241×(3/2)11, 但其成功率较低, 约为18%. Barkan等[6]提出了A5/1的唯密文Time-memory tradeoff攻击, 但该攻击需要很复杂的预计算. Ekdahl等[7]首次提出了A5/1的相关攻击, 该攻击在获知几分钟密钥流的情况下可以在PC机上几分钟内恢复密钥. Maximov等[8]利用A5/1内部状态与输出比特的联系改进了文献[7]提出的相关攻击, 此时, 获知9.2～23 s的密钥流便可在PC机上几分钟内恢复密钥. Gendrullis等[9]在文献[5]的基础上, 改进了A5/1的攻击, 只需获知64比特的密钥流便可利用特殊硬件装置COPACOBANA在几小时内恢复64比特的内部状态.

故障分析是一种间接分析方法, 在密码系统物理实现阶段引入故障得到正误密钥流, 再通过对正误密钥流的分析获取密码算法的密钥信息或内部状态. Gomulkiewicz等[10]针对A5/1特殊的钟控模式, 提出一种再同步故障分析. 该分析采用的故障模型是在指定时刻阻止某个LFSR移位一次, 由正误密钥流的再同步得出引入故障前后移位方式的同步, 从而缩小此时内部状态的搜索范围, 进而进行有效的攻击. Guess-determine攻击的思想较简单, 先猜测某一时刻寄存器的部分比特信息, 然后确定剩余的比特信息(主要通过解线性或非线性方程组), 进而确定该时刻寄存器的所有比特信息. 本文结合故障攻击与Guess-determine攻击的思想, 提出A5/1在另一种模型下的故障分析, 通过引入故障, 可淘汰占总猜测数99.9%的错误猜测, 极大提高了错误猜测的过滤能力, 过滤思想简单易实现, 对剩余的错误猜测经过二次筛选便可唯一恢复正确的64内部状态. 攻击的复杂度约为240, 且整个攻击只需要3个故障, 攻击成功的概率大于99%.

1 A5/1算法

A5/1是一个同步流密码, 初始输入为64比特的会话密钥和22比特的初始向量, 其中22比特的初始向量是一个公开的22比特帧序列号. A5/1以帧为单位生成密钥流(4.6 ms为一帧), 并对明文数据流进行加密, 每帧生成228比特的密钥流. A5/1内部由3个长度分别为19,22和23的线性反馈移位寄存器(LFSR)R1,R2,R3组成, 抽头数分别为4,2,4, 且3个LFSR的反馈多项式均为本原多项式, 故由R1,R2,R3产生的序列有最长周期. R1,R2,R3的移位规则由3个控制比特R1[8],R2[10],R3[10]决定, R1,R2,R3的MSBs(most significant bits)异或得到输出密钥流.

A5/1的每帧密钥流按如下方式产生：

1) 初始化： 首先3个移位寄存器全部置0, 然后在64个时钟周期内, 将每个LFSR都移位64次(不带钟控), 每次移位后将密钥比特K[i](i=0,1,2,…,63)与每个LFSR的最低位比特异或. 其次, 在22个时钟周期内, 将每个LFSR都移位22次(不带钟控), 每次移位后将22比特初始向量(帧序列号)IV[i](i=0,1,2,…,21)与每个LFSR的最低位比特异或, 记初始化后的内部状态为Si；

2) 热身阶段： 初始化后, 由状态Si出发, 按照钟控规则移位100个周期, 将产生的密钥流丢掉, 记此时的内部状态为Sw；

3) 产生密钥流： 由状态Sw出发, 按照钟控规则生成228比特的密钥流, 用于加密明文流.

A5/1的钟控机制采用择多逻辑, 由控制比特R1[8],R2[10]和R3[10]决定： 每次移位前计算R1[8],R2[10]和R3[10]的占多数值, 例如3个比特为(0,0,1), 则maj(0,0,1)=0. 一般情况下, 若有3个比特(a,b,c), 且把a,b,c3个比特的多数值记为maj(a,b,c), 则maj(a,b,c)=ab⊕ac⊕bc. 此时, R1移位当且仅当R1[8]=maj(R1[8],R2[10],R3[10]), R2移位当且仅当R2[10]=maj(R1[8],R2[10],R3[10]), R3移位当且仅当R3[10]=maj(R1[8],R2[10],R3[10]). 移位后, R1,R2和R3的MSBs异或即得最终密钥流, 如图1所示.

图1 流密码A5/1Fig.1 A5/1 stream cipher

2 故障分析

2.1 故障诱导模型

本文采用的故障诱导模型是在寄存器指定位置诱导单比特的故障, 例如R1[8]原本值为1, 引入故障后, R1[8]变为0. 为分析方便, 假设在内部状态为Sw时分别在R1[8], R2[10]和R3[10]诱导单比特故障. 于是, 便可得到1条正确的228比特密钥流和3条错误的228比特密钥流. 利用这些正误密钥流恢复A5/1的内部状态Sw, 得知Sw后, 由文献[3]的方法便可恢复加密密钥.

2.2 分析步骤

1) 产生正确的228比特密钥流S0, 且记此时的密钥为K, 初始向量为IV.

2) 重置A5/1加密器, 即重新将密钥K和初始向量IV初始化. 然后按照故障诱导模型, 在内部状态为Sw时分别在R1[8],R2[10]和R3[10]诱导单比特故障, 得到3条错误密钥流S1,S2,S3.

3) 猜测R1[0],R1[1],…,R1[8],R2[0],R2[1],…,R2[10],R3[0],R3[1],…,R3[10]共31比特, 将R1[9],R1[10],…,R1[18],R2[11],R2[12],…,R2[21],R3[11],R3[12],…,R3[22]作为未知量, 此时针对每个具体猜测执行以下步骤: ① 根据已知的移位方式和正确密钥流S0得到一组关于未知量的线性方程； ② 将R1[8]变为R1[8]⊕1, 其余猜测不变, 根据此时的移位方式和密钥流S1同样得到一组包含未知量的线性方程； ③ 将R2[10]变为R2[10]⊕1, 其余猜测不变, 根据此时的移位方式和密钥流S2同样得到一组包含未知量的线性方程； ④ 将R3[10]变为R3[10]⊕1, 其余猜测不变, 根据此时的移位方式和密钥流S3同样得到一组包含未知量的线性方程.

4) 将四组方程组合并, 考察其是否有解. 若方程组无解则猜测错误, 转3)； 否则, 执行5).

5) 求出相应方程组的解, 此时64比特的内部状态全部已知, 记为Sw*. 然后按照A5/1的钟控模式生成新的密钥流S0*, 将S0*与S0进行逐比特比较, 如果出现某一比特不同, 则表明猜测错误, 转3)； 若S0*与S0完全一致, 则视Sw*为正确的内部状态Sw, 攻击结束.

2.3 计算机模拟实现

在一般PC机上, 通过C语言编程可模拟实现上述攻击.

1) 先直接给定初始的64比特内部状态Sw, 按照A5/1的钟控规则生成正确的密钥流； 然后分别改变R1[8],R2[10],R3[10], 其余比特不变, 按规则生成另外3条故障密钥流；

2) 猜测左边31比特的控制比特, 针对每种猜测列出方程组G, 然后判断G是否有解；

3) 若G有解, 则统计相应方程组的秩, 并解出相应的解, 然后按钟控规则生成228比特流, 通过比较再次筛选错误的猜测.

模拟实验显示, 通过判断G有无解, 能淘汰占总猜测数99.9%以上的错误猜测(平均剩下220种猜测不能淘汰), 之后对有解的G进行二次筛选后便可唯一确定正确的64比特内部状态Sw. 有解情形下,G的秩平均大于23, 且已知求解一个变量个数为33的方程组复杂度约为332≈210, 故全部攻击的复杂度约为220+(33-23)+10=240, 且只需要3个故障.

事实上, 总猜测数为231, 淘汰99.9%后剩下约220个解, 最差的情况假设每个G都有232个解, 则共有252个解. 这些解对应252条比特流, 在独立随机假设下, 两条长度为228的比特流完全相同的概率为2228, 故若由某一解(Sw*)产生的228比特流与正确密钥流S0完全一致, 则认为该解即为正确的内部状态Sw, 得知Sw后由文献[3]中方法便可恢复得到A5/1的加密密钥. 本文在运行环境为Intel(R) Pentium(R) 4, CPU 2.80 GHz, 内存为512 Mb的PC机上, 通过编程模拟实验, 运行3～4 d得到了唯一的正确内部状态Sw. 表1列出了几组实验结果.

表1 几组实验结果

*样本Ⅰ和样本Ⅱ未做恢复内部状态的实验.

2.4 A5/1在另一种故障模型下的讨论

假设指定LFSR随机诱导单比特的故障, 其与固定比特位置诱导故障相比, 这种故障诱导更易实现. 下面讨论在这种模型下, 如何通过密钥流判断故障位置, 并提取相应的故障密钥流.

前面的分析中, 分别是在状态Sw的R1[8],R2[10],R3[10]诱导故障, 这是因为此时能最大限度地改变加密器移位方式, 从而获得更多线性无关方程, 过滤猜测更有效. 如果在R1[8]发生故障, 则此时加密器的第一次移位方式发生了改变, 于是从第一比特开始, 输出密钥流便可能发生错误, 在独立随机假设下, 每比特密钥流发生错误的概率为1/2. 记事件F： 从第一个输出比特开始, 连续10个输出比特皆发生错误. 则此时F发生的概率P=2-10. 如果在R1[18]发生故障, 若R1不移位, 则相应的输出比特皆发生错误； R1移位一次后, 此后的至少18比特不会发生错误. 于是, 事件F发生的概率P=4-10, 因为每次R1不移位的概率为1/4. 如果在R1[17]发生故障, 则只有在第一个周期R1移位, 且之后的9个周期R1都不移位, 事件F才可能发生, 故事件F发生的概率P=(3/4)×4-9. 如果在R1[16]发生故障, 则显然事件F不可能发生. 类似地, 在其余位置发生故障, 事件F都不可能发生. 因此, 若在R1[8]发生故障, 则所得故障密钥流前10比特皆发生错误的概率远大于在R1其余位置发生故障的情况. 于是, 若得到的故障密钥流前10比特皆发生错误, 则认为故障发生在R1[8], 判断错误的概率约为4-10/2-10≈0.1%. 此时, 随机获得一条在R1[8]发生故障的密钥流约需随机诱导故障19×210次.

在LFSR R2和R3诱导随机故障的讨论类似于R1的讨论. 判断故障发生在R2[10]和R3[10]当且仅当得到的输出密钥流前10比特皆出错, 且判断错误的概率均约为0.1%.

分别获得在R1[8],R2[10],R3[10]发生故障对应的密钥流后, 类似于第一种模型下的分析, 便可恢复A5/1的密钥, 且成功概率约为(1-0.1%)3>99%, 随机获取需要的故障密钥流需要随机诱导故障(19+22+23)×210≈216次.

综上所述, 本文给出了A5/1的一种新的故障分析方法, 先给出了其在固定比特位置诱导故障模型下的分析, 再将其推广到随机位置诱导故障模型下, 平均可淘汰占总猜测数99.9%的错误猜测, 最终可完全恢复A5/1的内部状态. 整个攻击只需要3个故障, 复杂度约为240.

[1] Briceno M, Goldberg I, Wagner D. A Pedagogical Implementation of A5/1 and A5/2 “Voice Pricacy” Encryption Algorithms [EB/OL]. 1999-10-23. http://cryptome.org/gsm-a512.htm.

[2] Golic J D. Cryptanalysis of Alleged A5 Stream Cipher [C]//Advances in Cryptology, Proceedings of Eurocrypt’97. [S.l.]: Springer-Verlag, 1997: 239-255.

[3] Biryukov A, Shamir A, Wagner D. Real Time Cryptanalysis of A5/1 on a PC [C]//Proceedings of the 7th International Workshop on Fast Software Encryption. London: Springer-Verlag, 2000: 1-18.

[4] Biham E, Dunkelman O. Cryptanalysis of the A5/1 GSM Stream Cipher [C]//Proceedings of the First International Conference on Progress in Cryptology. London: Springer-Verlag, 2000: 43-51.

[5] Keller J, Seitz B. A Hardware-Based Attack on the A5/1 Stream Cipher [EB/OL]. 2001. http://pv.fernunihagen.de/docs/apc2001-final.pdf.

[6] Barkan E, Biham E, Keller N. Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communications [J]. Journal of Cryptology, 2008, 21(3): 392-429.

[7] Ekdahl P, Johansson T. Another Attack on A5/1 [J]. IEEE Transactions on Information Theory, 2003, 49(1): 284-289.

[8] Maximov A, Johansson T, Babbage S. An Improved Correlation Attack on A5/1 [C]//Proceedings of the 11th International Conferece on Selected Areas in Cryptography. Berlin: Springer-Verlag, 2004: 1-18.

[9] Gendrullis T, NovotnM, Rupp A. A Real-World Attack Breaking A5/1 within Hours [C]//Proceedings of the 10th International Workshop on Cryptographic Hardware and Embedded Systems. Berlin: Springer-Verlag, 2008: 266-282.

[10] Gomulkiewicz M, Kutylowski M, Vierhaus H T, et al. Synchronization Fault Cryptanalysis for Breaking A5/1 [C]//Proceedings of the 4th International Conference on Experimental and Efficient Algorithms. Berlin: Springer-Verlag, 2005: 415-427.