SHA2[1]是美国国家标准与技术研究院(NIST)2001年发布的哈希算法, 作为 SHA1[2]的替代哈希算法, 包括 SHA224, SHA256, SHA384, SHA512,SHA512/224 和 SHA512/256 等 6种不同的算法标准,广泛应用于数字签名与验证、消息认证码生成和验证以及伪随机数生成等领域。
很多应用(如公共密钥设施(PKI)[3], IPSec[4],SSL/TLS[5]和 802.16 标准[6])都包含数字认证、数字签名和伪随机数生成等服务。这些服务在进行过程中, 对数据进行哈希计算是特别关键的步骤。当具有安全保护功能应用处理的用户数据比较多时, 特别是拥有大量客户端的服务器, 对处理数据的吞吐率有很高的要求, 而应用的吞吐率往往由哈希函数的吞吐率决定。
基于处理速度和安全保护方面的考虑, 产业界很多公司采用硬件电路实现哈希函数, 例如NASA只授权使用特定的硬件电路对关键数据进行加密。
随着区块链技术[7]的兴起, 大量的数据完整性验证、数字签名和伪随机数生成等功能应用到区块链的底层计算中。具有完整性验证和数据压缩功能的哈希计算在交易和区块的同步过程中是必不可少的环节。随着通信技术的发展和区块链共识算法的进化, 网络传输过程的延迟和共识机制对数据同步的影响越来越小, 而节点对交易和区块的验证计算对数据同步的影响越来越大。所以, 哈希计算硬件加速器性能的提升对区块链交易和区块验证速度的提升有较大的帮助, 从而对促进区块链技术的商业应用落地有一定的帮助。
1 SHA2硬件电路及相关研究
为了提升 SHA2 哈希计算的性能, 产业界和学术界对哈希函数硬件电路的优化集中在结构优化和路径延迟优化两个方面。从基本迭代结构, 到部分展开结构, SHA2 硬件电路的优化方案不断演进。为减少关键路径上的路径延迟, 各种技术(如延迟均衡和加法器进位链优化(CSA 等))不断被采用。
1.1 基本迭代架构
Roar 等[8]提出基本迭代结构的 SHA2 硬件电路,相对于软件加密方案, 明显地提高了处理速度, 但具有 7个加法器的关键路径太长, 路径延迟也比较大, 限制电路性能的提高。
1.2 全展开结构
Deepakumara 等[9]利用全展开结构, 使 MD5 硬件电路的计算吞吐率得到明显提升, 但因关键路径太长而限制了电路工作频率的提高。然而, 它为进一步提高 SHA2 硬件电路的性能提供了一种与以往不同的思路——展开结构。
1.3 部分展开结构
为了提升单个消息哈希计算的性能和缓解全展开结构中关键路径太长的问题, Michail 等[10–11]和Dadda 等[12]采用部分展开结构来提升 SHA2 电路的处理性能。这种结构每个时钟周期处理 k 轮哈希变换, 计算一次消息摘要迭代的时钟周期缩小为原来的 1/k。
这种方法为相邻两轮哈希变换的一系列运算的整合优化提供了可能性, 以每个周期展开两轮哈希变换为例, 其关键路径上串联 6个加法器, 路径延迟在很大程度上把电路工作频率限制在较低的水平, 特别是在 SHA2-512 处理时, 6个串联的 64 位加法器的路径延迟更大。
基于展开系数为 2 的 SHA2 部分展开结构, 虽然 Michail 等[10–11]和 Dadda 等[12]的电路不同, 但缩短关键路径的思路大体上相同。1) 为了缩短两轮哈希变换的关键路径, 把每个周期的两轮哈希变换处理分为前处理和后处理, 两个模块都采用准流水线结构。2) 由于所有 Wt 在迭代变换前可以预先计算都得到, 并且常数 Kt 是基于迭代次数的先验值,所以 Wt 与 Kt 的求和可以在 At 和 Et 的计算路径之外提前运算, 并将求和结果存在中间寄存器中, 以备 At 和 Et 的计算之用。3) 采用多操作数加法器代替两操作数加法器, 从而减少多个串联的加法器进位链的个数, 减少串联求和运算中进位链对关键路径的影响。
Michail 等 [10–11]和 Dadda 等 [12]提 出 的 SHA256硬件优化方案都可以显著地提高 SHA256 硬件加速引擎的吞吐率, 但提出的“连接预计算和后计算两级准流水结构”并不是真正的流水线结构, 实际上还是平均每个时钟周期处理一轮 SHA2 运算, 不能充分发挥“部分展开结构”成倍提升性能的效果。
2 提出的优化方案
目前, SHA2 系列哈希函数在区块链技术中得到广泛的应用。为了满足区块链对 SHA2 系列不同哈希函数的高性能计算需求, 本文分别从系统结构和微观计算方面做了相应的改进。
2.1 优化的系统架构
如图1 所示, 优化的 SHA2 硬件加速器的系统架构包括消息填充模块、消息乒乓缓存器和消息迭代压缩模块。通过采用乒乓缓存器、消息填充模块和消息迭代压缩模块, 可以实现两级流水处理, 流水线的处理级别是一个包含 16个消息字的消息块。对待压缩的源数据, 首先由填充单元对源数据进行数据填充和分块(每个消息块包含 16个消息字), 写入填充数据的 2 Kb 乒乓缓存中(2 Kb 是 SHA384/SHA-512 处理的两个完整消息块的容量)。只要填充数据的乒乓缓存中含有一个完成的消息块, 迭代压缩模块就可以开始进行迭代处理。迭代压缩模块每个时钟周期处理两个哈希变换, 对应地, 每个时钟周期从填充乒乓缓存读出两个消息字。迭代压缩模块中, 8个 64 位寄存器 a~h 用来存储哈希迭代处理中的中间状态, 8个 64 位寄存器 h0~h7 用来存储消息块的哈希摘要值, 16个 64 位寄存器 w0~w15 用来存储消息字或者扩展消息字, 控制模块负责迭代轮次的控制、K 值的读取以及寄存器 a~h、h0~h7和 w0~w15 的读写等。
图1 优化的SHA2硬件加速器的系统架构
Fig.1 System architecture of proposed SHA2 hardware accelerator
SHA2 哈希计算引擎不仅可以支持对消息进行SHA2 系列哈希函数的运算, 还可以支持对消息进行 SHA2 系列哈希函数的双重运算。哈希函数的双重运算或者双重哈希, 是将由哈希函数计算得到消息的哈希摘要作为消息, 并对之进行哈希函数处理。在迭代压缩单元的控制器的控制下, 把哈希摘要 h0, h1, …, h7 作为消息, 并对其进行迭代哈希变换。
2.2 优化的哈希迭代
本文采用如下更加优化的技术来实现 SHA2 计算引擎的性能的提升。
2.2.1 两轮展开的哈希两级流水架构
采用预计算时序均衡技术, 把两轮展开的哈希迭代运算均匀地分为预计算和后计算两部分, 并将这两部分计算分别作为流水线处理的两级电路。预计算和后计算两级流水电路的均匀划分使流水线电路的时序更加均衡, 图2 示意两轮 SHA2 系列哈希函数计算部分的划分。预计算部分可由式(1)~(4)表示:
图2 预计算和后计算的流水线结构
Fig.2Pipeline diagram of pre-computationand pos-computation
后计算部分由式(5)~(8)表示:
式(1)~(8)都是多操作数的求和计算。通过采用新型的进位链更短的多加数求和计算技术, 这些求和计算的关键路径得以缩短, 从而实现在较高的时钟频率下, 展开的两轮哈希迭代运算可以满足时序要求的目标。
2.2.2 使用多操作数加法压缩器
预计算部分的最长路径为计算 V0 和 V1 的路径, 是 6个加数求和的运算。对 6个加数求和的硬件电路由多操作数加法压缩器和快速加法器组成。如图3 所示, 6个操作数求和的电路可以由 3:2 压缩器、4:2 压缩器和 5:2 压缩器来实现。表1 描述门数以及在关键路径延迟的门数。
图3 实现预计算压缩器和加法器的不同组合
Fig.3 Combinations of compressors and adder used to perform pre-computation
表1 不同压缩器的门数
Table 1 Gate count of various compressors
压缩器类别 输入个数 输出个数 关键路径门数 总门数3:2压缩器 3 2 2*XOR 2*XOR + MUX 4:2压缩器 5 3 2*XOR 3*XOR+2*MUX 5:2压缩器 7 4 2*XOR 6*XOR+2*MUX+3*OR+3*AND
从表2 可以看出, 采用 4:2 压缩器、3:2 压缩器和快速加法器的方案是实现预计算部分的 V0 和 V1计算的最优方案, 临界路径短、成本低。
表2 预计算单元不同方案的路径延迟和门数
Table 2 Path delay and gate count of different schemes for pre-computation unit
实现类别 关键路径资源 所用资源图3(a) 6*XOR+Adder 6*XOR+3*MUX+Adder图3(b) 7*XOR+Adder 8*XOR+4*MUX+Adder图3(c) 10*XOR+Adder 10*XOR+5*MUX+3*OR+3*AND+Adder
后计算部分是两块相同的哈希计算电路的级联运算, 它们分别负责 post0_A, post0_E, post0_Hx0和 post0_Hx1 的计算与 post1_A, post1_E, post1_Hx0和 post1_Hx1 的计算。如图4 所示, 通过对推导postX_Hx0 和 postX_A 的路径的分析, 可以确定采用 4:2 压缩器、3:2 压缩器和快速加法器计算 postX_Hx0 和 postX_A 的方案最优。采用 3:2 压缩器和快速加法器计算 postX_Hx0 和 postX_E 的方案是最优方案, 关键路径延迟也最小。
图4 后计算中使用的多操作数加法
Fig.4 Mult-operand addition used in post-computation
2.2.3 4:2/3:2 压 缩 器 用 XOR-XNOR 和 MUX 代 替XOR 门
由于 XOR-XNOR 组合门和 MUX 门的延迟时间小于 XOR 门[13], 因此本文使用 XOR-XNOR 组合门和 MUX 门替代 4:2 压缩器和 3:2 压缩器的 XOR门, 以减小 4:2 压缩器和 3:2 压缩器的延迟。
2.2.4 快速加法器
连波进位加法器(RCA)的进位链延迟与加法器的位数成正比, 所用的硬件资源也与位数成正比。超前进位加法器(CLA)的进位链关键路径与位数无关, 计算进位输出的延迟固定为 3 级门延迟, 如果扩大加法器位宽, 则电路就变得非常复杂。32 位或 64 位加法运算通常是由小的超前进位加法器(4 位或 8 位超前进位加法器)串联而成的传播进位加法器。选择进位加法器首先把进位分别为 0 和 1 的两个求和结果同时计算出来, 然后再利用进位输入值, 选择相应的结果作为最终结果。关键路径主要由低位的加法器和高位选择进位加法器引入的多路器组成, 其延迟远低于超前进位加法器的关键路径延迟, 但在同样位数的加法器中, 选择进位加法器所用的门数比超前进位加法器多。综合考虑时序和面积两个因素, 我们采用超前进位加法器、传播进位加法器和选择进位加法器的组合方式设计, 可以适应不同需求的 64 位快速加法器。
表3 列出不同快速加法器的性能和资源。通过分析, 我们采用 3 对 16 位传播进位加法器, 分别基于进位输入为 0 和 1 两种情况, 对高 48 位操作数实现进位选择加法器(其中 16 位传播进位加法器由两个 8 位超前进位加法器组成)来实现加法器的快速运算。加法器的速度提升以增加 3个 8 位超前进位加法器为代价来换取, 因此只用于后运算部分的关键路径 post0_A, post0_E, post1_A, post1_E, post0_hx0 以 及 post0_hx1, post1_hx0 和 post1_hx1 的 计算。在预计算部分的两输入加法运算, 可以使用 64 位 FastAdder (8 位 CLA 和 32 位 CPA)或 64 位超前进位加法器。
表3 不同快速加法器的性能和资源
Table 3 Performance and resources of various fast adders
说明: 4bcla 是 4 位超前进位加法器; 8bCLA 是 8 位超前进位加法器。
64位快速加法器 关键路径门数 总加法器数64FastAdder (4bcla, 4bCPA) 3*AND+15*MUX 31*(4bcla)64FastAdder (4bcla, 8bCPA) 6*AND+7*MUX 31*(4bcla)64FastAdder (4bcla, 16bCPA) 12*AND+3*MUX 30*(4bcla)64FastAdder (4bcla, 32bCPA) 24*AND+1*MUX 24*(4bcla)64FastAdder (4bcla, 64bCPA) 48*AND 16*(4bcla)64FastAdder (8bCLA, 8bCPA) 3*AND+7*MUX 15*(8bCLA)64FastAdder (8bCLA, 16bCPA) 6*AND+3*MUX 14*(8bCLA)64FastAdder (8bCLA, 32bCPA) 12*AND+1*MUX 12*(8bCLA)64FastAdder (8bCLA, 64bCPA) 24*AND 8*(8bCLA)
为了均衡预计算和后计算的延迟, 选择64Fast-Adder (8 位 CLA 和 64 位 C PA)作为预计算的加法器,选择 64FastAdder (8 位 CLA 和 16 位 CPA)作为 后计算部分中计算 post0_A, post0_E, post1_A 和 post1_E的加法器, 计算 post0_hx0 和 post0_hx1 的加法器选择 64FastAdder (8 位 CLA 和 64 位 CPA), 计算 post1_hx0 和 post1_hx1 的 加 法 器 选 择 64FastAdder (8 位CLA 和 16 位 CPA), 使预计算和后计算的延迟值在32个门延迟左右。在满足时序要求的前提下, 几条计算路径中不使用统一的快速加法器, 可以在时序要求不太高的路径采用超前进位加法器, 从而可以节省硬件资源。
基于以上分析, SHA2 的迭代压缩模块采用两轮哈希变换展开技术, 可以使每一时钟周期处理两轮哈希变换, 性能比传统的每个时钟周期处理一轮哈希变换方案提升一倍。SHA2 的迭代压缩模块采用预计算和后计算的两级流水线结构、与进位无关的多操作数加法压缩器技术和快速加法器技术等,使得哈希变换部分的关键路径变短, 可以使迭代压缩模块工作在更高时钟频率。通过这两个方面的优化, 哈希计算引擎的吞吐率得到大幅提升。
3 实验和讨论
在本文提出的方案中, 填充部分和迭代部分都以流水线的形式来实现, 所以 SHA2 迭代部分所需的消息字已经在填充乒乓缓冲区中准备好, 无需等待填充处理。因此, 对 SHA2 单哈希的性能分析主要基于 SHA2 迭代的处理速度。
SHA2 硬件加速器的吞吐率可以用式(9)表示:
其中, BlockSize 表示消息块的大小, f 表示工作频率,ClockCycles 表示用于获取最终摘要的时钟周期。
根据 SHA2 的算法, 我们可以知道 SHA224 和SHA384 的 吞 吐 率 分 别 与 SHA256 和 SHA512 的 吞吐率一致。因此, 我们选用 SHA256 和 SHA512 两种哈希算法来完成 SHA2 硬件加速器的性能测试。该硬件 SHA2 加速器使用 Xilinx FPGA (Virtex 6 xc6vlx760) 进行测试, 工作频率为 92.1 MHz, 成本为 8216 LUTs。通过测试, 可以得到 SHA256 和SHA512 的吞吐率, 见表4。
表4 基于 Virtex 6 的 SHA2 单哈希和双哈希吞吐率
Table 4 Throughput of SHA2 single Hash and double hash based on Virtex 6
SHA2类型 吞吐率/Mbps单哈希 双哈希SHA256 1428.95 714.47 SHA512 2300.25 1150.13
SHA256 与文献[14]的性能比较如表5 所示。虽然文献[14]的工作频率比本文方案高, 但其处理 SHA256 的吞吐率比本文方案低。
表5 SHA256 的吞吐率比较
Table 5 Throughput comparison of SHA256
SHA256硬件 器件 时钟/ MHz 吞吐率/Mbps文献[14]Virtex 354 1405本文方法 Virtex 6 92.1 1428.95
SHA512 与文献[15]的计算性能比较如表6 所示。可以看出, 本文在处理 SHA512 时的工作频率和吞吐率都明显超过文献[15]。
表6 SHA512的吞吐率比较
Table 6 Throughput comparison of SHA512
SHA512硬件 器件 时钟/MHz 吞吐率/Mbps文献[15]Virtex 50 467本文方法 Virtex 6 92.1 2300.25
根据上述分析, 在硬件共享情况下, 该 SHA2硬件加速器显著地提升了 SHA2 系列哈希计算的性能。
4 总结
针对以往 SHA2 硬件吞吐率难以提升的问题,本文提出一种新的改进方法, 还提供了一种能够满足区块链 SHA2 双哈希计算需求的快速实现方法。
1) 使用乒乓缓存存储前期生成的 SHA2 填充数据, 使 SHA2 填充处理和迭代运算的两个硬件电路以两级流的形式并行处理。
2) 提取两轮哈希迭代中的独立元素作为预处理部分, 与迭代运算的后处理部分形成真正的流水线处理, 成功地避免以往研究中提出的伪流水线设计。
3) 在前处理部分和后处理部分, 采用 3:2/4:2 压缩器和无进位链的快速加法器来缩短关键路径, 减少关键路径延迟。
为了适应区块链技术的 SHA2 双哈希要求, 本文还支持对计算出的源操作数的摘要进行二次哈希, 以便得到双哈希计算的最终结果, 减少外部存储器和相关数据处理的访问时间, 提高了 SHA2 双哈希计算的处理速度。这些方法对于提高哈希函数独立硬件(如 SHA256, SH384, SHA512甚至SM3)的性能有参考意义。
[1]National Institute of Standards and Technology.FIPS PUB 180-3, Secure Hash standard [EB/OL].(2008–10)[2021–11–25].https://csrc.nist.gov/csrc/media/pub lications/fips/180/3/archive/2008-10-31/documents/fips 180-3_final.pdf
[2]National Institute of Standards and Technology.FIPS 180-4, Secure Hash Standard [EB/OL].(2012–06–03)[2021–11–25].https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.180-4.pdf
[3]Cooper D.Internet x.509 public key infrastructure certificate and certificate revocation list (CRL) profile.RFC 5280 [EB/OL].(2008–05)[2021–11–25].http://mirrors.nju.edu.cn/rfc/beta/errata/rfc5280.html#btn_3579
[4]Thayer R, Doraswamy N, Glenn R.IP security document roadmap.RFC 2411 [EB/OL].(1998–11)[2021–11–25].http://mirrors.zju.edu.cn/rfc/rfc2411.html
[5]Freier A.O, Karlton P, Kocher P.The secure sockets layer (SSL) protocol version 3.0.RFC 6101 [EB/OL].(2011–08)[2021–11–25].https://www.rfc-editor.org/rfc/rfc6101
[6]Eklund C, Marks R, Stanwood K, et al.IEEE standard 802.16: a technical overview of the WirelessMANTM air interface for broadband wireless access.IEEE Communications Magazine, 2002, 40(6): 98–107
[7]Zheng Z, Xie S, Dai H, et al.An overview of blockchain technology: architecture, consensus, and future trends // 2017 IEEE International Congress on Big Data (BigData Congress).Honolulu, 2017: 557–564
[8]Roar L, Grembowski T, Gaj K.A 1 Gbit/s partially unrolled architecture of hash functions SHA-1 and SHA-512 // Okamoto T.Topics in Cryptology — CTRSA 2004: Lecture Notes in Computer Science.Berlin: Springer, 2004: 2964
[9]Deepakumara J, Heys H, Venkatesan R.FPGA implementation of MD5 Hash algorithm // Canadian Conference on Electrical and Computer Engineering 2001: Conference Proceedings (Cat.No.01TH8555).Toronto, 2001: 919–924
[10]Michail H, Kakarountas A, Milidonis A, et al.A Topdown design methodology for ultrahigh-performance Hashing cores.IEEE Transactions on Dependable and Secure Computing, 2009, 6(4): 255–268
[11]Michail H, Milidonis A, Kakarountas A, et al.Novel high throughput implementation of SHA-256 Hash function through pre-computation technique // 2005 12th IEEE International Conference on Electronics:Circuits and Systems.Gammarth, 2005: 1–4
[12]Dadda L, Macchetti M, Owen J.An ASIC design for a high speed implementation of the Hash function SHA-256 (384, 512) // Automation and Test in Europe Conference and Exhibition: Proceedings Design.Paris,2004: 70–75
[13]Woo-Hyun K, Hoon-Jae K, Soo-Won K.Low power logic design using push-pull pass-transistor logics.International Journal of Electronics, 2010, 8(5): 467–478
[14]Wong M M, Pudi V, Chattopadhyay A.Lightweight and high performance SHA-256 using architectural folding and 4-2 adder compressor // 2018 IFIP/IEEE International Conference on Very Large Scale Integration (VLSI-SoC).Verona, 2018: 95–100
[15]Sun W, Guo H, He H, et al.Design and optimized implementation of the SHA-2 (256, 384, 512) Hash algorithms // 2007 7th International Conference on ASIC.Guilin, 2007: 858–861