A5/1的 故 障 分 析

左 平, 申延成, 華宏圖,3, 陳守東

(1. 吉林大學(xué) 商學(xué)院, 長(zhǎng)春 130012; 2. 空軍航空大學(xué) 基礎(chǔ)部, 長(zhǎng)春 130022; 3. 吉林大學(xué) 數(shù)學(xué)學(xué)院, 長(zhǎng)春 130012)

A5/1算法是歐洲數(shù)字蜂窩移動(dòng)電話系統(tǒng)GSM中采用的流密碼加密算法, 用于手機(jī)到基站線路上的數(shù)據(jù)和話音加密. 由于A5/1算法在GSM通信中應(yīng)用廣泛, 因此受到密碼專家的廣泛關(guān)注[1-10]. Golic[2]提出了對(duì)A5/1的兩種攻擊方法： Guess-determine攻擊和Time-memory tradeoff攻擊. 之后, Biryukov等[3]對(duì)Golic提出的第二種攻擊方法進(jìn)行了改進(jìn), 但該攻擊需要很大的存儲(chǔ)空間(約300 Gb)和很長(zhǎng)的預(yù)計(jì)算. Biham等[4]提出一種不同的攻擊方法, 該攻擊需要獲知幾十秒的密鑰流, 時(shí)間復(fù)雜度約為240. Keller等[5]基于Guess-determine攻擊提出了A5/1的基于硬件攻擊方法, 采用特殊的硬件實(shí)現(xiàn)其對(duì)A5/1的攻擊, 攻擊復(fù)雜度為241×(3/2)11, 但其成功率較低, 約為18%. Barkan等[6]提出了A5/1的唯密文Time-memory tradeoff攻擊, 但該攻擊需要很復(fù)雜的預(yù)計(jì)算. Ekdahl等[7]首次提出了A5/1的相關(guān)攻擊, 該攻擊在獲知幾分鐘密鑰流的情況下可以在PC機(jī)上幾分鐘內(nèi)恢復(fù)密鑰. Maximov等[8]利用A5/1內(nèi)部狀態(tài)與輸出比特的聯(lián)系改進(jìn)了文獻(xiàn)[7]提出的相關(guān)攻擊, 此時(shí), 獲知9.2～23 s的密鑰流便可在PC機(jī)上幾分鐘內(nèi)恢復(fù)密鑰. Gendrullis等[9]在文獻(xiàn)[5]的基礎(chǔ)上, 改進(jìn)了A5/1的攻擊, 只需獲知64比特的密鑰流便可利用特殊硬件裝置COPACOBANA在幾小時(shí)內(nèi)恢復(fù)64比特的內(nèi)部狀態(tài).

故障分析是一種間接分析方法, 在密碼系統(tǒng)物理實(shí)現(xiàn)階段引入故障得到正誤密鑰流, 再通過對(duì)正誤密鑰流的分析獲取密碼算法的密鑰信息或內(nèi)部狀態(tài). Gomulkiewicz等[10]針對(duì)A5/1特殊的鐘控模式, 提出一種再同步故障分析. 該分析采用的故障模型是在指定時(shí)刻阻止某個(gè)LFSR移位一次, 由正誤密鑰流的再同步得出引入故障前后移位方式的同步, 從而縮小此時(shí)內(nèi)部狀態(tài)的搜索范圍, 進(jìn)而進(jìn)行有效的攻擊. Guess-determine攻擊的思想較簡(jiǎn)單, 先猜測(cè)某一時(shí)刻寄存器的部分比特信息, 然后確定剩余的比特信息(主要通過解線性或非線性方程組), 進(jìn)而確定該時(shí)刻寄存器的所有比特信息. 本文結(jié)合故障攻擊與Guess-determine攻擊的思想, 提出A5/1在另一種模型下的故障分析, 通過引入故障, 可淘汰占總猜測(cè)數(shù)99.9%的錯(cuò)誤猜測(cè), 極大提高了錯(cuò)誤猜測(cè)的過濾能力, 過濾思想簡(jiǎn)單易實(shí)現(xiàn), 對(duì)剩余的錯(cuò)誤猜測(cè)經(jīng)過二次篩選便可唯一恢復(fù)正確的64內(nèi)部狀態(tài). 攻擊的復(fù)雜度約為240, 且整個(gè)攻擊只需要3個(gè)故障, 攻擊成功的概率大于99%.

