范建军

(湖北科技学院 计算机科学与技术学院,湖北 咸宁 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