Re: [Cfrg] Point format endian

[Michael Clark <[e-mail]>]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 26/1/15 5:12 am, Alyssa Rowan wrote:
> On 24/01/2015 16:18, Salz, Rich wrote:
> 
>>> [DH] So a long-standing tradition of the on-the-wire format is 
>>> changed because of the way the first curve25519 library was 
>>> written? That's a weak justification.
> 
> So all the running code in every X25519 library out there (there
> are several) should change its on-the-wire format because of the
> way some other earlier wire protocols (with explicitly no relation
> to this one, as Rich mentions) were written? ¬_¬
> 
>> [RS] The IETF should follow its tradition and drop its wire
>> format tradition.
> 
> Agreed. To the extent it matters, there's no justification for 
> changing the X25519 wire format to big-endian at all; it'd just be 
> gratuitous incompatibility with existing libraries for no reason if
> we did. I might not put it quite as sarcastically as djb, but I am
> not a fan of that. Running code wins: and that's little-endian.

Can't we just define point formats with '_le' suffix?

software still needs to consider endianness as these libraries are
likely to be ported to big endian systems (< power8, < sparc9, etc),
but nowadays big endian should perhaps pay the bswap price (however
sadly the older systems are the slower ones). "network byte order"
loses some meaning. format names should then become endian explicit.

the bignum libraries would typically have limbs in host-endianness,
and it makes sense for scalar growth that they store vectors of limbs
little end first, but they could be either big or little endian host
words packed little word first in memory. it is host dependent.

(example 128)

32-bit limbs on a little-endian system (memory representation):

  (limb0_le32), (limb1_le32), (limb2_le32), (limb3_le32)
   0x80000000 ,  0x00000000 ,  0x00000000 ,  0x00000000

32-bit limbs on a big-endian system (memory representation):

  (limb0_be32), (limb1_be32), (limb2_be32), (limb3_le32)
   0x00000080 ,  0x00000000 ,  0x00000000 ,  0x00000000

the natural composition of little endian limbs and little limb first
(2nd order bignum endianness) on a little endian system ends up being
byte-level little endian big nums, so yes little endian representation
is more efficient on modern systems.

on the other hand, with fixed-size bignums (for timing resistance)
where you know the size in advance, it would be possible to use big
word/limb first but the memory access pattern might be non-optimal.
suspect most bignum code is designed with little word/limb first for
scalar growth (and fixed size is essentially a subset or variable size).

this however is besides the point. as people indicate, these are
internal implementation details, and an implementation can serialize
and deserialize numbers before and after any computation.

big-endian still exists however it makes a reasonable amount of sense
for a new wire-format to make the (now less common) big-endian systems
pay the bswap price and use little endian on the network.

the other thing to remember is there is also base 2 little endian; or
bit reflection, versus what we call little endian (byte-level little
endian). see {Bit Reflection Peculiarity of GCM}. However in the case
of GCM, this is opaque so is not an issue. Just want to point out
there is another endianness. In bit reflection (or base 2 le) the
above example would = 1 not 128.

the swizzle code is already there, just it doesn't have a conditional
on it. If there are _le point formats then all the bswaps will eval to
nothing on the systems that are the most common today.

X25519 will likely be ported to big-endian systems?

if it isn't "network byte order" then endianness should be explicit in
a point format name i.e. add "_le" suffix. rationale for old names :-D

as developers, we will still need the bswaps in there either way, even
in the little-endian case where they the macros will evaluable to
nothing, assuming the code gets ported to < power8, < sparc9, etc

a shrewd strategy is send the endianness of your platform and have le
point format. You pay no price for this strategy unless the other end
is big endian. So make little endian point formats.

endianness is a pain. We need a <stdenian.h> in ISO C17, and
<cstdenian> in C++17. WIP. This still needs to emit BSWAP asm on MSC.

  http://austingroupbugs.net/view.php?id=162
  https://gist.github.com/michaeljclark/3b4fd912f6fa8bb598b3

endianness will need to be dealt with for some time to come,
especially in network code where everything is still "network byte order"
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1

iEYEARECAAYFAlTGCscACgkQa/HXs1fvPk8vAwCgpKjRExM/R3MmPBTvH/CUJAH7
iCEAoIZQhNum36Wn/Bnglrl2CQCGzWOk
=bc3q
-----END PGP SIGNATURE-----