GPU上典型存儲(chǔ)器難散列函數(shù)的優(yōu)化

陳 虎，韓建國(guó)

(1.華南理工大學(xué)軟件學(xué)院，廣東 廣州 510006;2.廣東省科技基礎(chǔ)條件平臺(tái)中心,廣東 廣州 510006)

1 引言

在口令安全機(jī)制中，往往基于一般散列函數(shù)構(gòu)造特定的口令散列函數(shù)。在設(shè)置口令時(shí)，口令驗(yàn)證方計(jì)算并存儲(chǔ)用戶口令明文對(duì)應(yīng)的口令散列函數(shù)值(密文)，從而避免口令明文的泄露。在驗(yàn)證口令時(shí)，口令驗(yàn)證方計(jì)算用戶輸入口令對(duì)應(yīng)的口令散列函數(shù)值并與存儲(chǔ)的密文進(jìn)行對(duì)比。在恢復(fù)口令時(shí)，可以并行計(jì)算多個(gè)口令明文的散列值，并與待猜測(cè)的密文比較。因此，口令散列函數(shù)的計(jì)算性能成為口令攻防兩方面的關(guān)鍵性問題。可以使用MD5[1]、SHA1[2]等簡(jiǎn)單散列函數(shù)作為口令散列函數(shù)，其計(jì)算過(guò)程較為簡(jiǎn)單，但難以抵抗較大規(guī)模的口令攻擊。也可以使用PBKDF2[3]等構(gòu)造口令散列函數(shù)，其通過(guò)多次迭代簡(jiǎn)單散列函數(shù)以增加計(jì)算量，但是此類計(jì)算密集型的散列函數(shù)易于在FPGA、ASIC等專用硬件上[4,5]并行計(jì)算多條口令明文的散列函數(shù)實(shí)例，具有較高的性能，對(duì)口令安全構(gòu)成潛在威脅。

存儲(chǔ)器難散列函數(shù)(Memory-Hard Hash Functions)[6]具備抗ASIC攻擊的能力，有望成為新型的口令散列函數(shù)。這類散列函數(shù)在執(zhí)行過(guò)程中需要較大的存儲(chǔ)器容量，而且計(jì)算和訪存的比例相近。這使得ASIC上實(shí)現(xiàn)該類函數(shù)面臨困難：如果將散列函數(shù)計(jì)算所需要的存儲(chǔ)器都放置在ASIC芯片上，將占用大量的晶體管，從而降低芯片的計(jì)算能力；如果采用片外存儲(chǔ)器存儲(chǔ)，芯片的存儲(chǔ)器訪問帶寬可能會(huì)成為系統(tǒng)瓶頸，而且存儲(chǔ)器訪問的功耗依然與傳統(tǒng)的CPU/GPU系統(tǒng)相當(dāng)[7]。

得益于強(qiáng)大的計(jì)算能力和完整的生態(tài)環(huán)境，高性能的通用GPU[8,9]是當(dāng)前口令恢復(fù)的主要硬件平臺(tái)。hashcat[10]、John the Ripper[11]等高效的口令猜測(cè)軟件對(duì)傳統(tǒng)的口令散列函數(shù)進(jìn)行了深入的優(yōu)化，具有很高的執(zhí)行效率，但是在GPU上優(yōu)化實(shí)現(xiàn)存儲(chǔ)器難散列函數(shù)的方法還沒有得到深入的研究。

本文主要研究利用GPU體系結(jié)構(gòu)的特點(diǎn)提升存儲(chǔ)器難散列函數(shù)計(jì)算吞吐率的方法。GPU的片上存儲(chǔ)器容量非常有限，難以在片上存放這些散列函數(shù)所需要的存儲(chǔ)空間。但是，GPU提供了很高的存儲(chǔ)器訪問帶寬和較大容量的全局存儲(chǔ)器，可以在全局存儲(chǔ)器中存放存儲(chǔ)器難散列函數(shù)所需要的內(nèi)容。為了更有效地發(fā)揮GPU潛在的計(jì)算能力，本文一方面研究了存儲(chǔ)器難散列函數(shù)的數(shù)據(jù)布局，以提升存儲(chǔ)器的訪問效率；另一方面利用GPU上多線程間寄存器交換數(shù)據(jù)的方法，使多個(gè)線程協(xié)作執(zhí)行同一個(gè)散列函數(shù)實(shí)例，從而增加線程的數(shù)量，更好地隱蔽存儲(chǔ)器的訪問延遲，提升吞吐率。

