[Cryptography] Solving Matt's hash problem

Sam Hartman hartmans at mit.edu
Thu Nov 17 18:27:24 EST 2022


>>>>> "Jerry" == Jerry Leichter <leichter at lrw.com> writes:

    Jerry> Call the article with all 0's (say) as a placeholder for the
    Jerry> hash A0.  Now replace the 0's with H(A0) to create A1.
    Jerry> Almost certainly, H(A0) != H(A1).  You can replace replace
    Jerry> H(A0) with H(A1) to get A2, but hash changes again.  What
    Jerry> you're looking for is essentially a fixed point - but even
    Jerry> assuming it exists (there's no particular reason I can see
    Jerry> why it has to) - how would you find it?

Well, that's the interesting question though isn't it.
You have presented a good argument why finding the fixed point might be
hard.
And it might well be, and obviously is under the random oracle model.

I'm concerned though when I see arguments like the above arguing for the
security of a system.
Because there might well be some sort of trick. And it might be easy
once you have found the trick.
But most of the theoretical models for security  do not preclude such a
trick.
I think it's important to be careful about what our security models do
hope to provide us, and what they do not.

I think it's valuable to encourage people to look at an article like
that and to

1) Notice why it might be hard to put the hash of the article within the
article--namely that you'd have to find a fixed point.

2) Notice that many of the common arguments about why it *has to be
hard* break down.  As an example, you can clearly construct a family of
hashes that do make it easy to embed a fixed point.  You could do
something like look for a certain structure in the message being hashed
and exclude from hashing a certain structure.  For example look for
<hashgoeshere>abcdef09845...</hashgoeshere> and simply not include the
contents of that tag in your hashing.  That's obviously undesirable from
a security standpoint, but black-box analysis of such a hash function is
unlikely to  detect such a flaw, particularly if ex ploiting the flaw
requires knowing a key embedded into the design of the hash.
We could reduce the security of such a structural modification to a hash
to the security of the hash on which it is based on  for a large number
of the security models we think about.
Which is to say that asking ourselves whether there is a trick is an
entirely reasonable thing to do.

3) Then think about what it might look like if there were such a trick
for an actual real-world hash function.
Intuitively it seems like there isn't such a trick, but arguing about
that is going to require digging into the details of how a specific hash
function works.

I've seen some real world attacks that came about because  someone
argued that finding a flaw might be hard and stopped there.  And it was
hard until someone actually found the flaw, and then we had a real mess
on our hands.  I mean it might be hard to make predictable changes to a
plaintext given CBC encryption.  After all, it's encrypted, and the
encryption provides confidentiality.  So it might be hard to make
predictable changes in the decrypted plaintext.
And many people back when I started working on security protocols made
some really bad protocols based on reasoning like that.
And then people articulated the trick, and we had a mess to clean up.

I like Victor's style of argument about this issue.  He articulated why
it would be challenging under a random model, and then explicitly stated
that our hashes were not random, and left it there.


More information about the cryptography mailing list