Implementation choices in light of recent attacks?

[John Kelsey]

>From: bear <bear at sonic.net>
>Sent: Sep 1, 2004 2:43 PM
>To: Jim McCoy <mccoy at mad-scientist.com>
>Cc: cryptography at metzdowd.com
>Subject: Re: Implementation choices in light of recent attacks?

>On Wed, 1 Sep 2004, Jim McCoy wrote:

>>After digesting the various bits of information and speculation on the
>>recent breaks and partial attacks on various popular hash functions I
>>am wondering if anyone has suggestions for implementation choices for
>>someone needing a (hopefully) strong hash today, but who needs to keep
>>the hash output size in the 128-192 bit range.  A cursory examination
>>of Tiger seems to indicate that it uses a different methodology than
>>the MDx & SHAx lines, does this mean that it does not suffer from the
>>recent hash attacks?  Would a SHA256 that has its output chopped be
>>sufficient?
>>Any suggestions would be appreciated.

>I believe that SHA256 with its output cut to 128 bits will be
>effective.  The simplest construction is to just throw away
>half the bits.

Yes, but it does depend a little on what you're trying to defend against, right?  I mean, if you're worried about not having a strong hash function with a 128-bit output anymore, then it seems like you should always be able to truncate a stronger hash.  

If I had a way to force the low 128 bits of SHA1 to collide much faster than 2^{64}, while randomizing the remaining 32 bits, I could use it to find full SHA1 collisions faster than 2^{80}work.  This doesn't work if my trick for getting collisions in 128 bits requires that the remaining 32 bits not collide, however.  (This can happen if you have a truncated differential through the whole hash function whose output value is (x,0,0,0,0), e.g., it forces a nonzero difference into the first word of output.  I believe this came up in Biham and Chen's SHA0 near collisions, requiring running the differential across two or more compression functions.  The same basic problem came up in Biham and Shamir's N-HASH results, many years ago.  So you can't get a simple reduction proof here, but maybe someone better at proofs can do a more complicated one....

If you're worried about cryptanalysis of existing MD5-like functions, then there's probably some benefit to looking at alternative designs that look radically different, like Whirlpool or Tiger.  But I'm not sure how much analysis either has seen, so I'd be reluctant to feel like I really understood their security yet.  It's clear from recent events that "designed by smart people" isn't enough by itself to give you lots of confidence in hash functions, any more than in block ciphers.  

Finally, if you want to use truncation on hashes, make sure it's never possible to get the two sides confused about which hash is to be used.  There are a lot of places, such as KDFs, where you can get some really nasty attacks if you can get Alice to use SHA256 and Bob to use SHA256 with the output truncated to 224 bits.  (Yes, this is the reason SHA224 has a different starting IV than SHA256.) 

>			Bear

--John Kelsey

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