Subject: Re: [Cfrg] Field Element Format

From: Paul Lambert <[email-masked]>
Date: Tue, 27 Jan 2015 12:43:00 -0800

I think that Dan Harkins had a good point about the need for clarity about
both the internal and external structure of an octet string representing a
field 
element.

Issue: Specifications MUST prescribe octet-string format for all
       applications of a field element (not just over-the-wire)

Suggested 
A specific recommendation would be to define not just the Œwire-format¹ of
field elements, but to be very specific that that both wire-format
and any other protocol usage of the field element as a octet string
must be in the prescribed encoding format.

Current text:
>Wire-format of field elements
>When transmitting field elements in the Diffie-Hellman protocol below,
>they
>MUST be encoded as an array of bytes, x, in Š

Suggested change:
< Octet-string format of field elements
<
< Field elements are converted to a string of octets for transmission in
< the Diffie-Hellman protocol below and for other cryptographic
< protocol uses and operations that are not performed on Gfp
< (e.g. Hash(field element). When converting a field element
< to an octet-string, the field element
< MUST be encoded as an array of bytes x, in Š

Note that the text above is independent of the endian, I left that out ...

Paul

PS - whoever is moderating this discussion, would you please add this to
your tracking list as an editorial comment to review and determine
if action or not is required.  Since we are supposedly Œreviewing¹
a document, tracking and clear resolution of topics
would be valuable. 

It would be of great value to publish the list so that
we could have a clear burn-down list to reach an end.

On 1/27/15, 11:56 AM, "Michael Clark" <[email-masked]> wrote:

>On 27/1/15 6:34 pm, Peter Gutmann wrote:
>> 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.
>
>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? :-)
>
>_______________________________________________
>Cfrg mailing list
>[email-masked]
>http://www.irtf.org/mailman/listinfo/cfrg