陳孟東，原 昊，謝向輝，吳 東

(數(shù)學(xué)工程與先進(jìn)計算國家重點實驗室，江蘇 無錫 214125)

1 引言

隨著計算機(jī)技術(shù)的發(fā)展和互聯(lián)網(wǎng)規(guī)模的擴(kuò)大，互聯(lián)網(wǎng)安全問題也越來越受到公眾的關(guān)注，為確保私人、企業(yè)乃至國家的網(wǎng)絡(luò)安全，人們采取多種手段來保護(hù)自身的信息安全。其中很常用的方式就是對重要信息或系統(tǒng)進(jìn)行身份認(rèn)證，除軍事、金融等對安全性要求極高的領(lǐng)域之外，操作系統(tǒng)、數(shù)據(jù)庫、文件加密應(yīng)用、流行的網(wǎng)絡(luò)應(yīng)用(如電子郵件、即時通訊工具、論壇等)都依靠身份認(rèn)證機(jī)制進(jìn)行用戶賬戶或者使用權(quán)限的認(rèn)證[1]。廣泛使用的身份認(rèn)證機(jī)制需要一個用戶名和安全字符串組合的身份信息。通常使用單向哈希函數(shù)來計算摘要值，并將摘要值與用戶憑據(jù)一同存儲。當(dāng)用戶進(jìn)行身份驗證時，其認(rèn)證系統(tǒng)通過接收用戶輸入的安全字符串，重新使用哈希函數(shù)把用戶名和安全字符串轉(zhuǎn)換成摘要值，并和系統(tǒng)存儲的摘要值進(jìn)行對比，以此完成認(rèn)證過程[2]。通常使用的哈希函數(shù)包括MD4、MD5和SHA1等。

身份認(rèn)證機(jī)制在提供安全保障的同時，也會帶來一些問題。過多或者過于復(fù)雜的安全字符串會給用戶帶來記憶負(fù)擔(dān)，一旦遺忘字符串，用戶將無法獲取權(quán)限或者無法訪問文檔，因而帶來不便和損失。同時，采用安全字符串認(rèn)證的系統(tǒng)和文檔也會對國家安全部門的取證工作造成阻力[3]。為滿足個人、企業(yè)和政府在這方面的需求，安全字符串的恢復(fù)技術(shù)應(yīng)運而生。安全字符串的恢復(fù)通過在大量候選字符串上進(jìn)行哈希運算并驗證，從而找到丟失或遺忘的正確字符串，它已經(jīng)成為密碼學(xué)的重要研究方向之一[4]。安全字符串的恢復(fù)方法主要有暴力搜索法、字典法和時空折衷法等，其中字典法通過搜集已知的安全字符串可能的取值，形成一個字典文件，恢復(fù)時僅從這個字典文件中取值進(jìn)行正向的哈希運算并和存儲摘要進(jìn)行比較，具有搜索空間小、命中率高的特點，是一種行之有效的方法。然而字典法也存在問題，其恢復(fù)的成功率與字典的質(zhì)量密切相關(guān)，如何提高字典的覆蓋空間、提升字典的質(zhì)量是一個重點[5]。

由于人的記憶力限制以及個人習(xí)慣等因素，人們在設(shè)置安全字符串時常常是基于一個基礎(chǔ)加以簡單變形形成新的字符串，如增加前綴、增加后綴、大小寫變換、修改部分字母等，每種變形稱為一個基本規(guī)則[6,7]。幾個基本規(guī)則可以組合在一起共同對字符串進(jìn)行處理，稱為一次變換。相反地，在字符串恢復(fù)過程中，將每一個字典條目按照一定的規(guī)則進(jìn)行變形變換，形成新的安全字符串，膨脹擴(kuò)大了原字典文件的規(guī)模和覆蓋率，是提升字典質(zhì)量的有效方法。基于規(guī)則變換的安全字符串恢復(fù)方式通過模擬人在設(shè)置安全字符串時的內(nèi)在規(guī)律，進(jìn)一步提升字典的質(zhì)量，巧妙設(shè)置的字典結(jié)合規(guī)則變換，可以在滿足搜索規(guī)模、時效等限制時，顯著提升恢復(fù)的命中率。同時，使用規(guī)則變換對字典進(jìn)行擴(kuò)充，在處理單元內(nèi)部進(jìn)行規(guī)則的處理以及新字符串的生成，還可以減少字典本身的存儲和傳輸需求，解決哈希計算模塊和字典存取模塊之間的速度差異問題，保證整體的恢復(fù)效率。這種恢復(fù)方式越來越受到重視，多個研究證明了采用規(guī)則變換的有效性[8 - 10]。基于規(guī)則變換的安全字符串恢復(fù)過程如圖1所示，圖中虛線框內(nèi)為規(guī)則的處理過程，新生成的字符串?dāng)?shù)量是原字典條目數(shù)與變換條目數(shù)的乘積。

