Douglas Crockford

2017-02-24

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 a_prime := 11111111111111111027 def b_prime := 9999999999999999961 def c_prime := 7777777777777777687 def d_prime := 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) * a_prime b_high ; b_low := (b_result xor word) * b_prime c_high ; c_low := (c_result xor word) * c_prime d_high ; d_low := (d_result xor word) * d_prime # 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 b_result c_result d_result ]; }

A cryptographic hash function should have five properties:

- It is one way only. It is not possible to reverse the hashing process to uncover the input.
- It is deterministic. A given input will always produce the same hash.
- It is avalanching. A small change in the input will produce a big change in the hash.
- It is fast.
- 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.