DES破解机

**EFF DES 破解機**（英語：EFF DES cracker）是電子前哨基金會（EFF）在 1998 年建造的機器，用於暴力破解美國政府的資料加密標準，即 DES 加密演算法，暱稱「**深譯**」（英語：Deep Crack）。這台機器能夠對 DES 金鑰空間中所有的金鑰逐一進行嘗試，從而將密文破解，其目的在於證明 DES 的金鑰長度不足，不能保證安全。

本機器的相關技術資料，包括原理圖、電路圖、晶片 VHDL 原始碼、模擬器原始碼，均被電子前哨基金會公開發表在《破解 DES》一書中，並使用了公有領域許可協定，允許任何人複製、使用與修改。為了避開美國政府的出口管制，原始碼是以書本形式而不是電子形式發布的。書中的原始碼含有機器可讀的元資料，方便讀者使用 OCR 將原始碼錄入電腦。

## 背景

### 金鑰長度爭議

DES 是最早的電腦加密演算法之一，它在政府、金融、網路等許多領域都得到了廣泛應用。並且，該加密演算法是美國聯邦政府的一項標準，美國政府鼓勵使用 DES 加密除了國家機密之外的任何敏感訊息。

DES 加密演算法的金鑰長度為 56 位，這意味著加密時存在 256 個金鑰可供選擇，即 7.2 萬萬億（72,057,594,037,927,936）種可能性。但是，DES 依然長期面臨「金鑰長度過短、安全性不足」的批評。

早在 1975 年演算法公開之初，著名的史丹福大學密碼學家馬丁・赫爾曼與惠特菲爾德・迪菲就批評 DES 演算法易被暴力破解，因此不安全，惟有將金鑰長度提升到至少 128 位元才能保證安全。二人還構想了一台可在一天內測試所有金鑰的機器，需要的成本為 2000 萬美元，並指出這對於美國國家安全局（NSA）等情報機構而言並非是一筆很大的開銷，並認為成本在 10 年後還會進一步下降到 20 萬美元。

在隨後的 20 年間，晶片的價格確實不斷下降、效能不斷提升，使電子前哨基金會這樣的小型非營利組織也具有了破解 DES 的能力。

### 對密碼學的管制

在 20 世紀，以 NSA 為首的美國政府以及盟友為了維護自身的利益，對密碼學進行嚴格管制，限制密碼學的傳播並降低現有系統的安全性，甚至加入後門。例如，一位在 1980 年代曾參與過 GSM 研發的專家表示，為保護手機通話不被竊聽，原計劃採用 128 位元加密進行保護。但隨後遭到英國政府方面的施壓，使最終的 A5/1 加密演算法被迫削弱為 54 位元，團隊中的許多專家對此十分憤怒。時至 90 年代末，隨著網際網路與電子商務的興起，使用密碼學保護公民隱私與商業訊息的訴求，與美國政府管制政策之間的矛盾逐漸升溫。媒體與公眾將這段歷史時期統稱為密碼戰爭。

直到 1998 年 DES 已被兩次破解後，美國聯邦調查局局長路易斯・弗里依然堅持對密碼學的嚴格管制，始終不承認 DES 並不安全：

## DES 挑戰賽

由於上述原因，RSA 安全公司希望以實際行動向公眾展示 DES 的金鑰長度過短，時下已不能保證安全性，因此在 1997 年舉辦了首屆 DES 挑戰賽，成功者可獲得一萬美元的獎金。第一屆大賽被來自科羅拉多州洛夫蘭的洛克・沃瑟所帶領的團隊破解成功，耗時 96 天。接著，RSA 安全公司隨後舉辦了第二屆挑戰賽，其中的初賽由網際網路最早的分散式計算平台 distributed.net 的 22,000 名志願者們挑戰成功。他們使用自己的個人電腦參與計算，共歷時 39 天，於 1998 年 2 月成功破解密文，解密後得到「機密訊息為：人多好辦事」（The secret message is: Many hands make light work）的文字。

