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

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