New algorithms may lower the cost of secure computing

Wednesday, March 2, 2016

Here at Google we strive to make computing not only more cost-efficient, faster, and easier but also more secure. Hash functions are essential building blocks in computing, but must be protected against certain inputs. Today, we are open-sourcing 3 new hash function implementations: faster, data-parallel versions of SipHash, a fast cryptographically strong pseudorandom function, and the entirely new HighwayHash, which reaches even higher speeds thanks to the data parallel features of modern computers.

Our first hash function produces the same output as SipHash, but 1.5 times as quickly thanks to AVX-2 instructions. The second improvement uses j-lanes tree hashing to process multiple inputs in parallel, which is 3 times as fast. This technique is known to be secure, but produces different output than the original SipHash and is slightly slower for short inputs.

HighwayHash is based on a new way of mixing inputs with just a few AVX-2 multiply and permute instructions. We are hopeful that the result is a cryptographically strong pseudorandom function, but new cryptanalysis methods might be needed for analyzing this promising family of hash functions. HighwayHash is significantly faster than SipHash for all measured input sizes, with about 7 times higher throughput at 1 KiB.

We believe our efforts represent the current state of the art in high-speed attack-resistant hashing. These new functions can lower the cost of safe and secure computing. We invite everyone to use, study, and analyze the open-source implementations.

By Jan Wassenberg and Jyrki Alakuijala, Google Research