[Cryptography] Solving Matt's hash problem

Weger, Benne de b.m.m.d.weger at TUE.nl
Wed Nov 16 09:56:58 EST 2022

> >In Matt Levine's long article about cryptocurrencies, he describes in
> >accurate detail how hashing works, and mentions in an aside that he
> >cannot include the hash of the article in the article itself, you (the
> >reader) figure out why.
> >
> >I know this is a preimage problem, but is there anything about making
> >the hash itself part of the input that would make it harder or easier
> >to solve?

In a mathematical sense this is trivial: for an n-bit hash function,
produce a file containing the 2^n different possible hash values in your 
favourite representation. There it is.

The file will contain at least n.2^n bits. Can we do better? Yes, if
we allow the hashes to be represented by bit strings of length n: the
optimal solution of a bitstring that contains all possible bitstrings
of length n as substrings is a binary "De Bruijn" sequence of
order n, see https://en.wikipedia.org/wiki/De_Bruijn_sequence.
The length is 2^n + n-1, the n-1 coming from repeating the first n-1
bits to deal with the original sequence being defined as cyclic, which
we don't want here. Way better than n.2^n, but it still won't fit on
your hard disk if n gets too far above 40. 

Can we do better? Probably yes. Starting with an empty file and 
iteratively appending the file hash to the file, until a previous hash 
occurs, will produce, with high probability (if I'm not mistaken), a 
file with approximately 2^{n/2} hashes, so approximately n.2^{n/2} bits, 
and this does the job. Probably with a De Bruijn-type idea (i.e. taking 
for the hashes bitstrings of length n starting at any offset) we again 
can remove the factor n.

So I would say that the question should be rephrased in asking for
a solution with small enough space and time complexity, such as their
product being essentially better than 2^n.

Benne de Weger

More information about the cryptography mailing list