[curves] Twist security for elliptic curves

[Trevor Perrin]

On Thu, Jun 25, 2015 at 5:42 AM, Johannes Merkle
<johannes.merkle at secunet.com> wrote:
> Trevor Perrin schrieb am 23.06.2015 um 01:57:
>>
>> 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.

Are there cases where separate standards for asymmetric crypto for HW
vs SW was a good idea?

I guess NIST/SECG had binary-field curves that were faster on HW, as
well as prime-field curves.  But I think the binary-field curves
weren't used much.


I could understand if there's very different performance for HW vs SW.
But that doesn't seem the case here.  Curves over efficient prime
fields like 25519 can be optimized well on SW and HW.

Even for less-optimized implementations (generic field multiplier),
using blinded scalars, the speed hit for curves like 25519 or
Goldilocks vs random-prime curves seems small:

Assuming point-on-curve checks are performed, the Lochter paper and
your email suggest a blinding factor of keysize/2 bits, instead of 64
bits.  So that's a slowdown of ~1.2x for a 256-bit curve and ~1.3x at
448 bits.

This doesn't seem worth fragmenting standards over, particularly
because the more efficient equations of newer curves probably make up
that difference?


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

By "twist security being potentially dangerous ... issues ...
drawbacks" all you mean is that twist-secure curves might lull
implementors into a false sense of security, so they might skip the
point-on-curve check?

So you're arguing to remove a safeguard to make it extra-clear people
should be doing another safeguard?

I'm not sure what "high-assurance" means here (or in [1,2]).  But
assuming it means something like "conservative security design",
wouldn't you rather have both safeguards?

Trevor

[1] http://csrc.nist.gov/groups/ST/ecc-workshop-2015/presentations/session4-merkle-johannes.pdf
[2] http://eprint.iacr.org/2014/832.pdf