Re: [Cfrg] Formal request from TLS WG to CFRG for new elliptic curves

[Simon Josefsson <[e-mail]>]

I'm reviewing the selection criteria.  Some of the requirements are
rather fine-grained and poorly justified, and appear to limit the search
space.  If taken literally, I believe they exclude some good candidates
and steer the selection into a rather small field of available options.

I'm fine with R1-R3.

"Paterson, Kenny" <[e-mail]> writes:

> Intellectual Property
>
>    R4.  Required: available worldwide under reasonable and well
>    understood licensing terms [1]
>
>    R5.  Desired: available worldwide under royalty-free licensing
>    terms [1]

I believe non-royalty-free licensing terms is a nonstarter.  I suggest
collapsing this into:

R4'. Required: available for worldwide implementation (by both
     proprietary and free open source software) and use under well
     understood and royalty-free licensing terms

> Interoperability
>
>    R6.  Desired: can be used with current software implementations
>    (using different curve parameters) of TLS, PKIX, SSH, and IKE [4]
>
>    R7.  Desired: can be used within current ECC standards of TLS,
>    PKIX, SSH, and IKE [4]

I do not see why these are desirable properties, so I disagree they
should be a selection criteria.  These properties restricts the search
space.  I would prefer if the CFRG are at liberty to recommend the best
alternative even if it is clearly not re-usable in existing software or
standards.  I would go even further saying that one of the reasons for
doing this excercise is that the existing software and standards are not
sufficient.

On the topic of interoperability, I would propose to add the following,
to me, more important property:

Rx. Desired: either a clear algorithm description exists (with clarity
on byte-ordering etc) or multiple interoperable implementations are
available.

If some alternative does not appear to be sufficiently specified or
widely implemented, the CFRG could take on driving a document to clarify
the solution.

> Security
>
>    R8.  Required: amenable to constant-time implementations, to avoid
>    side channel attacks [2]
>
>    R9.  Required: resist twist attacks [2]
>
>    R10.  Required: curve parameters should have good provenance;
>    random curves should be provably pseudorandom [5]
>
>    R11.  Desired for key exchange: resist invalid curve attacks [2];
>    note that complete addition laws help and are thus desirable [2].
>    (Note that the use of ephemeral keys also resist such attacks.)

Instead of R8-R11, I suggest to summarize this more generally as:

R8'. Required: the solution should be secure against reasonable and
well-understood threats, including (but not limited to and necessarily
not all of) brute-force, side-channel, invalid-curve, twist attacks, or
maliciously chosen curve parameters.

Designing against security threats is a balance, and I would say that
there are no perfect solutions.  Every solution will have some area
where they perform less well compared to some other solution.  I believe
the overall choice(s) should reflect well-balanced alternatives with
strong advantages and some understood disadvantages.

>    R12.  Required for PAKE: indistinguishability of curve points from
>    random strings [2]

I do not see why this is a desirable property for TLS, or other IETF
areas, so I disagree it should be a requirement.

/Simon