Figure 1 Secure string recovery process based on rule transformation圖1 基于規(guī)則變換的安全字符串恢復(fù)過程

業(yè)界有許多總結(jié)積累而成的字符串變形規(guī)則，多個安全字符串恢復(fù)工具[6,7,11]都有自己支持的規(guī)則，并提供字典加規(guī)則的恢復(fù)模式。這其中，hashcat[6]應(yīng)用廣泛，是一款多平臺的免費恢復(fù)套件，支持包括CPU、GPU(支持NVIDIA GPU和AMD GPU)、DSP、FPGA等包含OpenCL運行時的各種平臺，支持Linux、Windows、MacOS多種操作系統(tǒng)，支持分布式處理，支持近200種算法，支持多種恢復(fù)模式，支持字典與規(guī)則的處理，其規(guī)則的處理過程主要在CPU和GPU上進(jìn)行。

hashcat所采用的規(guī)則具有代表性，其共支持基本規(guī)則41種，表1列出了幾種典型的基本規(guī)則，并以字符串p@ssW0rd為輸入，舉例說明了基本規(guī)則的變形結(jié)果。hashcat自帶301 472個條目的變換文件，每次變換由一到幾個基本規(guī)則組成。例如變換“{$0l”代表先循環(huán)左移，然后將字符“0”作為后綴，然后再全部變換為小寫字母，所有3個基本規(guī)則處理結(jié)束后才生成1個新的字符串。

Table 1 Examples of typical rules表1 典型規(guī)則示例

性能和功耗成本是規(guī)則處理乃至安全字符串恢復(fù)系統(tǒng)的重要考慮因素?；疽?guī)則包括幾十種，而且還有復(fù)雜的組合情況，實際使用中，在任務(wù)規(guī)模大的情況下，字典文件可能多達(dá)幾億個條目，變換文件可能包含幾十萬次變換，規(guī)則處理過程是一項計算量大、對處理時間要求很高的任務(wù)，到目前為止公開的實現(xiàn)方式中，不管是開源工具[6,7]還是學(xué)術(shù)研究[12 - 14]都是基于CPU和GPU進(jìn)行處理，在處理速度、系統(tǒng)功耗等方面有諸多不足。本文針對hashcat自帶的基本規(guī)則及其變換文件，基于現(xiàn)有工程中使用的安全字符串恢復(fù)系統(tǒng)，提出了一種適用于規(guī)則的分布式處理架構(gòu)。實驗結(jié)果表明該處理架構(gòu)滿足實際工程需求，在處理性能、系統(tǒng)能效等方面表現(xiàn)良好。

2 分布式的規(guī)則處理架構(gòu)

2.1 分布式平臺介紹

本文的分布式規(guī)則處理架構(gòu)基于“蟻群”平臺實現(xiàn)，蟻群平臺是由眾多可重構(gòu)計算結(jié)點構(gòu)成的計算系統(tǒng)，每個計算結(jié)點內(nèi)含1塊Zynq芯片(Zynq7030)，有低功耗 CPU 和 FPGA 混合計算核心[15]，2種異構(gòu)計算資源通過高速的互連總線緊密耦合，可以支持通用計算任務(wù)和加速計算任務(wù)的并行協(xié)同執(zhí)行?；旌虾诵耐鈬闪? GB的低功耗DDR內(nèi)存、32 GB Flash存儲器、千兆以太網(wǎng)接口、高速環(huán)形網(wǎng)接口等。蟻群硬件系統(tǒng)采用了模塊化設(shè)計的方法，16個低功耗混合計算核心的異構(gòu)結(jié)點通過2套環(huán)網(wǎng)構(gòu)成計算板，多塊計算板組成ATCA機(jī)箱，按照需求可組建包含數(shù)千、數(shù)萬個結(jié)點的計算加速系統(tǒng)，系統(tǒng)結(jié)構(gòu)如圖2所示。