本文以經(jīng)典的存儲(chǔ)器難散列函數(shù)Scrypt[12]為例說(shuō)明了GPU上優(yōu)化實(shí)現(xiàn)方法，并使用該方法優(yōu)化實(shí)現(xiàn)了較為復(fù)雜的存儲(chǔ)器難散列函數(shù)Argon2d[13]。與hashcat的實(shí)現(xiàn)方法相比，本文提出的優(yōu)化方法使得Scrypt的性能提升了2.03倍。

本文第2節(jié)介紹存儲(chǔ)器難散列函數(shù)和GPU體系結(jié)構(gòu)的基本特點(diǎn)；第3節(jié)介紹對(duì)Scrypt的優(yōu)化實(shí)現(xiàn)方法；第4節(jié)討論Scrypt性能測(cè)試結(jié)果，并簡(jiǎn)要介紹Argon2d算法的性能，說(shuō)明本文提出的方法可以優(yōu)化多種存儲(chǔ)器難散列函數(shù)；第5節(jié)總結(jié)了本文的工作。

2 相關(guān)工作

2.1 存儲(chǔ)器難散列函數(shù)

存儲(chǔ)器難散列函數(shù)的主要特征包括：(1)每個(gè)實(shí)例執(zhí)行過(guò)程中需要占用較大容量的存儲(chǔ)器，其存儲(chǔ)器容量參數(shù)往往可以配置，從數(shù)百K字節(jié)到數(shù)G字節(jié)不等。從口令安全的實(shí)際應(yīng)用場(chǎng)景看，其存儲(chǔ)器容量往往介于數(shù)百K字節(jié)至數(shù)M字節(jié)。(2)可以分為獨(dú)立型和依賴型2種。前者的存儲(chǔ)訪問地址序列固定，與輸入的明文無(wú)關(guān)，具有較好的抗側(cè)信道攻擊能力，但由于地址序列固定，可以通過(guò)預(yù)先優(yōu)化存儲(chǔ)器布局獲得較高的計(jì)算性能[14,15]。后者的存儲(chǔ)器訪問地址依賴于散列函數(shù)的輸入明文，事先難以確定存儲(chǔ)器訪問的地址序列，這使得系統(tǒng)實(shí)現(xiàn)更為困難。(3)散列函數(shù)執(zhí)行過(guò)程中計(jì)算和訪存比例較為接近，在實(shí)現(xiàn)的過(guò)程中如果減少內(nèi)存的使用量，則會(huì)顯著增加計(jì)算量。這個(gè)特征使得在ASIC上使用較少的片上存儲(chǔ)器壓縮存儲(chǔ)變得得不償失。

典型的存儲(chǔ)器難散列函數(shù)包括Scrypt、Argoon2、Lyra[16]和Ballon[17]等，其中Scrypt是出現(xiàn)較早的存儲(chǔ)器難散列函數(shù)，目前已經(jīng)成為RFC標(biāo)準(zhǔn)[18]。Argon2是2015年口令散列函數(shù)競(jìng)賽[19]的優(yōu)勝者，包含依賴型和獨(dú)立型2種類型：Argon2d和Argon2i。Argon2原理較為復(fù)雜，限于篇幅，本文僅介紹Scrypt的原理。

Scrypt的配置參數(shù)包括：CPU/存儲(chǔ)器開銷參數(shù)N、塊大小r、并行度p和輸出長(zhǎng)度dkLen，輸入包括口令pwd和鹽salt。Scrypt的原理如圖1所示，分為3個(gè)步驟：

