Affiliations: Department of Computer Engineering, Rochester Institute of Technology, 83 Lomb Memorial Drive, Rochester, NY 14623, USA. E-mails: jasonlowden@live.com, mxleec@rit.edu, slaeec@rit.edu
Correspondence:
[*]
Corresponding author: Marcin Łukowiak, Department of Computer Engineering, Rochester Institute of Technology, 83 Lomb Memorial Drive, Rochester, NY 14623, USA. E-mail: mxleec@rit.edu.
Abstract: In an effort to provide security and data integrity, hashing algorithms have been designed to consume an input of any length to produce a fixed length output. Keccak was selected by NIST to become the next Secure Hashing Algorithm (SHA-3) after nearly five years of competition. In addition to providing a sequential operating mode, there is also a tree mode that allows large input messages to be hashed in parallel. This work focuses on the exploration and analysis of the Keccak tree hashing mode on a GPU platform. Based on the implementation, there are core features of the GPU that could be used to accelerate the time it takes to complete a hash due to the massively parallel architecture of the device. In addition to analyzing the speed of the algorithm, the underlying hardware is profiled to identify the bottlenecks that limited the hash speed. The results of this work show that tree hashing can hash data at rates of up to 3 GB/s for the fixed size tree mode. On a 3.40 GHz CPU, this is the equivalent of 1.03 cycles per byte, more than six times faster than a sequential implementation for a very large input. For the variable size tree mode, the throughput was 500 MB/s. Based on the performance analysis, modification of the input rate of the Keccak sponge resulted in a negligible change to the overall speed. As a result of the hardware profiling, the register and L1 cache usage in the GPU was a major bottleneck to the overall throughput.
Keywords: Keccak, tree hashing, Graphics Processing Unit
