From owner-freebsd-current Fri Aug 25 18:47:42 2000 Delivered-To: freebsd-current@freebsd.org Received: from r00t.besiex.org (r00t.besiex.org [208.222.215.145]) by hub.freebsd.org (Postfix) with ESMTP id 015A137B423 for ; Fri, 25 Aug 2000 18:47:39 -0700 (PDT) Received: (from adam@localhost) by r00t.besiex.org (8.8.7/8.8.7) id VAA22230; Fri, 25 Aug 2000 21:47:35 -0400 Date: Fri, 25 Aug 2000 21:47:35 -0400 Message-Id: <200008260147.VAA22230@r00t.besiex.org> From: adam@cypherspace.org To: current@freebsd.org Subject: MACs vs Hash fns. and collision resistance Sender: owner-freebsd-current@FreeBSD.ORG Precedence: bulk X-Loop: FreeBSD.ORG [I see my post made it] To expand briefly on my comment about collision resistance > - the hash function constructed from using Blowfish in CBC mode you -- > have to be careful how you use block ciphers to construct hash > functions -- they have quite different properties. For example > collision resistance is not generally important for a block cipher, > but is all-important for a hash function -- I haven't looked in detail at what the code does, but I think I can guess from the description: CBC mode means you start with y_0 = IV, and compute ciphertext y_i = E_k( x_i ^ y_{i-1} ). In this case I see y_0 is set to zero (or perhaps left undefined). (^ = xor) A CBC-MAC is where you use IV = 0, a MAC key k and you output the last block of the MAC. However you can't use a raw CBC-MAC as a variable length MAC, without using one of the padding options. The collision resistance property of a hash function (which SHA1 and MD5 exhibit) is that it should be computationally expensive for an attacker to find h( x ) == h( y ) st x != y. The birthday attack is when you try to find any x and y hashing to the same value, and a targetted collsiion is when you have a given x and you want to find a y with the same hash value. Your hash function is optimally collision resistant if you can't find targetted collisions any more cheaply than 2^|output_size-1| average tries, and can't find birthday collision in less than average 2^|output_size/2-1| tries. So if we take the 256 bit CBC hash with an unknown key k, lets say with input string x_1 || x_2 then the following computes a collision: h1 = h( x1 ) h2 = h( x1 || x2 ) = h( x1 || x2 || h2 ^ h1 ^ x2 ) and you don't even need to know the key K to find this collision. So ok that's using different length messages, but if you have the key you can construct more arbitrary collisions. Yarrow calls for a (keyless) hash function rather than a MAC, so using a MAC with a key related to inputs or related to K from yarrow may invalidate some assumptions they are making. This is not to say what you have isn't safe -- I haven't really looked at it closely to see if this is a problem in practice -- but I just wanted to point out it's not a good idea to just swap out constructs without being sure the designers weren't relying on a property you have removed. And also, even if it turns out to be secure, once it's finished you can't in fairness to the authors call it yarrow, so you lose the ability to say "freeBSD uses yarrow", the closest you could come would be to say it uses a "variant of yarrow with a blowfish-CBC-MAC instead of a hash function" and then justify all of the assumptions and reasons why you think it's still secure and does't violate any assumptions the yarrow authors were making that matter to it's security. Adam To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-current" in the body of the message