Joseph Crail

Zero-Hash Challenge

Fowler-Noll-Vo (or FNV) is a non-cryptographic hash function created by Glenn Fowler, Landon Curt Noll, and Kiem-Phong Vo in 1991, and was recently published as RFC 9923. Due to its speed and ease of implementation, it is ubiquitous across many applications, even in OpenTelemetry's eBPF-based continuous profiler.

As part of an ongoing challenge, the FNV authors are interested in finding all of the shortest strings that produce a hash value of zero for various alphabets, sizes, and variants. Zero represents a fundamental vulnerability for FNV due to its reliance on multiplication and exclusive-or operations. If these operations generate an intermediate hash value of zero at any point and the remaining input bytes are also zero, the final hash value would remain unchanged, making collisions trivial to find.

I created a novel approach that solves three open zero-hash questions. Due to budgetary and memory constraints, I limited myself to consumer-grade hardware without relying on GPUs or high-performance computing. This had the fortunate side-effect of keeping performance within a constant factor of a theoretical exhaustive search on a TOP200 supercomputer.

What questions were solved?

I focused on 64-bit FNV-1a as this algorithm variant had open questions and was also computationally feasible on consumer-grade hardware.

The equivalent pseudocode is:

algorithm fnv1a64 is
    input: string s
    output: uint64 hash

    hash := 0xcbf29ce484222325

    for each byte b in s do
        hash := hash xor b
        hash := (hash * 0x100000001b3) mod 2^64

    return hash

