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

From: Peter Gutmann <[email-masked]>
Date: Mon, 26 Jan 2015 10:20:34 +0000

Mike Hamburg <[email-masked]> writes:

>But will the endian complicate the implementation of the new curves?

Given that every single crypto bignum representation that I'm aware of (X.509,
S/MIME, PGP, SSH, TLS, OCSP, CMP, TSP, and many more) are all big-endian,
there are probably lots of crypto libraries that simply don't have little-
endian import/export routines.  Looking at BN_bn2bin()/BN_bin2bn() from one
widely-used library that powers half the Internet (and mobile phone market),
it only supports the big-endian format.  So that's automatic non-support for
the world's most widely-used crypto library outside of MS CryptoAPI (which
doesn't expose its bignum library).

I can't believe we're even having this endless discussion.  The universal
standard for external representations of bignums in IETF protocols is big-
endian.  Even the PGP and S/MIME, and SSH and TLS, folks have managed to agree
on that one.

Peter.

---

From: Alyssa Rowan <[email-masked]>
Date: Mon, 26 Jan 2015 10:41:47 +0000

On 26/01/2015 10:20, Peter Gutmann wrote:

> The universal standard for external representations of bignums in 
> IETF protocols is big- endian.

They are NOT bignums. As per TLS WG discussion, all new curves' wire
formats are opaque octet strings.

> Even the PGP and S/MIME, and SSH and TLS, folks have managed to 
> agree on that one.

GnuPG and SSH folks are using 25519's native big-endian formats.

If we try to change it arbitrarily and confusingly, everyone will
ignore CFRG - we're late to the party anyway - and will use the native
format.

- -- 
/akr

---

From: Alyssa Rowan <[email-masked]>
Date: Mon, 26 Jan 2015 11:07:14 +0000

> GnuPG and SSH folks are using 25519's native big-endian formats.

Um, I mean little-endian there. Clearly I need more tea. <g>

- -- 
/akr

---

From: Michael Clark <[email-masked]>
Date: Mon, 26 Jan 2015 20:57:57 +0800

> endian.  Even the PGP and S/MIME, and SSH and TLS, folks have managed to agree

Yes. Legacy. "network byte order" is big-endian.

It's tradition versus efficiency. big-endian is tradition. little-endian
is how most CPUs work these days. The reality is Sparc9, ARMv3, and
Power8 are now all bi-endian and are adopting little endian ABIs. Power8
being the most recent to change (ppc64le).

Given the algo is new, one could /consider/ a BN_bn2binle and
BN_binle2bn (or an endian argument variant). It's a small change.

I see the current code is working byte by byte due to endianness. It
takes 2nd order little endian (with host endian limbs due to the shifts)
and converts to big endian wire format. It reads from the distant big
end (little-endian) and writes out big endian. It bswaps.

        n=i=BN_num_bytes(a);
        while (i--)
                {
                l=a->d[i/BN_BYTES];
                *(to++)=(unsigned char)(l>>(8*(i%BN_BYTES)))&0xff;
                }
        return(n);

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. It may not even register on a profile (we can use
gperftools to check). This code is *absolutely fine*. That said we could
make BN_bn2bin faster, use BSWAP intrinsic on x86_64, sparc, arm, ppc
and use 64-bit loads and stores (including test cases and corner cases).
Let me know if anyone wants to sponsor?

Also BN_num_bits_word could use __builtin_clz or __builtin_clzll
(_BitscanForward, _BitscanReverse on MSC). No cache surface for a table
lookup. Modern compilers have these intrinsics. On Pentium III there is
BSR, and in SSE4 there is LZCNT instruction, and there is even a cache
friendly alternative that uses Henry S. Warren's Hacker's Delight tricks:

  https://gcc.gnu.org/bugzilla/show_bug.cgi?id=36041