(1)使用PBKDF2_HMAC_SHA256(pwd,salt,p×128r)生成p個(gè)128r字節(jié)的初始數(shù)據(jù)塊，分別作為p個(gè)線程的輸入B。

(2)p個(gè)線程使用ROMix算法分別填充p塊容量為N×128r字節(jié)的存儲(chǔ)器，并迭代得到128r字節(jié)的結(jié)果B′。

(3)對(duì)p個(gè)結(jié)果使用PBKDF2_HMAC_SHA256生成長(zhǎng)度為dkLen位的散列函數(shù)值。

Figure 1 Structure of Scrypt圖1 Scrypt結(jié)構(gòu)

ROMix算法包含了N個(gè)128r字節(jié)塊構(gòu)成的數(shù)組V，其中第1塊V0由PBKDF2_HMAC_SHA256()所產(chǎn)生的1個(gè)128r字節(jié)塊B初始化。在第1階段(第2～4行)中，Scrypt按照順序依次使用BlockMix算法填充數(shù)組V，其中Vi僅僅依賴于Vi-1。在第2階段(第5～7行)中，第6步的Integerify函數(shù)取X的最后64字節(jié)作為一個(gè)小端對(duì)齊的整數(shù)，并由此隨機(jī)選擇V中的一個(gè)塊，在第7步中更新X。經(jīng)過(guò)N次迭代后，得到128r字節(jié)的輸出B′。ROMix算法依賴關(guān)系如圖2所示，其中X0,…,XN-1對(duì)應(yīng)算法1中第7步X在第i次循環(huán)時(shí)的值，節(jié)點(diǎn)之間的實(shí)線為必然的依賴關(guān)系，虛線為隨機(jī)的依賴關(guān)系。

算法1ROMix算法

Input:B,r,N。

Output:B′。

1:X←B;//X為中間變量

2:forifrom 0 toN-1do

3:Vi←X;

4:X←BlockMix(X)

5：endfor

6:forifrom 0 toN-1do

7:j←Integerify(X) modN;

8:X←BlockMix(X^Vj);

9：endfor

10:B′ ←X;

Figure 2 Dependency graph of ROMix圖2 ROMix算法的數(shù)據(jù)依賴圖

BlockMix算法由Salsa20/8散列函數(shù)派生得到，其輸入和輸出都是2r個(gè)64字節(jié)的數(shù)據(jù)塊，如算法2所示。

算法2BlockMix算法

Input:2r個(gè)64字節(jié)的數(shù)據(jù)塊B0…B2r-1。

Output:更新后的2r個(gè)64字節(jié)的數(shù)據(jù)塊B′0…B′2r-1。

1:X←B2r-1；//X為中間變量

2:forifrom 0 to 2r-1do

3:T←X^Bi；//T為中間變量

4:X←salsa20/8(T);

5:Yi←X；//Yi(0≤i≤2r-1)為中間變量

6:endfor

7:B′←(Y0,Y2,…,Y2r-2,Y1,Y3,…,Y2r-1)

存儲(chǔ)器難散列函數(shù)Scrypt具有以下特點(diǎn)[12]：

(1)在串行隨機(jī)訪問的計(jì)算機(jī)上，需要的存儲(chǔ)空間為O(N)，計(jì)算次數(shù)T(N)=O(N)。

(2)在具有S*(N)=M(N)個(gè)處理器和S*(N)存儲(chǔ)空間的并行隨機(jī)訪問計(jì)算機(jī)上，算法執(zhí)行時(shí)間T*(N)=O(N2/M(N))，即SN(N)×T*(N)=O(N2)。

Scrypt的主要特點(diǎn)是計(jì)算次數(shù)和所需要的存儲(chǔ)器容量成正比，且在并行計(jì)算機(jī)上其時(shí)空乘積為O(N2)，這使得它在并行計(jì)算機(jī)上的速度提升無(wú)法按照硬件資源的數(shù)量增加呈線性關(guān)系。

2.2 GPU體系結(jié)構(gòu)特點(diǎn)

