Fash256: The Fast Hash Function

Douglas Crockford
2018-03-18

Fash256 is an efficient hashing function. It crunches 64 bits at a time to produce a 256 bit result. It might possibly be a cryptographic hash function, but this has not been determined yet. More study is needed.

Fash256 is a quadrupling of Fash64.

This is an implementation in a mythical language.

def prime_11 := 11111111111111111027
def prime_9 := 9999999999999999961
def prime_7 := 7777777777777777687
def prime_5 := 5555555555555555533

# The state of the hash function is kept in eight variables.

var a_result: uint64
var b_result: uint64
var c_result: uint64
var d_result: uint64

var a_sum: uint64
var b_sum: uint64
var c_sum: uint64
var d_sum: uint64


# The fash256_begin function initializes the result and sum variables.

def fash256_begin() {
    a_result := 8888888888888888881
    b_result := 6666666666666666619
    c_result := 4444444444444444409
    d_result := 2222222222222222177

    a_sum := 7777777777777777687
    b_sum := 5555555555555555533
    c_sum := 3333333333333333271
    d_sum := 1111111111111111037
}


# The fash256_word function hashes one 64-bit word.

def fash256_word(word: uint64) {

# The fash256_word function does the work.
# It takes a 64-bit word, and scrambles it into the hash.

    var a_high: uint64
    var b_high: uint64
    var c_high: uint64
    var d_high: uint64

    var a_low: uint64
    var b_low: uint64
    var c_low: uint64
    var d_low: uint64

# Mix the word with the current state of the hash
# and multiply it with the big primes.

    a_high ; a_low := (a_result xor word) * prime_11
    b_high ; b_low := (b_result xor word) * prime_9
    c_high ; c_low := (c_result xor word) * prime_7
    d_high ; d_low := (d_result xor word) * prime_5

# Add the high part to the sum.

    a_sum += a_high
    b_sum += b_high
    c_sum += c_high
    d_sum += d_high

# Mix the low part with a sum from another quadrant.

    a_result := a_low xor d_sum
    b_result := b_low xor a_sum
    c_result := c_low xor b_sum
    d_result := d_low xor c_sum
}


# The fash256_block function hashes an array of words.

def fash256_block(block: array of uint64) {
    block.each(fash256_word)
}


# The fash256_end function returns the result.

def fash256_end() {
    return [
        a_result + c_sum
        b_result + d_sum
        c_result + a_sum
        d_result + b_sum
    ];
}

A cryptographic hash function should have five properties:

1. It is one way only. It is not possible to reverse the hashing process to uncover the input.
2. It is deterministic. A given input will always produce the same hash.
3. It is avalanching. A small change in the input will produce a big change in the hash.
4. It is fast.
5. It is non-colliding. It is infeasible to find two inputs with the same hash.

Fash64 delivers on the first four, but fails badly on the fifth. First, its result is too short, which by itself makes collisions inevitable. Even worse, it can be reset, which makes it trivial to construct two inputs with the same hash.

Fash256 corrects this by essentially doing Fash64 four times with four different primes, each producing a quadrant of the result. It is still possible to reset a quadrant, but resetting two quadrants is hard. Resetting three quadrants is very hard. It is necessary to reset all four quadrants in order to force a collision.