publication . Article . Preprint . 2016

Fast keyed hash/pseudo-random function using SIMD multiply and permute

Jan Wassenberg;
  • Published: 19 Dec 2016
Abstract
HighwayHash is a new pseudo-random function based on SIMD multiply and permute instructions for thorough and fast hashing. It is 5.2 times as fast as SipHash for 1 KiB inputs. An open-source implementation is available under a permissive license. We discuss design choices and provide statistical analysis, speed measurements and preliminary cryptanalysis. Assuming it withstands further analysis, strengthened variants may also substantially accelerate file checksums and stream ciphers.
Subjects
free text keywords: Computer Science - Cryptography and Security, D.4.6
21 references, page 1 of 2

[1] J. Aumasson and D. Bernstein. Siphash: a fast short-input PRF. IACR, 2012: 351, 2012. URL http://eprint.iacr.org/2012/351. [OpenAIRE]

[2] ECRYPT. Measurements of hash functions, indexed by machine, September 2015. URL https://bench.cr.yp.to/results-hash.html.

[3] M. Bolet J. Aumasson, D. Bernstein. Hash- ooding DoS reloaded: attacks and defenses, December 2012. URL https://131002.net/siphash/siphashdos_ 29c3_slides.pdf.

[4] S. Gueron and Y. Lindell. GCM-SIV: Full nonce misuse-resistant authenticated encryption at under one cycle per byte. IACR, 2015:102, 2015. URL http: //eprint.iacr.org/2015/102.

[5] V. Hoang, T. Krovetz, and P. Rogaway. AEZ v4.1: Authenticated encryption by enciphering, October 2015. URL http://web.cs.ucdavis.edu/~rogaway/ aez/aez.pdf.

[6] D. Lemire and O. Kaser. Faster 64-bit universal hashing using carry-less multiplications. Journal of Cryptographic Engineering, 6(3):171{185, 2016. URL http://dx.doi.org/10.1007/s13389-015-0110-5.

[7] D. Lemire. Private communication, December 2016.

[8] Shay Gueron. Parallelized hashing via j-lanes and j-pointers tree modes, with applications to SHA-256. IACR, 2014:170, 2014. URL http://eprint.iacr. org/2014/170. [OpenAIRE]

[9] J. Wassenberg. Fast strong hash functions: Siphash/Highwayhash, May 2016. URL https://github.com/google/highwayhash.

[10] A. Fog. Instruction tables, January 2016. URL http://agner.org/optimize/ instruction_tables.pdf.

[11] J. von Neumann. Various techniques for use in connection with random digits. In von Neumann's Collected Works, volume 5, pages 768{770. Pergamon, 1963.

[12] G. Brassard, P. Hoyer, and A. Tapp. Quantum algorithm for the collision problem, May 1997. URL http://arxiv.org/abs/quant-ph/9705002. [OpenAIRE]

[13] A. Yee. Pi, September 2015. URL http://www.numberworld.org/digits/ Pi/.

[14] Intel. Intel 64 and IA-32 architectures optimization reference manual, January 2016. URL http://goo.gl/9IkxGj.

[15] Intel. Intel Xeon processor E5-1650 v3. URL http://ark.intel.com/ products/82765/Intel-Xeon-Processor-E5-1650-v3-15M-Cache-3_ 50-GHz.

21 references, page 1 of 2
Abstract
HighwayHash is a new pseudo-random function based on SIMD multiply and permute instructions for thorough and fast hashing. It is 5.2 times as fast as SipHash for 1 KiB inputs. An open-source implementation is available under a permissive license. We discuss design choices and provide statistical analysis, speed measurements and preliminary cryptanalysis. Assuming it withstands further analysis, strengthened variants may also substantially accelerate file checksums and stream ciphers.
Subjects
free text keywords: Computer Science - Cryptography and Security, D.4.6
21 references, page 1 of 2

[1] J. Aumasson and D. Bernstein. Siphash: a fast short-input PRF. IACR, 2012: 351, 2012. URL http://eprint.iacr.org/2012/351. [OpenAIRE]

[2] ECRYPT. Measurements of hash functions, indexed by machine, September 2015. URL https://bench.cr.yp.to/results-hash.html.

[3] M. Bolet J. Aumasson, D. Bernstein. Hash- ooding DoS reloaded: attacks and defenses, December 2012. URL https://131002.net/siphash/siphashdos_ 29c3_slides.pdf.

[4] S. Gueron and Y. Lindell. GCM-SIV: Full nonce misuse-resistant authenticated encryption at under one cycle per byte. IACR, 2015:102, 2015. URL http: //eprint.iacr.org/2015/102.

[5] V. Hoang, T. Krovetz, and P. Rogaway. AEZ v4.1: Authenticated encryption by enciphering, October 2015. URL http://web.cs.ucdavis.edu/~rogaway/ aez/aez.pdf.

[6] D. Lemire and O. Kaser. Faster 64-bit universal hashing using carry-less multiplications. Journal of Cryptographic Engineering, 6(3):171{185, 2016. URL http://dx.doi.org/10.1007/s13389-015-0110-5.

[7] D. Lemire. Private communication, December 2016.

[8] Shay Gueron. Parallelized hashing via j-lanes and j-pointers tree modes, with applications to SHA-256. IACR, 2014:170, 2014. URL http://eprint.iacr. org/2014/170. [OpenAIRE]

[9] J. Wassenberg. Fast strong hash functions: Siphash/Highwayhash, May 2016. URL https://github.com/google/highwayhash.

[10] A. Fog. Instruction tables, January 2016. URL http://agner.org/optimize/ instruction_tables.pdf.

[11] J. von Neumann. Various techniques for use in connection with random digits. In von Neumann's Collected Works, volume 5, pages 768{770. Pergamon, 1963.

[12] G. Brassard, P. Hoyer, and A. Tapp. Quantum algorithm for the collision problem, May 1997. URL http://arxiv.org/abs/quant-ph/9705002. [OpenAIRE]

[13] A. Yee. Pi, September 2015. URL http://www.numberworld.org/digits/ Pi/.

[14] Intel. Intel 64 and IA-32 architectures optimization reference manual, January 2016. URL http://goo.gl/9IkxGj.

[15] Intel. Intel Xeon processor E5-1650 v3. URL http://ark.intel.com/ products/82765/Intel-Xeon-Processor-E5-1650-v3-15M-Cache-3_ 50-GHz.

21 references, page 1 of 2
Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue
publication . Article . Preprint . 2016

Fast keyed hash/pseudo-random function using SIMD multiply and permute

Jan Wassenberg;