SHA散列算法擴展指令探究

范建軍

(湖北科技學院 計算機科學與技術學院,湖北 咸寧 437100)

SHA散列算法擴展指令探究

范建軍

(湖北科技學院 計算機科學與技術學院,湖北 咸寧 437100)

網絡安全領域中的鑒別和數字簽名是保障數據傳輸安全的重要手段之一，在互聯網的應用中已被商家和客戶廣泛接受，但實現它們的算法計算量較大，耗費時間，有時需要專用設備完成，成本較高。使用SHA指令系統，由CPU來完成這些任務，這可以很好地降低成本，提高速度。文章研究了SHA指令的特性并給出了具體的應用。

SHA-1算法；SHA-256算法；散列指令

一、SHA散列算法概述[1]

SHA散列算法(Secure Hash Algorithm)廣泛地用于數字簽名和報文識別應用程序開發中。該算法經過安全領域專家多年來的研究和實驗，現已被全世界廣泛采用。該算法的核心是將接收到的一段報文以一種不可逆的方式將它轉換成一段長度較短、位數固定的輸出密文即散列值的過程。

SHA散列算法已由美國國家標準技術研究所發布作為美國國家標準，編號為FIPS PUB 180。該標準規定了SHA-1，SHA-224，SHA-256，SHA-384，和SHA-512這幾種單向散列算法。SHA-1，SHA-224和SHA-256適用于長度不超過264二進制位的報文。SHA-384和SHA-512適用于長度不超過2128二進制位的報文。其中，SHA-1生成的散列值為160位，SHA-256生成的散列值為256位。

SHA散列算法的處理過程包含5個步驟：

步驟1：附加填充比特。將報文以512位為單位分成若干個數據塊，每塊又分成16個32位字，但報文長度與448模512同余，不夠部分需填充比特位，使其達到要求，填充的最高位為1，其余都為0。

步驟2：附加長度值。將一個64位塊附加到報文后面，這個塊被當作一個無符號二進制數，它的值等于初始報文(填充前)的位長度。

步驟3：初始化SHA緩存。對于SHA-1使用一個160比特的緩存來存放該散列算法的中間值及最終值；該緩存分為5個32位的寄存器(A，B，C，D，E)。對于SHA-256使用一個256比特的緩存來存放該散列算法的中間值及最終值；該緩存分為8個32位的寄存器(A，B，C，D，E，F，G，H)。這些寄存器用規定的常量進行初始化。

步驟4：處理512位(16個32位字)報文分塊序列中的每個報文塊。算法的核心由80輪(對于SHA-1)或由64輪(對于SHA-256)構成，每輪結構相似，但使用不同的原始邏輯Round函數。

1)SHA-1報文調度值Wi的計算：

For i=0 to 79

If (0 ≤ i ≤ 15) Wi = Mi

Else Wi = ROL1(Wi-3 XOR Wi-8 XOR Wi-14 XOR Wi-16)

2)SHA-256報文調度值Wi的計算，它包括σ函數，ROR(右旋轉)和SHR (右移)操作：

For i=0 to 63

If (0 ≤ i ≤ 15) Wi = Mi

Else Wi = σ1(Wi-2) + Wi-7 + σ0(Wi-15) + Wi-16

其中σ0(W)是ROR7(W) XOR ROR18(W) XOR SHR3(W)，σ1(W)是ROR17(W) XOR ROR19(W) XOR SHR10(W)。

3)SHA-1各Round函數為：

For i=0 to 79

{

T = ROL5(A) + fi(B, C, D) + E + Ki + Wi；

E = D；D = C；C = ROL 30 (B)；B = A；A = T

}

其中，K是4個常量值(針對輪0-19、20-39、40-59、60-79)，f是基于相同的K四個函數之一。

4)SHA-1本次數據塊計算的最后輸出：

前一次數據塊計算的最后輸出加上本次數據塊計算最后一輪Round函數的對應輸出。

