highwayhash

README

HighwayHash

HighwayHash is a pseudo-random-function (PRF) developed by Jyrki Alakuijala, Bill Cox and Jan Wassenberg (Google research). HighwayHash takes a 256 bit key and computes 64, 128 or 256 bit hash values of given messages.

It can be used to prevent hash-flooding attacks or authenticate short-lived messages. Additionally it can be used as a fingerprinting function. HighwayHash is not a general purpose cryptographic hash function (such as Blake2b, SHA-3 or SHA-2) and should not be used if strong collision resistance is required.

This repository contains a native Go version and optimized assembly implementations for Intel, ARM and ppc64le architectures.

High performance

HighwayHash is an approximately 5x faster SIMD hash function as compared to SipHash which in itself is a fast and 'cryptographically strong' pseudo-random function designed by Aumasson and Bernstein.

HighwayHash uses a new way of mixing inputs with AVX2 multiply and permute instructions. The multiplications are 32x32 bit giving 64 bits-wide results and are therefore infeasible to reverse. Additionally permuting equalizes the distribution of the resulting bytes. The algorithm outputs digests ranging from 64 bits up to 256 bits at no extra cost.

Stable

All three output sizes of HighwayHash have been declared stable as of January 2018. This means that the hash results for any given input message are guaranteed not to change.

Installation

Install: go get -u github.com/minio/highwayhash

Intel Performance

Below are the single core results on an Intel Core i7 (3.1 GHz) for 256 bit outputs:

BenchmarkSum256_16      		  204.17 MB/s
BenchmarkSum256_64      		 1040.63 MB/s
BenchmarkSum256_1K      		 8653.30 MB/s
BenchmarkSum256_8K      		13476.07 MB/s
BenchmarkSum256_1M      		14928.71 MB/s
BenchmarkSum256_5M      		14180.04 MB/s
BenchmarkSum256_10M     		12458.65 MB/s
BenchmarkSum256_25M     		11927.25 MB/s

So for moderately sized messages it tops out at about 15 GB/sec. Also for small messages (1K) the performance is already at approximately 60% of the maximum throughput.

ARM Performance

Below are the single core results on an EC2 c7g.4xlarge (Graviton3) instance for 256 bit outputs:

BenchmarkSum256_16                143.66 MB/s
BenchmarkSum256_64                628.75 MB/s
BenchmarkSum256_1K               3621.71 MB/s
BenchmarkSum256_8K               5039.64 MB/s
BenchmarkSum256_1M               5279.79 MB/s
BenchmarkSum256_5M               5474.60 MB/s
BenchmarkSum256_10M              5621.73 MB/s
BenchmarkSum256_25M              5250.47 MB/s

ppc64le Performance

The ppc64le accelerated version is roughly 10x faster compared to the non-optimized version:

benchmark              old MB/s     new MB/s     speedup
BenchmarkWrite_8K      531.19       5566.41      10.48x
BenchmarkSum64_8K      518.86       4971.88      9.58x
BenchmarkSum256_8K     502.45       4474.20      8.90x

Performance compared to other hashing techniques

On a Skylake CPU (3.0 GHz Xeon Platinum 8124M) the table below shows how HighwayHash compares to other hashing techniques for 5 MB messages (single core performance, all Golang implementations, see benchmark).

BenchmarkHighwayHash      	    	11986.98 MB/s
BenchmarkSHA256_AVX512    	    	 3552.74 MB/s
BenchmarkBlake2b          	    	  972.38 MB/s
BenchmarkSHA1             	    	  950.64 MB/s
BenchmarkMD5              	    	  684.18 MB/s
BenchmarkSHA512           	    	  562.04 MB/s
BenchmarkSHA256           	    	  383.07 MB/s

Note: the AVX512 version of SHA256 uses the multi-buffer crypto library technique as developed by Intel, more details can be found in sha256-simd.

Qualitative assessment

We have performed a 'qualitative' assessment of how HighwayHash compares to Blake2b in terms of the distribution of the checksums for varying numbers of messages. It shows that HighwayHash behaves similarly according to the following graph:

More information can be found in HashCompare.

Requirements

All Go versions >= 1.11 are supported (needed for required assembly support for the different platforms).

Contributing

Contributions are welcome, please send PRs for any enhancements.