Let me know if you can find me a sponsor. I'm currently (as a passtime)
doing cycle counts on intrinsic and C fallbacks for these kinds of
routines.. (to fill in for compilers without them). Testing on
MSC/GCC/Clang on Darwin/Android/Windows/Linux.

With little endian wire format and use of 32-bit or 64-bits limbs on all
modern systems (sparc9, power8, x86, arm) BN_bn2binle routine would
essentially be memcpy. That's the sad part.

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.

  BSWAP is one 1 cycle per 32-bit word on i386
  BSWAP is one 1 cycle per 64-bit word on x86_64
  BSWAP has been around since i486

Someone starting today would indicate endianness statically or
dyanamically in their number format and use the hot potato principle.
Get it off your hands at the lowest cost to yourself, which nowadays is
little-endian. Remember GHASH is Bit Reflected (base 2 little endian)
and it made it into a spec.

Peter makes a pretty good case to stick with big-endian, from a
consistency point of view, but not from an efficiency point of view.

Seems like we will be swizzling onto and off the network into
eternity... unless someone makes a decision otherwise...

---

From: Michael Clark <[email-masked]>
Date: Tue, 27 Jan 2015 13:50:03 +0800

> and it made it into a spec.

Just saw DJB's email on twitter.

https://www.ietf.org/mail-archive/web/cfrg/current/msg05938.html

Wrote this last night before seeing it:

I believe GCM GHASH is bit-reflected (more accurately bit level little
endian, the true opposite to big-endian or "true little endian") on the
wire in the GCM AEAD hash. It is an existing example of not using
big-endian, but also not using little-endian as we commonly know it
(bignums: with 8-bit big endian limbs, little limb first).

The finite field bit set for GHASH could potentially be represented in
either big-endian or little-endian. e.g. where the bit offsets [0-127]
are within either of those domains, but it is neither. It is perhaps
better called "true little-endian or base 2 little-endian".

Just citing this as precedence for a 16-octet opaque encoding of a
galois field value that is not big-endian and is used in TLS, SSH, etc.

That said, GHASH is really a GF(2^n) bit set, and not a scalar.

The fact that GHASH only uses xor and shifts makes it different to
scalarmult, however the Intel PCLMULQDQ GHASH implementation needs to
deal with this bit-reflection property in AES-GCM as the PCLMULQDQ
instruction shifts "left", not "right" as you would typically do for
GHASH. It seems to cause extra work for computers with little-endian
bignums and 8-bit big endian limbs, little 8-bit limb first.
litte-endian as we know it is a misnomer and GHASH is perhaps "true
little-endian". GCM is an example of making computers work even harder
using an even more obscure encoding.

If you want to break a tradition; it pays to have a counter example
where it has already been broken (and made things harder).

You have to consciously decide to "not do extra work" on most computers
or maintain tradition. le wire format still needs bswaps for portable
code: just they will be compiled out on prevalent systems "today" versus
mid-to-late-90's.

Ref:
{Carry-Less Multiplication and Its Usage for Computing the GCM Mode}

---

From: Watson Ladd <[email-masked]>
Date: Mon, 26 Jan 2015 22:00:52 -0800

> being the most recent to change (ppc64le).

No it's not because of efficiency. Nor is C code necessarily endian
dependent. See http://commandcenter.blogspot.com/2012/04/byte-order-fallacy.html
for details, and explanations of why code that depends on endianness
is usually wrong. Rather, it has to do with the format of existing
implementations: everyone who grabs the NaCl implementation is using
an little-endian encoding. Changing this would mean that there are no
existing implementations. It would cause significant confusion between
old and new versions.

> BN_binle2bn (or an endian argument variant). It's a small change.

Why do people feel the need to write their own buggy implementations
of Curve25519, when there are several public domain ones for the
taking, especially when this means giving up the optimizations related
to reduced radix format?

> Let me know if anyone wants to sponsor?

And you have benchmarks showing that this code is the bottleneck, and
not the bignum multiply inner loop?

