A5/1

A5/1

概述
首次发布	1994年對外洩漏總體設計 1999年通過反向工程破解並公開 （1987年開發）
系列	A5/2、A5/3（KASUMI）
密码细节
密钥长度	64或54位
状态长度	114位
最佳公开破解
通過對初始化密鑰程序的攻擊，可以利用數秒鐘的已知明文在少於一分鐘的時間內攻破 針對GSM協議的攻擊可在個人電腦的處理能力下，在數秒鐘內分析出密鑰。

A5/1是用於在GSM標準中提供行動通信保密性的流密碼，它是指定用於GSM的七個加密算法之一。A5/1的設計最初沒有對外公開，但由於洩漏和逆向工程而廣為人知。已經確定了A5/1中存在許多嚴重缺陷。

歷史和用法

A5/1在歐洲和美國使用。A5/2為A5/1削弱過的版本，用於出口到某些地區。A5/1是在1987年開發的，當時尚未考慮在歐洲以外使用GSM，而A5/2是在1989年開發的。儘管設計最初都是保密的，但總體設計在1994年被洩露。該算法完全由Marc Briceno於1999年從GSM電話利用反向工程取得。在2000年時，大約1.3億個GSM客戶端依賴A5/1來保護其語音通信的機密性；到2014年，這一數字增加為72億。

安全研究人員Ross Anderson在1994年報導說：「在1980年代中期，北約訊號情報機構之間就GSM的加密是否應該擁有較高的安全性，有著激烈的爭論。德國方面認為應該如此，因為的德國邊界有很長一部分與華沙公約組織接壤，但其他北約成員國沒有這個狀況，目前採用的演算法是法國設計。」

A5/2

A5/2是用於出口，相對於A5/1比較弱。它是指定用於用於GSM的七種A5加密算法之一。

該密碼基於具有不規則時鐘的四個線性反饋移位寄存器和非線性組合器的組合。

1999年，Ian Goldberg和David A. Wagner在發布A5/2的同一個月中對其進行了加密分析，結果表明該A5/2非常脆弱，以至於低端設備都可能會實時地破解它。

自2006年7月1日起，GSMA（GSM協會）強制要求GSM移動電話不再支持A5/2密碼，這是因為它的弱點以及3GPP協會認為A5/1是強制性的。2007年7月，3GPP批准了一項更改請求，以禁止在任何新手機中使用A5/2。如果網絡不支持電話所實現的A5/1或任何其他A5算法時，則可以使用未加密的連接。

說明

A5/1流密碼使用三個LFSR。如果某個寄存器的鐘控位（橙色）和另一個寄存器的鐘控位相同或著三個寄存器的鐘控位都相同，則對該寄存器作移位操作

GSM傳輸使用突發脈衝序列（Bursts）。一個典型的信道在一個方向上，每4.615毫秒發送一個突發脈衝（帧），每一幀包含114個可用於信息的位元。A5/1用於為每個幀產生密鑰流的114位序列，該序列在調製之前與114位進行異或 。使用64位密鑰和公開的22位幀號初始化A5/1。 早期的GSM使用Comp128v1生成密鑰，將10個密鑰位固定為零，因此有效密鑰長度為54位。通過引入Comp128v3（可產生正確的64位密鑰）可以糾正此缺陷。 當以GPRS/EDGE模式工作時，更高帶寬的無線電調製允許更大的348位幀，然後在流密碼模式下使用A5/3（KASUMI）來保持機密性。

A5/1基於具有不規則鐘控的三個線性反饋移位寄存器 （LFSR）的組合。 三個移位寄存器的指定如下：

寄存器編號	寄存器位數	反饋方程	鐘控位	抽頭
1	19	$x^{19}+x^{18}+x^{17}+x^{14}+1$	8	13, 16, 17, 18
2	22	$x^{22}+x^{21}+1$	10	20, 21
3	23	$x^{23}+x^{22}+x^{21}+x^{8}+1$	10	7, 20, 21, 22

最低有效位的索引為0。

鐘控會使用擇多原則來決定是否對寄存器作移位操作。每個寄存器都有一個相關的鐘控位。在每個週期，檢查三個寄存器的鐘控位，並確定多數位（0或者1）。如果鐘控位與多數位一致，則對寄存器作移位操作。因此，在每個步驟中至少要對兩個或三個寄存器進行移位，並且每個寄存器移位的概率是3/4。

比如，三個寄存器的鐘控位為分別為0、0、1。此時0為多數位，鐘控便會移位鐘控位為0的第一和二個寄存器，而第三個寄存器維持不變。

