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

[Michael Clark <[e-mail]>]

On 27/1/15 2:00 pm, Watson Ladd wrote:
> On Mon, Jan 26, 2015 at 4:57 AM, Michael Clark <[e-mail]> wrote:
>> 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).
> 
> 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.
> 
>>
>> Given the algo is new, one could /consider/ a BN_bn2binle and
>> 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?

I hope this is not implied by my email.

>> 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?
> 
> And you have benchmarks showing that this code is the bottleneck, and
> 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.

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

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.

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

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.