[Cryptography] Solving Matt's hash problem

[Viktor Dukhovni]

On Wed, Nov 16, 2022 at 02:56:58PM +0000, Weger, Benne de via cryptography wrote:

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

I took the problem as asking given a fixed given enclosing message (an
article on the subject of hashes, ...), with a variable slot just wide
enough for a hash, to find a hash that would then be the hash of the
whole article *including* that hash.

This is also different from quines, because the article is not some
animated GIF, or program, ... that "prints" its owne hash, but rather
just "natural" (given) text that is not specifically cooked to contain
variants of colliding blocks.

For example replace the text between "<" and ">" with a hex-encoded MD5
hash <d41d8cd98f00b204e9800998ecf8427e> of the body of my post computed
after the replacement.

This is only has an 63% chance of being possible at all, the expected
number of solutions is 1, and I suspect there's no known efficient way
to find a solution if it exists.

-- 
    Viktor.