Figure 2 Structure of distributed computing platform圖2 分布式計算平臺結(jié)構(gòu)

結(jié)點內(nèi)，CPU和FPGA通過高級可擴(kuò)展接口AXI(Advanced eXtensible Interface)總線相連，有4個高速接口可用于數(shù)據(jù)傳輸，總帶寬可超過4 GB/s。結(jié)點間，F(xiàn)PGA通過高速串行口GTX組成高速環(huán)網(wǎng)，單端口傳輸帶寬可達(dá)6.6 Gb/s；CPU通過千兆以太網(wǎng)相連。蟻群系統(tǒng)中，結(jié)點內(nèi)的混合核心以及結(jié)點間均有著很高的數(shù)據(jù)傳輸帶寬。

2.2 規(guī)則的分布式拆分

安全字符串的恢復(fù)需要在短時間內(nèi)完成規(guī)則的處理，生成新的字符串以便進(jìn)行驗證工作，而單個計算結(jié)點的計算能力畢竟有限，因此充分利用蟻群分布式的計算資源，提升規(guī)則處理速度很有必要。如圖1所示，規(guī)則處理的過程需要對所有的字典條目和規(guī)則變換條目進(jìn)行處理，不同變換間、不同字典條目之間沒有關(guān)聯(lián)性，沒有數(shù)據(jù)的交互，可以通過拆分變換文件和字典文件，將整體任務(wù)分割成不同的子任務(wù)，進(jìn)行分布式并行處理，通過分布規(guī)模的擴(kuò)大，提高整體的處理速度。

此外，硬件資源的限制也對分布式處理提出了需求。規(guī)則的處理是同哈希算法的驗證過程結(jié)合一起使用的，規(guī)則處理生成的安全字符串需要正向的哈希運算來計算摘要值，從而和存儲的摘要值進(jìn)行比較，以便找到正確的安全字符串。在蟻群結(jié)點內(nèi)部，主要的計算能力來自可重構(gòu)FPGA，規(guī)則的處理工作以及哈希運算工作主要都是在FPGA上進(jìn)行。當(dāng)在1個芯片內(nèi)同時實現(xiàn)41種基本規(guī)則時，需要占用較多的硬件資源，通過前期實驗發(fā)現(xiàn)，在1個結(jié)點內(nèi)實現(xiàn)所有的規(guī)則處理功能需要占用Zynq 7030芯片約70%的硬件資源，此時，對于一些簡單的哈希算法，可以利用剩余30%的資源進(jìn)行片上的運算驗證，而對于一些復(fù)雜的哈希算法已經(jīng)沒有足夠的面積和資源來進(jìn)行片內(nèi)的驗證運算。而在分布式環(huán)境中，考慮將規(guī)則組合進(jìn)行拆分，每個結(jié)點支持不同的基本規(guī)則，僅對部分變換進(jìn)行支持，通過多個結(jié)點支持所有的規(guī)則變換功能。同時，單個結(jié)點僅支持幾個基本規(guī)則，可以有足夠的硬件資源來對處理的流程進(jìn)行優(yōu)化，從而提升每個結(jié)點內(nèi)規(guī)則處理的速度。

如圖3所示，對41種基本規(guī)則進(jìn)行拆分，根據(jù)拆分的結(jié)果將變換文件也進(jìn)行拆分，每個計算結(jié)點僅支持幾種基本規(guī)則，僅處理由這幾種基本規(guī)則組合形成的變換。

Figure 3 Schematic diagram of splitting of rules and transformation files圖3 規(guī)則與變換文件拆分示意圖

對規(guī)則的拆分，基于已有的規(guī)則變換文件進(jìn)行。本文用“N組合”來表示1次變換中使用的基本規(guī)則的種類數(shù)，理論上N的取值可以從1～41。但是，對301 472個已有規(guī)則變換進(jìn)行分析，可以發(fā)現(xiàn)N的取值只是從1～6，即并不是41種基本規(guī)則都存在組合在一起使用的情況。表2統(tǒng)計了已有變換文件中所有N組合出現(xiàn)的種類數(shù)，占據(jù)大多數(shù)的是1組合、2組合和3組合。如3組合一共出現(xiàn)了4 934種，這個數(shù)字是小于C(41,3)的，即不是41種基本規(guī)則中任意3種都存在組合的情況。表2的第2行是該種組合覆蓋的總的變換數(shù)量，可見1組合、2組合和3組合覆蓋了總的變換的99.6%，由于1組合包含在2組合和3組合中，所以規(guī)則的拆分主要針對2組合和3組合進(jìn)行。

