From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@sympa.inria.fr Delivered-To: caml-list@sympa.inria.fr 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 A00DE7EE25 for ; Tue, 19 Nov 2013 23:31:39 +0100 (CET) Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of nicolas.braudsantoni@gmail.com) identity=pra; client-ip=74.125.83.52; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="nicolas.braudsantoni@gmail.com"; x-sender="nicolas.braudsantoni@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail3-smtp-sop.national.inria.fr: domain of nicolas.braudsantoni@gmail.com designates 74.125.83.52 as permitted sender) identity=mailfrom; client-ip=74.125.83.52; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="nicolas.braudsantoni@gmail.com"; x-sender="nicolas.braudsantoni@gmail.com"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of postmaster@mail-ee0-f52.google.com) identity=helo; client-ip=74.125.83.52; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="nicolas.braudsantoni@gmail.com"; x-sender="postmaster@mail-ee0-f52.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AkQDAALmi1JKfVM0lGdsb2JhbABZgz/AEoEiFg4BAQEBBwsLCRIqgiUBAQVAARsJEwIDDAYFCwcGCRYPCQMCAQIBEREBBQEODhMIAQEXh1MBAw8EAQiiNIxXgwmEJgoZJw1kiAcBBQyOCQcBAYFAFoQcA5AwgTGCT4NigS+FEIliQYRUgWcJFw X-IPAS-Result: AkQDAALmi1JKfVM0lGdsb2JhbABZgz/AEoEiFg4BAQEBBwsLCRIqgiUBAQVAARsJEwIDDAYFCwcGCRYPCQMCAQIBEREBBQEODhMIAQEXh1MBAw8EAQiiNIxXgwmEJgoZJw1kiAcBBQyOCQcBAYFAFoQcA5AwgTGCT4NigS+FEIliQYRUgWcJFw X-IronPort-AV: E=Sophos;i="4.93,732,1378850400"; d="asc'?scan'208";a="36576870" Received: from mail-ee0-f52.google.com ([74.125.83.52]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/RC4-SHA; 19 Nov 2013 23:31:39 +0100 Received: by mail-ee0-f52.google.com with SMTP id l10so3625358eei.11 for ; Tue, 19 Nov 2013 14:31:38 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=message-id:date:from:user-agent:mime-version:to:subject:references :in-reply-to:content-type; bh=SDjyxSRkSTI/Vwt0peOPpFRt5KnDlhrv4sY+a53sjC8=; b=GMMr4yvwl6B/NPv23o8valoyEu+606vZEdUQXZ2USi8WL7A3JtkZFv4HaOjYLPq/8H rvJwGNTQ+m76FaYBG4YeajmjFhWt3/moejoxw/eUmQvFtYh4fiPntZG0XLckF7froO+n HUK8Nr+extXAtD+7mgb90hbRCS2u0+gl8IWycSf4qn4vJs/VEC4G5CNZ2e6P0/f/Vhzt UybcODwtTuavT16bbFBn9g6WbN1HS0FoHu0BefG/ZJem2WmEIf8KW5rkKh5xSyBpsITl evLwczPh8JGFLechxoi5viv7xraX2MfN1HFD21RU0O6hAIqsUJjPvxUhGkYfgLcnyS9v mG0A== X-Received: by 10.14.103.69 with SMTP id e45mr6679519eeg.51.1384900298555; Tue, 19 Nov 2013 14:31:38 -0800 (PST) Received: from [193.170.224.192] (m-192.vc-graz.ac.at. [193.170.224.192]) by mx.google.com with ESMTPSA id w6sm53169500eeo.12.2013.11.19.14.31.36 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Tue, 19 Nov 2013 14:31:37 -0800 (PST) Message-ID: <528BE6C2.4000703@gmail.com> Date: Tue, 19 Nov 2013 23:31:30 +0100 From: Nicolas Braud-Santoni User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.0 MIME-Version: 1.0 To: caml-list@inria.fr References: <20131118204426.GA14731@annexia.org> <1384819720.4083.57.camel@zotac> <1384859953.62343.YahooMailNeo@web120403.mail.ne1.yahoo.com> In-Reply-To: <1384859953.62343.YahooMailNeo@web120403.mail.ne1.yahoo.com> X-Enigmail-Version: 1.6 Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="f0b6fVWrw8aOpvnB1V5TSRif2fmwi1nbu" Subject: Re: [Caml-list] Hardening [Perl's] hash function further This is an OpenPGP/MIME signed message (RFC 4880 and 3156) --f0b6fVWrw8aOpvnB1V5TSRif2fmwi1nbu Content-Type: text/plain; charset=windows-1252 Content-Transfer-Encoding: quoted-printable On 19/11/2013 12:19, Dario Teixeira wrote: > Just to make sure we are all on the same page, allow me to summarise > the main points under discussion. I think we all agree on the following: > > - Any hashtable implementation that uses a non-cryptographic hash functi= on > 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 time > by tweaking the hash function, you are still stuck in an arms race with > attackers. Depends on what you mean by =93non-cryptographic=94. But not using a PRF (a strong hash function) seems to be unpractical. > - Solution approach #1: switch to a cryptographic hash function. This > approach is simple and would solve the problem once and for all. > Unfortunately, the performance would be terrible (how much though?). As I stated in my previous mail, some recent hash function have good speed (without relying on fancy superscalar instructions). Moreover, it is unclear how time is spent inside `caml_hash`. However, changing the hash function isn't so simple, as : - Hashtbl's documentation[1] specifies that =93in non-randomized mode, the order in which the bindings are enumerated is reproducible between [...] minor versions of OCaml=94. This means the change cannot be made (for the non-randomized mode) until OCaml 5. - Implementing a hash function in a form suitable for `byterun/hash.c` requires - to care about endiannes ? (though the hash function doesn't seem to be specified to be architecture-independent, it is currently the case[2]) - to be able to feed the data to the hash function in small =93chunks=94 while traversing the OCaml value. [1] http://caml.inria.fr/pub/docs/manual-ocaml/libref/Hashtbl.html [2] Except for 64-bit values that cannot be represented in 32-bit, of course > - Solution approach #2: keep the non-cryptographic hash function but use > a balanced tree for the buckets instead of an association list. [...] = performance is most likely better than the first approach. Again, I'm wary of =93hand waving=94 statements about performance in this c= ase. > - Since this problem presents itself on limited domains, [...] if the ad= opted solution does > indeed have a serious performance penalty, then it should be opt-in. If the performance penalty is prohibitive, this seems clear, yes. Best, Nicolas --f0b6fVWrw8aOpvnB1V5TSRif2fmwi1nbu Content-Type: application/pgp-signature; name="signature.asc" Content-Description: OpenPGP digital signature Content-Disposition: attachment; filename="signature.asc" -----BEGIN PGP SIGNATURE----- Version: GnuPG v2.0.22 (GNU/Linux) iQIcBAEBAgAGBQJSi+bHAAoJEPv4tP2UoeSeLtgP/iHmU/Tz7crGlWhMXRB0a9mA 1HfnuyTKARcyFlzymUhFst+7yfctj+kHXBg5HomuscE52qghPT6qVbGoVbFgcGkt j6TdCbWjqvEfm478zP1oAqVbembl9Qxn6fjUWA9zdfn/+biQV6Xh0xa2pLDNIEBW 1+tggnCuGG/CzU/GK6FqKKJFY3sBt7SIspdcqJpdx3d20RXJFa1YLTWyVDuMe9Nm tWfdWxJk7I/qXMy7AMWMvlXClJIvtLDV5pM5JsEhu4JXy6opvf6LXBx605nCnFyU niAV7nLpfk1KFeD4+PeaZ8KSMO7f13DxvrEH76YBvM25LWTMd4jeFj+cQCq5jtif k/xCXJsL0X7jDID6xIvGKgw6AiawpN3G0oc6r2tpxUk+epPjRHhonVvPZhrtQZBQ YRVH4uPU2RzQ4fFM1hoGXD4CJn8+6MsrqMZEhiV8NdUpnU9pKW6CJPkNtjllgfBO VaCz+QlpmCGAlxsQyieRcqsAM5PXR9+YPuV5L6SIaDGemqEAMXps+JxtWlBrQpsd iEBT7F7+OJsF6W9XpXtkl17Gp02sICpB6+MDWZraSGzdE8zCoNFXBHGYtaLyV6TR gQ264YoErPK1fBKCZ7Kms6bGDcm12dkewzhl8ERYueSPKsUZ+E4wK3trpFdWcajb ssp7GToe+vL45aevQo/i =9gZL -----END PGP SIGNATURE----- --f0b6fVWrw8aOpvnB1V5TSRif2fmwi1nbu--