From mboxrd@z Thu Jan 1 00:00:00 1970 Message-ID: Date: Sat, 19 Feb 2005 23:24:21 -0500 From: Karl Magdsick To: Fans of the OS Plan 9 from Bell Labs <9fans@cse.psu.edu> Subject: Re: [9fans] Venti security in view of SHA-1 exploit In-Reply-To: Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit References: <9006e346da4717eaae1f97188a21d77d@telus.net> Topicbox-Message-UUID: 10bed348-ead0-11e9-9d60-3106f5b1d025 > All of this assumes the attacker gets to choose which block > to cause a collision on. I havent followed the previous MD5 > work, does anyone know if this is the case? If the attack > is limited to just finding any two blocks that collide then > neither of these attacks would be viable. > > In the case of SHA1 the scant information released so far > indicates its still a 2^69 attack. That's a LOT of operations. It would appear that it is the latter type of attack, limited to only finding two random blocks that collide. (The expected work factor for this type of attack is 2**80 for an ideal 160-bit hash function.) As I remember, the SHA-0 attack required that the blocks were indentical except for the most significant bits of a few adjascent 32-bit (big-endian) words. The non-identical bits had to fit a very special relation (related to the GF2**16 primitive polynomial used in the SHA-0 block expansion function). The attack consisted of creating lots and lots of blocks fitting these properties and checking if any of them hashed to the same value. Supposedly, the SHA-1 break is related to the SHA-0 break, so it's mostly an academic problem for the time being. On the other hand, a collision with a work factor of 2**69 indicates weaknesses in SHA-1. Researchers will likely find better and better ways to exploit these weaknesses. They may also find ways of exploiting these weaknesses to break its weak collision resistance or its one-way properties. They've basically found a way to speed up bruit force by 2048 times, which isn't too bad. The main problem is that it's a bad omen. SHA-256, Tiger, and Whirlpool are probably the most likely candidates for SHA-1 replacements, maybe with truncated outputs. However, SHA-1 and MD-5 are the most scrutinized hash functions. These candidates may all have much more serious problems that are relatively easy to find. In particular, Whirlpool is related to Rijndael, which is vulnerable to XSLT attacks. It will likely be a while before there's a consensus on which hash should be used to replace SHA-1. -Karl