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.