5)SHA-256各Round函數為：

For i=0 to 63

{

T1 = H + Σ1(E) + Ch(E,F,G) + Ki + Wi

T2 = Σ0(A) + Maj(A,B,C)

H = G；G = F；F = E；E = D + T1；D = C；C = B；B = A；A = T1 + T2

}

K是64個常量值，Σ1()、Σ0()、Ch()、Maj()是邏輯函數。

6)SHA-256本次數據塊計算的最后輸出：

前一次數據塊計算的最后輸出加上本次數據塊計算最后一輪Round函數的對應輸出。

步驟5：輸出。所有的512位數據塊處理完成后，最后階段產生的輸出就是該報文的散列值，SHA-1是160位，SHA-256是256位。

二、SHA指令執行環境[2]

SHA指令是在原來的處理器SIMD指令集的基礎上添加的擴展指令集,利用SIMD定義的16個全新的128位寄存器XMM0—XMM15，每個寄存器可以同時存放4個32二進制數的特點，SHA指令使用它們來完成SHA算法的相應處理步驟。SIMD的寄存器和這個4個32二進制數在寄存器中排列順序見圖1：

圖1 XXM寄存器

XXM寄存器中的這個128位SIMD的二進制數據中包含了4個32二進制數DATA0、DATA1、DATA2和DATA3。

三、SHA散列算法指令集的研究[3]

SHA散列算法指令集分2組，一組是針對SHA-1散列算法，另一組是針對SHA-256散列算法。類似于通用的X86指令，SHA指令包括兩種尋址方式：reg-reg和reg-mem。

1.SHA-1新指令集

SHA-1指令共4條指令。兩條指令sha1msg1和sha1msg2提供SHA-1算法的調度值計算。sha1msg1指令加速調度值的Wt-14 XOR Wt-16部分的計算。sha1msg2指令加速 Wt-3與之前計算的Wt-8 XOR Wt-14 XOR Wt-16的異或，然后左旋轉1位，最終得到4個32位調度值。sha1rnds4指令執行4輪Round函數功能。sha1nexte指令快速計算出E。

1)SHA1RNDS4 xmm1, xmm2/m128，imm8

說明：使用由第一個操作數提供的初始化SHA-1狀態變量 (A,B,C,D)，由第二個操作數提供的一些預先計算好的分別用于4輪的報文雙字以及狀態變量E，執行4輪Round函數計算，更新SHA-1的狀態(A、B、C、D)，將結果存儲到目的操作數中，imm8決定使用哪一個f()。SHA1RNDS4指令的操作：

IF(imm8[1:0]=0)

THEN f()←f0(), K←K0 ;

ELSE IF (imm8[1:0] = 1 )

THEN f()←f1(), K←K1 ;

ELSE IF (imm8[1:0] = 2 )

THEN f()←f2(), K←K2 ;

ELSE IF (imm8[1:0] = 3 )

THEN f()←f3(), K←K3;

FI;

A←SRC1[127:96];

B←SRC1[95:64];

C←SRC1[63:32];

D←SRC1[31:0];

W0E←SRC2[127:96];

W1←SRC2[95:64];

W2←SRC2[63:32];

W3←SRC2[31:0];

Round i = 0 operation:

A_1←f(B,C,D)+(A ROL 5)+W0E+K;

B_1←A;

C_1←B ROL 30;

D_1←C;

E_1←D;

FOR i = 1 to 3

A_(i+1)←f(B_i,C_i,D_i)+(A_i ROL 5)+Wi+E_i+K;

B_(i+1)←A_i;

C_(i+1)←B_i ROL 30;

D_(i+1)←C_i;

E_(i+1)←D_i;

ENDFOR

DEST[127:96]←A_4;

DEST[95:64] ←B_4;

DEST[63:32] ←C_4;

DEST[31:0] ←D_4;

2)SHA1NEXTE xmm1, xmm2/m128