與CPU相比，GPU使用了更多的晶體管構(gòu)造計(jì)算單元，片上存儲(chǔ)器容量非常小。GPU中包含了多個(gè)流多處理器組SM(Stream Multiprocessors)，每個(gè)SM包含了多個(gè)計(jì)算單元、64～192 KB的共享存儲(chǔ)器/Cache和大容量的寄存器文件。一個(gè)SM上可以同時(shí)并發(fā)運(yùn)行多個(gè)輕量級(jí)線程，并且零開銷實(shí)現(xiàn)線程切換。

NVIDIA公司的GPU采用了單指令多線程SIMT(Single Instruction Multiple Threads)[8]的并行方式，即多個(gè)線程執(zhí)行相同的指令，但是使用不同的數(shù)據(jù)。SM調(diào)度的基本單位是由32個(gè)線程構(gòu)成的warp，同一個(gè)warp的所有線程執(zhí)行相同的指令。同一warp內(nèi)的線程可以使用混洗指令直接交換數(shù)據(jù)，無(wú)需訪存存儲(chǔ)器，執(zhí)行開銷很小。一個(gè)warp執(zhí)行高延遲的訪存指令時(shí)，將會(huì)掛起直至訪存指令結(jié)束。在此期間，執(zhí)行算術(shù)邏輯指令的其他warp仍可以并發(fā)執(zhí)行，可以在一定程度上隱藏內(nèi)存訪問的延遲。

GPU訪問全局存儲(chǔ)器的基本單位[20]是以128字節(jié)為單位的區(qū)段。一個(gè)warp的32個(gè)線程可以同時(shí)訪問32個(gè)不同地址。如果這32個(gè)地址均處于一個(gè)區(qū)段內(nèi)，一次全局存儲(chǔ)器訪問就可以滿足這個(gè)訪問請(qǐng)求。如果這32個(gè)地址分散在m個(gè)區(qū)段，則需要m次全局存儲(chǔ)器訪問，存儲(chǔ)器訪問效率降低為1/m。

3 GPU上Scrypt算法的優(yōu)化

存儲(chǔ)器難散列函數(shù)在執(zhí)行過(guò)程中使用的內(nèi)存容量較大，同時(shí)伴隨著大量的訪存操作。需要優(yōu)化全局存儲(chǔ)器的數(shù)據(jù)布局，提高存儲(chǔ)器帶寬的利用率。與此同時(shí)，口令恢復(fù)過(guò)程可以并行執(zhí)行多個(gè)散列函數(shù)實(shí)例。如果一個(gè)GPU線程計(jì)算一個(gè)散列函數(shù)實(shí)例，由于受到顯存大小的約束，GPU中線程數(shù)量受限，難以隱藏存儲(chǔ)器訪問帶來(lái)的延遲。

本文采用多個(gè)線程協(xié)作計(jì)算一個(gè)散列函數(shù)實(shí)例的方法，使得在同樣散列函數(shù)實(shí)例的情況下，具有更多的工作線程，更為有效地隱藏存儲(chǔ)器訪問延遲。

3.1 2種存儲(chǔ)器布局

Figure 3 Two storage methods圖3 2種存儲(chǔ)方式

在交織存儲(chǔ)方式中，每個(gè)warp交織存儲(chǔ)32個(gè)線程的內(nèi)容，即不同線程的相同位置的字連續(xù)存放。在順序存儲(chǔ)方式中，同一個(gè)線程對(duì)應(yīng)數(shù)據(jù)連續(xù)存放，不同線程的存儲(chǔ)區(qū)域不發(fā)生交疊。對(duì)于一個(gè)warp中第t個(gè)線程的第i個(gè)塊的第j個(gè)字，交織存儲(chǔ)的地址AI和順序存儲(chǔ)的地址AN的計(jì)算方法分別如式(1)和式(2)所示：

AI(t,i,j)=32×(32r×i+j)+t

(1)

AN=32r×N×t+32r×i+j

(2)

其中,0≤t≤31，0≤i≤N-1，0≤j≤32r-1。

