硬件安全（1）—— SHA-1算法在FPGA上的实现-2_sha1 并行 verilog

SHA-1算法在FPGA上的实现-2

在上一篇文章中，我详细介绍了SHA-1算法的计算过程。SHA-1算法主要由消息填充(Message Padding)和哈希计算(Hash Function Engine)两部分组成。消息块标准长度规定为512bits一组。消息填充在实现过程中需要区分长度不足一个消息块( < 512 bits)、长度超过一个消息块( > 512 bits)与长度刚好为一个消息块( = 512 bits)的时候。在这一篇文章中，我将介绍消息填充以及哈希计算的FPGA实现思路。

消息填充（Message Padding）

在SHA-1算法当中，输入消息的处理是需要重点考虑的几个部分之一。SHA-1算法要求输入的消息块将被分割成512bits为一组，即16个字（每个字长度为32bits）。在整个算法当中，每个字参与一轮计算，一共80轮，前16轮使用原本的“字”，后64轮使用扩展后的“字”，具体的扩展方法在上一篇文章中有提到，这里不再赘叙。

上图是我节选自网络的一张PPT，它形象的介绍了在SHA-1算法中消息填充的方法。值得注意的是，Message Padding中特意在原始消息后，填充“0”之前，使用了一个“1” bit。这里使用“1”，而不是全部使用“0”来填充的原因是考虑到了二义性。
对应在SHA-1算法的消息填充步骤中，在填充的原始消息后加“1”的原因就是，如果我们的填充函数只是简单地添加零位，直到填充的消息具有正确的长度，那么这将导致以下形式的冲突，Hash(M) = Hash(M||0)。也就是出现了两个数，经过了Hash计算后得出了同一个哈希值。Hash Function的缺陷之一就是可能会出现两个数，比如上述的消息（M）和消息（M||0），注意，（M||0）指的是消息（M）后拼接了一个0,在哈希运算中映射到同一个哈希值。这就意味着了Hash函数被Attacked，密码被攻破，敌手不需要知道SHA-1的初始值（IV）以及原始消息，只需要用类似的方式碰撞出相同的Hash值，就可以通过验证，获取信息。“1”bit的存在意义就是在加密后，不会如同长度为1-512bits的“0”一般，被敌手轻易查获。

// Message Padding fsm 
always @(posedge clk or negedge rst_n)
begin
	if(!rst_n) begin
		current_state <= s_IDLE;
	end
	else begin
		current_state <= next_state;
	end
end
always @ (*) 
begin
	case(current_state)
		s_IDLE: i_start && i_last 		? 		next_state = s_PAD 	:
				i_start                	? 		next_state = s_OP		:
													next_state = s_IDLE	;
		s_OP:	w_alg_done				?			next_state = s_PAD	:
																next_state = s_OP		;
		s_PAD:	w_blen_512 && (w_len < 'h38) ?	next_state = s_PAD	:
																				next_state = s_DONE;
		s_DONE: next_state = s_IDLE;
		default: next_state = s_IDLE;
	endcase
end
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

在上面这个状态机中，我考虑了填充长度不足一个消息块（448 bits)以及该消息块是最后一个消息块的情况。具体情况还有，消息块长度为消息单位长度的整数倍的情况、消息块长度为0的情况。可以请读者自己酌情添加。

哈希计算（Hash Function）

哈希函数SHA-1的具体计算在上一篇中已经详细介绍，这里不再赘述，直接给出代码。

SHA-1 Function

在SHA-1算法的计算轮次中，使用到了三种不同的函数，分别是Ch(x,y,z)、Parity(x,y,z)、Maj(x,y,z)，以及ROTLⁿ(x)具体的代码实现展示如下：

// ch(x,y,z) 
function [31:0] sha1_ch();
input [31:0] x,y,z;
begin
	sha1_ch = (x & y) ^ (~x & z);
end
endfunction
// parity(x,y,z)
function [31:0] sha1_parity();
input [31:0] x,y,z;
begin
	sha1_parity = x ^ y ^ z;
