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

David Jacobson <dmjacobson@sbcglobal.net> Wed, 12 July 2017 02:18 UTC

Return-Path: <dmjacobson@sbcglobal.net>
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 329F7120725 for <cfrg@ietfa.amsl.com>; Tue, 11 Jul 2017 19:18:24 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.7
X-Spam-Level:
X-Spam-Status: No, score=-2.7 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_LOW=-0.7] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=sbcglobal.net
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 WUcKjK1lP58u for <cfrg@ietfa.amsl.com>; Tue, 11 Jul 2017 19:18:22 -0700 (PDT)
Received: from nm18-vm4.access.bullet.mail.bf1.yahoo.com (nm18-vm4.access.bullet.mail.bf1.yahoo.com [216.109.115.83]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 8622A120454 for <cfrg@irtf.org>; Tue, 11 Jul 2017 19:18:22 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sbcglobal.net; s=s2048; t=1499825901; bh=uCNFmpF+zqp7IBMHyo0dsKud7Tq6Tnu/SpOdK4GQz9Q=; h=Subject:To:References:From:Date:In-Reply-To:From:Subject; b=n1bHJ3MlOrDRVyLfDxt9zMTWOXWQ2OF8vVHoZ0JIi852PZL/GA2p9v5buobFQiN5hyS5fDWoqE7RxDVfY0gbiCpN1zi8NnKtYymIGifVxKKORGK5QzefXIApnSOh6BEe4q1ngJW7I1+sMK4gX3dnc0lAc2/FmRNR+d+KdQUh/mFlpvCCYhOJvkD75LO4T7tXNcLswnoTkB2oa8+TCoq2Sq12pD1f0QZp7+sTyMarQjN5hN6Vjeur44ucXv7IW6rRFxZbPdT/RJK551xETArImkJAY0icLE3AZIODsicl6i/2gOoAbPpB/8WADWI7yEJd43RD4EX4x/y0UhnnuGguUg==
Received: from [66.196.81.157] by nm18.access.bullet.mail.bf1.yahoo.com with NNFMP; 12 Jul 2017 02:18:21 -0000
Received: from [10.218.253.202] by tm3.access.bullet.mail.bf1.yahoo.com with NNFMP; 12 Jul 2017 02:18:21 -0000
Received: from [127.0.0.1] by smtp119.sbc.mail.ne1.yahoo.com with NNFMP; 12 Jul 2017 02:18:21 -0000
X-Yahoo-Newman-Id: 468197.53913.bm@smtp119.sbc.mail.ne1.yahoo.com
X-Yahoo-Newman-Property: ymail-3
X-YMail-OSG: MMgQT64VM1l2niu8M5pa0OI8aqBfkvkyPOu.KTBHfzfw51w ZbMFu8izQsyPkPBxrw.DWKIChzkKAsi0R6PAZ.mFoVptrhF4x80V0XmtKkcW Qwj1hRtvt.aEGMBDblyTTFlHl5B1lcFoQtRL4XvLcJHVyPgIIZGnWPBh46V2 wHAcnOdd_Q9vU5hIwIeNbJHXXGJLIv57lhCIMZ5bveQjF.WJ0uoc8tkrgZSs TkKELQh1dO5SglNVbpreOX51L.9eB_TO42YMl_MyeYbPLlEcDIpza5TT7AG7 zadLl435Dgvn33PV6dYqVQRB0w5ad4tiLH.cCaYrYyzZ.P05giJTwJ6JuHpu OWao2ZjSD._yq1Cv1qQN9Ms2xOvUyYofmTV7rRAHNZPh3I7No2Y2HV77.zM9 wOFklCwXQ.RAPeRAEY9NBN01xlxb4fOvIwwzkCzr_eykJMs78a.F7Mp2_4Kp KwyUnUZOIlTFVoGH.Sz2qna14f05fZ5dZAPX2ge_Dmro_z2GiIAs_PgpWwJA NUwhC84FD7yfLIkmC2MGTKxy72W8KWAp8ihFtQFSbLQ--
X-Yahoo-SMTP: nOrmCa6swBAE50FabWnlVFUpgFVJ9Gbi__8U5mpvhtQq7tTV1g--
To: Samuel Neves <samuel.c.p.neves@gmail.com>, "cfrg@irtf.org" <cfrg@irtf.org>
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>
From: David Jacobson <dmjacobson@sbcglobal.net>
Message-ID: <838cb765-1ecb-5dbd-f308-bbd415e6321c@sbcglobal.net>
Date: Tue, 11 Jul 2017 19:18:18 -0700
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.12; rv:45.0) Gecko/20100101 Thunderbird/45.8.0
MIME-Version: 1.0
In-Reply-To: <CAEX_ruGD5V7nus20d8507q09PMSJghv6xh-a-_fbHbs1nF33EQ@mail.gmail.com>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/k6KyAjMVOiD3PlhMwDjw4PmQhwQ>
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 02:18:24 -0000

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.

    --David Jacobson