A5/1

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算法時，則可以使用未加密的連接。

某些攻擊需要昂貴的預處理階段，在此階段之後幾分鐘或幾秒鐘即可破解密碼。早期發現的漏洞只能在已知明文的前提下利用，並且是被動攻擊。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的後一半。，這是基於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密碼的攻擊。 作者聲稱，可用於攻擊使用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的加密」。

參考來源
其他來源
*
*

外部連結
*
*
*
*
*
*