作者：DAVID HULTON，DAVID PELLERIN

六十多年來(lái)，密碼學(xué)（包括代碼創(chuàng)建、分析和破解）一直是計(jì)算技術(shù)最重要的驅(qū)動(dòng)力之一。事實(shí)上，現(xiàn)代計(jì)算機(jī)的發(fā)展在很大程度上歸功于第二次世界大戰(zhàn)期間和之后的計(jì)算機(jī)先驅(qū)艾倫·圖靈和克勞德·香農(nóng)等密碼學(xué)研究。

在無(wú)處不在的有線和無(wú)線通信的現(xiàn)代時(shí)代，密碼學(xué)研究再次導(dǎo)致計(jì)算的巨大進(jìn)步。隨著越來(lái)越多的個(gè)人、商業(yè)、軍事和國(guó)家安全數(shù)據(jù)在網(wǎng)上傳輸和管理，惡作劇的機(jī)會(huì)越來(lái)越多，因此更強(qiáng)大的加密方法至關(guān)重要。對(duì)改進(jìn)加密的研究需要分析和審計(jì)當(dāng)今廣泛使用的系統(tǒng)以及未來(lái)的系統(tǒng)。

以下討論的重點(diǎn)是如何使用廣泛使用的現(xiàn)場(chǎng)可編程門陣列（FPGA）集群來(lái)加速加密算法，特別是代碼破解。我們首先解釋了加密計(jì)算背后的挑戰(zhàn)，然后介紹了一個(gè)案例研究，說(shuō)明FPGA加速方法如何加速?gòu)V泛使用的數(shù)據(jù)安全方法（包括DES、WPA、WEP和GSM）的解密，并將基于FPGA的方法與更傳統(tǒng)的面向軟件的方法進(jìn)行比較。最后，我們證明了包含在單個(gè) 4U 機(jī)箱中且功耗低于 1，400 W 的商用 FPGA 集群提供的計(jì)算相當(dāng)于 1，000 多個(gè)雙核處理器。

白帽子與黑帽子

代碼破解是一項(xiàng)有爭(zhēng)議的活動(dòng)，對(duì)于那些追求它來(lái)訪問(wèn)其他禁區(qū)信息的人來(lái)說(shuō)，會(huì)帶來(lái)重大的法律風(fēng)險(xiǎn)。同樣，對(duì)于那些成為此類入侵目標(biāo)的人來(lái)說(shuō)，存在財(cái)務(wù)損失或敏感數(shù)據(jù)泄露的重大風(fēng)險(xiǎn)。所有數(shù)字?jǐn)?shù)據(jù)用戶都有理由擔(dān)心他們所依賴的系統(tǒng)是否容易受到未經(jīng)授權(quán)的訪問(wèn)。出于這個(gè)原因，許多組織和政府利用密碼學(xué)專家進(jìn)行安全審計(jì)。這些專業(yè)黑客在其所有者的許可下，合法地試圖闖入系統(tǒng)，測(cè)試商業(yè)和公共數(shù)據(jù)網(wǎng)絡(luò)安全。

在審計(jì)一個(gè)可能安全的系統(tǒng)時(shí)，“白帽”黑客將部署與“黑帽”黑客大致相同的軟件算法和硬件。此活動(dòng)稱為滲透測(cè)試，旨在查找和報(bào)告數(shù)據(jù)安全策略中的漏洞。是否使用了不充分或過(guò)時(shí)的加密方法？系統(tǒng)用戶通常選擇弱密碼嗎？是否存在操作系統(tǒng)或應(yīng)用程序?qū)勇┒矗?/p>

這種破解的另一個(gè)合法原因是恢復(fù)丟失和忘記的密碼。由于密碼錯(cuò)誤而導(dǎo)致數(shù)據(jù)鎖定和不可用，每年會(huì)導(dǎo)致大量的生產(chǎn)力損失。機(jī)密文件和整個(gè)數(shù)據(jù)庫(kù)可能變得毫無(wú)用處，甚至對(duì)其合法所有者也是如此。因此，政府、行業(yè)和學(xué)術(shù)界每天都使用基于黑帽破解方法的密碼恢復(fù)軟件工具，以重新獲得對(duì)關(guān)鍵數(shù)據(jù)的訪問(wèn)權(quán)限。

加密計(jì)算的挑戰(zhàn)

構(gòu)成這些安全破解和密碼恢復(fù)工具基礎(chǔ)的算法需要大量的計(jì)算能力，并且可能需要很長(zhǎng)的運(yùn)行時(shí)間才能完成。事實(shí)上，雖然在一臺(tái)計(jì)算機(jī)上運(yùn)行的廣泛可用的軟件工具可以在幾分鐘內(nèi)破解基于字典的密碼，但恢復(fù)相對(duì)強(qiáng)大的密碼可能需要多年的迭代計(jì)算。

