[curves] Twist security for elliptic curves

[Johannes Merkle]

Trevor Perrin schrieb am 26.06.2015 um 01:35:
> 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 don't think there is (other) precedence for such a separation in the standards. Which doesn't mean that it isn't a
good idea if the requirements differ considerably.

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

Of course, in theory, hardware can also be optimized for special primes. However, its one thing to implement a
specialized multiplier as a prototype but a very different thing to developed this as a product. I talked about that
with the guys from Infineon and NXP. They say that they have to maintain hardware implementations for general primes
anyway, e.g. for RSA. Their implementations are not replaced with new versions but continuously evolving, going back to
the very first implementations in the early 90s. For them, developing a new multiplier from scratch and maintaining it
as a second product is a complete no-go as this would imply tremendous additional costs. You have to take into account
that they have to certify their chips according to CC EAL4+ or higher which is a very lengthly and expensive process.
(Additional certifications are required for the smart card operating system and crypto applications based on the chip.)
Costs and resources for product management would also double.


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

Its not just the computation time, generating random bits of sufficient quality can also be time consuming, depending on
your entropy source. And in devices like smart cards, 20% can already be an issue.

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

My position is that we have different requirements for HW and SW, so why not having different curves?

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

Yes.
> 
> So you're arguing to remove a safeguard to make it extra-clear people
> should be doing another safeguard?
> 
If a safeguard does not provide the protection it is supposed to do, it might be better to remove it. We are talking
about the case, where resulting points are revealed and side-channels allow to launch the attack.

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


I used the term "high assurance" in my talk at the NIST ECC workshop. I mean implementations that run in potentially
hostile environments, e.g. smart cards, smart meter devices, RFID tags, etc. There, you need to take additional side
channels into account and typically apply very conservative designs. Due to these additional countermeasures and
security certifications (often required by regulations), development cycles are much longer there.


-- 
Johannes