Re: [Cfrg] Hardware requirements for elliptic curves

[Johannes Merkle <[e-mail]>]

Michael Hamburg wrote on 04.09.2014 17:21:
> 
>> On Sep 4, 2014, at 5:55 AM, Johannes Merkle <[e-mail]> wrote:
>>
>> Michael Hamburg wrote on 02.09.2014 18:31:
>>> I agree with Alyssa that hardware performance isn’t our concern here.
>>
>> I disagree with this oversimplification. Currently, the fraction of TLS implementations based on HW is relatively
>> small but not negligible. And in the future it will increase:
>>
>> 1. Heartbleed has shown that it is dangerous to keep private keys in software. Hopefully, this lesson has been learned.
>>
>> 2. There are security critical infrastructures emerging, where TLS will be used with hardware crypto
>> implementations. Examples are car2car and car2X, health care infrastructures, smart meter,
>> e-government communications services.
>>
>> 3. In the foreseeable future, we will see a huge number of constrained devices in the IoT potentially deploying TLS
>> (e.g. for home automation, sensor networks).
>>
>> Furthermore, other IETF protocols are well within the scope of our effort. (As Kenny wrote in his announcement of the
>> current effort "We regard this as a major work item for CFRG and one where CFRG can provide real value to the TLS WG
>> and the IETF more widely.") For IPSec, there is indeed a significant number of implementations based on smart cards or
>> small HW crypto modules (for instance from my employer).
>>
>>
>> -- 
>> Johannes
> 
> You know what?  I spoke too soon on this, and you changed my mind.  Hardware does matter, even though it isn’t the main focus of this research group.
> 
> But I still don’t understand why hardware favors short Weierstrass curves or random primes.  Short Weierstrass really doesn’t seem simpler than Edwards to me.  It’s slower, less regular, and doesn’t parallelize as well (if you have high perf hardware).  It wants a halve() operation for best performance in addition to add/sub/mul, and you can’t just use one unified formula for everything if you’re complexity constrained.  The cofactor is potentially an issue, but you can just wipe out the cofactor first and then check against the identity.

I am not at all a hardware expert. But we just had a meeting of the ECC Brainpool, where several hardware vendors are
represented. What I understood is that they do not want to specialize their hardware to minimize their investment while
being fully flexible (algorithm agile). Remember that multipliers are also needed for RSA where the numbers do not have
a special shape. Furthermore, I guess that new implementations can be built easier based on existing ones.

> 
> And random primes aren’t better either: they’re still much slower than special primes in hardware, and it’s more complex to invert mod them (more complex Fermat’s Little Theorem, or have to implement EGCD), and you can’t switch between Barrett and Montgomery reduction as easily.  From Joppe Bos' email, it sounds like primes make one blinding technique more effective.  But if you suddenly have double the performance budget (from a faster prime) can you not do even better?
> 
The point is that flexible (non-specialized) hardware multipliers do not take advantage of specialized primes.
Specialized multipliers are certainly possible but are less agile w.r.t algorithms / curves. Flexibility is particularly
important due to the long development / certification cycles and the tremendous costs involved.


-- 
Johannes