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

> -----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...