Compact Keccak Hardware Architecture for Data Integrity and Authentication on FPGAs

ABSTRACT

Cryptographic hash functions play a crucial role in networking and communication security, including their use for data integrity and message authentication. Keccak hash algorithm is one of the finalists in the next generation SHA-3 hash algorithm competition. It is based on the sponge construction whose hardware performance is worth investigation. We developed an efficient hardware architecture for the Keccak hash algorithm on Field-Programmable Gate Array (FPGA). Due to the serialization exploited in the proposed architecture, the area needed for its implementation is reduced significantly accompanied by higher efficiency rate. In addition, low latency is attained so that higher operating frequencies can be accessed. We use the coprocessor approach which exploits the use of RAM blocks that exist in most FPGA platforms. For this coprocessor, a new datapath structure allowing parallel execution of multiple instructions is designed. Implementation results prove that our Keccak coprocessor achieves high performance in a small area.     

Hardware implementation analysis of SHA-256 and SHA-512 algorithms on FPGAs

Hash functions are common and important cryptographic primitives, which are very critical for data integrity assurance and data origin authentication security services. Field programmable gate arrays (FPGAs) being reconfigurable, flexible and physically secure are a natural choice for implementation of hash functions in a broad range of applications with different area-performance requirements. In this paper, we explore alternative architectures for the implementation of hash algorithms of the secure hash standards SHA-256 and SHA-512 on FPGAs and study their area-performance trade-offs. As several 64-bit adders are needed in SHA-512 hash value computation, new architectures proposed in this paper implement modulo-64 addition as modulo-32, modulo-16 and modulo-8 additions with a view to reduce the chip area. Hash function SHA-512 is implemented in different FPGA families of ALTERA to compare their performance metrics such as area, memory, latency, clocking frequency and throughput to guide a designer to select the most suitable FPGA for an application. In addition, a common architecture is designed for implementing SHA-256 and SHA-512 algorithms.     

Implementation of the SHA-2 Hash Family Standard Using FPGAs

The continued growth of both wired and wireless communications has triggered the revolution for the generation of new cryptographic algorithms. SHA-2 hash family is a new standard in the widely used hash functions category. An architecture and the VLSI implementation of this standard are proposed in this work. The proposed architecture supports a multi-mode operation in the sense that it performs all the three hash functions (256, 384 and 512) of the SHA-2 standard. The proposed system is compared with the implementation of each hash function in a separate FPGA device. Comparing with previous designs, the introduced system can work in higher operation frequency and needs less silicon area resources. The achieved performance in the term of throughput of the proposed system/architecture is much higher (in a range from 277 to 417%) than the other hardware implementations. The introduced architecture also performs much better than the implementations of the existing standard SHA-1, and also offers a higher security level strength. The proposed system could be used for the implementation of integrity units, and in many other sensitive cryptographic applications, such as, digital signatures, message authentication codes and random number generators.     

BLAKE算法的硬件实现研究

随着对MD5和SHA1攻击方法的提出,美国国家标准技术研究所(NIST)组织启动了SHA-3的征集计划,目前已进入第3轮.BLAKE算法进入了最后一轮竞赛,文中首先综述了BLAKE算法从提交到目前为止在硬件评估方面的状况.在此基础上优化了BLAKE压缩函数在FPGA上实现的关键路径,并在FPGA平台上实现了BLAKE算法.和现有的BLAKE算法在FPGA上实现的吞吐率相比,文中实现结构的吞吐率又有提升.     

Compact and unified hardware architecture for SHA-1 and SHA-256 of trusted mobile computing