近年來(lái)，計(jì)算機(jī)集群通過(guò)添加GPU和FPGA加速器而得到增強(qiáng)。這些設(shè)備憑借其并行結(jié)構(gòu)，可以為許多計(jì)算機(jī)密集型算法（包括密碼恢復(fù)）提供實(shí)質(zhì)性的加速。

由于 GPU 起源于標(biāo)準(zhǔn)現(xiàn)成計(jì)算機(jī)系統(tǒng)的圖形處理，因此大多數(shù)程序員都廣為人知。然而，盡管它們可以為代碼破解算法提供顯著的性能提升［1］，但 GPU 并未針對(duì)此應(yīng)用進(jìn)行很好的優(yōu)化。特別是，數(shù)字加密標(biāo)準(zhǔn) （DES） 和 SAFER（用于藍(lán)牙）等按位加密算法不適合在 CPU 或 GPU 上實(shí)現(xiàn)高效實(shí)現(xiàn)。相對(duì)于正在執(zhí)行的計(jì)算，GPU 還需要大量功率。GPU 提供高水平的加速，但功耗成本很高。相反，F(xiàn)PGA提供了一個(gè)可行的替代方案。

案例研究：用于高性能密碼破解的 FPGA

為了 演示 FPGA 如何 滿足 更快 密碼 恢復(fù) 的 需求， 我們 選擇 了 一組 具有 代表性 的 密碼 破解 問(wèn)題， 并在 FPGA 集群 上 部署 了 高度 并行 的 恢復(fù) 算法。

本演示中使用的系統(tǒng)包括包含 77 個(gè) Xilinx Virtex-5 FPGA 器件的 Pico SC3 集群、包含多達(dá) 176 個(gè) Spartan-3 FPGA 的 SC4 集群，以及包含 72 個(gè)更大容量 Spartan-6 FPGA 的 SC5 集群。在所有情況下，這些集群都安裝在一個(gè)低于 1，400 W 的 4U 機(jī)箱圖紙中。 使用 FPGA 硬件設(shè)計(jì)方法和工具，我們成功部署了以下加密方法的恢復(fù)算法：

文件保險(xiǎn)箱

FileVault 基于高級(jí)加密標(biāo)準(zhǔn) （AES），為 Apple Macintosh 操作系統(tǒng)提供加密文件系統(tǒng)。恢復(fù)文件保險(xiǎn)箱密碼需要使用 SHA-1 哈希函數(shù)對(duì)可能的密碼進(jìn)行數(shù)千次哈希處理。此派生方法稱為基于密碼的密鑰派生函數(shù) （PBKDF2），用于嘗試解密 FileVault 映像。使用 72-FPGA SC5 集群，與在 2.93 GHz 的英特爾酷睿 i7 處理器上運(yùn)行的原始軟件實(shí)施相比，我們能夠?qū)?FileVault 密鑰恢復(fù)應(yīng)用程序的速度提高 498 倍。結(jié)果是運(yùn)行時(shí)間從 21 小時(shí)減少到僅 2.5 分鐘（參見(jiàn)圖 2）。

圖2：使用 FPGA 集群，F(xiàn)ileVault 破解速度在 CPU 上加速了 498 倍

Wi-Fi 保護(hù)訪問(wèn) （WPA）

WPA 用于保護(hù)無(wú)線網(wǎng)絡(luò)，并通過(guò)臨時(shí)密鑰完整性協(xié)議實(shí)現(xiàn)。WPA 和 WPA2 旨在取代上一代有線等效保密 （WEP） 協(xié)議。WPA 恢復(fù)的特點(diǎn)是對(duì)網(wǎng)絡(luò)的候選密碼執(zhí)行 PBKDF2 SHA-1 算法，然后比較身份驗(yàn)證哈希以確定密碼是否正確。在基于 FPGA 的集群上運(yùn)行時(shí)，與英特爾酷睿 i7 處理器軟件運(yùn)行時(shí)相比，該算法的加速度提高了 498 倍。

韋普

WEP（或有線等效保密，如前所述）于1997年首次推出，至今仍常用于家庭和企業(yè)，以保護(hù)無(wú)線接入點(diǎn)免受入侵。WEP 的安全性明顯低于 WPA;因此，對(duì)于需要高級(jí)別安全性的組織，包括政府和軍隊(duì)，WEP現(xiàn)在正在被WPA和其他更安全的系統(tǒng)所取代。破壞 WEP 涉及嘗試由偽隨機(jī)位流形成的每個(gè)可能的密鑰，這些位流已組合（使用獨(dú)占 OR 操作）與每個(gè) WEP 數(shù)據(jù)包中存在的已知明文和校驗(yàn)和。統(tǒng)計(jì)方法可以通過(guò)減小密鑰空間的大小和要測(cè)試的相應(yīng)密鑰數(shù)量來(lái)加速這種攻擊。在破解 WEP 時(shí)，我們將暴力破解整個(gè) 40 位密鑰空間所需的時(shí)間從英特爾酷睿 i7 處理器上估計(jì)的 42 天縮短到 FPGA 集群上的 4.7 分鐘。這種性能來(lái)自于在 FPGA 集群中每秒生成 38 億個(gè)密鑰，如圖 3 所示，性能提高了 12，933 倍。