1 A5/1算法

A5/1是一個(gè)同步流密碼, 初始輸入為64比特的會(huì)話密鑰和22比特的初始向量, 其中22比特的初始向量是一個(gè)公開的22比特幀序列號(hào). A5/1以幀為單位生成密鑰流(4.6 ms為一幀), 并對(duì)明文數(shù)據(jù)流進(jìn)行加密, 每幀生成228比特的密鑰流. A5/1內(nèi)部由3個(gè)長(zhǎng)度分別為19,22和23的線性反饋移位寄存器(LFSR)R1,R2,R3組成, 抽頭數(shù)分別為4,2,4, 且3個(gè)LFSR的反饋多項(xiàng)式均為本原多項(xiàng)式, 故由R1,R2,R3產(chǎn)生的序列有最長(zhǎng)周期. R1,R2,R3的移位規(guī)則由3個(gè)控制比特R1[8],R2[10],R3[10]決定, R1,R2,R3的MSBs(most significant bits)異或得到輸出密鑰流.

A5/1的每幀密鑰流按如下方式產(chǎn)生：

1) 初始化： 首先3個(gè)移位寄存器全部置0, 然后在64個(gè)時(shí)鐘周期內(nèi), 將每個(gè)LFSR都移位64次(不帶鐘控), 每次移位后將密鑰比特K[i](i=0,1,2,…,63)與每個(gè)LFSR的最低位比特異或. 其次, 在22個(gè)時(shí)鐘周期內(nèi), 將每個(gè)LFSR都移位22次(不帶鐘控), 每次移位后將22比特初始向量(幀序列號(hào))IV[i](i=0,1,2,…,21)與每個(gè)LFSR的最低位比特異或, 記初始化后的內(nèi)部狀態(tài)為Si；

2) 熱身階段： 初始化后, 由狀態(tài)Si出發(fā), 按照鐘控規(guī)則移位100個(gè)周期, 將產(chǎn)生的密鑰流丟掉, 記此時(shí)的內(nèi)部狀態(tài)為Sw；

3) 產(chǎn)生密鑰流： 由狀態(tài)Sw出發(fā), 按照鐘控規(guī)則生成228比特的密鑰流, 用于加密明文流.

A5/1的鐘控機(jī)制采用擇多邏輯, 由控制比特R1[8],R2[10]和R3[10]決定： 每次移位前計(jì)算R1[8],R2[10]和R3[10]的占多數(shù)值, 例如3個(gè)比特為(0,0,1), 則maj(0,0,1)=0. 一般情況下, 若有3個(gè)比特(a,b,c), 且把a(bǔ),b,c3個(gè)比特的多數(shù)值記為maj(a,b,c), 則maj(a,b,c)=ab⊕ac⊕bc. 此時(shí), R1移位當(dāng)且僅當(dāng)R1[8]=maj(R1[8],R2[10],R3[10]), R2移位當(dāng)且僅當(dāng)R2[10]=maj(R1[8],R2[10],R3[10]), R3移位當(dāng)且僅當(dāng)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 故障誘導(dǎo)模型

本文采用的故障誘導(dǎo)模型是在寄存器指定位置誘導(dǎo)單比特的故障, 例如R1[8]原本值為1, 引入故障后, R1[8]變?yōu)?. 為分析方便, 假設(shè)在內(nèi)部狀態(tài)為Sw時(shí)分別在R1[8], R2[10]和R3[10]誘導(dǎo)單比特故障. 于是, 便可得到1條正確的228比特密鑰流和3條錯(cuò)誤的228比特密鑰流. 利用這些正誤密鑰流恢復(fù)A5/1的內(nèi)部狀態(tài)Sw, 得知Sw后, 由文獻(xiàn)[3]的方法便可恢復(fù)加密密鑰.

2.2 分析步驟

1) 產(chǎn)生正確的228比特密鑰流S0, 且記此時(shí)的密鑰為K, 初始向量為IV.

2) 重置A5/1加密器, 即重新將密鑰K和初始向量IV初始化. 然后按照故障誘導(dǎo)模型, 在內(nèi)部狀態(tài)為Sw時(shí)分別在R1[8],R2[10]和R3[10]誘導(dǎo)單比特故障, 得到3條錯(cuò)誤密鑰流S1,S2,S3.

