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 52F827EF0D for ; Mon, 22 Feb 2016 21:28:17 +0100 (CET) IronPort-PHdr: 9a23:sb1fqBJRLxRTBZ1pqdmcpTZWNBhigK39O0sv0rFitYgULfvxwZ3uMQTl6Ol3ixeRBMOAu60C1rad6vu/EUU7or+/81k6OKRWUBEEjchE1ycBO+WiTXPBEfjxciYhF95DXlI2t1uyMExSBdqsLwaK+i760zceF13FOBZvIaytQ8iJ35vxirz5osaMKyxzxxODIppKZC2sqgvQssREyaBDEY0WjiXzn31TZu5NznlpL1/A1zz158O34YIxu38I46Fp34d6XK77Z6U1S6BDRHRjajhtpZ6jiR6WZguG4DM6XWJexhFICg6D6h79BM2p6QP1s+N83G+ROsigHp4uXjH3yqZvQRnfszsOMTk7/X/WgYQkiaNfqRS6uzRwxofVZMeeM/8oLfCVRs8TWWcUBpUZbCdGGI7pKtJXV+c= Authentication-Results: mail3-smtp-sop.national.inria.fr; spf=None smtp.pra=milanst@gmail.com; spf=Pass smtp.mailfrom=milanst@gmail.com; spf=None smtp.helo=postmaster@mail-io0-f171.google.com Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of milanst@gmail.com) identity=pra; client-ip=209.85.223.171; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="milanst@gmail.com"; x-sender="milanst@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail3-smtp-sop.national.inria.fr: domain of milanst@gmail.com designates 209.85.223.171 as permitted sender) identity=mailfrom; client-ip=209.85.223.171; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="milanst@gmail.com"; x-sender="milanst@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-io0-f171.google.com) identity=helo; client-ip=209.85.223.171; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="milanst@gmail.com"; x-sender="postmaster@mail-io0-f171.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: A0BXAABebstWkavfVdFegm6BfA8GhDW2GQENgWaGDQKBPQc4FAEBAQEBAQEBEAEBAQEHCwsJHzGCLYIUAQEBAwESER0BGx0BAwELBgUEBw0qAgIhAQERAQUBHAYTIodjAQMKCJ1GgTE+MYs0gWmCV4UDChknDVGDeQEBAQEBAQEBAQEBAQEBAQEBARIBBQoEhgSEOoI6hHuBOgWOHohpi2uBc45zhwWGBhEegQ8eAQGCOAwSCIFmHi6IOQEBAQ X-IPAS-Result: A0BXAABebstWkavfVdFegm6BfA8GhDW2GQENgWaGDQKBPQc4FAEBAQEBAQEBEAEBAQEHCwsJHzGCLYIUAQEBAwESER0BGx0BAwELBgUEBw0qAgIhAQERAQUBHAYTIodjAQMKCJ1GgTE+MYs0gWmCV4UDChknDVGDeQEBAQEBAQEBAQEBAQEBAQEBARIBBQoEhgSEOoI6hHuBOgWOHohpi2uBc45zhwWGBhEegQ8eAQGCOAwSCIFmHi6IOQEBAQ X-IronPort-AV: E=Sophos;i="5.22,486,1449529200"; d="scan'208,217";a="165620418" Received: from mail-io0-f171.google.com ([209.85.223.171]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/AES128-GCM-SHA256; 22 Feb 2016 21:28:16 +0100 Received: by mail-io0-f171.google.com with SMTP id l127so190075099iof.3 for ; Mon, 22 Feb 2016 12:28:16 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=aisSfT15s1re2vniK3baXTkYOvPPkrD1dXXttnVnH8U=; b=WPxsd+/oYtmwdhpejZXKUDhfe46aw03TcWImeWUeoT4MucklnbskICXi4BAP3cdclX YZAEqXNAHBPMItEIblZVSoEw+VIgPeMH/1a0VB2Q6jH3UOM0JZS58YkI0Rg5//Cuxda0 /5NRVEg08bG3P0/VVJGWPlvTp7uyN9Mlp5t3A47TzZF5gNYtxgOl9ckktIZBsIitBXok TkCZU42SpE2k3Kd+HMxXCIxp2CGqNZyFYxpFzCfSPBfpu0+Gmr191/qeXfdHz68rzH7z 8R7r88qZqQJX6gistUR7VFvWbDkUZVCVEMAiPlCk8Ge0VpZ+fqE5hB0gQKxq5fhKWJq/ p00g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:date :message-id:subject:from:to:cc:content-type; bh=aisSfT15s1re2vniK3baXTkYOvPPkrD1dXXttnVnH8U=; b=bxAfO3BXO+og7Wsfyn7zEEI9fAh6k5+aAs2g4idg3zQTMm+z6iRUhcAOhtGz27XFrY UBse/1agHwD+VuLfaVSpm4O+RueMos6qJVNhGsF2DBTyq8vaBGlPZJSefZEPUkP8VNxv uR33xKWvKm0sZg7rvXMOryI7cI3rbJdzJi4mtuwnduaid8RGHDJwi+GpGgNa6zHdlx// KhCT0nl+gYHFh02SIHSCewKTvh/ii9jM7kkG5qhE7P5mhuf+fMl0pHatYF84+bw/oF2/ gzoKMT1wGPH1J19ssHtj8IzVKNlyO8HuxiIS/qzhKzHPQ8k0YHHzKrqZQobU3TdTwVy5 29aA== X-Gm-Message-State: AG10YOR5PKRsNVeP8sZZK6pNKgONdpMuL3QFbYrLqEa475BSvs86hEJ/c1EP8FSqJsW27rm/L6WR1KtZG3W50Q== MIME-Version: 1.0 X-Received: by 10.107.154.80 with SMTP id c77mr31210526ioe.162.1456172894949; Mon, 22 Feb 2016 12:28:14 -0800 (PST) Received: by 10.79.12.80 with HTTP; Mon, 22 Feb 2016 12:28:14 -0800 (PST) Received: by 10.79.12.80 with HTTP; Mon, 22 Feb 2016 12:28:14 -0800 (PST) In-Reply-To: References: <20160222094853.GH1544@nunchakus.loria.fr> <46EAD496-8667-47FE-B39A-74DA94BC0C25@gmail.com> <4BDBBF0B-1783-4F91-9EFA-D3E9FF9EF1EF@gmail.com> <3DA136DD-0A26-4247-852E-DA596EBFE031@gmail.com> Date: Mon, 22 Feb 2016 15:28:14 -0500 Message-ID: From: =?UTF-8?Q?Milan_Stanojevi=C4=87?= To: Chan Ngo Cc: Caml List , Anton Bachin Content-Type: multipart/alternative; boundary=001a1140f634229752052c61acbb Subject: Re: [Caml-list] Constant-time function --001a1140f634229752052c61acbb Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Oh, that's tricky then. I mean, it's not hard to make this particular function behave how you want, but in general ocaml compiler might optimize some constructs such that time behavior of your code changes slightly (and in some cases a lot). For example allocation can increase or decrease with small changes which will affect your program's running time. Now, I don't know much about crypto so I don't know how much you care about this. On Feb 22, 2016 15:16, "Chan Ngo" wrote: > Hi Milan, > > thanks, I see what you mentioned with the =E2=80=9C&&=E2=80=9D operator. = In fact, one case > the behavior as I wanted is in crypto primitive (we need constant-time > function to avoid time side-channel attack, for example, give any input f= or > comparing with the secret hash value with fixed size, the time execution = of > comparing is constant. > > Best, > Chan > > On Feb 22, 2016, at 3:12 PM, Milan Stanojevi=C4=87 wr= ote: > > Compiler short circuits && operator so your loop runs only til the first > element that differs. If you swap the arguments to && you should get the > behavior of visiting all elements (which is of course undesirable in > practice) > > > --001a1140f634229752052c61acbb Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable

Oh, that's tricky then.
I mean, it's not hard to make this particular function behave how you w= ant, but in general ocaml compiler might optimize some constructs such that= time behavior of your code changes slightly (and in some cases a lot). For= example allocation can increase or decrease with small changes which will = affect your program's running time.
Now, I don't know much about crypto so I don't know how much you ca= re about this.

On Feb 22, 2016 15:16, "Chan Ngo" <= chan.ngo2203@gmail.com> wr= ote:
Hi Milan,

thanks, I see what you me= ntioned with the =E2=80=9C&&=E2=80=9D operator. In fact, one case t= he behavior as I wanted is in crypto primitive (we need constant-time funct= ion to avoid time side-channel attack, for example, give any input for comp= aring with the secret hash value with fixed size, the time execution of com= paring is constant.

Best,
Chan

On Feb 22, 2016, at 3:12 PM, Milan= Stanojevi=C4=87 <milanst@gmail.com> wrote:

Compiler short circuit= s && operator so your loop runs only til the first element that dif= fers. If you swap the arguments to && you should get the behavior o= f visiting all elements (which is of course undesirable in practice)


--001a1140f634229752052c61acbb--