交織存儲(chǔ)方式中，一個(gè)warp中的32個(gè)線程同時(shí)計(jì)算32個(gè)Scrypt散列函數(shù)實(shí)例，且每個(gè)線程按照32位無(wú)符號(hào)整數(shù)的方式并行訪問存儲(chǔ)器。ROMix算法的第1階段，32個(gè)線程發(fā)出的存儲(chǔ)器訪問地址處于一個(gè)128字節(jié)的區(qū)段中，GPU的帶寬利用率為100%。但是，在第2階段中，32個(gè)線程可能訪問不同的塊，導(dǎo)致32個(gè)地址處于不同的區(qū)段中。在最壞的情況下，所需要讀取的數(shù)據(jù)分布于32個(gè)不同的區(qū)段，此時(shí)存儲(chǔ)器帶寬的利用率僅為1/32。

在順序存儲(chǔ)方式中，每個(gè)線程計(jì)算一個(gè)Scrypt實(shí)例且僅使用32位存儲(chǔ)器訪問時(shí)，存儲(chǔ)器帶寬利用率為1/32。為了避免這個(gè)問題，可以使用16字節(jié)的存儲(chǔ)器訪問。CUDA的程序設(shè)計(jì)指導(dǎo)[20]指出，如果warp中每個(gè)線程均訪問16個(gè)字節(jié)存儲(chǔ)器，則GPU產(chǎn)生4個(gè)存儲(chǔ)器訪問請(qǐng)求，且每個(gè)請(qǐng)求完成8個(gè)線程的存儲(chǔ)器訪問。如果這8個(gè)線程計(jì)算不同的實(shí)例，其地址將處于不同的區(qū)段，在Scrypt的2個(gè)階段中存儲(chǔ)器帶寬的利用率均為1/8。

3.2 多線程協(xié)同計(jì)算

由于GPU的顯存容量有限，在N較大的情況下，可以同時(shí)支持的Scrypt散列函數(shù)實(shí)例數(shù)受到限制，導(dǎo)致能并發(fā)計(jì)算的線程數(shù)有限，從而影響系統(tǒng)的吞吐率。為此，本文考慮4個(gè)線程協(xié)同計(jì)算1個(gè)散列函數(shù)的實(shí)例。

Scrypt的主要計(jì)算基于散列函數(shù)Salsa20/8[21]，其偽代碼如下所示，其中R(d,s)表示對(duì)32位無(wú)符號(hào)整數(shù)d循環(huán)右移s位。

算法3Salsa20/8

{//b0…b15:16個(gè)32位的字輸入

//x0,…,x15:16個(gè)中間變量

1:x0…x15←b0…b15;

2:forifrom 0 to 3do

3:x4^=R(x0+x12,7);x8^=R(x4+x0,9)；

4:x12^=R(x8+x4,13);x0^=R(x12+x8,18)；

5:x9^=R(x5+x1,7);x13^=R(x9+x5,9)；

6:x1^=R(x13+x9,13);x5^=R(x1+x13,18)；

7:x14^=R(x10+x6,7);x2^=R(x14+x10,9)；

8:x6^=R(x2+x14,13);x10^=R(x6+x2,18)；

9:x3^=R(x15+x11,7);x7^=R(x3+x15,9)；

10:x11^=R(x7+x3,13);x15^=R(x11+x7,18)；

11:x1^=R(x0+x3,7);x2^=R(x1+x0,9)；

12:x3^=R(x2+x1,13);x0^=R(x3+x2,18)；

13:x6^=R(x5+x4,7);x7^=R(x6+x5,9)；

14:x4^=R(x7+x6,13);x5^=R(x4+x7,18)；

15:x11^=R(x10+x9,7);x8^=R(x11+x10,9)；

16:x9^=R(x8+x11,13);x10^=R(x9+x8,18)；

17:x12^=R(x15+x14,7);x13^=R(x12+x15,9)；

18:x14^=R(x13+x12,13);x15^=R(x14+x13,18)；

19:endfor

20:forifrom 0 to 15do

}