3) 猜測(cè)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]作為未知量, 此時(shí)針對(duì)每個(gè)具體猜測(cè)執(zhí)行以下步驟: ① 根據(jù)已知的移位方式和正確密鑰流S0得到一組關(guān)于未知量的線性方程； ② 將R1[8]變?yōu)镽1[8]⊕1, 其余猜測(cè)不變, 根據(jù)此時(shí)的移位方式和密鑰流S1同樣得到一組包含未知量的線性方程； ③ 將R2[10]變?yōu)镽2[10]⊕1, 其余猜測(cè)不變, 根據(jù)此時(shí)的移位方式和密鑰流S2同樣得到一組包含未知量的線性方程； ④ 將R3[10]變?yōu)镽3[10]⊕1, 其余猜測(cè)不變, 根據(jù)此時(shí)的移位方式和密鑰流S3同樣得到一組包含未知量的線性方程.

4) 將四組方程組合并, 考察其是否有解. 若方程組無(wú)解則猜測(cè)錯(cuò)誤, 轉(zhuǎn)3)； 否則, 執(zhí)行5).

5) 求出相應(yīng)方程組的解, 此時(shí)64比特的內(nèi)部狀態(tài)全部已知, 記為Sw*. 然后按照A5/1的鐘控模式生成新的密鑰流S0*, 將S0*與S0進(jìn)行逐比特比較, 如果出現(xiàn)某一比特不同, 則表明猜測(cè)錯(cuò)誤, 轉(zhuǎn)3)； 若S0*與S0完全一致, 則視Sw*為正確的內(nèi)部狀態(tài)Sw, 攻擊結(jié)束.

2.3 計(jì)算機(jī)模擬實(shí)現(xiàn)

在一般PC機(jī)上, 通過C語(yǔ)言編程可模擬實(shí)現(xiàn)上述攻擊.

1) 先直接給定初始的64比特內(nèi)部狀態(tài)Sw, 按照A5/1的鐘控規(guī)則生成正確的密鑰流； 然后分別改變R1[8],R2[10],R3[10], 其余比特不變, 按規(guī)則生成另外3條故障密鑰流；

2) 猜測(cè)左邊31比特的控制比特, 針對(duì)每種猜測(cè)列出方程組G, 然后判斷G是否有解；

3) 若G有解, 則統(tǒng)計(jì)相應(yīng)方程組的秩, 并解出相應(yīng)的解, 然后按鐘控規(guī)則生成228比特流, 通過比較再次篩選錯(cuò)誤的猜測(cè).

模擬實(shí)驗(yàn)顯示, 通過判斷G有無(wú)解, 能淘汰占總猜測(cè)數(shù)99.9%以上的錯(cuò)誤猜測(cè)(平均剩下220種猜測(cè)不能淘汰), 之后對(duì)有解的G進(jìn)行二次篩選后便可唯一確定正確的64比特內(nèi)部狀態(tài)Sw. 有解情形下,G的秩平均大于23, 且已知求解一個(gè)變量個(gè)數(shù)為33的方程組復(fù)雜度約為332≈210, 故全部攻擊的復(fù)雜度約為220+(33-23)+10=240, 且只需要3個(gè)故障.

事實(shí)上, 總猜測(cè)數(shù)為231, 淘汰99.9%后剩下約220個(gè)解, 最差的情況假設(shè)每個(gè)G都有232個(gè)解, 則共有252個(gè)解. 這些解對(duì)應(yīng)252條比特流, 在獨(dú)立隨機(jī)假設(shè)下, 兩條長(zhǎng)度為228的比特流完全相同的概率為2228, 故若由某一解(Sw*)產(chǎn)生的228比特流與正確密鑰流S0完全一致, 則認(rèn)為該解即為正確的內(nèi)部狀態(tài)Sw, 得知Sw后由文獻(xiàn)[3]中方法便可恢復(fù)得到A5/1的加密密鑰. 本文在運(yùn)行環(huán)境為Intel(R) Pentium(R) 4, CPU 2.80 GHz, 內(nèi)存為512 Mb的PC機(jī)上, 通過編程模擬實(shí)驗(yàn), 運(yùn)行3～4 d得到了唯一的正確內(nèi)部狀態(tài)Sw. 表1列出了幾組實(shí)驗(yàn)結(jié)果.