end
endfunction
// maj(x,y,z)
function [31:0] sha1_maj();
input [31:0] x,y,z;
begin
	sha1_maj = (x & y) ^ (x & z) ^ (y & z);
end
endfunction
// ROTL
function [31:0] sha_rotl();
input [31:0] x;
input integer n;
sha_rotl = (x << n) | (x >> 32 - n);
endfunction
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

SHA-1 Constants

在SHA-1算法中，每20轮有一个K值参与计算，一共4个K值，K值为常量，实现代码如下：

function [31:0] sha1_find_k();
input x;
reg [31:0] p_K [0:3];
begin
	{p_K[0], p_K[1], p_K[2], p_K[3]} = 
		{32'h5a827999, 32'h6ed9eba1, 32'h8f1bbcdc, 32'hca62c1d6};
end
endfunction
1
2
3
4
5
6
7
8

Hash IV (Initial Value)

Hash 算法能实现不固定长度的消息块通过运算转化为固定长度的消息摘要，在SHA-1中，这个固定长度为5个字，160bits。最初的值可根据官方参考，展示如下：

H[0] = 32'h67452301 ;
H[1] = 32'hefcdab89 ;
H[2] = 32'h98badcfe ;
H[3] = 32'h10325476 ;
H[4] = 32'hc3d2e1f0 ;
1
2
3
4
5

SHA-1 Processing

经过消息块的分组&填充处理，并扩展之后，SHA-1算法的最终实现参考如下：

module	sha1_round(
	input					clk,
	input					rst_n,
	input					i_first,
	input	[511:0]		i_msg,
	output	[159:0]		o_digest
);
reg	[31:0]		T;
reg	[31:0]		W;
reg	[31:0]		WT;
integer i;

always @ (posedge clk) begin
if(first) begin
	H[0] = 32'h67452301 ;
	H[1] = 32'hefcdab89 ;
	H[2] = 32'h98badcfe ;
	H[3] = 32'h10325476 ;
	H[4] = 32'hc3d2e1f0 ;
end
else begin
	W[4] = W[3];
	W[3] = W[2];
	W[2] = sha1_rotl(W[1], 30);
	W[1] = W[0];
	W[0] = T;
end
end
always @ (posedge clk)begin
for(i = 0; i<5; i++) begin
	W[i] = H[i];
end
end
	
always @ (posedge clk) begin
for(i = 0; i<20; i++)begin
	T = sha1_rotl(H[0], 5) + sha1_ch(h[1],H[2],H[3]) + H[4] + sha1_find_k(0) + WT[i];
end
for(i = 20; i<40; i++)begin
	T = sha1_rotl(H[0], 5) + sha1_parity(h[1],H[2],H[3]) + H[4] + sha1_find_k(1) + WT[i];
end
for(i = 40; i<60; i++)begin
	T = sha1_rotl(H[0], 5) + sha1_maj(h[1],H[2],H[3]) + H[4] + sha1_find_k(2) + WT[i];
end
for(i = 60; i<80; i++)begin
	T = sha1_rotl(H[0], 5) + sha1_parity(h[1],H[2],H[3]) + H[4] + sha1_find_k(4) + WT[i];
end
end

always @ (posedge clk) begin
	for(i = 0; i<16; i++)begin
		WT[i] = i_msg[i+:32];
	end
	for(i=16; i<80; i++)begin
		WT[i] = (WT[i-3] << 1) | (WT[i-3] >> 31) ^ (WT[i-8] << 1) | (WT[i-8] >> 31) ^ (WT[i-14] << 1) | (WT[i-14] >> 31) ^ (WT[i-16] << 1) | (WT[i-16] >> 31);
	end
end
assign o_digest = {W[5], W[4], W[3], W[2], W[1], W[0]};
endmodule
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

总结

在该章中，我使用Verilog HDL代码实现了SHA-1算法中算法的具体计算以及消息的填充。所有的代码都是凭借记忆手打，仅供参考。如果有疑问，可以留言，欢迎相互交流。