上述函數(shù)可以分為2段：第1段是第3行到第10行，第2段是第11行到第18行。將16個(gè)中間變量劃分為{x0,x4,x8,x12}，{x1,x5,x9,x13}，{x2,x6,x10,x14}和{x3,x7,x11,x15}4個(gè)集合。基于此數(shù)據(jù)劃分，第1段的16個(gè)移位/加法操作可以按照下述計(jì)算次序由4個(gè)線程分4步并行完成：〈x4,x9,x14,x3〉，〈x8,x13,x2,x7〉，〈x12,x1,x6,x11〉，〈x0,x5,x10,x15〉。同理，第2段的計(jì)算過(guò)程中，4個(gè)線程使用的數(shù)據(jù)集合分別為{x0,x1,x2,x3}，{x4,x5,x6,x7}，{x8,x9,x10,x11}，{x12,x13,x14,x15}，并行計(jì)算次序?yàn)椋骸磝1,x6,x11,x12〉，〈x2,x7,x8,x13〉，〈x3,x4,x9,x14〉，〈x0,x5,x10,x15〉。由此可以看出，可以使用4個(gè)線程同時(shí)完成一個(gè)Salsa20/8散列函數(shù)的計(jì)算。需要設(shè)計(jì)中間變量x0, …,x15的存儲(chǔ)布局和交換方法，使得每個(gè)線程分別包含4個(gè)局部變量，并行執(zhí)行第1段操作，然后進(jìn)行一次數(shù)據(jù)交換，再并行執(zhí)行第2段操作。

在GPU中可以使用共享存儲(chǔ)器或warp混洗函數(shù)實(shí)現(xiàn)同一個(gè)warp內(nèi)多個(gè)線程間數(shù)據(jù)交換。共享存儲(chǔ)器分為16個(gè)存儲(chǔ)器體，如果1個(gè)warp中的16個(gè)線程同時(shí)訪問不同體，可以達(dá)到共享存儲(chǔ)器體的最大訪問帶寬?？梢詫f(xié)同計(jì)算同一個(gè)實(shí)例的4個(gè)不同線程的中間變量x0, …,x15分布到不同的存儲(chǔ)器體上，并精心排布第2段計(jì)算的次序(如圖4所示)，使得4個(gè)協(xié)作線程在整個(gè)Salsa20/8計(jì)算過(guò)程中不發(fā)生體沖突，但是這將引入比較復(fù)雜的地址計(jì)算。另外一種方法使用了NVIDIA公司特有的warp混洗函數(shù)實(shí)現(xiàn)同一個(gè)warp內(nèi)的多個(gè)線程間快速數(shù)據(jù)交換。測(cè)試表明，使用warp混洗函數(shù)的性能稍高于使用共享存儲(chǔ)器的性能，這可能是因?yàn)楣蚕泶鎯?chǔ)器地址計(jì)算的開銷和較高的存儲(chǔ)器訪問延遲導(dǎo)致的。因此，本文在NIVIDIA公司的GPU上使用了混洗函數(shù)。在不支持warp混洗函數(shù)的其他類型GPU上可以考慮采用局部存儲(chǔ)器的交換方法。

Figure 4 Layout of intermediate variables in Salsa20/8圖4 Salsa20/8中間變量的存儲(chǔ)布局

4 測(cè)試與分析

本節(jié)在GTX TITAN X上進(jìn)行性能測(cè)試，其硬件參數(shù)如表1所示。測(cè)試主要包括3個(gè)方面：(1)在(N,p,r)=(1024,1,1)的參數(shù)配置下，比較交叉存儲(chǔ)、單線程順序存儲(chǔ)和4線程順序存儲(chǔ)3種方法實(shí)現(xiàn)Scrypt的性能；(2)上述3種方法實(shí)現(xiàn)Argon2d的性能；(3)所需存儲(chǔ)容量變化時(shí)，散列函數(shù)的性能。

