From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by yquem.inria.fr (Postfix) with ESMTP id 5F346BC37 for ; Mon, 22 Feb 2010 00:10:04 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: ApsEAF1MgUtQRFuwWWdsb2JhbACbBQsBFhUEOLsjhGsEjis X-IronPort-AV: E=Sophos;i="4.49,513,1262559600"; d="scan'208";a="53334232" Received: from furbychan.cocan.org ([80.68.91.176]) by mail1-smtp-roc.national.inria.fr with ESMTP; 22 Feb 2010 00:10:04 +0100 Received: from rich by furbychan.cocan.org with local (Exim 4.63) (envelope-from ) id 1NjKw5-0002OK-UD; Sun, 21 Feb 2010 23:10:01 +0000 Date: Sun, 21 Feb 2010 23:10:01 +0000 To: Jacques Garrigue Cc: kamaradclimber@gmail.com, caml-list@inria.fr Subject: Re: [Caml-list] range of hash function Message-ID: <20100221231001.GA8709@annexia.org> References: <1ae8fe881002200054s2e9752d8x620695c3c4e27939@mail.gmail.com> <20100220.225412.98507853.garrigue@math.nagoya-u.ac.jp> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20100220.225412.98507853.garrigue@math.nagoya-u.ac.jp> User-Agent: Mutt/1.5.13 (2006-08-11) From: Richard Jones X-Spam: no; 0.00; hash:01 hash:01 hashtables:01 assertion:01 20,:98 git:98 git:98 wrote:01 caml-list:01 algorithm:01 algorithmic:02 garrigue:03 slightly:03 jacques:03 character:04 On Sat, Feb 20, 2010 at 10:54:12PM +0900, Jacques Garrigue wrote: > Since you have the algorithm, you can predict collisions. Basically > shifting character n by 1 is equivalent to shifting character n+1 by > 19, so you have lots of collisions. But this hash function being > intended for hashtables, collisions are not a problem, uniform > distribution matters more. I would slightly dispute your assertion that collisions are not a problem, because of algorithmic complexity attacks: http://www.cs.rice.edu/~scrosby/hash/CrosbyWallach_UsenixSec2003/index.html The hash implementation used by Perl was changed to avoid this attack: http://perl5.git.perl.org/perl.git/blob/HEAD:/perl.c#l1465 Rich. -- Richard Jones Red Hat