Subject: Re: [Cfrg] Point format endian (was: Adoption of draft-ladd-spake2 as a RG document)

From: Peter Gutmann <[email-masked]>
Date: Tue, 27 Jan 2015 10:34:58 +0000

Michael Clark <[email-masked]> writes:

>This code could do with some optimization, bswap(32|64) intrinsic (uses BSWAP
>machine instruction on x86_64, ARM, etc), working with a machine word size
>loop with a small tail loop to handle the modulus of the difference in length
>of the bignum from the machine word size. It is working byte by byte.

This is another example of "I can't believe we're having this discussion".
We're talking about bignum operations measured in the millions of CPU cycles
(a basic 1024-bit RSA decrypt is about 10M cycles, with P256 it's 7M cycles,
courtesy of the Crypto++ benchmark data) and you're bringing up optimising
something that might take a few hundred cycles (ignoring memory latency
overhead, which is going to hit you at some point whether you endian-reverse
or not).

The issue isn't about whether a 0.001% overhead is worth applying custom
architecture-specific assembly-language to eliminate, it's the issue of
encoding a particular implementation artefact into a standard.  As djb has
helpfully pointed out, he could have decided to encode the values as ASCII
decimal digits, or perhaps doodles, sign language, and squirrel noises.  Would
crypto standards then require that everything using 25519 be able to encode
the output as squirrel noises just because that's what one implementation
does?

The universal standard for crypto bignums is big-endian (things like
[email-masked] aren't a standard, it's what one implementation
chooses to do).  The 25519 form is an implementation artefact and should have
no place in a standard.

Peter.

---

From: Stephen Farrell <[email-masked]>
Date: Tue, 27 Jan 2015 10:56:45 +0000

On 27/01/15 10:34, Peter Gutmann wrote:
> The universal standard for crypto bignums is big-endian

Hmmm.... sez who? :-)

But seriously, if in fact this makes little or no difference,
which I believe is the case, and which I believe you are also
arguing, then what is the problem with going with the initial
coder's choice here?

If there is no problem then just doing that and making sure
it's properly documented should be just fine I'd have thought.

S.

---

From: Derek Atkins <[email-masked]>
Date: Tue, 27 Jan 2015 10:41:11 -0500

>> The universal standard for crypto bignums is big-endian

PKIX, OpenPGP, OpenSSH, Kerberos, TLS...  Pretty much every existing
IETF security standard I know of to date encodes numbers in big-endian
format.

> it's properly documented should be just fine I'd have thought.

It would mean a completely separate code path to support 25519 versus
supporting most (all?) existing ECC curves.

> S.

-derek
-- 
       Derek Atkins                 617-623-3745
       [email-masked]             www.ihtfp.com
       Computer and Internet Security Consultant

---

From: "Salz, Rich" <[email-masked]>
Date: Tue, 27 Jan 2015 15:46:28 +0000

> supporting most (all?) existing ECC curves.

Don't they have a different code path for the math implementation?

If the parsing/serialization special-code so onerous?  If so, shouldn't we have the Y coordinate?

---

From: Stephen Farrell <[email-masked]>
Date: Tue, 27 Jan 2015 15:57:38 +0000

> Don't they have a different code path for the math implementation?

Right. So it makes very little to no difference really I'd guess.

Or if someone has code where it would then sending a pointer to
that would help me at least. Anytime I've done that kind of code
it'd have been no problem at all to deal with this issue.

S.

---

From: Paul Hoffman <[email-masked]>
Date: Tue, 27 Jan 2015 08:07:29 -0800

We do not need "consensus" in this RG, just assurance that what we recommend does not have security holes. No one has suggested any security holes based on the endianness. The argument that "using different math would add code" is true, but pretty much irrelevant relative the to the size of the code needed to add a new curve. There is no interoperability issue: if someone messes up the math in either endian direction, they will know the first time they test their code, and there is approximately 2^-128 chance that if they got it wrong and only tested one vector, that they will accidentally get a good result.

The longer we argue about our preferences (instead of actual security issues), the worse off the IETF is.

--Paul Hoffman

---

From: Derek Atkins <[email-masked]>
Date: Tue, 27 Jan 2015 11:12:22 -0500

