?splints for broken hash functions

[bear]

On Thu, 26 Aug 2004, John Denker wrote:

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

The conjecture is false.

The Joux attack will still work to find multicollisions,
and it will not increase the work factor at all.  In
fact in some cases it will actually decrease it.

I think you're trying to use the encrypted form of the
message as a redundancy code for tamper-resistance;
presumably the collisions found will be highly unlikely
to share the structure of being a message concatenated
with its encrypted form under AES.

This will help in some applications:  If used for
bit commitment, for example, a "collision" when
eventually presented would clearly *not* be the
initial message because it would lack the redundant
structure of a message followed by its own AES
encrypted form.

However, that's not the same property as collision
resistance.  The attack is derived from the structure
of the conventional hash function and the way it handles
blocks one at a time.  More blocks does not make it
any harder.

A given block of the message to be hashed is normally
one of to inputs to a particular round of the hash
function.  The other is the "internal state" of the
hash function.  These are operated on to produce the
new "internal state" that is used along with the next
block of the message.... until the end of the message,
whereupon the internal state is typically read as the
value of the hash function.

An attacker using the Joux method would start knowing the
message and the initial state of the function.  He would
feed one block of the message into the hash function,
read the new internal state, and search for another block
that, given the same starting internal state, produces
the same ending internal state.  He also knows the starting
internal state of the hash function before the second
block, and can equally search for another block that,
starting from that internal state, produces the same
internal state as the state after the second block.
(and etc through the message, if he feels so inclined).

Now, if our attacker finds *two*  one-block collisions
in different blocks, he can "mix and match" them to get
*four* colliding whole messages, of which the original
message is one and two would have come from his search
in a random function.  That means he got one for "free".
If he finds a collision in each of eight different blocks,
he can mix and match them to get 256 colliding messages,
of which one is the original message and eight are what
he would have gotten from a collision search for a fully
random function, so 247 of them are "free."

In fact, the more blocks he has to work with, the more
different places he can find collisions in.  So in that
sense appending the ciphertext of the message makes it
*less* secure.  Consider the results of searching for
sixteen one-block collisions in an eight-block message;
with only eight blocks, you get the most free stuff if
you find two block collisions per block; now you have
3^8 colliding messages.  But if the message is extended
to sixteen blocks, for the same effort you get one
collision per block and 2^16 collisions.  2^16 is a lot
more than 3^8, so extending the message gives the
attacker more freebies per block collision found.

One-block messages are completely immune to the attack.

Hal's proposed solution is to double the length of the
internal state, which makes the block collisions much
harder to find and thereby cancels out the advantage
of recombining block collisions.

				Bear



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