破解 GSM 編密系統歷史簡述

GSM 是目前世界上最廣為使用的行動電話技術。截至 2002 年 12 月為止,在全球超過 191 個國家中共有 7 億 8750 萬個電話用戶,佔了數位無線通訊市場的 71% 強。

當然 GSM 系統結合了保密安全機制,電信 Operator 與用戶藉由這些編密機制來保護他們通話的隱私與完整性。前段先以身分認證機制來讓 subscriber 連上網路,接著再以加密演算法來為用戶們的通話內容做加密保護。

GSM 主要使用了三種加密演算法:A5 是 stream-cipher(註:以網路電話為例,雖然便利,但它以網路作為傳輸媒介,很容易被第三者竊聽,因此在這些規格中均有定義保護封包的技術如 PGP、IPSec 等,這些方式都是以塊狀密碼系統(Block Cipher System)加密資料,然而塊狀密碼系統極為複雜且耗時,將它使用在即時系統中可能造成封包傳送上的延誤。而串流密碼系統(Stream Cipher System)有別於塊狀密碼系統,是種 架構相當簡單且加密速度非常快速的密碼系統,非常適用處理即時資料,目前在無線通訊 GSM 系統中的加密演算法 A5 即是使用此種系統架構)、A3 是 authentication algorithm 和 A8 為 key agreement algorithm。其中 A3 與 A8 並沒有在 GSM 標準規範中被定義,而只有提到它們兩者的外部介面該如何使用與統一。每家 Operator 可以選擇自己想用的加密演算法設計,然而大部分的 Operators 都採用在 GSM MoU 中提出的 COMP128 演算法系統。雖然這個演算法沒有被公開發表過,不過其相關說明仍可以在此找到。而且也被人嘗試破解分析過,因為這個破解可以解出手機與網路間的 Master Key,因此可以在網路上複製一個你的 GSM 手機身分出來。

A5 演算法是 GSM 標準規範中的一部分,但是它從來沒有被公開過技術內容與細節。A5 演算法有兩個版本:A5/1 是 strong 版本,有出口限制;A5/2 是 weak 版本,沒有出口限制。A5/1 與 A5/2 兩個演算法的正確設計後來被 Marc Briceno、Ian Goldberg 和 David Wagner 用逆向工程給破解出來

clone
當年用來逆向工程破解出 A5 演算法的實機平台

後來還有一個新版本 A5/3 演算法,不過尚未被 GSM 標準所採用。近來有人注意到,GSM 系統也採用了 block-cipher KASUMI,值得一提的是,未來的第三代行動通訊網路(3GPP)也採用了類似 KASUMI 演算法的加密系統。A5/1 接續被好幾組研究團隊嘗試破解分析過,我不多著墨,把焦點放在 A5/2 上頭,也算是配合下一篇文章的方向。

A5/2 演算法被逆向工程解出來後,也馬上就被 Goldberg、Wagner 與 Green 等人研究破解與分析,並於 1999 年發表論文。他們的攻擊方式是為人所熟知的明文(plaintext)攻擊,所以他們需要得知兩個 GSM frames 裡頭明文之間的差異處。要進行這項攻擊所需的時間複雜度接近 216 點積(dot product)上 114-bit 大小的向量(而且後來這篇以色列研究學者發現這個破解在大約一半左右的情況下都是失敗的,因為它有個限制條件就是在初始化 cipher 後,R4 參數中的第 11 個 bit 必須為零)。後來 Petrovic 等人又提出新的破解方式,可以做到說把數百個已知且有序的 bits 灌進 A5/2 加解密器後,能有極高的機率成功預測 A5/2 cipher 的 output。但是,後來的這個破解法並沒有包含破解 A5/2 演算法的初始金鑰值,因此並沒有辦法利用他們提出來的方法當作進一步破解用的建置方塊,且其複雜度經人預估,也有 400×719 size 大小的 217 階高斯化簡矩陣這麼複雜。

那麼,有沒有更好的破解法呢?

更多關於 GSM 系統安全性相關資訊,可以參考 GSM SECURITY 網站。


This article has been published @ September 23, 2003 | Restored @ April 22, 2006 by Google + WayBackMachine

歷史上的今天

About mtlin

I'm easygoing and sometimes sentimental, also can be very funny. Geek style but social. A Blogger, a Wikipedian and an Engineer.
This entry was posted in Technology, Wireless and tagged , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , . Bookmark the permalink.

2 Responses to 破解 GSM 編密系統歷史簡述

  1. Pingback: Morton’s Weblog » Blog Archive » GSM Security Broken

  2. Pingback: Cable Network Operator

Leave a Reply

Your email address will not be published.