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

## 說明

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）的組合。 三個移位暫存器的指定如下：

最低有效位的索引為 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）.