最初，寄存器每一位設置為零。然後在64個週期中，根據以下方案混合64位密鑰：在周期$0\leq {i}<64$，第${i}$位使用異或將密鑰位添加到每個寄存器的最低有效位—

$R[0]=R[0]\oplus K[i].$

然後將寄存器移位。

接著在用同樣的方案混合22位的幀號。然後，整個系統使用前述的鐘控機制循環100個週期，並丟棄輸出。完成此操作後，密碼已準備好生成輸出密鑰流的兩個114位序列，下行（從基地台接收到的訊號）使用前114位，上行（回傳給基地台的訊號）使用後114位。

安全

手機屏幕上的消息，帶有關於未加密的警告

A5/1已經有許多公開破解，根據已披露的內部文檔，美國國家安全局（NSA）能夠對A5/1消息進行例行解密。

某些攻擊需要昂貴的預處理階段，在此階段之後幾分鐘或幾秒鐘即可破解密碼。早期發現的漏洞只能在已知明文的前提下利用，並且是被動攻擊。2003年，發現了更嚴重的漏洞，可以在唯密文的前提下利用，或采用主動攻擊。在2006年，Elad Barkan、Eli Biham和Nathan Keller展示了針對A5/1， A5/3甚至是GPRS的攻擊，攻擊者可以竊聽GSM手機訊號，實時解密或保存訊息，以在未來任何時間解密。

根據Jan Arild Audestad教授的說法，在1982年開始的標準化過程中，最初提出A5/1的密鑰長度為128位。當時，預計128位的安全性足以滿足為來十五年的需求。現在的研究人員相信，在量子計算出現之前，128位實際上仍然是安全的。Audestad、Peter van der Arend和Thomas Haug表示英國堅持使用較弱的加密，Haug表示英國代表告訴他這是安全的。為了讓英國的特勤人員更容易竊聽，英國建議使用48位的密鑰長度，而西德則希望使用安全性更高的加密的來防止東德間諜活動。最後折衷方案是54位的密鑰長度。

已知明文攻擊

1994年， Ross Anderson提出了對A5/1的首次攻擊。安德森的基本思想是猜測寄存器R1和R2的完整內容以及寄存器R3的一半。 這樣，就可以確定所有三個寄存器的時鐘，並且可以計算R3的後一半。

在1997年，Jovan Golic提出了一種基於求解線性方程組的攻擊，該方法具有$2^{40.16}$的時間複雜度下破解（單位表示為所需線性方程組解的個數）。

在2000年， Alex Biryukov、Adi Shamir和David Wagner表明，可以基於時間—記憶體權衡攻擊對A5/1進行實時破密，這是基於Jovan Golic的早期工作。權衡取捨允許攻擊者利用長度為兩分鐘的已知明文，在一秒鐘內分析出密鑰，或著利用一秒鐘的已知明文在數分鐘內分析出密鑰，但是攻擊者必須首先完成一個昂貴的預處理程序，該階段需要$2^{48}$步來計算300GB的數據。在預處理，數據需求，攻擊時間和內存複雜度之間可能要進行一些折衷。

同年， Eli Biham和Orr Dunkelman公開了另一個對A5/1的攻擊，通過A5/1鐘控給出$2^{20.8}$位的已知明文，其總工作複雜度為$2^{39.91}$。在$2^{38}$的預計算階段之後，此攻擊需要共需要32GB的內存。

Ekdahl和Johansson發表了有關初始化過程的攻擊，該攻擊可通過兩到五分鐘的已知明文在幾分鐘內破解A5/1。此攻擊不需要預處理階段。2004年，包含Maximov的幾名研究人員將該結果改進為需要「少於一分鐘的計算時間和幾秒鐘的已知明文」的攻擊。 Elad Barkan和Eli Biham在2005年進一步改善了這一攻擊。

針對GSM系統的攻擊

在2003年，Barkan 等人。發表了一些有關GSM加密的攻擊，是首次發現主動攻擊。可以說服GSM手機短暫使用弱得多的A5/2密碼。在使用同樣的密鑰下，相比於比較強健的A5/1，A5/2更容易被攻破。在針對A5/1的第二次攻擊中概述，唯密文的前提下可以使用時間—記憶體權衡攻擊，這需要大量的預計算。

2006年， Elad Barkan、Eli Biham和Nathan Keller出版了他們2003年論文的完整版本，其中包括針對A5/X密碼的攻擊。 作者聲稱：

