Re: [Cfrg] big-endian short-Weierstrass please

[Dan Brown <[e-mail]>]

Well, maybe everybody could agree on this middle ground? 

00) Continue (or start) to allow generic ECC modes in IETF protocols, such
as the specified curve option RFC 4492, while specifically encouraging
implementers to use best practices, e.g. recommend constant-time for private
key operations, checks for MOV, etc., to help implementers look out for the
known pitfalls, perhaps collected in an RFC. 

10) Continue to use the old ECC standards' big-endian short Weierstrass
formats to specify arbitrary curves whenever the above-mentioned optional
generic ECC modes are actually used.  

01) Continue to use big-endian short-Weierstrass point and KDF input formats
for these generic ECC modes, at least whenever the curve is specified using
big-endian short-Weierstrass.  So, just to be clear, if somebody happens to
specify Curve25519 using the big-endian short Weierstrass a and b, then the
old formats will be honoured, not the new.  So, this would be backwards
compatible optional way to use Curve25519.

11) For curves indicated via names or OIDs, use a format determined by that
name.

This middle ground refers to formats only: not signature algorithms, key
agreement algorithms.

Specific replies to previous message inserted below (but somewhat
independently of the comment above).

> -----Original Message-----
> From: Cfrg [mailto:[e-mail]] On Behalf Of Daniel Kahn Gillmor
> On Tue 2015-01-27 10:41:50 -0500, Dan Brown wrote:
> > But I wonder if there are any old implementations of the standards I
> > listed above, that accept generic specified short Weierstrass curves,
> > but lock together the KDF and raw ECDH operations.  Users stuck with
> > such implementations couldn't gain _all_ the benefits of Curve25519,
> > side channel resistance or whatever, but surely there's some residual
> > benefits for them to use Curve25519 with a generic representation:
> > maybe the rigidity Curve25519, or interoperability with other users
> > with the newfangled software, not to mention the blessing of the
collective
> wisdom of CFRG.
> >
> > If the argument is that no such implementations could exist, or that
> > the implementations, or even old ECC standards, are so bad that we
> > should try to discourage interoperability, then please present that
case.
> 
> It sounds to me like you're presenting a choice between two options for
the
> CFRG:
> 
>  0) help more people move to better curves, without moving anyone to
>     better algorithms or requiring anyone to move to better
>     implementations.
> 
>  1) Allow people who can move to better algorithms, implementations, and
>     curves to do so in one step, while leaving people with brittle
>     software behind if the new system is adopted in exclusion to the
>     old.

That's another way to put it, though I was not exactly asking for 0 they way
you put it. Specifically, I was _not_ proposing to stop anybody from moving
ahead to newer implementations.  I was only aiming to maintain having
backwards interoperability with old implementations.  For example, RFC 4492
allows curves to be specified in Weierstrass form, not just as named form.
I don't know if any TLS implementations support the specified curve option,
but if they do, then it would be nice if the new implementations could talk
to them, using the new curves.  

Well, in that case, I suppose that the new implementations talking to old
implementations could just as well revert to old point formats, to send on
the wire, and to compute shared secrets.  There might side be channels on
the old side, but at least the new side would be safe: stopping half the
leak might have some small value.  Of course, for that, new implementations
would have to support big-endian short-Weierstrass, but they wouldn't use it
normally, except for backwards compatibility.

> 
> It seems like the answer to this would be governed by your perception of
> (a) existing curves compared algorithms and implementations, and (b) how
> you expect the rollout+deprecation process to happen, but even considering
> both of these choices independently, it seems like (1) is better.

Yes, about (a) and (b).  Still not sure about (1). 

> 
> Curves vs. Algorithms and Implementations
> =========================================
> 
> If you feel that the existing curves themselves are the main source of
concern,
> but not the algorithms and implementations, you might lean a little bit
toward
> (0).  However, there seems to be a general consensus that existing
> implemetations and algorithms themselves are problematic
> -- for example, libraries like OpenSSL have rewritten their P-256
> implementations in the last year, and deterministic signature mechanisms
are
> clearly better than traditional ECDSA.  So (1) is more appealing -- if we
can fix
> more things during this transition, we should fix them.

Hmm, yes, I think that most of the claimed security benefits for Curve25519
have to do with implementability: efficiency, avoiding security pitfalls in
implementations.  More precisely, these are claimed as the primary benefits.
The rigidity of the curve is claimed only a secondary benefit (compared to
the primary benefits), as I understand the claims.  In any case, that's how
I'd classify the benefits the Curve25519 and similar.

> 
> Rollout and Deprecation
> =======================
> 
> There is existing code that is never going to change.  There is existing
code that
> can be minorly changed by tweaked parameters.  And there is existing code
> that can be easily, fully upgraded.
> 
> The first group is never going to disappear, and unfortuately, members of
that
> group might be too important for every tool to just ignore the group
entirely
> (consider systems that want to talk to home routers or networked printers,
or
> systems that are only willing to use NIST curves).  So tools that require
> backward compatibility that covers these systems will need to have some
level
> of fallback interoperability to existing practice in both curves and
algorithms.
> 
> But if we're going to have the fallback to existing practice anyway, we
can also
> use that to cover those implementations that can only accept minor
changes.
>

Ok, I'm the last person to know about software upgrades etc., but I do
understand that the old standards allowed specified curves, which in theory
allows the curve choice to be updated on the fly, without upgrading the
software.

Note: I know that X9.62 and SEC1 placed restrictions on the field size and
curve sizes.  The SEC1 field sizes were meant to encourage interoperability.
Suppose these old standards were updated to allow new curves.  Ok, more
work.  Change formats, yet more work.  But, doable.  

Aside: interoperability which seems necessary for non-monopoly security.  We
don't want everybody to use the same software, right?  Interoperablity
sometimes involves conceding perfection for something good enough, right?
 
> (1) seems like the better option to me, from an overall ecological point
of view.
> Let's take advantage of this transition time to include important fixes in
all
> areas, for those who can make them.
> 
> 
> 
> 
> As for byte-ordering: higher levels of abstraction (both on the wire and
> logically) all prefer fixed-length bitstrings anyway.  So that's the
interface that
> we should use for the primitive.  We should declare something explicit so
that
> libraries know what to produce to get canonical bitstrings, and move on.

Done that, almost. Old ECC standards chose octet strings for EC public key
reps and for KDF inputs.  They just chose the prevailing big-endian approach
and moved on (perhaps never expecting this decision to be revisited, and
furthermore being told to move on ;-)

One and half exceptions to octet string only formats, hence the "almost"
above. (1/2) EC standards chose preserve integers in ECDSA: F_p field
elements were mapped into the field F_n, by preserving integers and reducing
mod n, which would have been equivalent to converting to fixed-length
big-endian octet string and then converting back to integers,  (3/2) for
ASN.1 representation of ECDSA signatures the old EC standards encode the
integers in (r,s) as ASN.1 integer types.  An alternative would have been
for the EC standards to convert integers (r,s) in a signature to octet
strings before going into ASN.1, but if you are using ASN.1 already, why not
keep integers as integers?

> Little-endian is fine.

Ignoring any backwards interoperability, I would agree, in fact, it is
probably better if it works better with current computer architecture.
Isn't maintaining backwards interoperability usually supposed to a good
thing?