This paper presents a compact and unified hardware architecture implementing SHA-1 and SHA-256 algorithms that is suitable for the mobile trusted module (MTM), which should satisfy small area and low-power condition. The built-in hardware hash engine in a MTM is one of the most important circuit blocks and dominates the performance of the whole platform because it is used as a key primitive to support most MTM commands concerning to the platform integrity and the command authentication. Unlike the general trusted platform module (TPM) for PCs, the MTM, that is to be employed in mobile devices, has very stringent limitations with respect to available power, circuit area, and so on. Therefore, MTM needs the spatially optimized architecture and design method for the construction of a compact SHA hardware. The proposed hardware for unified SHA-1 and SHA-256 component can compute a sequence of 512-bit data blocks and has been implemented into 12,400 gates of 0.25 μm CMOS process. Furthermore, in the processing speed and power consumption, it shows the better performance in comparison with commercial TPM chips and software-only implementation. The highest operation frequency and throughput of the proposed architecture are 137 MHz and 197.6 Mbps, respectively, which satisfy the processing requirement for the mobile application.     

应用于后量子密码的高速高效SHA-3硬件单元设计

随着量子计算技术的高速发展,传统的公钥密码体制正在遭受破译的威胁,将现有加密技术过渡到具有量子安全的后量子密码方案上是现阶段密码学界的研究热点。在现有的后量子密码(Post-Quantum Cryptography,PQC)方案中,基于格问题的密码方案由于其安全性,易实施性和使用灵活的众多优点,成为了最具潜力的PQC方案。SHA-3作为格密码方案中用于生成伪随机序列以及对关键信息散列的核心算子之一,其实现性能对整体后量子密码方案性能具有重要影响。考虑到今后PQC在多种设备场景下部署的巨大需求,SHA-3的硬件实现面临着高性能与有限资源开销相互制约的瓶颈挑战。对此,本文提出了一种高效高速的SHA-3硬件结构,这种结构可以应用于所有的SHA-3家族函数中。首先,本设计将64 bit轮常数简化为7 bit,既减少了轮常数所需的存储空间,也降低了运算复杂度。其次,提出了一种新型的流水线结构,这种新型结构相比于通常的流水线结构对关键路径分割得更加均匀。最后,将新型流水线结构与展开的优化方法结合,使系统的吞吐量大幅提高。本设计基于XilinxVirtex-6现场可编程逻辑阵列(FPGA)完成了原型实现,结果显示,所设计的SHA-3硬件单元最高工作频率可达459 MHz,效率达到14.71 Mbps/Slice。相比于现有的相关设计,最大工作频率提高了10.9%,效率提升了28.2%。     

基于FPGA的SHA-1算法的设计与实现

SHA-1算法是目前常用的安全散列算法，被广泛地应用于电子商务等信息安全领域。为了满足安全散列算法的计算速度，该文将SHA-1分成5个硬件结构模块来实现，每个模块可以独立工作。对其进行了优化，达到了缩短关键路径的目的，提高了计算速度。独立的模块使得对每个模块的修改都不会影响其他模块的工作，为模块的进一步优化提供了方便。     

SHA2 and SHA-3 accelerator design in a 7 nm technology within the European Processor Initiative

This paper proposes the architecture of the hash accelerator, developed in the framework of the European Processor Initiative. The proposed circuit supports all the SHA2 and SHA-3 operative modes and is to be one of the hardware cryptographic accelerators within the crypto-tile of the European Processor Initiative. The accelerator has been verified on a Stratix IV FPGA and then synthesised on the Artisan 7 nanometres TSMC silicon technology, obtaining throughputs higher than 50 Gbps for the SHA2 and 230 Gbps for the SHA-3, with complexity ranging from 15 to about 30 kGE and estimated power dissipation of about 13 (SHA2) to 26 (SHA-3) mW (supply voltage 0.75 V). The proposed design demonstrates absolute performances beyond the state-of-the-art and efficiency aligned with it. One of the main contributions is that this is the first SHA-2 SHA-3 accelerator synthesised on such advanced technology.     

可重构散列函数密码芯片的设计与实现

根据不同环境对安全散列算法安全强度的不同要求,采用可重构体系结构的思想和方法,设计一种可重构的散列函数密码芯片。实验结果表明,在Altera Stratix II系列现场可编程门阵列上,SHA-1, SHA-224/256, SHA-384/512的吞吐率分别可达到727.853 Mb/s, 909.816 Mb/s和1.456 Gb/s。     

单向散列函数SHA-512的优化设计