說明：第一個操作數存放的是根據4輪計算之后SHA-1的狀態值，利用其A值計算出E值并與第一個操作數存放的調度值相加，再將它們存儲在目的操作數中。

3)SHA1MSG1 xmm1, xmm2/m128

說明：為下一次SHA-1的4個調度值做一次中間計算。

4)SHA1MSG2 xmm1, xmm2/m128

說明：做最后一次計算，以得到下一次SHA-1的4個調度值。

2.SHA-256新指令集

SHA-256指令共有3條指令。兩條指令sha256msg1和sha256msg2提供SHA-256算法的調度值計算。sha256msg1指令加速調度值的σ0(Wt-15) + Wt-16部分的計算。sha256msg2指令加速σ1(Wt-2)與之前計算的Wt-7 + Σ0(Wt-15) + Wt-16的加法，最終得到4個32位調度值。sha256rnds2指令執行2輪Round函數功能。

1)SHA256RNDS2 xmm1, xmm2/m128,

說明：執行2輪SHA-256操作。第一個操作數是初始化的SHA-256狀態(C,D,G,H)，第二個操作數是初始化的SHA-256狀態(A,B,E,F)，XMM0存儲著預先計算好的分別用于下2輪的報文雙字。請注意，只有xmm0較低的兩個雙字被指令使用。把更新的SHA-256狀態(A，B，E，F)寫入到第一個操作數，而第二個操作數可以作為以后輪的更新狀態(C，D，G，H)。SHA256RNDS2指令的操作：

A_0←SRC2[127:96];

B_0←SRC2[95:64];

C_0←SRC1[127:96];

D_0←SRC1[95:64];

E_0←SRC2[63:32];

F_0←SRC2[31:0];

G_0←SRC1[63:32];

H_0←SRC1[31:0];

WK0←XMM0[31: 0];

WK1←XMM0[63: 32];

FOR i = 0 to 1

A_(i+1)←Ch(E_i,F_i,G_i)+Σ1(E_i)+WKi+H_i+Maj(A_i,B_i,C_i)+Σ0( A_i);

B_(i+1)←A_i;

C_(i+1)←B_i ;

D_(i+1)←C_i;

E_(i+1)←Ch(E_i,F_i,G_i)+Σ1(E_i)+WKi+H_i+D_i;

F_(i+1)←E_i ;

G_(i+1)←F_i;

H_(i+1)←G_i;

ENDFOR

DEST[127:96]←A_2;

DEST[95:64] ←B_2;

DEST[63:32] ←E_2;

DEST[31:0] ←F_2;

2)SHA256MSG1 xmm1, xmm2/m128

說明：為下一次SHA-256的4個調度值做一次中間計算。

3)SHA256MSG2 xmm1, xmm2/m128

說明：做最后一次計算，以得到下一次SHA-256的4個調度值。

四、應用舉例[4]

下面給出SHA-1指令的應用實例。

SHA-1每次處理一個512位即64個字節的數據塊，在處理過程中需要做80輪Round計算。下面給出運用SHA-1指令編寫實施SHA-1算法的程序代碼。假設64個字節大小的數據塊存儲在內存緩沖區中，用指針BLOCK_PTR指向該內存緩沖區，代碼中涉及的工作變量如ABCD_SAVE、BLOCK0表示某一個XMM寄存器。

首先將初始值保存到工作變量，先從內存緩沖區取16個字節，做0-3輪，由sha1rnds4指令完成；再從內存緩沖區取16個字節，做4-7輪，由sha1nexte、sha1rnds4指令完成，sha1msg1指令為下一輪準備調整值；再一次從內存緩沖區取16個字節，做8-11輪，由sha1nexte、sha1rnds4指令完成，sha1msg1和pxor指令為下一輪準備調整值；從內存緩沖區中取出最后16個字節，做12-15輪，由sha1nexte、sha1msg2、sha1rnds4指令完成，sha1msg1和pxor指令為下一輪準備調整值；代碼如下：