> and it made it into a spec.

 Re GHASH. It doesn't matter in hardware either way, as reflection is
just relabeling, but in software you have to do some weird twists to
make it work out. Even Intel's carryless multiplies do things the
natural way. By contrast the Curve25519 format we are deciding is
between s[0..31] is s[0]+256*s[1]+..256^(31)*s[31], or
256^(31)*s[0]+256^(30)*s[1]+..s[31]: all systems agree on the value of
each byte, and the question is which bignum it represents. It's easy
to turn this into whatever internal representation you need, unlike
swapping bits in a byte.

Let me see if I get your second line correct. Instead of picking one
format, and encoding to and from it with a trivial amount of portable
C, we should use architecture specific micro-optimizations, and force
the implementation and testing of two distinct output and input
methods, for a nearly unmeasurable speed gain. Of course, there are
many architectures where you cannot serialize in the way you suggest:
unaligned loads and stores are not supported on many MIPS processors,
and there is no guarantee that alignment of bignum fields will be
maintained.

> consistency point of view, but not from an efficiency point of view.

He argued that this would mean automatic OpenSSL nonsupport. Given
that Rich Salz is on the development team of OpenSSL, I consider this
unlikely. Furthermore, you can take curve25519-donna and use it today:
it doesn't entail modifications (which are themselves trivial) to the
bignum library.

I am amazed that we are repeating discussions that were had in TLS. Or
maybe I shouldn't be. At what point can we declare that Curve25519 can
be adopted by IETF protocols? It would be nice if we could report
something by Austin, and maybe have a plan to finish up higher
security levels and signatures by the summer.

Sincerely,
Watson Ladd
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> 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

---

From: Michael Clark <[email-masked]>
Date: Tue, 27 Jan 2015 14:24:01 +0800

> taking, especially when this means giving up the optimizations related

I hope this is not implied by my email.

> not the bignum multiply inner loop?

Not yet. However I doubt the bswap in and out has a large bearing (as I
hint). I was rather responding to a mention of the existing bignum code;
and went and had a look at the code to see for myself.

It makes sense to use the Curve25519 format and calculations if they are
already optimized. i.e. consider it an intrinsic with its own wire
format. Given there is no such thing as a standard wire format, given
all the different encodings within IETF and ones adopted from outside.

> and there is no guarantee that alignment of bignum fields will be

I'm not suggesting that. I'm merely illustrating the cost of swaps.
1st and 2nd order little endian: 32-bit or 64-bit limbs, containing
8-bit big-endian limbs ends up as a memcpy on little-endian.

You can then argue either way for little-endian or big-endian based on
this logic, however even small additional costs are redundant for
optimal performance, if one wants to optimize for platforms (as
typically ends up being done). serialization/deserialization is probably
low on the profile as I hint. it still is neither a good case for either
change or tradition. eliminated cost over a large scale of current CPUs
is eliminated cost. it all adds up.

> security levels and signatures by the summer.

Yes. It's not a good argument for non-support. The code is not
difficult. It's all of the established test cases, and if they are
already established within the domain of this curve in its format then
it is clearly harder to change it to another format.

GCM was the other case where the primitive has its own encoding.

The issue really is the inertia from a). how Curve25519 represents and
b). how current implementations have a tradition of representing.

given Curve25519 is new, a *prudent* risk mitigation strategy is to
avoid change, and accept its representation. it is not making any
changes to any existing representation so introduces no risk of
regression when added to * implementations. this is always my stance on
change management when looking at additive changes.

---

From: "D. J. Bernstein" <[email-masked]>
Date: 28 Jan 2015 02:29:32 -0000

Peter Gutmann writes:
> Looking at BN_bn2bin()/BN_bin2bn() from one
> it only supports the big-endian format.