在分析NIST的散列函数SHA-512基础上，对散列函数SHA-512中的关键运算部分进行了分解，通过采用中间变量进行预行计算，达到了SHA-512中迭代部分的并行计算处理，提高了运算速度。通过这种新的硬件结构，优化后的散列函数SHA-512在71.5MHz时钟频率下性能达到了1 652Mbit/s的数据吞吐量，比优化前性能提高了约2倍，最后还将实验结果与MD-5、SHA-1商用IP核性能进行了比较。     

Cryptographic hash standards: where do we go from here?

Successful attacks against the two most commonly used cryptographic hash functions, MD5 and SHA-1, have triggered a kind of feeding frenzy in the cryptographic community. Many researchers are now working on hash function attacks, and we can expect new results in this area for the next several years. This article discusses the SHA-1 attack and the US National Institute of Standards and Technology's (NIST's) plans for SHA-1 and hash functions in general.     

High-Speed FPGA Implementation of Secure Hash Algorithm for IPSec and VPN Applications

Hash functions are special cryptographic algorithms, which are applied wherever message integrity and authentication are critical. Implementations of these functions are cryptographic primitives widely used in common cryptographic schemes and security protocols such as Internet Protocol Security (IPSec) and Virtual Private Network (VPN). In this paper, a novel FPGA implementation of the Secure Hash Algorithm 1 (SHA-1) is proposed. The proposed architecture exploits the benefits of pipeline and re-timing of execution through pre-computation of intermediate temporal values. Pipeline allows division of the calculation of the hash value in four discreet stages, corresponding to the four required rounds of the algorithm. Re-timing is based on the decomposition of the SHA-1 expression to separate information dependencies and independencies. This allows pre-computation of intermediate temporal values in parallel to the calculation of other independent values. Exploiting the information dependencies, the fundamental operational block of SHA-1 is modified so that maximum operation frequency is increased by 30% approximately with negligible area penalty compared to other academic and commercial implementations. The proposed SHA-1 hash function was prototyped and verified using a XILINX FPGA device. The implementation’s characteristics are compared to alternative implementations proposed by the academia and the industry, which are available in the international IP market. The proposed implementation achieved a throughput that exceeded 2,5 Gbps, which is the highest among all similar IP cores for the targeted XILINX technology.     

Improved preimage attack on one-block MD4

MD4 is a hash function designed by Rivest in 1990. The design philosophy of many important hash functions, such as MD5, SHA-1 and SHA-2, originated from that of MD4. We propose an improved preimage attack on one-block MD4 with the time complexity 2⁹⁵ MD4 compression function operations, as compared to the 2^{107 1} complexity of the previous attack by Aoki et al. (SAC 2008). The attack is based on previous methods, but introduces new techniques. We also use the same techniques to improve the pseudo-preimage and preimage attacks on Extended MD4 with 2^25.2 and 2^12.6 improvement factor, as compared to previous attacks by Sasaki et al. (ACISP 2009).     

On security arguments of the second round SHA-3 candidates

In 2007, the US National Institute for Standards and Technology (NIST) announced a call for the design of a new cryptographic hash algorithm in response to vulnerabilities like differential attacks identified in existing hash functions, such as MD5 and SHA-1. NIST received many submissions, 51 of which got accepted to the first round. 14 candidates were left in the second round, out of which five candidates have been recently chosen for the final round. An important criterion in the selection process is the SHA-3 hash function security. We identify two important classes of security arguments for the new designs: (1) the possible reductions of the hash function security to the security of its underlying building blocks and (2) arguments against differential attack on building blocks. In this paper, we compare the state of the art provable security reductions for the second round candidates and review arguments and bounds against classes of differential attacks. We discuss all the SHA-3 candidates at a high functional level, analyze, and summarize the security reduction results and bounds against differential attacks. Additionally, we generalize the well-known proof of collision resistance preservation, such that all SHA-3 candidates with a suffix-free padding are covered.     

可重构计算平台上SHA系列函数的优化实现