movdqa ABCD_SAVE, ABCD

movdqa E_SAVE, E0

movdqu BLOCK0, [BLOCK_PTR + 0*16]

pshufb BLOCK0, SHUF_MASK

paddd E0,BLOCK0

movdqa E1,ABCD

sha1rnds4 ABCD, E0, 0

movdqu BLOCK1, [BLOCK_PTR + 1*16]

pshufb BLOCK1, SHUF_MASK

sha1nexte E1, BLOCK1

movdqa E0, ABCD

sha1rnds4 ABCD, E1, 0

sha1msg1 BLOCK0, BLOCK1

movdqu BLOCK2, [BLOCK_PTR + 2*16]

pshufb BLOCK2, SHUF_MASK

sha1nexte E0, BLOCK2

movdqa E1,ABCD

sha1rnds4 ABCD, E0, 0

sha1msg1 BLOCK1, BLOCK2

pxor BLOCK0, BLOCK2

movdqu BLOCK3, [DATA_PTR + 3*16]

pshufb BLOCK3, SHUF_MASK

sha1nexte E1, BLOCK3

movdqa E0, ABCD

sha1msg2 BLOCK0, BLOCK3

sha1rnds4 ABCD, E1, 0

sha1msg1 BLOCK2, BLOCK3

pxor BLOCK1, BLOCK3

之后繼續直到第64-67輪，都采取12-15輪模式完成，但不包括讀取數據部分，代碼模式如下：

sha1nexte E0,BLOCK0

movdqa E1,ABCD

sha1msg2 BLOCK1, BLOCK0

sha1rnds4 ABCD, E0, 0

sha1msg1 BLOCK3, BLOCK0

pxor BLOCK2, BLOCK0

末尾12輪(68-79)只需要少量的指令就可以完成，代碼如下：

;;68-71輪

sha1nexte E1,BLOCK1

movdqa E0,ABCD

sha1msg2 BLOCK2, BLOCK1

sha1rnds4 ABCD, E1, 3

pxor BLOCK3, BLOCK1

;;72-75輪

sha1nexte E0,BLOCK2

movdqa E1,ABCD

sha1msg2 BLOCK3, BLOCK2

sha1rnds4 ABCD, E0, 3

;;76-79輪

sha1nexte E1,BLOCK3

movdqa E0,ABCD

sha1rnds4 ABCD, E1, 3

最后用sha1nexte指令計算E的最終值，paddd指令計算ABCD的最終值：

sha1nexte E0, E_SAVE

paddd ABCD, ABCD_SAVE

SHA-256指令的應用實例類似上述代碼思路，受篇幅限制不再舉例。

五、結論

隨著Intel i7處理器的廣泛普及，使用SHA指令必將給程序設計人員在開發網絡安全產品時帶來新選擇。利用文中詳細介紹的內容，程序員可以簡化相關算法的代碼設計，創造出更好的信息識別軟件產品。

[1] Federal Information Processing Standards Publication 180-2：Announcing the SECURE HASH STANDARD[M/CD]. 2002 August 1. http://csrc.nist.gov/publications/fips/fips180-2/

[2]Intel Corporation: Intel 64 and IA-32 Architecture Software Developer's Manual Volume 1: Basic Architecture[M/CD]. http://WWW.INTEL.COM Order Number 253665-059US 2016.

[3]Intel Corporation: Intel 64 and IA-32 Architecture Software Developer's Manual Volume 2: Instruction Set Reference [M/CD]. http://WWW.INTEL.COM Order Number 325383-059US 2016.

[4]Se-Joon Chung ，Euiwoong Lee: In-Depth Analysis of Bitcoin Mining Algorithm Across Different Hardware[M/CD]. http://WWW.INTEL.COM.

2095-4654(2016)12-0053-04

2016-06-18

TP313

A