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

[Michael Clark <[e-mail]>]

On 26/1/15 6:20 pm, Peter Gutmann wrote:
> Mike Hamburg <[e-mail]> 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.

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...