针对当前哈希函数算法标准和应用需求不同的现状,以及同一系统对安全性可能有着不同的要求,采用可重构的设计思想,在对SHA-1、SHA-256、SHA-512三种哈希函数的不同特征进行深入分析的基础上,总结归纳出统一的处理模型。根据不同的要求,每一种SHA(SHA-1、SHA-256、SHA-512)系列哈希函数都可以单独灵活地执行。使用流水线,并在关键路径进行加法器的优化,提高了算法的吞吐率。并且使用效能比的概念,与M3服务器对比,可重构平台的效能比比通用服务器高很多。     

Hardware-Enhanced Association Rule Mining with Hashing and Pipelining

Generally speaking, to implement Apriori-based association rule mining in hardware, one has to load candidate itemsets and a database into the hardware. Since the capacity of the hardware architecture is fixed, if the number of candidate itemsets or the number of items in the database is larger than the hardware capacity, the items are loaded into the hardware separately. The time complexity of those steps that need to load candidate itemsets or database items into the hardware is in proportion to the number of candidate itemsets multiplied by the number of items in the database. Too many candidate itemsets and a large database would create a performance bottleneck. In this paper, we propose a HAsh-based and Pipelined (abbreviated as HAPPI) architecture for hardware- enhanced association rule mining. We apply the pipeline methodology in the HAPPI architecture to compare itemsets with the database and collect useful information for reducing the number of candidate itemsets and items in the database simultaneously. When the database is fed into the hardware, candidate itemsets are compared with the items in the database to find frequent itemsets. At the same time, trimming information is collected from each transaction. In addition, itemsets are generated from transactions and hashed into a hash table. The useful trimming information and the hash table enable us to reduce the number of items in the database and the number of candidate itemsets. Therefore, we can effectively reduce the frequency of loading the database into the hardware. As such, HAPPI solves the bottleneck problem in a priori-based hardware schemes. We also derive some properties to investigate the performance of this hardware implementation. As shown by the experiment results, HAPPI significantly outperforms the previous hardware approach and the software algorithm in terms of execution time.     

A Top-Down Design Methodology for Ultrahigh-Performance Hashing Cores

Many cryptographic primitives that are used in cryptographic schemes and security protocols such as SET, PKI, IPSec, and VPNs utilize hash functions, which form a special family of cryptographic algorithms. Applications that use these security schemes are becoming very popular as time goes by and this means that some of these applications call for higher throughput either due to their rapid acceptance by the market or due to their nature. In this work, a new methodology is presented for achieving high operating frequency and throughput for the implementations of all widely used—and those expected to be used in the near future—hash functions such as MD-5, SHA-1, RIPEMD (all versions), SHA-256, SHA-384, SHA-512, and so forth. In the proposed methodology, five different techniques have been developed and combined with the finest way so as to achieve the maximum performance. Compared to conventional pipelined implementations of hash functions (in FPGAs), the proposed methodology can lead even to a 160 percent throughput increase.     

A New Hash Competition

Since the discovery of collision attacks against several well-known cryptographic hash functions in 2004, a rush of new cryptanalytic results cast doubt on the current hash function standards. The relatively new NIST SHA-2 standards aren't yet immediately threatened, but their long-term viability is now in question. The US National Institute of Standards and Technology (NIST) has therefore begun an international competition to select a new SHA-3 standard. This article outlines the competition, its rules, the requirements for the hash function candidates, and the process that NIST will use to select the final winning SHA-3 standard.     

一个实用的针对URL的哈希函数

在Web信息处理的研究中，不少情况下需要对很大的URL序列进行散列（hashing）操作．本文提出了一个针对URL数据集合的均匀哈希函数，它是ELFhash函数的变型．通过对天网搜索引擎采集的1亿多个URL集合的抽样实验表明：它能有效使得URL集在哈希表中均匀散布．并通过与MD5和SHA-1的对比，认为它是实用的．最后，指出了进一步的研究方向．     

密码杂凑函数及其安全性分析

文章提出了针对密码杂凑函数及其安全性进行研究的重要意义,列举了单向杂凑函数、MD5、SHA-1等技术原理进行了技术分析,并从攻击手段入手,分析了密码杂凑函数的安全性,提出对SHA-1与MD-5的＂破解＂应客观看待的观点。