?splints for broken hash functions

John Denker jsd at av8n.com
Thu Aug 26 22:00:16 EDT 2004


Hi --

I don't fully understand the new attacks on the hash
functions (which I suppose is forgiveable, since the
papers don't seem to be available).

But here's a shot in the dark that seems promising at
first glance:

Given a message m, pad it to a length of at least one
block to form M.  Then encrypt M with some standard
algorithm (e.g. AES) using some agreed-upon key to
form E(M).  Then concatenate.  Then calculate the hash,
i.e.
   hash2(M) := hash1[M (+) E(M)].

The conjecture is that hash2() is stronger than hash1().

Note that encryption alone is not enough;  you could
just find a collision pair (X and Y) for the unadorned
hash1 function, then apply the decryption function D()
and then you've got a collision pair D(X) and D(Y) for
the encrypt-then-hash function.

But having both M and E(M) changes the story.  You have
to fiddle bits of M to get a collision in the first
block, and that will mess up whatever you're trying to
do to find collisions in the later block where E(M) is
processed.

===========

Here's another splint using the same general idea, but
with less complexity:  calculate the hash once then
prepend that to the message and hash again, i.e.
    hash3(M) := hash1[hash1(M) (+) M]

The idea is that anything you do to M to arrange a
collision in the later blocks will severely mess up
whatever you wanted to do with the first block.

The work for the legit hash user is only slightly more
than doubled, while the work for the attacker is, I
conjecture, increased quite a bit more than that.

=============================================

I find it ironic that only a few weeks ago in the thread
on "the future of security" there seemed to be a general
consensus that the future would not involve much interesting
work on the mathematics of cryptography or cryptographic
primitives.

As Yogi Berra supposedly said, it's hard to make predictions,
especially about the future.

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com



More information about the cryptography mailing list