Re: [Cfrg] Requirements for elliptic curves with a view towards constrained devices

[Watson Ladd <[e-mail]>]

On Fri, Nov 21, 2014 at 9:26 AM, Andy Lutomirski <[e-mail]> wrote:
> On Fri, Nov 21, 2014 at 8:58 AM, Watson Ladd <[e-mail]> wrote:
>> On Fri, Nov 21, 2014 at 4:51 AM, Lochter, Manfred
>> <[e-mail]> wrote:
>>>
>>>
>>>
>>>
>>>
>>> __________ ursprüngliche Nachricht __________
>>>
>>> Von:            Watson Ladd <[e-mail]>
>>> Datum:  Donnerstag, 20. November 2014, 16:21:50
>>> An:             "Lochter, Manfred" <[e-mail]>
>>> Kopie:  "[e-mail]" <[e-mail]>
>>> Betr.:  Re: [Cfrg] Requirements for elliptic curves with a view towards
>>> constrained devices
>>>
>>>> On Thu, Nov 20, 2014 at 12:01 AM, Lochter, Manfred
>>>>
>>>> <[e-mail]> wrote:
>>>> >> Of course, you don't need to take my word for it: Cloudflare was very
>>>> >> clear that widespread ECDSA support was essential to making TLS free.
>>>> >> Mobile devices are having issues with verification times for NIST
>>>> >> P384. V2V proposals involves a staggering number of verifications a
>>>> >> second, but oddly enough don't use batching or efficient signatures,
>>>> >> thus forcing larger, more expensive hardware.
>>>> >
>>>> > Is there really a requirement for mobile devices to use a 384 bit curve?
>>>> > Why is 256 not sufficient? In which scenarios do you see the neccessity
>>>> > to use P-384? Which specific mobile devices are having issues with
>>>> > verification times? Are they having these problems only in connection
>>>> > with the proposed protocols you mention?
>>>>
>>>> When my mobile phone's browser connects to a website whose certificate
>>>> is signed by P384, a P384 verification better take place. Not
>>>> supporting P384 introduces an interoperability problem.
>>>
>>> I'm glad that you agree with my previously stated position that 384-bit curves
>>> are needed. Following your reasoning 256/384/512(521) bit curves have to be
>>> supported. In this case I would rather see performance problems on the
>>> 512/521 end.
>>> I would very much appreciate if you could also answer my other questions
>>> above.
>>> You seem to say that car-to-car communication will use the curves proposed by
>>> the cfrg. This supports the inital position we took in the Brainpool position
>>> paper (eprint 832/2014). I'm glad that we seem to agree on that.
>>
>> The V2V projects aren't. Despite high performance constraints they are
>> not making optimal choices. Batch signatures would seem a natural fit,
>> and yet ECDSA is still being used. P256 seems to be selected, despite
>> Koblitz curves existing. But blinding won't be used: the performance
>> hit is too much, and the security model doesn't require it. It doesn't
>> seem like they will switch to Curve25519 if the CFRG recommends it.
>
> Don't the V2V things need high *real-time* performance contraints?  To
> me, that would seem to rule out batch signatures entirely, unless
> there's a magic verifier that can retain good performance even in the
> presence of an invalid signature.

Most signatures are valid: while its true that a significant number of
bad signatures will slow batch verification, that number can be quite
large. For example, http://cr.yp.to/badbatch/badbatch-20120919.pdf
claims that 10 bad signatures out of 64 can be identified faster then
separate verification for each signature. It's clear that no matter if
verification or bandwidth is the limiting factor, malicious attackers
can carry out a denial of service.

Of course, there are several more predictable and simpler
optimizations that can be done, even if one has to stick with
NIST-approved curves. Amusingly, while Bitcoin uses a Koblitz curve,
it is only recently that bitcoin-core has been modified to take
advantage of this, due to verification becoming quite time consuming.

The gold standard for verification speed is e=3 RSA. But signing is
very, very slow.

Sincerely,
Watson Ladd
>
> --Andy



-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin