[Cryptography] Solving Matt's hash problem

[Viktor Dukhovni]

On Sat, Nov 12, 2022 at 12:18:33PM +0000, John Levine wrote:

> 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?

If the message is fixed length, and the only thing we can vary is the
embedded hash, then we're looking for a fixed-point of a "random"
function from hash values to hash values.  There are two potential
barriers:

1. The random function might not even have a fixed-point.

    The probably of a random endomorphism on m valus, for large m, not
    having a fixed point is ((m-1)/m))^m or ~1/e.  So the solution has
    an ~37% chance of not existing at all.

    More generally, for k << m, the probability of having $k$ fixed
    points is approximately Poisson with a mean of 1:

        P(k) ~ 1 / (e * k!)

    this diminishes quickly with k.  Having many fixed points is
    unlikely.

    This is also the distribution of the number of preimages of a
    point.  So 1/e points have no preimage, and for points with
    at least one preimage the average number of preimages is
    (e/e-1) ~ 1.58.

2. Even if a fixed point exists, finding one is non-trivial:

    With all 2^n n-bit strings as the input space, starting from a
    random hash, the typical number of steps before returning to a
    previous value is by the birthday paradox O(2^(n/2)), which is then
    plausibly a good estimate for twice the typical cycle length of the
    iterated random function.

    With the cycles rather long on average, finding a short cycle (let
    alone a fixed-point) is intuitively challenging, but I don't know
    the literature, there are likely rather more detailed analyses than
    the above naive hand waving (which could even be in error).

Of course our actual hash functions are not "random" functions, they
just play them on TV, but it would plausibly take some rather special
structure to make progress on finding a fixed-point.

-- 
    Viktor.