表1 幾組實(shí)驗(yàn)結(jié)果

*樣本Ⅰ和樣本Ⅱ未做恢復(fù)內(nèi)部狀態(tài)的實(shí)驗(yàn).

2.4 A5/1在另一種故障模型下的討論

假設(shè)指定LFSR隨機(jī)誘導(dǎo)單比特的故障, 其與固定比特位置誘導(dǎo)故障相比, 這種故障誘導(dǎo)更易實(shí)現(xiàn). 下面討論在這種模型下, 如何通過密鑰流判斷故障位置, 并提取相應(yīng)的故障密鑰流.

前面的分析中, 分別是在狀態(tài)Sw的R1[8],R2[10],R3[10]誘導(dǎo)故障, 這是因?yàn)榇藭r(shí)能最大限度地改變加密器移位方式, 從而獲得更多線性無(wú)關(guān)方程, 過濾猜測(cè)更有效. 如果在R1[8]發(fā)生故障, 則此時(shí)加密器的第一次移位方式發(fā)生了改變, 于是從第一比特開始, 輸出密鑰流便可能發(fā)生錯(cuò)誤, 在獨(dú)立隨機(jī)假設(shè)下, 每比特密鑰流發(fā)生錯(cuò)誤的概率為1/2. 記事件F： 從第一個(gè)輸出比特開始, 連續(xù)10個(gè)輸出比特皆發(fā)生錯(cuò)誤. 則此時(shí)F發(fā)生的概率P=2-10. 如果在R1[18]發(fā)生故障, 若R1不移位, 則相應(yīng)的輸出比特皆發(fā)生錯(cuò)誤； R1移位一次后, 此后的至少18比特不會(huì)發(fā)生錯(cuò)誤. 于是, 事件F發(fā)生的概率P=4-10, 因?yàn)槊看蜶1不移位的概率為1/4. 如果在R1[17]發(fā)生故障, 則只有在第一個(gè)周期R1移位, 且之后的9個(gè)周期R1都不移位, 事件F才可能發(fā)生, 故事件F發(fā)生的概率P=(3/4)×4-9. 如果在R1[16]發(fā)生故障, 則顯然事件F不可能發(fā)生. 類似地, 在其余位置發(fā)生故障, 事件F都不可能發(fā)生. 因此, 若在R1[8]發(fā)生故障, 則所得故障密鑰流前10比特皆發(fā)生錯(cuò)誤的概率遠(yuǎn)大于在R1其余位置發(fā)生故障的情況. 于是, 若得到的故障密鑰流前10比特皆發(fā)生錯(cuò)誤, 則認(rèn)為故障發(fā)生在R1[8], 判斷錯(cuò)誤的概率約為4-10/2-10≈0.1%. 此時(shí), 隨機(jī)獲得一條在R1[8]發(fā)生故障的密鑰流約需隨機(jī)誘導(dǎo)故障19×210次.

在LFSR R2和R3誘導(dǎo)隨機(jī)故障的討論類似于R1的討論. 判斷故障發(fā)生在R2[10]和R3[10]當(dāng)且僅當(dāng)?shù)玫降妮敵雒荑€流前10比特皆出錯(cuò), 且判斷錯(cuò)誤的概率均約為0.1%.

分別獲得在R1[8],R2[10],R3[10]發(fā)生故障對(duì)應(yīng)的密鑰流后, 類似于第一種模型下的分析, 便可恢復(fù)A5/1的密鑰, 且成功概率約為(1-0.1%)3>99%, 隨機(jī)獲取需要的故障密鑰流需要隨機(jī)誘導(dǎo)故障(19+22+23)×210≈216次.

綜上所述, 本文給出了A5/1的一種新的故障分析方法, 先給出了其在固定比特位置誘導(dǎo)故障模型下的分析, 再將其推廣到隨機(jī)位置誘導(dǎo)故障模型下, 平均可淘汰占總猜測(cè)數(shù)99.9%的錯(cuò)誤猜測(cè), 最終可完全恢復(fù)A5/1的內(nèi)部狀態(tài). 整個(gè)攻擊只需要3個(gè)故障, 復(fù)雜度約為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.