[curves] Curve19119: A legacy-level little brother of Curve25519

[Björn Haase]

Hello,

>Were your fears justified about the practical impact on the
>authentication delay?  Was a Curve25519-based PAKE unusably slow and
>Curve19119 usably fast?  From your paper (which I may have skimmed too
>fast) it looks like a Curve25519-based PAKE took 4s, but I don't see
>timing for a Curve19119-based PAKE.

In fact, we have switched back to Curve25519 for our production software
after having succeeded to speed up
Curve25519 by more than a factor of 3 than what we had beforehand in
https://eprint.iacr.org/2015/343.pdf
. Without this speedup factor of ~2 we would have had more than 8
seconds login delay
which would not have been accepted by our marketing. They would have
required us to go back to
challenge-response.

Note that in our paper we also are discouraging use of the lower
security legacy curve if
it could be avoided. However, since the main purpose of PAKE in our
industrial context
is not confidentiality (and perfect forward security) but secure
authentication, I assume that PAKE
schemes on very resource constrained devices might want to consider also
the legacy-level curves
if the application would otherwise be forced to switch back to
challenge-response protocols.

Yours,

Björn.

Am 27.07.2017 um 20:39 schrieb Taylor R Campbell:
>> Date: Thu, 27 Jul 2017 18:27:31 +0200
>> From: Björn Haase <bjoern.m.haase at web.de>
>>
>> Folks interested in a legacy-level high-efficiency curve targeting the
>> ~94 bit security level might like to have a look at Curve19119 and it's
>> associated DH protocol X19119.
> Neat.  The danger of a 94-bit security level for a discrete log system
> like this, of course, is that it takes only a single offline 2^94-cost
> precomputation for an attacker to quickly compute any discrete logs in
> the system.
>
> While 2^94 is probably outside the range of feasibility today, it's
> not unimaginably far away.  For comaparison, the Bitcoin hash rate,
> according to blockchain.info, is ~6e18 ~= 2^62 H/s ~= 2^87 H/year, and
> up by 5x from a year ago.  That's cost in SHA-256 evaluations, not in
> Curve19119 additions, so maybe off by another few bits, etc.
>
>>                                 Curve19119 and X19119 originally have
>> been developed for use with our variant of the PAKE protocol PACE. We
>> developed Curve19119 in order to get better responsiveness in our PAKE
>> protocol implementation in an explosion protected setting with severe
>> power constraints. Originally we did fear that Curve25519 might be too
>> slow.
>> [...]
>> We observe a speedup factor of roughly 1.9 in comparison to our X25519
>> implementation on a Cortex M0+ microcontroller.
> Were your fears justified about the practical impact on the
> authentication delay?  Was a Curve25519-based PAKE unusably slow and
> Curve19119 usably fast?  From your paper (which I may have skimmed too
> fast) it looks like a Curve25519-based PAKE took 4s, but I don't see
> timing for a Curve19119-based PAKE.
>
> Can't find the citation now, but I recall coming upon a study a few
> years back finding that a noticeable authentication delay actually
> *raised* users' perception of security versus a negligible
> authentication delay, as long as the noticeable delay wasn't too long
> for the users to get antsy.  (Insert caveats about human studies by
> computer security nerds, sampling biases, methodology, etc.)
>