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 598E77EE25 for ; Tue, 19 Nov 2013 12:19:17 +0100 (CET) Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of darioteixeira@yahoo.com) identity=pra; client-ip=98.138.91.173; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="darioteixeira@yahoo.com"; x-sender="darioteixeira@yahoo.com"; x-conformance=sidf_compatible Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of darioteixeira@yahoo.com) identity=mailfrom; client-ip=98.138.91.173; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="darioteixeira@yahoo.com"; x-sender="darioteixeira@yahoo.com"; x-conformance=sidf_compatible Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of postmaster@nm13-vm4.bullet.mail.ne1.yahoo.com) identity=helo; client-ip=98.138.91.173; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="darioteixeira@yahoo.com"; x-sender="postmaster@nm13-vm4.bullet.mail.ne1.yahoo.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgEEAAhIi1JiiluteWdsb2JhbABMDYQSCKxakl2BHxYOAQEJCwwIEiqCIAUBAQQBCyAVAQIVDRQBAQMLBgVGLwEOAQYSBgEth1MBAQIJBgSwcQmDAIQyASMDASMDiVMBBgoBAQGOCIEPMweEMgOJQo5Xhjg1VYhwcIQtgUc X-IPAS-Result: AgEEAAhIi1JiiluteWdsb2JhbABMDYQSCKxakl2BHxYOAQEJCwwIEiqCIAUBAQQBCyAVAQIVDRQBAQMLBgVGLwEOAQYSBgEth1MBAQIJBgSwcQmDAIQyASMDASMDiVMBBgoBAQGOCIEPMweEMgOJQo5Xhjg1VYhwcIQtgUc X-IronPort-AV: E=Sophos;i="4.93,729,1378850400"; d="scan'208";a="36435371" Received: from nm13-vm4.bullet.mail.ne1.yahoo.com ([98.138.91.173]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-SHA; 19 Nov 2013 12:19:15 +0100 Received: from [98.138.101.132] by nm13.bullet.mail.ne1.yahoo.com with NNFMP; 19 Nov 2013 11:19:13 -0000 Received: from [98.138.89.246] by tm20.bullet.mail.ne1.yahoo.com with NNFMP; 19 Nov 2013 11:19:13 -0000 Received: from [127.0.0.1] by omp1060.mail.ne1.yahoo.com with NNFMP; 19 Nov 2013 11:19:13 -0000 X-Yahoo-Newman-Property: ymail-3 X-Yahoo-Newman-Id: 273864.91773.bm@omp1060.mail.ne1.yahoo.com Received: (qmail 71519 invoked by uid 60001); 19 Nov 2013 11:19:13 -0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yahoo.com; s=s1024; t=1384859953; bh=msBaR9GsYkgqNsN38xiYQBIpLXiHc8wZzYoszlzi7A8=; h=X-YMail-OSG:Received:X-Rocket-MIMEInfo:X-Mailer:References:Message-ID:Date:From:Reply-To:Subject:To:Cc:In-Reply-To:MIME-Version:Content-Type:Content-Transfer-Encoding; b=VskyzH4f4TQnmSNn0JnYWZRTdEr2KhfImz9xT+OcrobHq7EpXM3fD3GdTKLtDwqUj1sU1kqqCrl2cngf/dbiZTh0CIKEmijFz3l6YawolVO89GvzGgfK6dkggrTKBw1dSXvq0y8K+Z2WE8bLFWJltmsuKSt0AFETuYTd1//AZoQ= DomainKey-Signature:a=rsa-sha1; q=dns; c=nofws; s=s1024; d=yahoo.com; h=X-YMail-OSG:Received:X-Rocket-MIMEInfo:X-Mailer:References:Message-ID:Date:From:Reply-To:Subject:To:Cc:In-Reply-To:MIME-Version:Content-Type:Content-Transfer-Encoding; b=eaHd+Fnoh1cTqlPPEb/alKnRQ77bCF5tfmR5vgtUcbx98ymjZc+k7cCvAE7M/M0cedhHYJ+DmaIu+RqAB1jF3ZM9zprZIgcT4hLwPzx8xO3GE2EJ29vQB1Z83mLwQ+tVm3q6DnkvnlZgpborHCjsi9FdsXZmlnI02Eu/8+ypTPA=; X-YMail-OSG: QH0302cVM1nIgDuQIIMUnli3_PCR_KQQj.Gj9HYICM88WZ_ 8KgXxMujp4HWF_smcjmA0sGCXMzqqaLCG9lJYj_vWu2n0u7QG_BHaDh4dhl_ T1B_YaxIoYII2Z5gtxBDiaKAKeDxe8gEkATgb44YjJLL3_XzZJVCPcqAuryB dKpK04UCh_cgZ16iBJYxRZZdA3D0JvhDwtxm8phjVPONjB1JyR3oKU5DaBLx nR_dhv53zGx56ZxXOm_H_prohu9oQJb.4_p4S3H67Z2lhXO0avjp4wKiq97p 2x33m8Yeir11ibWVkPO_hl1QUljlVmgQE7Lhj6i4qKyfS5sePI1dtOkgSns8 dKwkSz5erPEeazA0k7fO7jQ5qC4MHDsQ2Od4Rz5.gH_Hycss77pavXbYgd68 jW5XPWYMbZ3diWSSLnxGZRV9eYRg_2WqB6cbfvMEfv2ANuDgFPJIz655txyO tLOB728CqmsVA_o2vSIeRJCIeCKEF1XK4it13.eay4_KtZOm4e_azGDQMPNx Hf0PIVYwxNgj8oOxEE5UbQwE4xU0fCvgqyTRQWWURyWmYNJGFhphB3j6ln2t tMoHBvcYuALzOtcjGEFtGg74DU2IXLQMZY9mXmEoKtQ-- Received: from [195.23.39.203] by web120403.mail.ne1.yahoo.com via HTTP; Tue, 19 Nov 2013 03:19:13 PST X-Rocket-MIMEInfo: 002.001,SGksCgo.IEkndmUgdGhvdWdodCBhYm91dCB0aGlzIGR1cmluZyB0aGUgbGFzdCBkZWJhdGUgb24gcmFuZG9taXplZCBoYXNoaW5nCgo.ICh3aGljaCBJIHRoaW5rIGlzIG5vdyBrbm93biB0byBiZSBpbmVmZmVjdGl2ZSwgYXMgaW1wbGVtZW50ZWQsIHRvIGJlCj4gc2VjdXJlKSwgYW5kIEkgdGhpbmsgYSByZWFzb25hYmxlIGdvYWwgd291bGQgYmUgdG8gdXNlIGEgYmFsYW5jZWQgdHJlZQo.IG9mIGJ1Y2tldHMgdG8gYSBnb29kIHdvcnN0LWNhc2UsIGluc3RlYWQgb2YgZmlnaHRpbmcgYXQgdGhlIGhhc2gKPiABMAEBAQE- X-Mailer: YahooMailWebService/0.8.166.601 References: <20131118204426.GA14731@annexia.org> <1384819720.4083.57.camel@zotac> Message-ID: <1384859953.62343.YahooMailNeo@web120403.mail.ne1.yahoo.com> Date: Tue, 19 Nov 2013 03:19:13 -0800 (PST) From: Dario Teixeira Reply-To: Dario Teixeira To: Gabriel Scherer , David MENTRE Cc: Gerd Stolpmann , "Richard W.M. Jones" , caml users In-Reply-To: MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: quoted-printable Subject: Re: [Caml-list] Hardening [Perl's] hash function further Hi, > I've thought about this during the last debate on randomized hashing > (which I think is now known to be ineffective, as implemented, to be > secure), and I think a reasonable goal would be to use a balanced tree > of buckets to a good worst-case, instead of fighting at the hash > function level. As said at the time, this is what Core use, but I'm > not sure what the bookkeeping overhead is against current hashtables. > I hope it's possible to fight the constants to get something in the > same performance ballpark. Just to make sure we are all on the same page, allow me to summarise the main points under discussion.=A0 I think we all agree on the following: =A0- Any hashtable implementation that uses a non-cryptographic hash functi= on =A0=A0 and relies on an association list of buckets is vulnerable to attacks =A0=A0 that force the worst-case O(n) behaviour.=A0 Though you can buy some= time =A0=A0 by tweaking the hash function, you are still stuck in an arms race w= ith =A0=A0 attackers. =A0- Solution approach #1: switch to a cryptographic hash function.=A0 This =A0=A0 approach is simple and would solve the problem once and for all. =A0=A0 Unfortunately, the performance would be terrible (how much though?). =A0- Solution approach #2: keep the non-cryptographic hash function but use =A0=A0 a balanced tree for the buckets instead of an association list.=A0 T= his =A0=A0 should mitigate the worst-case scenario -- it would go from O(n) to =A0=A0 O(log n) -- and performance is most likely better than the first app= roach. =A0- Since this problem presents itself on limited domains, it seems unfair =A0=A0 to ask *all* applications to sacrifice performance to protect themse= lves =A0=A0 from non-existent attackers.=A0 Therefore, if the adopted solution d= oes =A0=A0 indeed have a serious performance penalty, then it should be opt-in. Did I miss something important?=A0 Anyway, it seems we are lacking actual metrics to quantify the performance impact of the various approaches. To complicate matters further, on some architectures but not on others you may now or in the future have silicon that speeds up the calculation of cryptographic hash functions... Best regards, Dario Teixeira