> Don't they have a different code path for the math implementation?

Maybe.  Maybe not.  A modmult is a modmult (to some degree).

> shouldn't we have the Y coordinate?

Anything new and different is onerous.  ;-) It means additional work
in terms of implementation, testing, validation, and interop.

My point is that there's years (decades, even) of standards and
implementation that parse network-byte-order numbers, even when the
local system is little-endian.  I don't see a good reason to change
that.  The only real argument I've seen is "well, the initial
implementation didn't do it that way, and other people have therefore
not done it that way."

-derek

---

From: "Derek Atkins" <[email-masked]>
Date: Tue, 27 Jan 2015 11:25:54 -0500

Paul,

On Tue, January 27, 2015 11:07 am, Paul Hoffman wrote:
> We do not need "consensus" in this RG, just assurance that what we
> recommend does not have security holes. No one has suggested any security
> holes based on the endianness. The argument that "using different math
> would add code" is true, but pretty much irrelevant relative the to the
> size of the code needed to add a new curve. There is no interoperability
> issue: if someone messes up the math in either endian direction, they will
> know the first time they test their code, and there is approximately
> 2^-128 chance that if they got it wrong and only tested one vector, that
> they will accidentally get a good result.
>

It is important for interoperability.  If I tell you that my ECC Public
Key is 0102030405060708090a but you interpret that as 0a090807060504030201
-- we will get different results even if both of us implement the math
correctly.  So I would argue that transmission encoding of keys and
results *is* a matter of security.

Then of course there's the matter of using the shared secret in another
algorithm, like AES.  Again, byte-order differences would result in
different AES keys.  Yet another matter of security.

Yes, it just mean we just need to "choose one".  But for the last 20+
years we've already chosen:  network-byte-order.

-derek

---

From: "Blumenthal, Uri - 0558 - MITLL" <[email-masked]>
Date: Tue, 27 Jan 2015 16:25:38 +0000

Actually, AFAIK, *every* IETF-developed Internet protocol (not just in Security area) uses Big Endian for on-the-wire.

--
Regards,
Uri Blumenthal                            Voice: (781) 981-1638
Cyber Systems and Technology   Fax:   (781) 981-0186
MIT Lincoln Laboratory                Cell:  (339) 223-5363
244 Wood Street, Lexington, MA 02420-9185       

Web:  http://www.ll.mit.edu/CST/
MIT LL Root CA:  <https://www.ll.mit.edu/labcertificateauthority.html>

----- Original Message -----
From: Derek Atkins [mailto:[email-masked]]
Sent: Tuesday, January 27, 2015 10:41 AM
To: Stephen Farrell <[email-masked]>
Cc: [email-masked]' <[email-masked]>; Peter Gutmann <[email-masked]>
Subject: Re: [Cfrg] Point format endian

-derek

_______________________________________________
Cfrg mailing list
[email-masked]
http://www.irtf.org/mailman/listinfo/cfrg

---

From: Paul Hoffman <[email-masked]>
Date: Tue, 27 Jan 2015 08:33:18 -0800

> results *is* a matter of security.

Correct: if you tell me your ECC public key and use a format that is the opposite of what is in the RFC, I won't understand it. That seems like an irrelevant argument.

> different AES keys.  Yet another matter of security.

See above. If you choose to use a format that is different than the RFC, you will not interoperate. 'Twas always thus.

> years we've already chosen:  network-byte-order.

Repeating your preference when it has no security implications doesn't help. If the eventual RFC specifies a different order than what you are used to, you can choose to follow the RFC or not.

--Paul Hoffman

---

From: Watson Ladd <[email-masked]>
Date: Tue, 27 Jan 2015 08:35:35 -0800

> results *is* a matter of security.

When I wrote the relevant section of the Turner draft, I was careful
to specify the keys as sequences of bytes. The concern you mention
doesn't exist: everything is a sequence of 32 bytes, with a defined
way to turn that into a number and process that number. If you don't
actually read the spec, of course you'll get it wrong.

> years we've already chosen:  network-byte-order.

I think Emerson had something to say about this argument.

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

---

