[curves] Twist security for elliptic curves
Trevor Perrin
trevp at trevp.net
Mon Jun 22 16:57:25 PDT 2015
On Mon, Jun 22, 2015 at 1:35 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.
Thanks for clarifying, I missed that.
If you could clarify further, what do you mean by "point validation"? Is it:
(A) = Point-on-curve
(B) = (A) + Point-not-in-small-subgroup
(C) = (A) + Point-in-main-subgroup
To prevent the Lochter issue I think (A) suffices. Do you think (B)
or (C) are important as well?
>> (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.
Maybe, but I agree with DJB the paper overstates its claims: it
doesn't apply to DH or ECDSA unless combined with unusual device
access (ability to read DH output or change the ECDSA base point).
>> 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.
OK, so the slowdown for special primes vs random primes with this
blinding countermeasure, for 256-bit curves, would be ~1.33x.
> 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.
I think that's the important question: Does point validation in DH
affect criteria for choosing curves?
You mention choosing curves for "hostile environment" scenarios. I
think the world prefers universal crypto standards, so I'll focus on
that:
I think (A) has similar cost on different curves, so doesn't affect
curve choice.
You argue that (A) makes twist-security unnecessary and dangerous,
since it might mislead implementors into not doing (A). That argument
seems weak:
* The conservative choice would be both: have twist-secure curves
*and* do point-on-curve checks.
* The point-on-curve check has a real complexity and performance cost
(e.g. several percent of scalar multiply). It seems reasonable to let
some implementations (e.g. high-speed SW) skip it, and rely on twist
security.
(B) only applies to cofactor>1 curves, but isn't an expensive check
(reject a list of input points). So this weakly argues for
cofactor=1.
(C) argues more strongly for cofactor=1, since for cofactor>1 the
check is typically a full scalar multiply. But is check (C) important
here? Let's assume check (B) is done and that the private scalar is a
multiple of the cofactor, like X25519, so the output ends up in the
main subgroup.
The only complaint I see is that if you don't check (C), multiple DH
inputs would map to the same output. This could be confusing if
you're using long-term DH keys for your identity. This could be
avoided by hashing the public keys into a session key, or by MAC'ing
them with every message sent. But there's an argument that (C) would
remove this property and mean one less thing to go wrong; also, some
people might be nervous about IPR for hashing-into-session-key with DH
identity keys, in some very specific cases (see Microsoft's KEA+).
Anyways, I'm curious what you (or others) think about the importance
of these checks, and how they affect curve preferences.
Trevor
More information about the Curves
mailing list