To evaluate this "support" claim, let's try writing actual code using
BN_bn2bin() to print a 256-bit x-coordinate as a 32-byte binary string:

   BIGNUM *x = 0;
   char xstr[32];
   ...
   BN_bn2bin(x,xstr);
   fwrite(xstr,1,32,stdout);

Let's assume that the (omitted) code computing x guarantees that x is
between 0 and 2^256-1 so that there isn't a buffer overflow here; assume
that the fwrite() doesn't fail; etc.

This code will pass typical test vectors. However, if you do thousands
of random tests under valgrind etc., then you'll see that this code is
simply wrong: integers x below 2^248 fail to write anything to the last
byte of xstr. The number of bytes touched by BN_bn2bin() is the minimum
number of bytes _needed_ for x, whereas what we want is exactly 32 bytes.

Second try. Let's clear xstr before calling BN_bn2bin():

   BIGNUM *x = 0;
   char xstr[32];
   ...
   memset(xstr,0,32);
   BN_bn2bin(x,xstr);
   fwrite(xstr,1,32,stdout);

This now passes memory tests---but it's still wrong, as sufficiently
comprehensive correctness tests will show. The problem is again with
the occasional integers x below 2^248: there's a difference between

   * the variable-size "big-endian" BN_bn2bin() format, aligning the
     first byte of output with the most significant byte used in x; and

   * the intended constant-size "big-endian" format, aligning 32 bytes
     of output with 32 bytes in x, no matter which bytes of x are 0.

Notice that this discrepancy is very much tied to the use of big-endian:
if the BN functions and target format had been little-endian then this
code _would_ have worked.

If you're thinking "Wait a minute, isn't there a symmetry between
little-endian and big-endian?": Yes, there is, but this is tied to the
symmetry between the convention of pointing to arrays via their _first_
element and the convention of pointing to arrays via their _last_
element. In the real world, machine languages and assembly languages and
C and so on have all converged upon the first convention by default, and
trying to fight this is silly.

Third try, now that we understand how severe the mismatch is between the
OpenSSL API and the target. Let's call an auxiliary OpenSSL function so
that we can figure out where we're supposed to put the first byte of x:

   BIGNUM *x = 0;
   char xstr[32];
   ...
   memset(xstr,0,32);
   BN_bn2bin(x,xstr + 32 - BN_num_bytes(x));
   fwrite(xstr,1,32,stdout);

This always works (I think---I'm not an OpenSSL expert), and it seems to
be what Peter is alluding to when he tells us that OpenSSL "supports the
big-endian format". For comparison, here's code that uses exactly the
same OpenSSL functions but reverses the order of output bytes:

   BIGNUM *x = 0;
   char xstr[32];
   int i;
   ...
   memset(xstr,0,32);
   BN_bn2bin(x,xstr + 32 - BN_num_bytes(x));
   for (i = 31;i >= 0;--i) putchar(xstr[i]);

For some reason Peter doesn't call this "support" for little-endian. I
suppose he could argue that this code is marginally more complex than
the previous code; but calling this a lack of "support"---and claiming
that it's a serious argument for choosing one format over another---is
quite a severe exaggeration of a tiny code change.

The difference between little-endian and big-endian is much more
noticeable for people doing serious size optimization of crypto code
(e.g., complete crypto libraries in <20KB of compiled code). These
people would never tolerate the ludicrously bloated code shown above:
it's crazy to use three functions to create a 32-byte copy of something
that should already be sitting in memory in the first place. These
people are happiest when the CPU, via the ABI, has easy instructions to
handle the I/O format---and at the CPU+ABI levels it's clear that the
religious war is over:

   * The big-endian CPUs have been killed by the little-endian CPUs and
     the agnostic CPUs.

   * For agnostic CPUs the big-endian ABIs are rapidly being replaced by
     little-endian ABIs.
     
I'm not saying that the resulting code-size benefit is very large; I'm
just saying that it outweighs the miniscule benefits of what some people
here are calling "tradition".

---Dan