Of the four 64-bit FNV-1a questions, there were only three (#44, #56, #68) where it was unknown if there were other solutions of the same length or shorter. The respective alphabets are alphanumeric, printable, and 7-bit (non-nul).

1st Attempt: Exhaustive Search

My initial half-serious approach was to check every string of a given length for a zero hash value.

To understand the scope of the problem, I calculated the search space size for certain alphabets and string lengths. For instance, there are 63^{11} (6.21E+19) different alphanumeric strings of length 11.

For each relevant combination of alphabet and string length, I estimated the respective search space time. I assumed consumer-grade hardware uses 500 billion op/s, a single discrete GPU uses 10 trillion FLOPS, and a TOP200 supercomputer uses 10 quadrillion FLOPS.

This is clearly unfeasible on my budget and hardware constraint.

2nd Attempt: SMT Solver

Let's try this from another angle. It is common enough in mathematics and computer science that many seemingly different problems have the same shape and can often be reframed as a constraint satisfaction problem. This is no less true with the zero-hash challenge.

More specifically, the zero-hash challenge is an instance of a satisfiability modulo theories (SMT) problem, since FNV can be expressed using linear integer arithmetic and bit vector arithmetic. This allows us to use existing SMT solvers to answer the open questions without needing to write custom software.

As an experiment, I used SMT-LIB, a common interface format for SMT solvers, to find the shortest binary data set that generated a zero hash value for 64-bit FNV-1a. Since this answer is already known, I could just focus on comparing performance with an exhaustive search.

(set-option :produce-models true)
(set-logic QF_BV)

(define-const h0    (_ BitVec 64) #xcbf29ce484222325)
(define-const prime (_ BitVec 64) #x00000100000001b3)
(define-const goal  (_ BitVec 64) #x0000000000000000)

(declare-fun b0 () (_ BitVec 8))
(declare-fun b1 () (_ BitVec 8))
(declare-fun b2 () (_ BitVec 8))
(declare-fun b3 () (_ BitVec 8))
(declare-fun b4 () (_ BitVec 8))
(declare-fun b5 () (_ BitVec 8))
(declare-fun b6 () (_ BitVec 8))
(declare-fun b7 () (_ BitVec 8))

(assert
  (let ((h1 ((_ extract 63 0) (bvmul (bvxor h0 ((_ zero_extend 56) b0)) prime))))
  (let ((h2 ((_ extract 63 0) (bvmul (bvxor h1 ((_ zero_extend 56) b1)) prime))))
  (let ((h3 ((_ extract 63 0) (bvmul (bvxor h2 ((_ zero_extend 56) b2)) prime))))
  (let ((h4 ((_ extract 63 0) (bvmul (bvxor h3 ((_ zero_extend 56) b3)) prime))))
  (let ((h5 ((_ extract 63 0) (bvmul (bvxor h4 ((_ zero_extend 56) b4)) prime))))
  (let ((h6 ((_ extract 63 0) (bvmul (bvxor h5 ((_ zero_extend 56) b5)) prime))))
  (let ((h7 ((_ extract 63 0) (bvmul (bvxor h6 ((_ zero_extend 56) b6)) prime))))
  (let ((h8 ((_ extract 63 0) (bvmul (bvxor h7 ((_ zero_extend 56) b7)) prime))))
  (= goal h8)
  )))))))))

(check-sat)
(get-model)

Z3 found the first solution and stopped after 15 hours and less than 1 GiB of memory; however, Z3 did not verify if other solutions were available. I evaluated other SMT solvers, such as cvc5, but they failed to complete in less time than Z3.

So, the experiment demonstrated that the zero-hash challenge is tractable on consumer-grade hardware. But I wasn't satisfied.

Zero-Hash Solver

By building upon my previous attempts and also conducting a literature review, the finished zero-hash solver is 16x faster than the SMT solver, finds all available solutions, and is within 2x of an exhaustive search on a TOP200 supercomputer.

To make this work, I created an explicit graph model using a deterministic acyclic finite state automaton, constructed an efficient graph with the FNV-1a inverse, and reduced the search space with a quotient graph.

Deterministic acyclic finite state automaton

Revisiting the previously defined 64-bit FNV-1a hash function, the body of the for loop is an intermediate hash function, f(h,b) \equiv (h \oplus b) \cdot p\ (\bmod\ 2^{n}), that computes intermediate hash values on each iteration. This suggests that the FNV-1a hash function has an implicit graph representation, since each hash value is dependent on the prior hash value and prior byte in a string; that is, intermediate hash values are nodes and bytes are edges.

This implicit graph representation can be modeled explicitly as a deterministic acyclic finite state automaton, which is a quintuple (\Sigma, S, s_{0}, \delta, F), where:

• \Sigma is the input alphabet (a finite non-empty set of symbols);
• S is a finite non-empty set of states;
• s_{0} is an initial state and an element of S;
• \delta is the state-transition function: \delta : S \times \Sigma \to S;
• F is the set of final states, a (possibly empty) subset of S;
• there is no string \omega over \Sigma and state s \in S such that \delta(s, \omega) = s.

In the context of the zero-hash challenge, \Sigma is one of the available alphabets, S is the set of pairs in which a pair is the current string length and intermediate hash values, s_{0} is the offset basis as determined by the particular FNV algorithm, \delta is the intermediate hash function, and F is \{0\}.

For example, if I used an alphabet of only three characters, the respective deterministic acyclic finite state automaton would look like the following figure. The rightmost node highlighted in red is the zero hash value.

Inverse of FNV-1a

If I had constructed the explicit graph for the zero-hash solver as suggested in the previous figure, it would incur a substantial memory cost. However, I realized that I could construct the graph in two pieces: 1) starting from the initial state and working forward, and 2) starting from the final state and working backward. The following figure illustrates this improvement.

To efficiently build backward from the final state, I needed to find the inverse of the intermediate hash function. Fortunately, every variant of the intermediate hash function, f(h,b) \equiv (h \oplus b) \cdot p\ (\bmod\ 2^{n}), has an inverse, f^{-1}(h,b) \equiv (h \cdot p^{-1}) \oplus b\ (\bmod\ 2^{n}), where p^{-1} is the modular multiplicative inverse.

Quotient graph

We now have a two-terminal graph with 64-bit nodes. The required storage space for this entire graph, including nodes and edges, will still exceed the available random-access memory on typical consumer-grade hardware. I ideally would like to find a way to squeeze this graph into the available memory.

A quotient graph can simplify the original graph while preserving the underlying structure. It works by replacing a subset of nodes related by some characteristic and then replacing the entire subset with a single node. Existing edges are reassigned to the new node and duplicate edges between nodes are removed. If the chosen characteristic is an equivalence relation, then we are guaranteed the reduced graph preserves the underlying structure of the original graph.

In our case, the intermediate hash function is a modular congruence, similar to a \equiv b\ (\bmod\ 2^{n}), and thus is an equivalence relation. We can create a quotient graph of the two-terminal graph with n-bit nodes, where n = \{8, 12, 16, 20, 24, 28\}, by changing the FNV-1a algorithm to use \bmod\ 2^{n}, instead of \bmod\ 2^{64}. So, we have now reduced the number of possible solutions by up to the square root of the original amount, while also trimming the size of each node in half.

To visualize this, suppose we have a constructed graph in which each node color represents a different characteristic.

For each column in the graph, if we merge all nodes with the same color into one, we create a smaller graph but preserve the edges.

Conclusion

When we combine everything together, the zero-hash solver finds all solutions in the same theoretical time that a birthday attack would find one solution. Even more, the zero-hash solver as implemented in Rust solves the 64-bit challenges within 2x of an exhaustive search on a TOP200 supercomputer.

If you are curious to learn more details, see my paper and implementation.