Re: [Cfrg] On why point and APIs formats matter (Re: Submission of curve25519 to NIST from CFRG -> was RE: On "non-NIST")

[Watson Ladd <[e-mail]>]

On Thu, Mar 12, 2015 at 4:40 AM, Dan Brown <[e-mail]> wrote:
> Just to clarify, the old standards point formats are (per curve):
>
> fixed length octet strings,
> big-endian (for mod p,n ints),
> short Weierstrass,
> x-only for computation purposes,
>
> where old standards means IEEE 1363, ANSI X9.62/63, SEC1, NIST, FIPS, ...
>
> with the _1_ exception ‎that _if_ ASN.1 is used to convey an ECDSA
signature, as in PKIX/X.509, then the INTEGER type is used for r and s. If
you are not using ASN.1, the old standards do not say how to encode a
signature: you can encode however you like. Weirdly, there's also an extra
conversion to BIT STRING which is not even a proper way to do ASN.1:
because a specific encod, DER, lands into an abstract value. Here, I think
ECDSA just followed the RSA /X.509 way.

Except there is a choice between compressed and uncompressed. Yes, one can
design a good API that deals with these issues, but most existing
implementations don't do this, forcing the right choice of encoding onto
the caller. The padding bug I mentioned above results from a different type
confusion, where the x coordinate has the same type as a DHE result, and
that type is not a string of bytes put directly into the hash function, but
rather a bignum that can be encoded multiple ways.

>
> I get the feeling that some people see ECDSA signatures in certs, and get
the impression that _all_ the old point formats are variable length, and
the ECDH calcs include y, etc. Wrong.

But implementations that support signatures as well do have to deal with
two distinct encodings bignums, and there are two different lengths of
point encodings: one for compressed, one for uncompressed. It's possible
people have their own oddball encodings of ECDSA signatures, but having
such encodings makes higher-level APIs tricky: either encoding is a
separate step, or you multiply the number of functions.

>
> ‎Also, there was an IKE spec that used both x and y for ECDH calcs, but I
think that's been fixed.
>
> Anyway, I slightly prefer the old formats, but don't mind adjusting them
on a per curve basis, or perhaps per hash/KDF/signature_alg, if people say
that's easy. It kinda precludes an old generic curve implementation being
able to talk Curve25519 with a new implementation, but maybe that's what's
wanted, anyway.

Yes, it's true that if someone actually implemented generic curve support,
they wouldn't be able to automatically support Curve25519 unless TLS
decided to use the Weierstrass coordinates, as that's the only option for
generic curves in TLS. It is of course easy to support the current
Curve25519 format with an existing implementation of ECC multiplication:
one reverses the bytes, adds a constant, recovers y, carries out the ECC
multiplication, discards y, subtracts the constant, and reverses the bytes.

The point of limiting the number of formats is to write a pair of functions
curve25519_scalarmult(char *p, const char *q, const char *s), and
curve25519_scalarmult_base(char *p, const char *s), and likewise higher
level signing and verification functions that work for all protocols. These
functions can and probably will share code internally, and can use whatever
calculations are desired.

One can achieve this for any reasonable set of choices: it's not an
advantage of one form over another. I've written such code (well, almost)
for the choices NIST made. But it's much harder to do this correctly for
things not x coordinate Montgomery, and the varieties of formats don't help.

The concerns raised about little-endian representation and existing API
compatibility presuppose libraries that force all users to pay attention to
such details, even when all they want is to encrypt and sign data. The
claimed advantage of these libraries is the flexibility to parametrize
protocol implementations over curves, and let users implement any protocol.
But that's not the library application programmers actually want to use,
and it's irrelevant how the library works internally.

Sincerely,
Watson Ladd

>
> Best regards,
>
> -- Dan
> Original Message
> From: Viktor Dukhovni
> Sent: Thursday, March 12, 2015 2:17 AM
> To:[e-mail]
> Reply To:[e-mail]
> Subject: Re: [Cfrg] On why point and APIs formats matter (Re: Submission
of curve25519 to NIST from CFRG -> was RE: On "non-NIST")
>
> On Tue, Mar 10, 2015 at 07:20:31PM -0700, Watson Ladd wrote:
>
>> > Your concerns about endianness are a trivial in comparison to the
>> >
>> > overall industry change to new public key algorithms. Please have some
>> > focus
>> >
>> > and do not add noise to the topic.
>>
>> No, they aren't: they are actually much more important than the
>> question of which curve to use.
>
> Though I still retain enough graduate school mathematics to understand
> the fundamentals of EC crypto, I am not a mathematician or cryptographer.
> Rather, these days I am an implementor of applications that employ
> crypto, most notably Postfix where I maintain the SMTP TLS feature-set,
> and I have plans to contribute DANE support to one or more TLS libraries.
>
> So with my implementor hat on (the only hat that fits here), I'd
> like very much to second Watson's remarks.
>
> In the DANE space with 24 different combinations of the TLSA (usage,
> selector, mtype) parameters not only do essentially all the other
> implementations I've tried to read offer incomplete support for
> some corner cases, they are also insecure for a subset of the
> parameters! On top of that, users get confused and publish
> incorrect records.
>
> Yes, the analogy is rather imperfect, but I believe that the key
> observations Watson makes are relevant.
>
> (In)security will depend a lot more on how easy it is to implement
> the design incorrectly than on how easy it will be to perform a
> cryptanalytic attack. The curves considered here are sufficiently
> strong to make implementation considerations be a key differentiator.
>
> So if we can agree that 25519 with a fixed length little-endian
> octet-string encoding (not variable length big-endian int) is more
> robust in the hands of mortal implementors, that should be given
> due consideration.
>
> --
> Viktor.
>
> _______________________________________________
> Cfrg mailing list
>[e-mail]
>http://www.irtf.org/mailman/listinfo/cfrg
>
>
> _______________________________________________
> Cfrg mailing list
>[e-mail]
>http://www.irtf.org/mailman/listinfo/cfrg
>

--
"Those who would give up Essential Liberty to purchase a little Temporary
Safety deserve neither Liberty nor Safety."
-- Benjamin Franklin