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行動電話不再支援A5/2密碼，這是因為它的弱點以及3GPP協會認為A5/1是強制性的。2007年7月，3GPP批准了一項更改請求，以禁止在任何新手機中使用A5/2。如果網路不支援電話所實現的A5/1或任何其他A5演算法時，則可以使用未加密的連線。說明.GSM傳輸使用突發脈衝序列來保持機密性。A5/1基於具有不規則鐘控的三個線性反饋移位暫存器 的組合。 三個移位暫存器的指定如下：最低有效位的索引為0。鐘控會使用擇多原則來決定是否對暫存器作移位操作。每個暫存器都有一個相關的鐘控位。在每個週期，檢查三個暫存器的鐘控位，並確定多數位。如果鐘控位與多數位一致，則對暫存器作移位操作。因此，在每個步驟中至少要對兩個或三個暫存器進行移位，並且每個暫存器移位的機率是3/4。比如，三個暫存器的鐘控位為分別為0、0、1。此時0為多數位，鐘控便會移位鐘控位為0的第一和二個暫存器，而第三個暫存器維持不變。最初，暫存器每一位設定為零。然後在64個週期中，根據以下方案混合64位金鑰：在週期formula_1，第formula_2位使用異或將金鑰位新增到每個暫存器的最低有效位—formula_3然後將暫存器移位。接著在用同樣的方案混合22位的幀號。然後，整個系統使用前述的鐘控機制迴圈100個週期，並丟棄輸出。完成此操作後，密碼已準備好生成輸出金鑰流的兩個114位序列，下行使用後114位。安全.A5/1已經有許多公開破解，根據已披露的內部文件，美國國家安全域性能夠對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提出了一種基於求解線性方程組的攻擊，該方法具有formula_4的時間複雜度下破解。在2000年， Alex Biryukov、Adi Shamir和David Wagner表明，可以基於時間—記憶體權衡攻擊對A5/1進行實時破密，這是基於Jovan Golic的早期工作。權衡取捨允許攻擊者利用長度為兩分鐘的已知明文，在一秒鐘內分析出金鑰，或著利用一秒鐘的已知明文在數分鐘內分析出金鑰，但是攻擊者必須首先完成一個昂貴的預處理程式，該階段需要formula_5步來計算300GB的資料。在預處理，資料需求，攻擊時間和記憶體複雜度之間可能要進行一些折衷。同年， Eli Biham和Orr Dunkelman公開了另一個對A5/1的攻擊，透過A5/1鐘控給出formula_6位的已知明文，其總工作複雜度為formula_7。在formula_8的預計算階段之後，此攻擊需要共需要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的攻擊。這些攻擊利用了GSM協議中的缺陷，並作用在使用諸如A5/2等弱較弱密碼演算法的手機上。我們強調這些攻擊是針對協議的，所以只要手機使用了較弱的密碼演算法就適用，例如，它們還適用於使用A5/1的密碼分析來攻擊使用A5/3的網路。不像以前的GSM攻擊需要不切實際的資訊，例如長時間的已知明文，我們的攻擊非常實用，不需要任何已知明文。此外，我們描述瞭如何強化攻擊的容錯性。我們的攻擊使攻擊者可以在竊聽的同時解密對話，或者留存在未來的任何時間解密。2007年，波鴻魯爾大學和基爾大學開始了一個研究專案，以開發基於FPGA的大規模並行加密加速器COPACOBANA。COPACOBANA是第一個使用快速時間—記憶體權衡技術的商業解決方案，可用於攻擊使用A5/1、A5/2演演算法的GSM語音加密，以及資料加密標準。 它還可以在無需預先計算大型彩虹表的情況下，對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破解計畫攻擊表。這些攻擊表的各部份加起來只有1.7TB。攻擊表在三個月內使用40個分散式的CUDA節點計算出來，然後由社群成員Farid Nasiri上傳到BitTorrent和Google雲端硬碟上。最近，該專案宣佈改用速度更快的ATI Evergreen程式碼，並更改了表的格式。Frank A. Stevenson宣佈使用ATI生成的表破解A5/1。愛德華·斯諾登在2013年洩露的檔案指出，NSA「可以處理A5/1的加密」。