[curves] Twist security for elliptic curves

[Johannes Merkle]

Trevor Perrin schrieb am 23.06.2015 um 01:57:
> 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?
> 

I was only referring to (A), because twist security has nothing to do with (B) or (C). If you have non-trivial cofactor,
you need to check at least (B) or multiply inputs with the cofactor, but this is a different story.


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

Right, like the Brown-Gallant / Cheon attack, it doesn't apply to ECDH as implemented in most protocols.


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

Universal crypto standards may be nice to have, but IMHO it's not always the best way to go. You often have algorithms
preferred for hardware and others being more efficient in software.  IMHO it would be good to have different curves
standardized to accommodate the different requirements / benefits for hard- and software.

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

I was not referring to SW implementations. Furthermore, I qualify my statement about twist security being potentially
dangerous to the (unusual) cases, where the common DH point is revealed. Nevertheless, as many speakers at the NIST
workshop have pointed out, the benefit of twist security is rather limited, and this limited benefit has to be carefully
balanced with its potential issues. For high-speed SW implementations, twist security may provide significant
advantages. But I advocate separate curves for high-assurance (hardware) implementations anyway and, there, I'm not sure
the benefit justify outweighs the potential drawbacks.

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

The argument is not weaker that that for twist security - you do not need to perform a simple check.

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

I'm also not sure if (C) poses a serious threat. But, yes, the protocol can prevent that easily by multiplying with the
cofactor.


-- 
Johannes