我們將介紹針對GSM加密通信非常實用的唯密文攻擊，以及對GSM協議的各種主動攻擊。這些攻擊甚至能破壞使用所謂“牢不可破”加密的GSM網絡。我們首先說到對A5/2的唯密文攻擊，該攻擊只需要幾十毫秒的加密手機通訊，利用個人電腦在數秒鐘即可分析出正確的密鑰。我們將此攻擊擴展為對A5/1的（更複雜的）唯密文攻擊。我們接著描述針對使用了A5/1，A5/3的網路協議，或甚至是GPRS協議的（主動）攻擊。這些攻擊利用了GSM協議中的缺陷，並作用在使用諸如A5/2等弱較弱密碼算法的手機上。我們強調這些攻擊是針對協議的，所以只要手機使用了較弱的密碼算法就適用，例如，它們還適用於使用A5/1的密碼分析來攻擊使用A5/3的網絡。不像以前的GSM攻擊需要不切實際的信息，例如長時間的已知明文，我們的攻擊非常實用，不需要任何已知明文。此外，我們描述瞭如何強化攻擊的容錯性。我們的攻擊使攻擊者可以在竊聽的同時解密對話，或者留存在未來的任何時間解密。

2007年，波鴻魯爾大學和基爾大學開始了一個研究項目，以開發基於FPGA的大規模並行加密加速器COPACOBANA。COPACOBANA是第一個使用快速時間—記憶體權衡技術的商業解決方案，可用於攻擊使用A5/1、A5/2演算法的GSM語音加密，以及資料加密標準（DES）。 它還可以在無需預先計算大型彩虹表的情況下，對GSM進行暴力破解。

2008年， 「The Hackers Choice」發起了一個項目，旨在對A5/1進行實用的攻擊。攻擊需要構建大約3TB的彩虹表。通過姊妹計畫中的掃描算法，該小組希望能夠在大約3-5分鐘內，從任何使用A5/1加密的GSM通聯記錄，或著SMS簡訊中分析出加密密鑰，從而可以聽取通聯記錄以及清楚的閱讀簡訊。但是這些彩虹表沒有公開。

密碼學家Karsten Nohl和SaschaKrißler在2009年黑帽安全會議上發表了一個類似的A5/1破解項目。通過Nvidia圖形處理器通用計算和P2P分佈式計算體系，創建了彩虹表。從2009年9月中旬開始，該項目運行了12個Nvidia GeForce GTX 260的運算量。根據作者的說法，此攻擊可用於密鑰大小最大為64位的任何加密算法。

Chris Paget和Karsten Nohl在2009年12月發布了針對A5/1的「A5/1破解計畫攻擊表（A5/1 Cracking Project attack tables）」。這些表結合了壓縮技術，包括彩虹表和特徵點鏈（distinguished point chains）。這些攻擊表的各部份加起來只有1.7TB。攻擊表在三個月內使用40個分佈式的CUDA節點計算出來，然後由社區成員Farid Nasiri上傳到BitTorrent和Google雲端硬碟上。最近，該項目宣布改用速度更快的ATI Evergreen代碼，並更改了表的格式。Frank A. Stevenson宣布使用ATI生成的表破解A5/1。

愛德華·斯諾登在2013年洩露的文件指出，NSA「可以處理A5/1的加密」。

其他來源

• Rose, Greg. A precis of the new attacks on GSM encryption (PDF). QUALCOMM Australia. 2003-09-10 [2020-02-21]. （原始内容 (PDF)存档于2011-09-27）. 
• Maximov, Alexander; Thomas Johansson; Steve Babbage. An Improved Correlation Attack on A5/1. Selected Areas in Cryptography 2004. 2004: 1–18. 

外部連結

• Briceno, Marc; Ian Goldberg; David Wagner. A pedagogical implementation of the GSM A5/1 and A5/2 "voice privacy" encryption algorithms. 1999-10-23 [2020-02-21]. （原始内容存档于2018-10-08）. 
• Huge GSM flaw allows hackers to listen in on voice calls. 2009-08-25 [2020-02-21]. （原始内容存档于2009-10-14）. 
• Horesh, Hadar. Technion team cracks GSM cellular phone encryption (PDF). Haaretz. 2003-09-03 [2020-02-21]. （原始内容 (PDF)存档于2016-03-03）. 
• Barkan, Elad; Eli Biham; Nathan Keller. Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication (Technical Report CS-2006-07). July 2006 [2020-09-24]. （原始内容存档于2019-12-27）. 
• Nathan Keller's Homepage. [2020-02-21]. （原始内容存档于2008-06-04）. 
• Animated SVG showing A5/1 stream cypher. [2020-02-21]. （原始内容存档于2012-03-26）.