基本介紹
- 中文名：EFF DES破解機
- 外文名：EFF DES cracker
- 提出時間：1998年
- 提出者：電子前哨基金會
- 用途：DES加密算法
- 學科：密碼學
背景,密鑰長度爭議,對密碼學的管制,DES挑戰賽,技術,
背景
密鑰長度爭議
DES加密算法的密鑰長度為56位，這意味著加密時存在2個密鑰可供選擇，即7.2萬萬億（72,057,594,037,927,936）種可能性。但是，DES依然長期面臨“密鑰長度過短、安全性不足”的批評。
早在1975年算法公開之初，著名的史丹福大學密碼學家馬丁·赫爾曼與惠特菲爾德·迪菲就批評DES算法易被暴力破解，因此不安全，惟有將密鑰長度提升到至少128位才能保證安全。二人還構想了一台可在一天內測試所有密鑰的機器，需要的成本為2000萬美元，並指出這對於美國國家安全局（NSA）等情治單位而言並非是一筆很大的開銷，並認為成本在10年後還會進一步下降到20萬美元。
在隨後的20年間，晶片的價格確實不斷下降、性能不斷提升，使電子前哨基金會這樣的小型非營利組織也具有了破解DES的能力。
對密碼學的管制
在20世紀，以NSA為首的美國政府以及盟友為了維護自身的利益，對密碼學進行嚴格管制，限制密碼學的傳播並降低現有系統的安全性，甚至加入後門。例如，一位在80年代曾參與過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的安全性僅僅是原密鑰長度的兩倍（2），並非三倍（2）。可見三重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天時間對所有可能的密鑰進行完整的搜尋，但實際使用時，破解出正確的密鑰往往只需要花費一半的時間。