Table 2 Statistical results of rule combinations表2 規(guī)則組合的統(tǒng)計結(jié)果

如果每個結(jié)點僅支持1種規(guī)則組合的情況，將需要太多的計算結(jié)點，所以對規(guī)則進(jìn)行拆分時，每個結(jié)點在滿足資源限制的情況下應(yīng)支持盡量多的規(guī)則組合。所要恢復(fù)的哈希算法已經(jīng)通過硬件實現(xiàn)，可以知道其在芯片中的資源占用，據(jù)此可以確定剩余給規(guī)則處理的資源，而每種基本規(guī)則的資源占用情況通過前期實驗也可以獲得。根據(jù)以上數(shù)據(jù)，可以將基本規(guī)則拆分成不同的組合，具體拆分時，按照圖4所示流程進(jìn)行。根據(jù)基本規(guī)則拆分的結(jié)果，將三十余萬個變換也進(jìn)行拆分，形成較小的任務(wù)課題，對應(yīng)到蟻群結(jié)點上。

Figure 4 Flow chart for rule splitting圖4 規(guī)則拆分流程圖

2.3 硬件規(guī)則處理器

對基本規(guī)則進(jìn)行拆分后，每個結(jié)點僅需要支持幾個基本規(guī)則即可。規(guī)則的處理功能主要在可重構(gòu)FPGA上實現(xiàn)，只需占用較少的硬件資源，保證哈希算法的處理性能。處理時，該結(jié)點對應(yīng)的字典文件和變換文件存放于片外DDR內(nèi)存中，通用ARM核心配置好字典文件與變換文件的大小以及存儲位置，F(xiàn)PGA便可以自動通過AXI總線從片外獲取字典和變換，并解析處理，生成新的字符串。

硬件規(guī)則處理器總體結(jié)構(gòu)如圖5所示，其主體為規(guī)則執(zhí)行單元REU (Rule Execute Unit)。REU負(fù)責(zé)各個規(guī)則的處理功能；譯碼電路負(fù)責(zé)對變換中的基本規(guī)則進(jìn)行譯碼，對各個REU進(jìn)行調(diào)度；總線接口電路包含AXI總線接口，并負(fù)責(zé)與片外的數(shù)據(jù)交互；預(yù)處理電路負(fù)責(zé)將連續(xù)存儲在一起的變換和字典數(shù)據(jù)處理成變換條目和字典條目，數(shù)據(jù)交互網(wǎng)絡(luò)負(fù)責(zé)REU間數(shù)據(jù)的交互以及將最終生成的安全字符串寫入FIFO中供哈希算法模塊使用。

Figure 5 Hardware structure rule processor圖5 硬件規(guī)則處理器結(jié)構(gòu)圖

因為哈希算法模塊以流水線實現(xiàn)，每個時鐘周期都可以對1個安全字符串進(jìn)行驗證，對規(guī)則執(zhí)行的速度提出很高的要求，為了盡量提升規(guī)則執(zhí)行的速度，設(shè)計中將單個規(guī)則執(zhí)行的過程進(jìn)行優(yōu)化，使其在1個時鐘周期內(nèi)完成，在譯碼電路的調(diào)度下，做到1個時鐘周期處理完1個基本規(guī)則，當(dāng)規(guī)則組合在一起進(jìn)行1次變換時，1次變換的執(zhí)行過程示意圖如圖6所示，圖6以3次規(guī)則組合使用為例進(jìn)行說明，3個時鐘周期執(zhí)行完畢。

Figure 6 Schematic diagram of execution process of one transformation圖6 1次變換的執(zhí)行過程示意圖

