[Cryptography] Solving Matt's hash problem

[Natanael]

Den tors 17 nov. 2022 07:24Viktor Dukhovni <cryptography at dukhovni.org>
skrev:

> 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


Hash quines don't require a program or scripting. All it needs is the
ability to produce data blocks which encode each character, with enough
room for hidden pseudorandomness to attack the weak collision resistance of
an algorithm like MD5. You can do it in HTML, PDF, and more. I wouldn't
even be surprised if it could be done in ASCII art against really weak hash
functions.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://www.metzdowd.com/pipermail/cryptography/attachments/20221117/8f32d069/attachment.htm>