From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by sympa.inria.fr (Postfix) with ESMTPS id 6E0347EE6B for ; Wed, 20 Nov 2013 22:47:16 +0100 (CET) Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of info@gerd-stolpmann.de) identity=pra; client-ip=212.227.126.187; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="info@gerd-stolpmann.de"; x-sender="info@gerd-stolpmann.de"; x-conformance=sidf_compatible Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of info@gerd-stolpmann.de) identity=mailfrom; client-ip=212.227.126.187; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="info@gerd-stolpmann.de"; x-sender="info@gerd-stolpmann.de"; x-conformance=sidf_compatible Received-SPF: Pass (mail3-smtp-sop.national.inria.fr: domain of postmaster@moutng.kundenserver.de designates 212.227.126.187 as permitted sender) identity=helo; client-ip=212.227.126.187; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="info@gerd-stolpmann.de"; x-sender="postmaster@moutng.kundenserver.de"; x-conformance=sidf_compatible; x-record-type="v=spf1" X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AkkDACwtjVLU4367lGdsb2JhbABZgz+DSrsCgRoWDgEBAQEHCwsJEiqCJgEFIzIQFBALDjQCAlcGEwmHfAmvUJEPF4k6hHCBGyYHgmuBRwOPBI9NjneBaA X-IPAS-Result: AkkDACwtjVLU4367lGdsb2JhbABZgz+DSrsCgRoWDgEBAQEHCwsJEiqCJgEFIzIQFBALDjQCAlcGEwmHfAmvUJEPF4k6hHCBGyYHgmuBRwOPBI9NjneBaA X-IronPort-AV: E=Sophos;i="4.93,739,1378850400"; d="asc'?scan'208";a="36839539" Received: from moutng.kundenserver.de ([212.227.126.187]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/RC4-SHA; 20 Nov 2013 22:47:15 +0100 Received: from office1.lan.sumadev.de (dslb-088-069-150-223.pools.arcor-ip.net [88.69.150.223]) by mrelayeu.kundenserver.de (node=mrbap3) with ESMTP (Nemesis) id 0MXXss-1WDY2Q0YrO-00Vxk0; Wed, 20 Nov 2013 22:47:12 +0100 Received: from [192.168.0.110] (ip-109-90-191-98.unitymediagroup.de [109.90.191.98]) by office1.lan.sumadev.de (Postfix) with ESMTPSA id 9B507C00D3; Wed, 20 Nov 2013 22:47:11 +0100 (CET) Message-ID: <1384984030.11161.19.camel@zotac> From: Gerd Stolpmann To: Florian Weimer Cc: Dario Teixeira , Gabriel Scherer , David MENTRE , Gerd Stolpmann , "Richard W.M. Jones" , caml users Date: Wed, 20 Nov 2013 22:47:10 +0100 In-Reply-To: <878uwinbqv.fsf@mid.deneb.enyo.de> References: <20131118204426.GA14731@annexia.org> <1384819720.4083.57.camel@zotac> <1384859953.62343.YahooMailNeo@web120403.mail.ne1.yahoo.com> <878uwinbqv.fsf@mid.deneb.enyo.de> Content-Type: multipart/signed; micalg="pgp-sha1"; protocol="application/pgp-signature"; boundary="=-D3JXoiyWrGCMmJonnql2" X-Mailer: Evolution 3.2.3-0ubuntu6 Mime-Version: 1.0 X-Provags-ID: V02:K0:+wwvUZTi2+lEsliN9e5byWYqLLPdjiRoQEeD7zoTv15 ncyg5zVI5TKy3evIXerz+IvluxhLmDFev7WmknqFOYH1/2aPsu bEtYp285UU+KqHv6cq8lBJG47cwf9xYnI+Uiva5xSkaTapWw8n +N8SYRXyknqOe9YtYRDMkQZoItB9D/Fs1niD9gvGR3NpiLIUKr J189oOxBXShnbHHRnEV4hBNB0wBNjXhpMvdo7eyUw9EWKbPOQ8 h81YpFaBuBYHCMTV6tUeXwmlxtZKfdPsaVK5x1hEaREwGfdSQ5 qtSIk+/FhxVmXRh+GgiF7nsYQPFiyg6K+BYzB6e3m8gfH/WhQr Fi3fX0/VaxqRUwot0BBdETDJt+oP7QFlWEkyHLpD0 Subject: Re: [Caml-list] Hardening [Perl's] hash function further --=-D3JXoiyWrGCMmJonnql2 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Am Mittwoch, den 20.11.2013, 19:56 +0100 schrieb Florian Weimer: > * Dario Teixeira: >=20 > > - Any hashtable implementation that uses a non-cryptographic hash func= tion > > and relies on an association list of buckets is vulnerable to attacks > > that force the worst-case O(n) behaviour. Though you can buy some t= ime > > by tweaking the hash function, you are still stuck in an arms race w= ith > > attackers. >=20 > You just need a keyed hash with a secret key, not a general-purpose > cryptographic hash function. So far, Jenkins' lookup3 function still > stands. The problem is this: You think you add n bits of randomness with the secret key. But because the hash function isn't cryptographic, there will be symmetries, and the n bits are actually not worth n bits. And because there is no cryptanalysis we don't know how safe we are. You don't need a giant compute centre for finding pairs (secret, keys) where the keys collide. I'd guess a normal GPU can compute more than 1E11 hashes of that complexity per second. That way you can watch out for keys that increase the likeliness of a collision. And that's only the brute force method. Also, you can test easily 100 or more different series of keys in a single HTTP request. If you find an attack method where the original n bits of randomness are, say, only worth 20 bits, you can shoot off the server process within a couple of minutes. And within an hour the whole computer. Of course, this is only speculation, but the point is that we cannot be sure that this isn't possible. Generally, I think it is better to change the hash table algorithm in situations where data from untrusted sources is processed. That means using balanced trees for the buckets. Consumes more RAM, but is provably safe. (Or, at minimum, limit the length of the buckets.) Gerd --=20 ------------------------------------------------------------ Gerd Stolpmann, Darmstadt, Germany gerd@gerd-stolpmann.de My OCaml site: http://www.camlcity.org Contact details: http://www.camlcity.org/contact.html Company homepage: http://www.gerd-stolpmann.de ------------------------------------------------------------ --=-D3JXoiyWrGCMmJonnql2 Content-Type: application/pgp-signature; name="signature.asc" Content-Description: This is a digitally signed message part Content-Transfer-Encoding: 7bit -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.11 (GNU/Linux) iQEcBAABAgAGBQJSjS3fAAoJEAaM4b9ZLB5TgmgH/iLJwJalip0KzOsLLIvW503h bZlxHvLbLCqUSbiUlJbLR7T1+d7mIRK567XJtH8yJlenj7bOq8isOFSTRGDwxzpb f7PzLG5HdcPj6SENaF/BoqNjEc5jPfh5Uc5rh7tM89I/OdAIrcvDm/w54JiyE/aJ wDBsVUSH8PCDOMrvmOYQj5H+asL1dPeGIijSgBoHMNBiHNu8oGM2UDxj0uVPT6df keqfguwFlYrntL6wN46gbD+6LgkB13rdo/7Nze116dWShJ69EMBS1wM3jhFtR5QT WU87tJueo19uhbEKApa3S9di7Xi7v27FhpjEzBI18aJGLtsOXLraBclg/xBMjEQ= =b0rG -----END PGP SIGNATURE----- --=-D3JXoiyWrGCMmJonnql2--