Documentation

Overview

Package highwayhash implements the pseudo-random-function (PRF) HighwayHash. HighwayHash is a fast hash function designed to defend hash-flooding attacks or to authenticate short-lived messages.

HighwayHash is not a general purpose cryptographic hash function and does not provide (strong) collision resistance.

Index

• Constants
• func New(key []byte) (hash.Hash, error)
• func New128(key []byte) (hash.Hash, error)
• func New64(key []byte) (hash.Hash64, error)
• func Sum(data, key []byte) [Size]byte
• func Sum128(data, key []byte) [Size128]byte
• func Sum64(data, key []byte) uint64

Examples

• New
• New64

Constants

const (
	// Size is the size of HighwayHash-256 checksum in bytes.
	Size = 32
	// Size128 is the size of HighwayHash-128 checksum in bytes.
	Size128 = 16
	// Size64 is the size of HighwayHash-64 checksum in bytes.
	Size64 = 8
)

Functions

func New

func New(key []byte) (hash.Hash, error)

New returns a hash.Hash computing the HighwayHash-256 checksum. It returns a non-nil error if the key is not 32 bytes long.

Example

ExampleNew shows how to use HighwayHash-256 to compute fingerprints of files.

key, err := hex.DecodeString("000102030405060708090A0B0C0D0E0FF0E0D0C0B0A090807060504030201000") // use your own key here
if err != nil {
	fmt.Printf("Cannot decode hex key: %v", err) // add error handling
	return
}

file, err := os.Open(".gitignore") // specify your file here
if err != nil {
	fmt.Printf("Failed to open the file: %v", err) // add error handling
	return
}
defer file.Close()

hash, err := New(key)
if err != nil {
	fmt.Printf("Failed to create HighwayHash instance: %v", err) // add error handling
	return
}

if _, err = io.Copy(hash, file); err != nil {
	fmt.Printf("Failed to read from file: %v", err) // add error handling
	return
}

checksum := hash.Sum(nil)
fmt.Println(hex.EncodeToString(checksum))

Output:

0a379f2bd8c9c1c6a501f3c327ce7efd10d98148d2c5c787d59b3171970daa65

func New128

func New128(key []byte) (hash.Hash, error)

New128 returns a hash.Hash computing the HighwayHash-128 checksum. It returns a non-nil error if the key is not 32 bytes long.

func New64

func New64(key []byte) (hash.Hash64, error)

New64 returns a hash.Hash computing the HighwayHash-64 checksum. It returns a non-nil error if the key is not 32 bytes long.

Example

ExampleNew64 shows how to use HighwayHash-64 to implement a content-addressable storage.

key, err := hex.DecodeString("000102030405060708090A0B0C0D0E0FF0E0D0C0B0A090807060504030201000") // use your own key here
if err != nil {
	fmt.Printf("Cannot decode hex key: %v", err) // add error handling
	return
}

AddressOf := func(key []byte, file string) (uint64, error) { // function to compute address based on content
	fsocket, err := os.Open(file)
	if err != nil {
		return 0, err
	}
	defer fsocket.Close()

	hash, err := New64(key)
	if err != nil {
		return 0, err
	}

	_, err = io.Copy(hash, fsocket)
	return hash.Sum64(), err
}

dir, err := ioutil.ReadDir(".")
if err != nil {
	fmt.Printf("Failed to read current directory: %v", err) // add error handling
	return
}

lookupMap := make(map[uint64]string, len(dir))
for _, file := range dir {
	if file.IsDir() {
		continue // skip sub-directroies in our example
	}
	address, err := AddressOf(key, file.Name())
	if err != nil {
		fmt.Printf("Failed to read file %s: %v", file.Name(), err) // add error handling
		return
	}
	lookupMap[address] = file.Name()
}

func Sum

func Sum(data, key []byte) [Size]byte

Sum computes the HighwayHash-256 checksum of data. It panics if the key is not 32 bytes long.

func Sum128

func Sum128(data, key []byte) [Size128]byte

Sum128 computes the HighwayHash-128 checksum of data. It panics if the key is not 32 bytes long.

func Sum64

func Sum64(data, key []byte) uint64

Sum64 computes the HighwayHash-64 checksum of data. It panics if the key is not 32 bytes long.