對于大量存在的規(guī)則組合使用的情況，即便1個基本規(guī)則在1個時鐘周期之內(nèi)執(zhí)行完成，完整的變換過程處理完畢，生成1個新的字符串仍需要多個周期，幾個規(guī)則組合在一起便需要幾個周期完成。此時，每個時刻只有1個REU在工作，處理效率較低。因此，需要在譯碼電路的控制下，盡量將整個變換過程做到全流水實現(xiàn)。

在只有1套規(guī)則處理單元的情況下，只有滿足同一時刻不能有處理單元的沖突，才可以做到全流水處理。通過對hashcat自帶變換文件的分析發(fā)現(xiàn)，大多數(shù)情況下，1次變換不使用相同的基本規(guī)則，據(jù)此設(shè)計了全流水的執(zhí)行結(jié)構(gòu)，執(zhí)行結(jié)構(gòu)的示意圖如圖7所示。此時，每1個時鐘周期都有1個安全字符串處理完畢，都有1個新的字符串產(chǎn)生，每1個時刻都有多個規(guī)則執(zhí)行單元在同時工作，無需插入氣泡，無需等待，最大限度提升了規(guī)則處理的效率。對于另外少部分的情況，在1次變換中存在相同基本規(guī)則時，通過譯碼電路的有效控制，字符串嚴(yán)格按照串行方式進(jìn)行處理，1個安全字符串完全處理完畢后才開始下1個處理工作，此時生成1個新的字符串需要多個時鐘周期。

Figure 7 Rule execution architecture supporting full flow圖7 支持全流水的規(guī)則執(zhí)行結(jié)構(gòu)

3 實驗結(jié)果

為驗證所設(shè)計的分布式規(guī)則處理架構(gòu)的功能正確性和性能指標(biāo)，本文在蟻群分布式平臺上進(jìn)行了開發(fā)實現(xiàn)，并針對不同的情況進(jìn)行了測試，分析了其性能以及功耗情況，并與其他平臺的運行結(jié)果進(jìn)行了對比分析。

3.1 硬件規(guī)則處理器實驗

在蟻群結(jié)點的ARM通用計算核心上開發(fā)配置管理程序，通過Vivado工具對FPGA設(shè)計部分進(jìn)行綜合與實現(xiàn)，結(jié)果顯示，單結(jié)點的硬件規(guī)則處理器運行結(jié)果正確，可以達(dá)到的最高工作頻率為150 MHz。

本文首次以FPGA硬件進(jìn)行規(guī)則的解析處理工作，并與Intel CPU和NVIDIA GPU上的軟件實現(xiàn)進(jìn)行對比。將相同的規(guī)則文件和字典文件分別在CPU和GPU上運行，并與本文的硬件規(guī)則處理器的結(jié)果進(jìn)行對比分析，對比了處理性能和功耗2個方面。軟件實現(xiàn)采用最新的hashcat 5.1.0進(jìn)行，hashcat號稱是業(yè)界最快的恢復(fù)工具[6]，軟件的結(jié)果與其運行平臺有很大的關(guān)系，如NVIDIA GPU中其桌面產(chǎn)品和專門用于高性能計算的產(chǎn)品，計算能力差距非常大，本文選取主流偏上的產(chǎn)品平臺進(jìn)行實驗，采用的CPU平臺為：Intel(R)Core(TM)i7-6700 CPU @ 3.40 GHz，32 GB內(nèi)存，GPU平臺為：NVIDIA GeForce GTX 1080 Ti。

對于變換情況，在每種平臺上分別測試了1組合、2組合和3組合的情況，字典中字符串的長度以8個字符為例進(jìn)行實驗，處理性能以每秒生成多少兆個新字符串進(jìn)行統(tǒng)計，結(jié)果如表3所示。

Table 3 Performance comparison of different platforms when dictionary length is 8表3 字典長度為8時不同平臺的性能對比 M個/s

通過分析可以發(fā)現(xiàn)：在全流水情況下，規(guī)則的組合情況對本文處理器的處理性能沒有影響，但對CPU和GPU平臺的影響較大，規(guī)則組合的次數(shù)越多，其處理性能越差。2或者3個基本規(guī)則組合在一起進(jìn)行1次變換占據(jù)絕大多數(shù)情況，此時規(guī)則處理器每秒生成150M個新字符串，處理性能優(yōu)于CPU平臺，差于GPU平臺。然而，當(dāng)使用該規(guī)則處理器來構(gòu)建大規(guī)模、分布式的規(guī)則處理系統(tǒng)時，其計算能力會顯著增加。

