Re: [Cfrg] Hardware requirements for elliptic curves

[Michael Hamburg <[e-mail]>]

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

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 hardware I’ve seen uses Montgomery reduction.  If everyone else does this too, it might be a minor strike against 2^big - small primes.  Other hardware folks: how do you do your reductions?  And how much of a pain would it be to switch to 2^big - small?  Am I missing something about short Weierstrass, cofactor problems or special primes?

Cheers,
— Mike