在 (N,p,r)=(1024,1,1)情況下，3種不同方法實(shí)現(xiàn)Scrypt性能如表2所示，其中hashcat使用了單線程順序存儲(chǔ)方法。由表2可以看出，4線程順序存儲(chǔ)方法具有最高的性能，是hashcat實(shí)現(xiàn)方法的2.03倍。

Table 2 Scrypt performance of three different methods(N=1024, p=1, r=1)表2 3種不同方法的Scrypt性能(N=1024,p=1,r=1)

Argon2d也是一種典型的存儲(chǔ)器難散列函數(shù)，其主要配置參數(shù)包括：并行度p，存儲(chǔ)器容量m，迭代次數(shù)T。一個(gè)Argon2d實(shí)例所需要的存儲(chǔ)容量為1204mp個(gè)字節(jié)。它在填充存儲(chǔ)器階段采用基于blake2b[22]的壓縮函數(shù)。與Salsa20/8類似，該函數(shù)可以由4個(gè)線程并行實(shí)現(xiàn)，也可以使用本文所述的4線程順序存儲(chǔ)方法。表3給出了3種方法的性能比較，可以看出，4線程順序存儲(chǔ)方法的性能是交織存儲(chǔ)方法性能的310%。

Table 3 Argon2d performance of three different methods(m=64, p=1, T=1)表3 3種不同方法的Argon2d性能(m=64,p=1,T=1)

當(dāng)N=1024時(shí)，一個(gè)Scrypt散列函數(shù)的實(shí)例需要128 KB的全局存儲(chǔ)器容量。在總?cè)萘繛?2 GB的顯存中，約有8～9 GB存儲(chǔ)器可供使用。在此配置下，4線程順序存儲(chǔ)方法可以使用的線程數(shù)為252K個(gè)，每個(gè)SM容納2K個(gè)線程。

受到顯存容量的限制，當(dāng)N增加時(shí)，單個(gè)GPU上可以并行計(jì)算的實(shí)例數(shù)(線程數(shù))也在不斷下降，如表4和圖5a所示。在Scrypt散列函數(shù)中，N增加一倍，計(jì)算和訪存的數(shù)量也都相應(yīng)增加一倍。在理想的情況下，N增加一倍，計(jì)算性能應(yīng)降低一半。但是，實(shí)際性能降低的速度遠(yuǎn)遠(yuǎn)高于50%。例如，在N=2048時(shí)，計(jì)算性能僅為N=1024時(shí)性能的12.65%。發(fā)生這種情況的主要原因是GPU中對(duì)全局存儲(chǔ)器訪問的延遲高達(dá)200～400個(gè)周期，需要依賴大量計(jì)算密集型的線程隱藏存儲(chǔ)器訪問導(dǎo)致的延遲。但是，N(單個(gè)實(shí)例的內(nèi)存使用量)增加時(shí)，可以并行計(jì)算的線程數(shù)隨之減少，降低了對(duì)存儲(chǔ)器訪問的隱藏能力，導(dǎo)致系統(tǒng)資源利用率和吞吐率顯著下降。

Table 4 Scrypt performance with different storage capacity (p=1, r=1)表4 Scrypt散列函數(shù)存儲(chǔ)容量變化時(shí)的性能(p=1，r=1)

與Scrypt類似，在其他參數(shù)不發(fā)生變化時(shí)，Argon2d的存儲(chǔ)容量增加一倍，其計(jì)算量和存儲(chǔ)器訪問量也增加一倍，理論計(jì)算性能應(yīng)該降低一半。存儲(chǔ)器容量發(fā)生變化時(shí)，Argon2d在GPU上的性能如表5和圖5b所示。在單個(gè)實(shí)例的存儲(chǔ)器容量從128 KB增加到256 KB時(shí)，其性能下降為128 KB時(shí)性能的25.71%?？梢钥闯?，在GPU上執(zhí)行這一類存儲(chǔ)器難散列函數(shù)的最重要問題是顯存容量有限，導(dǎo)致可以運(yùn)行的線程數(shù)受限，從而降低了GPU利用計(jì)算過(guò)程隱藏存儲(chǔ)器訪問的能力，影響了系統(tǒng)的資源利用率和吞吐率。

