fixed-point hash

posted on 19 Nov 2019

Suppose these requirements are given for a cryptographic hash function:

1) x != y  ->  hash(x) != hash(y)  (with high probability)
2) hash(x) != hash(y)  ->  x != y  (with high probability)
3) It is intractable to discover x given only hash(x)

None of them prohibit the existince of a fixed point:

Not a rule:  hash(x) != x

If hash(x) == x for some x, then you discover x when you’re given hash(x), so it doesn’t violate property #3.

If you were to simply pick an x and redefine hash(x) == x, as long as hash(x) doesn’t have known preimages, the fixed hash continues to satisfy all of the properties.

(In fact, you can set the output of any input value to any output value that doesn’t have a known preimage).

fixhash function

fixhash takes a hash function and a point, and replaces the hash function’s value at that point.

fixhash(hash,fixin,fixout) = H
  where
    H(fixin) = fixout
  | H(x) = hash(x)

Again, the key to using fixhash is to ensure fixout has no known preimage. Since you have one choice before a preimage is known for your fixed hash, to keep it simple you could choose fixout == fixin.

H0 function or nullable hash

The H0(x) function is defined with respect to a given hash function as:

H0 = fixhash(hash, 0, 0)

In other words,

H0(0) = 0
H0(x) = hash(x)

Everyone already knows hash(0), it’s a canonical test case for hash. No usage of the primitive can depend on the preimage of hash(0) being impossible to discover, because it is known: 0. Likewise knowing that the preimage of constant H0(0) is 0 could not somehow break a protocol that depended on the cryptographic properties of hash. That protocol would be insecure to begin with.

And yet, nobody knows unhash(0). The probability of ever encountering a collision remains negligible!

forecast

  • Writing hash-linked data structures with H0
  • H1, L1, H2, L2, … : Nullifying a region of the hash domain
  • Hash-domain kernel: DHT lookup as trap mechanism