From owner-freebsd-security@FreeBSD.ORG Thu Jan 28 21:06:20 2010 Return-Path: Delivered-To: freebsd-security@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id 988161065679 for ; Thu, 28 Jan 2010 21:06:20 +0000 (UTC) (envelope-from delphij@delphij.net) Received: from tarsier.geekcn.org (tarsier.geekcn.org [IPv6:2001:470:a803::1]) by mx1.freebsd.org (Postfix) with ESMTP id 2BAD78FC08 for ; Thu, 28 Jan 2010 21:06:20 +0000 (UTC) Received: from mail.geekcn.org (tarsier.geekcn.org [211.166.10.233]) by tarsier.geekcn.org (Postfix) with ESMTP id EE028A5D3F1; Fri, 29 Jan 2010 05:06:18 +0800 (CST) X-Virus-Scanned: amavisd-new at geekcn.org Received: from tarsier.geekcn.org ([211.166.10.233]) by mail.geekcn.org (mail.geekcn.org [211.166.10.233]) (amavisd-new, port 10024) with LMTP id nt1C2NjYCK+F; Fri, 29 Jan 2010 05:06:10 +0800 (CST) Received: from delta.delphij.net (drawbridge.ixsystems.com [206.40.55.65]) (using TLSv1 with cipher DHE-RSA-CAMELLIA256-SHA (256/256 bits)) (No client certificate requested) by tarsier.geekcn.org (Postfix) with ESMTPSA id 2693EA5D377; Fri, 29 Jan 2010 05:06:08 +0800 (CST) DomainKey-Signature: a=rsa-sha1; s=default; d=delphij.net; c=nofws; q=dns; h=message-id:date:from:reply-to:organization:user-agent: mime-version:to:cc:subject:references:in-reply-to: x-enigmail-version:openpgp:content-type:content-transfer-encoding; b=aXo42ZT9RdMhHQIokNc0lZ6a0q8G8ByM0KaflNmN6say/cn9ZMzk8BQmWD/9fQzxg VQEGE5j6wgchipv63ZvGQ== Message-ID: <4B61FC3C.1050905@delphij.net> Date: Thu, 28 Jan 2010 13:06:04 -0800 From: Xin LI Organization: The Geek China Organization User-Agent: Mozilla/5.0 (X11; U; FreeBSD amd64; en-US; rv:1.9.1.7) Gecko/20100122 Thunderbird/3.0.1 ThunderBrowse/3.2.8.1 MIME-Version: 1.0 To: Chris Palmer References: <20100128182413.GI892@noncombatant.org> <4B61EBDE.1040604@delphij.net> <20100128201100.GO892@noncombatant.org> In-Reply-To: <20100128201100.GO892@noncombatant.org> X-Enigmail-Version: 1.0 OpenPGP: id=3FCA37C1; url=http://www.delphij.net/delphij.asc Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Cc: freebsd-security@freebsd.org, d@delphij.net Subject: Re: PHK's MD5 might not be slow enough anymore X-BeenThere: freebsd-security@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list Reply-To: d@delphij.net List-Id: "Security issues \[members-only posting\]" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 28 Jan 2010 21:06:20 -0000 -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 2010/01/28 12:11, Chris Palmer wrote: > Xin LI writes: > >> The slowness was useful at the time when the code was written, but I don't >> think it would buy us as much nowadays, expect the slowness be halved from >> time to time, not to mention the use of distributed techniques to >> accelerate the build of dictionaries. > > The goal is to make the attacker *have* to use distributed techniques and to > buy more gear, rather than simply be able to brute them all in a few minutes > on a single cheap PC. MD5_SLOW is the factor by which you increase the > attacker's cost; it is easy for the defender to go very high here because > checking any one password is still fast. Distributed attacks existed when > PHK wrote the code originally, too -- I don't think anything has > fundamentally changed since then. Attackers use arrays of GPUs now? Ok, > increase MD5_SLOW some more. Isn't it a losing battle, if we increase something linearly to defeat something growing in geometric order? Defenders must carefully protect all weak points, while the attacker simply go the weakest chain of the whole system. >> Second, recent research has shown MD5 to be vulnerable to collision >> attacks [1] by the end of 2008. > > I'm not sure that attack against MD5 is relevant here, because we're not > using it in a way where collisions hurt. (Someone correct me if I'm wrong.) Yes and no. Collision attacks themselves would do nothing against our scenario. The design in crypt-md5.c not only "slow down" the computation, but also introduced additional protection by using intermediate hashes when doing the computation, like OPIE, which makes collision harder to use. > In fact, moving to a modern hash would weaken the defense, because e.g. > Skein is brilliantly fast -- the opposite of our goal. Modern hash algorithms are fast, but fast by itself is not anything wrong. Another benefit newer hash algorithms usually give is much more output bits, and every bit in the output, doubles the space needed to store the dictionary needed by the attacker, as well as the numbers of samples they presumably need to compute, while halving the chance they generate a collision for one given round. Cheers, - -- Xin LI http://www.delphij.net/ FreeBSD - The Power to Serve! Live free or die -----BEGIN PGP SIGNATURE----- Version: GnuPG v2.0.14 (FreeBSD) iQEcBAEBAgAGBQJLYfw8AAoJEATO+BI/yjfBTkIIAIp7NzGUdxqoRw7MbK/TzfOH Rx2cQzn/ld0eVTdPLHWBCShPgajcWiH99j3XPU7nj+JSl+B3qitmEu+Am/zT5GhZ wv8B9Vp+0aHrsOTdVEGw4yYHtE93VDEAzkdJ1PZndVJl/TSAWoxvIfkIkuLUJMp8 9zO53dSkM1EzIveTk5lCbDErYL8AlN+A1tIeycRTaFUhEbbRWzvcRzZ9iqCfUoB9 3WvHMykbFYfLHHEbT0dwQ3M1JzDDl51sBqxGUEUYlMkvfgrBa29r+LpvxO6+8ZiY aHrXZFU5O5RGNlJSRbbT0CkFKkpVWmLkyvJ2zhDEoIQx9Hpn8YRta6JqushEW8o= =ZB3V -----END PGP SIGNATURE-----