On Jun 22, 2015 1:36 AM, "Johannes Merkle" <<a href="mailto:johannes.merkle@secunet.com">johannes.merkle@secunet.com</a>> 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 > <a href="mailto:Curves@moderncrypto.org">Curves@moderncrypto.org</a> > <a href="https://moderncrypto.org/mailman/listinfo/curves">https://moderncrypto.org/mailman/listinfo/curves</a>