圖3：使用 FPGA 集群，WEP 破解速度在 CPU 上加速 12，933 倍

數(shù)字墻的脆弱性

基于FPGA的方法可用于破解許多曾經(jīng)看起來(lái)很強(qiáng)大的數(shù)據(jù)加密方案。使用配備 176 個(gè) FPGA 器件的單個(gè) FPGA 集群，我們最近使用單個(gè) FPGA 加速的 4U 服務(wù)器實(shí)現(xiàn)了已知的最高 56 位 DES 解密基準(zhǔn)速度，吞吐量超過(guò)每秒 2800 億個(gè)密鑰。

本演示中的并行 DES 破解算法使用蠻力方法來(lái)分析整個(gè) DES 56 位密鑰空間，迭代解密固定大小的數(shù)據(jù)塊，以查找將部分?jǐn)?shù)據(jù)解密為 ASCII 數(shù)字序列的密鑰。此技術(shù)通常用于恢復(fù)包含已知類型數(shù)據(jù)的加密文件的密鑰，例如包含財(cái)務(wù)或軍事信息的加密文檔。在當(dāng)前一代CPU內(nèi)核上運(yùn)行的DES破解軟件每秒可以處理大約1600萬(wàn)個(gè)DES密鑰操作。像 NVIDIA Tesla 這樣的現(xiàn)代 GPU 卡可以處理超過(guò) 10 倍的數(shù)字，即每秒大約 2.5 億次 DES 操作。

然而，當(dāng)使用基于單個(gè)現(xiàn)成主板的 FPGA 集群時(shí)，每個(gè) FPGA 每秒能夠執(zhí)行 16 億次 DES 操作。這意味著，在 PC 上執(zhí)行的密鑰恢復(fù)需要數(shù)年時(shí)間，即使使用 GPU 加速，也可以在不到三天的時(shí)間內(nèi)在 4U FPGA 集群上完成。隨著越來(lái)越多的FPGA部署在越來(lái)越大的集群中，解密數(shù)據(jù)所需的時(shí)間以近乎線性的方式減少。

盡管DES現(xiàn)在被認(rèn)為是過(guò)時(shí)的，因?yàn)樗憩F(xiàn)出易受攻擊的脆弱性，但目前常用的其他加密方法也存在風(fēng)險(xiǎn)。以全球移動(dòng)通信系統(tǒng)（GSM）為例，該標(biāo)準(zhǔn)承載著全球絕大多數(shù)蜂窩電話呼叫。在 2009 年 12 月于柏林舉行的混沌通信大會(huì)上，密碼學(xué)研究員 Karsten Nohl 宣布，他的團(tuán)隊(duì)（一群黑客協(xié)同工作以創(chuàng)建一個(gè)分布式計(jì)算集群）通過(guò)創(chuàng)建一個(gè)巨大的 2 TB 哈希值“彩虹表”來(lái)破解 GSM 加密［3］。簡(jiǎn)單來(lái)說(shuō)，彩虹表提供了一個(gè)具有反向查找方案的破解程序，可以快速解密無(wú)線語(yǔ)音數(shù)據(jù)。

Nohl在演講中表示，想要竊聽(tīng)GSM呼叫的個(gè)人或團(tuán)體目前需要在硬件上花費(fèi)約10萬(wàn)美元才能在一秒鐘或更短的時(shí)間內(nèi)破解A5 / 1加密呼叫。這項(xiàng)研究說(shuō)明了安全審計(jì)對(duì)于揭露和糾正廣泛使用的數(shù)據(jù)安全標(biāo)準(zhǔn)中的漏洞的重要性。FPGA加速器可以在這種審計(jì)中發(fā)揮重要作用。

借助 FPGA，更快地破解代碼

“黑帽”和“白帽”黑客都發(fā)現(xiàn)了FPGA計(jì)算在密碼學(xué)方面的強(qiáng)大功能。與計(jì)算的最初幾年一樣，其他應(yīng)用領(lǐng)域（包括基因組學(xué)、物理學(xué)和金融等不同領(lǐng)域的研究人員）也意識(shí)到了基于 FPGA 的并行平臺(tái)的優(yōu)勢(shì)。

代碼破解和密鑰恢復(fù)算法中計(jì)算量最大的部分是相對(duì)簡(jiǎn)單的操作，必須迭代執(zhí)行，并且可以并行化以實(shí)現(xiàn)高性能。當(dāng)部署在FPGA上時(shí)，由于所執(zhí)行任務(wù)的簡(jiǎn)單性，這些算法可以非常高效地使用可用的FPGA資源。并非所有軟件算法都能很好地融入FPGA集群，但許多復(fù)雜的計(jì)算問(wèn)題都可以以相同的方式解決。

審核編輯：郭婷