Possibly new result on truncating hashes

[John Kelsey]

Guys,

I have what seems like a new and interesting result, which I
haven't seen before, but which may or may not be new.  

The high order bit is that you can't generally guarantee
that truncating your hash (chopping off some bits) won't
weaken it.  That is, if you chop SHA256 off to 160 bits as a
replacement for SHA1 (something I'm working on with Niels
Ferguson for X9 right now), it's possible that there's no
attack on SHA256, but there is an attack on SHA160.  

How could this work?  Suppose we have an algorithm like the
Wang attacks on MD5, SHA0, or SHA1 for finding a single
collision pair.  The algorithm returns a single collision
pair on the first 160 bits of SHA256 for (say) 2^{64} work.
(Remember that this is just an example--I don't have any
such algorithm!)  Each time the algorithm is run, it gives a
new, unrelated collision pair, and the remaining 96 bits are
completely randomized by the collision pair.  

Now, this is an attack on SHA256 truncated to 160 bits.
Does it lead to an attack on SHA256 as a whole?  If it does,
then we can make a reduction proof that says that the
truncated hash is strong if the original hash is strong.
Unfortunately, we can't make this argument, because this
postulated collision algorithm can't be used to find a
collision in the whole SHA256 more efficiently than brute
force.

Let's do the counting argument:  Each time we call the
160-bit collision algorithm, we get a new pair which has the
same first 160 bits of SHA256 output, and random unrelated
last 96 bits of SHA256 output.  Each pair has a probability
of 2^{-96} of colliding in the remaining bits.  So, to get a
collision on the whole SHA256 using this 160-bit collision
algorithm, we expect to have to try about 2^{96} collision
pairs, each found at a cost of 2^{64}.  The resulting work
is 2^{64} * 2^{96} = 2^{160}, more than a straight
brute-force collision search on SHA256.  

What does this mean?  It means that just because you have a
good 256-bit hash, you can't necessarily make a good 160 bit
hash from it.  You might be able to--it seems like you
usually will be able to--but there's no guarantee.  

Comments?  Is this some well-known result that I'm
rediscovering?

--John



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