[curves] Twist security for elliptic curves

[Watson Ladd]

On Jun 22, 2015 1:36 AM, "Johannes Merkle" <johannes.merkle at secunet.com>
wrote:
>
> Trevor Perrin schrieb am 19.06.2015 um 23:15:
> >
> > Mostly agree with Watson, but I think there's an interesting question
here.
> >
> > The paper argues "even for twist secure curves a point validation has
> > to be performed".  They give a case where point validation adds
> > security, even for twist-secure curves:
> >  (1) power or EM sidechannel can observe bits of the scalar during
> > scalar multiplication
> >  (2) implementation performs scalar multiplication (aka DH) with fixed
> > private key
> >  (3) implementation uses a scalar blinding countermeasure with
> > inadequate blinding factor
>
> Well, that depends on what you call "inadequate". If points are
validated, a blinding factor of n/2 bit is sufficient
> even for Pseudo-Mersenne primes, but this twist attack requires n bit
blinding. So, the attack indeed requires longer
> blindings that necessary otherwise.

Why is n/2 bits sufficient? Bits n-1 through n/2 don't appear to be
protected with this proposal.

>
> >  (4) attacker can observe the input and output points
> >
> > That's a rare set of conditions (particularly last 2).
> >
>
> (2) and (4) might not be satisfied in many important applications, but we
should select curves that provide security
> independent of specific properties of the application.

Does Brainpool offer the same security claims when given an oracle that
computes xG for any G? The answer is no: an attack due to Cheon extracts
xG, x^2G, etc until we get G, then uses this information to recover x
faster then a discrete log.

In practice this sort of oracle attack isn't a concern. But given the
assumptions in the paper it is. This makes analysis of the improvement
given by SCA harder.

>
> > This doesn't strongly support the claim "point validation has to be
> > performed".  A better conclusion might be "use adequate blinding
> > factors".
> >
> > (I think they're suggesting 128 bit blinding factors for a
> > special-prime curve like Curve25519, vs 64 bits for a "random-prime"
> > curve like Brainpool-256.  So that's a 1.2x slowdown (~384 vs ~320
> > bits scalar) due to scalar-blinding, though the special-prime curve
> > will also have a 2x speedup in optimized implementations.)
>
> I am not sure what you are comparing here. Your statement "128 bit
blinding factors for a special-prime curve like
> Curve25519, vs 64 bits for a "random-prime" holds only in the absence of
the twist attack under discussion. If an
> implementation satisfies conditions (1),(2) and (4) above and does not
validate points, it needs to use 252 bit blinding
> factors, resulting in a slowdown of 59% for random primes (504 vs 316 bit
scalars) and a slowdown of approx. 20% for
> special primes (379 vs 316 bit scalars). For higher security levels (e.g.
for Ed448-Goldilocks) the impact is larger.
>
> My conclusion of that paper (and I have not contributed to it) would be
that twist security does not provide any
> performance benefit for implementations that need to thwart this attack
by longer blinding factors. Thus, if someone
> wants to select curves specifically for hostile environment scenarios
(smart cards etc), it is questionable if twist
> security should be a requirement, as it might be misleading to
implementors.

How many EC operations does a smart card need to do a second? Of course we
already know that validation is cheap, and standards don't specify blinding
factors. Yet somehow hardware implementations manage to figure out how long
a blinding factor to use: surely the can figure out the have to compute a
Jacobi symbol the same way.

I've got a list of ECC implementations that don't validate points in
protocols. It's included Bouncycastle, Go's TLS  stack, a browser, several
embedded TLS implementations, and is definitely incomplete.

All the ensuing vulnerabilities wouldn't exist with a secure x coordinate
only system like Curve25519.

Sincerely,
Watson Ladd
>
> --
> Johannes
> _______________________________________________
> Curves mailing list
> Curves at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/curves
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20150622/66bff7a2/attachment.html>