Re: [Cfrg] Requirements for curve candidate evaluation update

[Benjamin Black <[e-mail]>]

On Tue, Aug 12, 2014 at 3:05 PM, Salz, Rich <[e-mail]> wrote:
>
> I have asked before, perhaps you missed it.
>
>
>
> I take exception to your claims that “single curve model” and “no change
to wire formats” are facts on the ground.  Can you justify that?
>
>
>
> --
>
> Principal Security Engineer
>
> Akamai Technologies, Cambridge MA
>
> IM: [e-mail] Twitter: RichSalz

Rich,

The facts on the ground, as described in my post, are that people
implementing these systems may not be professional cryptographers, and even
if they are, they make mistakes, so requiring implementation of two
different models or transforms between models is a significant burden. If
an implementer wishes to use a different model internally, they can do so.
The difference is not requiring everyone do so.

As illustrated in the NaCl and TweetNaCl libraries having multiple required
models makes implementation more challenging, even for some of the best
cryptographers in the world. From
http://tweetnacl.cr.yp.to/tweetnacl-20131229.pdf :

"However, NaCl’s performance comes at a price. A single NaCl function
usually consists of several different implementations, often including
multiple assembly-language implementations optimized for different CPUs.
NaCl’s compilation system is correspondingly complicated. Auditing the NaCl
source is a time-consuming job. For example, four implementations of the
ed25519 signature system have been publicly available and waiting for
integration into NaCl since 2011, but in total they consist of 5521 lines
of C code and 16184 lines of qhasm code. Partial audits have revealed a bug
in this software (r1 += 0 + carry should be r2 += 0 + carry in
amd64-64-24k) that would not be caught by random tests; this illustrates
the importance of audits."

"In principle we could use the same scalar-multiplication code for both
Curve25519 and Ed25519. This would require conversion of points on M to
points on E and back. If we used the x-coordinate-based differential
addition ladder of Curve25519 also for Ed25519, we would additionally need
code to recover the y-coordinate as described by Okeya and Sakurai in [20].
Conversion code is not substantially shorter than the code required for the
Curve25519 Montgomery ladder, so we decided to not use the same code for
scalar multiplication in Curve25519 and Ed25519."

That requiring multiple models makes implementation more difficult and
implies more code is both intuitively obvious and supported by available
evidence. Again, implementers are allowed, even encouraged, to write
whatever optimizations they like. Requiring them to implement specific
optimizations for small performance gains at a cost of more, and more
difficult, code would be unusual in any IETF proposal, but is especially
out of place when the proposal is for core cryptography primitives.

You, like many of us, have had up close and personal experience with bugs
in crypto code. You know that even the best make mistakes. Requiring a
single model for everything significantly reduces opportunities for
mistakes and the small performance gain of multiple models does not justify
requiring the additional exposure.


b