Cryptology ePrint Archive: Report 2012/067

Parallelizing message schedules to accelerate the computations of hash functions

Shay Gueron, Vlad Krasnov

Abstract: This paper describes an algorithm for accelerating the computations of Davies-Meyer based hash functions. It is based on parallelizing the computation of several message schedules for several message blocks of a given message. This parallelization, together with the proper use of vector processor instructions (SIMD) improves the overall algorithm’s performance. Using this method, we obtain a new software implementation of SHA-256 that performs at 12.11 Cycles/Byte on the 2nd and 10.84 Cycles/Byte on the 3rd Generation Intel® Core™ processors. We also show how to extend the method to the soon-to-come AVX2 architecture, which has wider registers. Since processors with AVX2 will be available only in 2013, exact performance reporting is not yet possible. Instead, we show that our resulting SHA-256 and SHA-512 implementations have a reduced number of instructions. Based on our findings, we make some observations on the SHA3 competition. We argue that if the prospective SHA3 standard is expected to be competitive against the performance of SHA-256 or SHA-512, on the high end platforms, then its performance should be well below 10 Cycles/Byte on the current, and certainly on the near future processors. Not all the SHA3 finalists have this performance. Furthermore, even the fastest finalists will probably offer only a small performance advantage over the current SHA-256 and SHA-512 implementations.

Category / Keywords: SHA-256, SHA-512, SHA3 competition, SIMD architecture, Advanced Vector Extensions architectures, AVX, AVX2.

Date: received 15 Feb 2012, last revised 5 Jun 2012

Contact author: shay at math haifa ac il

Available format(s): PDF | BibTeX Citation

Note: Section 7.1, “Reflections on the SHA3 competition” was updated, and includes the performance of a faster version of Grøstl512 (brought to our attention by Martin Schläffer of the Grøstl team).

The Appendix includes full details on sources and compilation, to allow reproducing all of the results quoted in the paper.

Version: 20120605:183535 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]