Table 5 Argon2d performance with different storage capacity (p=1, T=1)表5 Argon2d散列函數(shù)存儲(chǔ)容量變化時(shí)的性能(p=1,T=1)

Figure 5 Performance vs storage capacity of Scrypt and Argon2d圖5 存儲(chǔ)容量變化時(shí)Scrypt和Argon2d的性能

在GPU上使用4線程協(xié)同計(jì)算和順序存儲(chǔ)方法計(jì)算存儲(chǔ)器難散列函數(shù)，具有以下優(yōu)點(diǎn)：(1)在相同的顯存容量下，相對(duì)于1個(gè)線程計(jì)算1個(gè)實(shí)例，4個(gè)線程同時(shí)計(jì)算1個(gè)實(shí)例使得可以并發(fā)執(zhí)行的線程數(shù)量增加4倍，增加了系統(tǒng)的并發(fā)能力。(2)在Salsa20/8的計(jì)算過(guò)程中，每個(gè)線程僅僅使用了4個(gè)32位字保存中間變量，寄存器使用量控制在32個(gè)字，提高了SM的使用率。(3)每個(gè)線程都使用16個(gè)字節(jié)的存儲(chǔ)器訪問而且采取了順序存儲(chǔ)方式，此時(shí)每個(gè)存儲(chǔ)器請(qǐng)求包含了8個(gè)線程的存儲(chǔ)器訪問。由于使用了4個(gè)線程同時(shí)計(jì)算一個(gè)實(shí)例，存儲(chǔ)器帶寬利用率也從原有單線程模式的1/8提高到50%。

5 結(jié)束語(yǔ)

由于抗ASIC的特征，存儲(chǔ)器難散列函數(shù)很有可能成為未來(lái)的口令散列函數(shù)。本文以典型的Scrypt和Argon2d為目標(biāo)，研究了GPU上存儲(chǔ)器難散列函數(shù)的性能優(yōu)化方法，比較和分析了交織存儲(chǔ)和順序存儲(chǔ)2種方法的存儲(chǔ)器帶寬利用率，指出使用16字節(jié)存儲(chǔ)器訪問和順序存儲(chǔ)方法可以更有效地利用GPU的存儲(chǔ)器帶寬。同時(shí)，本文提出了使用多個(gè)線程協(xié)作計(jì)算一個(gè)散列函數(shù)實(shí)例并使用warp間混洗函數(shù)交換數(shù)據(jù)的方法，有效減少了每個(gè)線程占用的資源，增加了可以并行運(yùn)行的線程數(shù)量，更為有效地隱藏了存儲(chǔ)器訪存的延遲，并將存儲(chǔ)器訪問帶寬的利用率提高到50%，較hashcat中的Scrypt實(shí)現(xiàn)，性能提升了2.03倍。

本文還使用4線程順序存儲(chǔ)方法實(shí)現(xiàn)了較為復(fù)雜的Argon2d散列函數(shù)，對(duì)于Argon2d依然具有較好的性能，說(shuō)明了其對(duì)于不同存儲(chǔ)器難散列函數(shù)的適應(yīng)性。

本文比較了2種存儲(chǔ)器難散列函數(shù)在不同存儲(chǔ)器容量需求下性能的變化情況。實(shí)驗(yàn)表明，由于顯存容量有限，可以并行執(zhí)行的散列函數(shù)實(shí)例受到約束，減少了GPU上可以并發(fā)執(zhí)行的線程數(shù)，使計(jì)算操作難以隱藏存儲(chǔ)器訪問延遲，從而降低了資源利用率，在GPU上執(zhí)行散列函數(shù)的性能大幅度下降。

如何克服顯存容量的瓶頸，保持可以并行工作的線程數(shù)量將是后續(xù)在GPU上優(yōu)化實(shí)現(xiàn)存儲(chǔ)器難散列函數(shù)的主要問題。