在規(guī)則處理過程中，對蟻群結(jié)點和GPU平臺的運行功耗進(jìn)行觀測，CPU的功耗以65 W計算，計算性能功耗比(每瓦特每秒可以處理的規(guī)則變換數(shù)量)，結(jié)果如圖8所示。對于2個或者3個基本規(guī)則組合在一起的情況，本文硬件規(guī)則處理器的性能功耗比相比于GPU提升1.4倍～2.1倍，相比于CPU提升49～70倍，在能效方面具有優(yōu)勢。

Figure 8 Comparison of energy efficiency on different platforms圖8 不同平臺間的能效對比

3.2 分布式拆分實驗

根據(jù)每個結(jié)點可以使用的硬件資源，將41種基本規(guī)則拆分成不同的小的集合，利用蟻群系統(tǒng)的分布式資源，支持所有三十余萬條目的規(guī)則變換。對規(guī)則進(jìn)行拆分時，結(jié)合2種實際的工作環(huán)境進(jìn)行：一種是哈希算法較復(fù)雜，留給規(guī)則處理的硬件資源較少的情況；另一種是哈希算法較簡單的情況。在分布式環(huán)境中，利用每個計算結(jié)點有限的硬件資源，實現(xiàn)完整的規(guī)則處理功能所需要的拆分?jǐn)?shù)量如表4所示。

Table 4 Results of rules splitting 表4 規(guī)則拆分結(jié)果

對表4進(jìn)行分析可以發(fā)現(xiàn)，所需要的拆分?jǐn)?shù)量受可用資源的影響較大。對于復(fù)雜算法，單個結(jié)點上留給規(guī)則處理的硬件資源較少，需要較大的分布規(guī)模才能完全實現(xiàn)所有的規(guī)則處理功能。對于簡單算法，片上留給規(guī)則處理的資源較多，只需較小的分布規(guī)模即可實現(xiàn)完整的規(guī)則處理功能。

在192個結(jié)點規(guī)模的蟻群系統(tǒng)上進(jìn)行分布式規(guī)則處理架構(gòu)的實現(xiàn)，此時蟻群系統(tǒng)的形態(tài)為14U的標(biāo)準(zhǔn)ATCA機(jī)箱。通過腳本語言開發(fā)自動化工具，調(diào)用Vivado工具，對規(guī)則拆分后各結(jié)點的FPGA邏輯進(jìn)行綜合與實現(xiàn)，生成比特流文件；在ARM通用計算核心上開發(fā)配置管理程序，對硬件規(guī)則處理器進(jìn)行配置管理；根據(jù)分布式系統(tǒng)的規(guī)模限制，結(jié)合FPGA的可重構(gòu)特性，對字典和變換文件進(jìn)行劃分，形成子課題；通過蟻群系統(tǒng)的Condor分布式管理程序進(jìn)行任務(wù)的分配管理。最終結(jié)果顯示，分布式規(guī)則處理架構(gòu)運行結(jié)果正確。因為規(guī)則處理任務(wù)結(jié)點間沒有數(shù)據(jù)的交互，結(jié)合課題的劃分和FPGA的重構(gòu)，實際運行性能為單結(jié)點的192倍，性能相比GPU提升2.4～3.6倍，相比CPU提升288～411倍，能效相比GPU提升1.4～2.1倍，相比CPU提升49～70倍。

4 結(jié)束語

字符串變換規(guī)則在安全字符串的恢復(fù)中具有重要作用，其處理過程復(fù)雜，對處理性能、系統(tǒng)功耗有很高的要求，本文針對這些需求，提出分布式的規(guī)則處理架構(gòu)，并首次采用FPGA硬件加速規(guī)則的處理過程，有效利用蟻群計算平臺的分布式計算資源，利用FPGA高并行、低功耗的特點，構(gòu)建了規(guī)則處理架構(gòu)，并進(jìn)行了設(shè)計實現(xiàn)。實驗結(jié)果表明，該分布式規(guī)則處理架構(gòu)處理性能高、運行功耗低，能效相比CPU、GPU有顯著提升，隨著分布式規(guī)模的擴(kuò)大可以達(dá)到很高的計算性能，滿足實際工程需求。