即使在 DES 已被兩次破解以後，聯邦調查局局長路易斯・弗里依然以「破譯時間過長，沒有意義」為理由，拒絕承認 DES 已不安全。因此，RSA 再次發起了第二次挑戰賽的複賽。1998 年，電子前哨基金會建造了「深譯」（名字來自 IBM 的「深藍」西洋棋電腦），總共花費不超過 250,000 美元。為了回應第二屆 DES 挑戰賽的號召，「深譯」加入了 1998 年 7 月 15 日舉行的複賽，僅用 56 小時成功破解了 DES 加密的訊息，獲得了 10,000 美元獎金。破譯後得到「機密訊息為：是時候讓 128 位元，192 位與 256 位金鑰登場了」（The secret message is: It's time for those 128-, 192-, and 256-bit keys）的文字。此次暴力破解攻擊展現了破解 DES 是非常可行的計劃，多數政府和大型企業完全有能力建造一台類似「深譯」的機器。

六個月之後，電子前哨基金會回應了 RSA 安全公司舉辦的第三屆挑戰賽，並與 distributed.net 團隊合作破譯了另一則 DES 加密的訊息，再次獲得了 10,000 美元。這次的整個破譯過程不到一天，僅用 22 小時 15 分，於 1999 年 1 月 19 日完成破解。

同年 10 月，美國政府宣布 DES 標準不會被廢除，但推薦使用其增強版三重 DES 替代。然而，這需要將 DES 反覆執行三次，使計算速度更加緩慢。而且與直覺相反，由於中途相遇攻擊的存在，三重 DES 的安全性僅僅是原金鑰長度的兩倍（2112），並非三倍（2168）。可見三重 DES 的安全性只有 112 位元，離密碼學界所推薦的 128 位元仍有一定差距，而且還需要高昂的計算成本，將其應用於網際網路時不能令人滿意。

2002 年 5 月 26 日，進階加密標準（即 AES）正式取代了 DES 資料加密標準成為了新的聯邦政府標準。不同於 DES，AES 不僅將金鑰長度提升至 128 位元與 256 位，還大幅提升了計算速度，並廣泛應用於今日的網際網路。

## 技術

「深譯」由密碼學研究公司、先進無線科技公司（Advanced Wireless Technologies）與電子前哨基金會聯合設計，總設計師是密碼學研究公司的主席保羅・科奇。先進無線科技公司製造了 1856 片客製化晶片（代號「深譯」，型號 AWT-4500），分別組裝在 29 塊電路板上，每塊電路板 64 片。這些電路板再被分別放入 6 個模組，然後安裝在一台改裝過的 Sun-4/470 工作站的機箱中。為了協助金鑰的搜尋工作，另外還使用了一台執行 Linux 作業系統的個人電腦負責控制機器。整台機器每秒鐘能嘗試 900 億個金鑰，共需要 9 天時間對所有可能的金鑰進行完整的搜尋，但實際使用時，破解出正確的金鑰往往只需要花費一半的時間。

本機器的相關技術資料，包括原理圖、電路圖、晶片 VHDL 原始碼、模擬器原始碼，均被電子前哨基金會公開發表在《破解 DES》一書中，並使用了公有領域許可協定，允許任何人複製、使用與修改。為了避開美國政府的出口管制，原始碼是以書本而不是電子形式發布的。書中的原始碼含有機器可讀的元資料，方便讀者使用 OCR 將原始碼錄入電腦。

2006 年，又一台客製化硬體攻擊 DES 加密的機器問世，名為 COPACOBANA（為英語：COst-optimized PArallel COdeBreaker 的縮寫，意為「低成本並列密碼破譯機」）。該機器得益於積體電路技術的進步，採用 FPGA 的設計，進一步降低了破解 DES 的成本。2012 年 7 月，安全研究人員大衛・赫爾頓（David Hulton）與莫克西・馬林斯佩克（Moxie Marlinspike）公布了一個通過暴力破解 DES 加密從而破解 MS-CHAPv2 協定的雲端運算工具，這讓普通大眾能夠在 24 小時之內利用一對已知的明文和密文破解 DES 金鑰。

## 參考文獻