From: Tony Arcieri <[email-masked]>
Date: Tue, 27 Jan 2015 11:40:27 -0800

> IETF security standard I know of to date encodes numbers in big-endian

Yet when it comes to running code, OpenSSH and GPG 2.1 are both using the
little endian versions of Curve25519 and Ed25519 already...

All of the existing material describing Curve25519 and Ed25519 describes it
in terms of little endian.

Changing the endianness now would break compatibility with all of the
existing running code and documentation, and for what? Why are we breaking
things and creating a pointless incompatibility?

"A foolish consistency..."

-- 
Tony Arcieri

---

From: Michael Clark <[email-masked]>
Date: Wed, 28 Jan 2015 03:56:00 +0800

> chooses to do).  The 25519 form is an implementation artefact and should have

I agree. I did qualify the statement that its unlikely to register on a
profile. e.g. don't forget to paraphrase without the context:

On 26/1/15 8:57 pm, Michael Clark wrote:
> So with big-endian wire-formats, practically all machines are going to
> bswap as the internal rep will be little endian. That cost is probably
> low compared to the cost of the computation, so there is a reasonable
> rationale to stick to big-endian.

This seems to be about adapting to IETF tradition. Fair enough.

The question is whether or not in the case of Curve25519, the keys are
considered an "opaque octet string" or unless the point needs to be
consumed and interpreted outside of the cryptographic primitive; then
there is an argument to follow the big-endian bignum tradition.

1). Will Curve25519 be used elsewhere (other than as a diffie-hellman
replacement) where the keys are exposed in form they need to be operated
on as a bignum, rather than opaque 32-byte octet strings? i.e. is to be
considered a standalone cryptographic primitive?

2). From reading Curve25519, the keys are stated as opaque, however I
understand that Curve25519 can be expressed in various isogenies where
the keys (32-byte strings) are no longer opaque and are big-nums. Is it
intended to be used in a general way as a parametrization?

If so it would mean it might be a good idea either for Curve25519 to use
byteswap from network byte order or to define a big-endian alternative
with a different name that does so. X25519; where the keys are no longer
opaque as per the current normative reference that specifies
"little-endian" 32-byte strings:

  https://tools.ietf.org/html/draft-josefsson-tls-curve25519-01
  http://cr.yp.to/ecdh/curve25519-20060209.pdf

a). If it is intended to be used as a standalone primitive, then it
doesn't matter so much: "32-byte octet string"

b). However if it is to be used generally as a parametrization that fits
into a curve generalization then this provides a good rationale to use
the tradition of big-endian bignums. i.e. ends up in ASN.1 fields, with
different parametrization of the same generalization.

Does that make it any easier? :-)

---

From: Damien Miller <[email-masked]>
Date: Wed, 28 Jan 2015 09:00:41 +1100 (AEDT)

> IETF security standard I know of to date encodes numbers in big-endian

No, OpenSSH uses little endian encoding for X25519 and Ed25519.

We don't care - they are opaque strings as far as our application is
concerned (which is IMO exactly how it should be).

+1 to little endian, for the sake of compatibility with deployed and
tested code.

-d

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Tue, 27 Jan 2015 20:24:48 -0500

On Tue, Jan 27, 2015 at 10:57 AM, Stephen Farrell <[email-masked]
> wrote:

> it'd have been no problem at all to deal with this issue.

Actually no, it makes a huge difference because I only have one encoder
library that serves all my algorithms and that maps the in-memory data
formats to one serialization format.

The algorithm implementations don't have their own bignum implementations
either. This is a different layer in the application stack, different rules
apply.

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Tue, 27 Jan 2015 20:34:13 -0500

> No, OpenSSH uses little endian encoding for X25519 and Ed25519.

TLS uses certificates. OpenSSH does not, it is currently using a raw key
which is a complete pain in the patootiee.

I am not going to be using any common code serializing for TLS and for
OpenSSH or GPG so the issue really does not arise there.

Internal consistency in TLS is what matters for TLS and after that internal
consistency in IETF. I really don't see why a TLS key would be used for
OpenSSH and it seems a bad idea to do so in any case. So making
transcription of keys easy is hardly a priority.