Re: [Cfrg] Side channel attack and Edwards curves...

"Scott Fluhrer (sfluhrer)" <sfluhrer@cisco.com> Wed, 12 July 2017 12:43 UTC

Return-Path: <sfluhrer@cisco.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 4582812783A for <cfrg@ietfa.amsl.com>; Wed, 12 Jul 2017 05:43:53 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -14.523
X-Spam-Level:
X-Spam-Status: No, score=-14.523 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, RCVD_IN_DNSWL_HI=-5, RCVD_IN_MSPIKE_H3=-0.01, RCVD_IN_MSPIKE_WL=-0.01, RP_MATCHES_RCVD=-0.001, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001, USER_IN_DEF_DKIM_WL=-7.5] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=cisco.com
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id gdJbZrjx-tnj for <cfrg@ietfa.amsl.com>; Wed, 12 Jul 2017 05:43:51 -0700 (PDT)
Received: from rcdn-iport-2.cisco.com (rcdn-iport-2.cisco.com [173.37.86.73]) (using TLSv1.2 with cipher DHE-RSA-SEED-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 728CF12EC30 for <cfrg@irtf.org>; Wed, 12 Jul 2017 05:43:51 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=cisco.com; i=@cisco.com; l=3672; q=dns/txt; s=iport; t=1499863431; x=1501073031; h=from:to:subject:date:message-id:references:in-reply-to: content-transfer-encoding:mime-version; bh=OKWikAKOVRWnrrYP9HRhoPftYpVHnppvJtZuM/Rbe+s=; b=i3SF8jl2pJ9sWdNDa5mV2+bJesBB6/OUjwB9uGM6tImAYP2QN06njYu/ xHBaUx5KXoLqI09tqrANnUFz/sbPr7u3HwxlZ2SJ2rl9LcCcFqbhTlVuH vdQhXllert1nR7XRY0wunCHFGyJ2IHd13kxQM9w7TiCXz1zofNd4AVPln s=;
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: =?us-ascii?q?A0AQAgA+GWZZ/4sNJK1dGgEBAQECAQEBA?= =?us-ascii?q?QgBAQEBg1pkgRQHn3KILo1VghEhC4VKAhqDM0AXAQIBAQEBAQEBayiFGAEBAQE?= =?us-ascii?q?BAgEBIRE6BhEEAgEIDgMEAQEBAgIjAwICAh8GCxQBCAgCBAESCBOJfAMVEKxvg?= =?us-ascii?q?iaHLw2DZAEBAQEBAQEBAQEBAQEBAQEBAQEBAR2BC4IZBIELgkKFBYJXKYIBgny?= =?us-ascii?q?CYQWebTsCjx+EZZIujAaJSgEhATWBCnUVSYcWdgGHS4ENAQEB?=
X-IronPort-AV: E=Sophos;i="5.40,349,1496102400"; d="scan'208";a="272070722"
Received: from alln-core-6.cisco.com ([173.36.13.139]) by rcdn-iport-2.cisco.com with ESMTP/TLS/DHE-RSA-AES256-SHA; 12 Jul 2017 12:43:31 +0000
Received: from XCH-RTP-008.cisco.com (xch-rtp-008.cisco.com [64.101.220.148]) by alln-core-6.cisco.com (8.14.5/8.14.5) with ESMTP id v6CChVPB018865 (version=TLSv1/SSLv3 cipher=AES256-SHA bits=256 verify=FAIL); Wed, 12 Jul 2017 12:43:31 GMT
Received: from xch-rtp-006.cisco.com (64.101.220.146) by XCH-RTP-008.cisco.com (64.101.220.148) with Microsoft SMTP Server (TLS) id 15.0.1210.3; Wed, 12 Jul 2017 08:43:30 -0400
Received: from xch-rtp-006.cisco.com ([64.101.220.146]) by XCH-RTP-006.cisco.com ([64.101.220.146]) with mapi id 15.00.1210.000; Wed, 12 Jul 2017 08:43:30 -0400
From: "Scott Fluhrer (sfluhrer)" <sfluhrer@cisco.com>
To: David Jacobson <dmjacobson@sbcglobal.net>, Samuel Neves <samuel.c.p.neves@gmail.com>, "cfrg@irtf.org" <cfrg@irtf.org>
Thread-Topic: [Cfrg] Side channel attack and Edwards curves...
Thread-Index: AQHS9b3vZ+aOkxg3wUKP5VNbVUjcgaJGC/6AgAAVBACAAA4lgIAAB/SAgAmKtwCAAGlfIA==
Date: Wed, 12 Jul 2017 12:43:30 +0000
Message-ID: <63bd361b2bc543b4a84de3678cea196a@XCH-RTP-006.cisco.com>
References: <CAMm+LwiDbjq7nENzvqKGmsQnz=y49nBSVhU0boddtbz3dJAHfw@mail.gmail.com> <CAHOTMVLyB6+r6XX3z5ifi7Ey7Qpi1uiZDLsGREsWhgxjqotPxQ@mail.gmail.com> <CAMm+LwiKUJSOEZefABwwkF8H_p+_WTZNGzzrezjCncVZzLd_dA@mail.gmail.com> <CAHOTMVL0hbxZ0PtHhMxjM7eXh+Mg57R=ReFteiMPViNZO4BtBg@mail.gmail.com> <CAEX_ruGD5V7nus20d8507q09PMSJghv6xh-a-_fbHbs1nF33EQ@mail.gmail.com> <838cb765-1ecb-5dbd-f308-bbd415e6321c@sbcglobal.net>
In-Reply-To: <838cb765-1ecb-5dbd-f308-bbd415e6321c@sbcglobal.net>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
x-ms-exchange-transport-fromentityheader: Hosted
x-originating-ip: [10.150.34.172]
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: base64
MIME-Version: 1.0
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/cipIC99eer4FlFObgji7HxEzIS4>
Subject: Re: [Cfrg] Side channel attack and Edwards curves...
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.22
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Wed, 12 Jul 2017 12:43:53 -0000

> -----Original Message-----
> From: Cfrg [mailto:cfrg-bounces@irtf.org] On Behalf Of David Jacobson
> Sent: Tuesday, July 11, 2017 10:18 PM
> To: Samuel Neves; cfrg@irtf.org
> Subject: Re: [Cfrg] Side channel attack and Edwards curves...
> 
> On 7/5/17 5:35 PM, Samuel Neves wrote:
> > Coron's countermeasures [1, §5]---the first and third one, in
> > particular---work well with Montgomery coordinates.
> >
> > [1] http://www.jscoron.fr/publications/dpaecc.pdf
> >
> > On Thu, Jul 6, 2017 at 1:07 AM, Tony Arcieri <bascule@gmail.com> wrote:
> >> On Wed, Jul 5, 2017 at 4:16 PM, Phillip Hallam-Baker
> >> <phill@hallambaker.com>
> >> wrote:
> >>> You can blind in either. But if you are going to blind then a lot of
> >>> the advantages of Montgomery start to collapse. because you have to
> >>> do that add stage.
> >>
> >> What if you blinded kP with r using:
> >>
> >>      r*([k r^-1]*P)
> >>
> >> which only requires inversions?
> >>
> >> --
> >> Tony Arcieri
> >>
> >> _______________________________________________
> >> Cfrg mailing list
> >> Cfrg@irtf.org
> >> https://www.irtf.org/mailman/listinfo/cfrg
> >>
> > _______________________________________________
> > Cfrg mailing list
> > Cfrg@irtf.org
> > https://www.irtf.org/mailman/listinfo/cfrg
> 
> I think you miscounted the cost.   You need an extra inversion and an
> extra point multiplication.
> 
> And even then the security is dubious.  The original motivation apparently
> was that you are worried that computing kP will leak k.
> Well, the proposal first leaks k r^-1, then it leaks r.  The attacker can just
> multiply the two leaked quantities and she has k.

I would disagree with this security assessment; side channel attacks generally don't leak the entire value in one run; they leak probabilistic information about the secret (and the attacker will typically use multiple runs using the same secret to recover sufficient information to actually do the recovery).  In this case, 'r' is selected randomly each time, and hence any specific multiplier that will be used will be uncorrelated with the secret and any other multiplier (except that the multiplication of two adjacent ones will result in the actual secret; partial leakage of bits of the multiplier isn't particularly useful to recover the modular product).  Hence, this actually does provide some level of protection, assuming that the attacker cannot obtain sufficient information from a single run (and if you start assuming that, you'd need to start looking into white-box crypto solutions).

Is this enough protection to be worth the cost?  That's a question I won't get into...