Tommaso Pegolotti
ETH Zurich, Zurich, Switzerland

Jan Gilcher
ETH Zurich, Zurich, Switzerland

Kenneth G. Paterson
ETH Zurich, Zurich, Switzerland

Markus Püschel
ETH Zurich, Zurich, Switzerland

Keywords: Universal Hash Functions, Poly1305, Message Authentication Code, MAC, Program Generator, Performance Model, Pareto-Frontiers

Abstract

Universal hash functions are a widely-used, fundamental building block in constructing more complex cryptographic schemes. This makes achieving high efficiency, both at the design and implementation level, an utmost priority. Using simple polynomial hash functions over prime fields is a popular choice; Poly1305 is a particular instance of such an approach that is standardized and widely deployed. However, even for simple polynomial hash functions, there are significant challenges in designing fast implementations. Firstly, there is a large set of choices for algorithmic parameters such as finite field and limb sizes. Secondly, the complexity and diversity of modern vector instruction set architectures (ISAs) makes performance evaluation, and subsequent parameter selection difficult. In this paper we present SPHGen, a program generator for simple polynomial hash functions. SPHGen takes as input the field parameters and outputs highly optimized code for a given vector ISA. The generated code is automatically verified by means of symbolic execution, ensuring functional correctness. Accompanying SPHGen is an accurate model that predicts the runtime of each generated program. Using SPHGen, one can readily identify the Pareto front of Pareto-optimal hash function parameters w.r.t. the security-performance trade-offs, and, when using the model, even without running any code. SPHGen and the model can be retargeted to different vector ISAs and languages; we consider AVX2, AVX512, AVX512_IFMA, and Jasmin as examples. We generate Jasmin code to ensure memory safety and constant-time execution. We report benchmarks showing that SPHGen offers significant performance improvements over the best previous non-vectorized code. In addition, for large messages, our automatically generated code offers speedups of up to 37% compared to the highly-optimized implementation of Poly1305 in OpenSSL, which is hand-coded in assembly.