Re: [CFRG] compact representation and HPKE

Well, there is a minor downside - the recipient has to do some extra work
(a modular square root) to reconstitute the y coordinate.

For an enfeebled recipient this might be quite onerous.

Mike

On Mon, Feb 8, 2021 at 10:42 PM Dan Harkins <dharkins@lounge.org> wrote:

>
>   Hello again,
>
>   I'd like to resurrect this before it becomes "it's too late to make
> changes
> that affect the wire". I created a pull request on github some time ago but
> it's been ignored so let me try again here (we still technically do our
> work
> on mailing lists).
>
>   When I brought it up initially there was a +1 and, as Mike notes, the
> y-coordinate is not needed. This 04 || x || y format for a key is just some
> ancient Certicom proposal and there's really no reason to perpetuate that.
>
>   The y-coordinate is extraneous. Getting rid of it for the NIST curves
> will
> make the API much cleaner and consistent.
>
>   This will reduce the size of the serialized public key by more than 50%
> and for apps that care about such things this would be a tremendous
> improvement.
>
>   Richard noted that one can lop off the 04 and the y-coordinate after
> serialization and pass x alone as part of the app using HPKE and then have
> the other size reconstruct it (with either y since the sign doesn't
> matter) before passing it on to be deserialized. While technically true,
> that completely defeats the whole point of formalizing this process.
>
>   In my pull request I noted that it does change the test vectors and that
> I would be happy to generate them. Well, I did it. I have new test vectors
> (based on -07) and will happily contribute them if asked. If the test
> vectors
> get changed again (with a new version string) I can reproduce new ones
> minus
> the y-coordinate in a matter of minutes.
>
>   Please consider this request. There is no downside to it.
>
>   regards,
>
>   Dan.
>
> On 11/6/20 4:44 PM, Dan Harkins wrote:
>
>
>   Yes, this is exactly right. The y-coordinate is not needed for these KEMs
> as the sign is unimportant.
>
>   The spec will be simpler and the interface more uniform if you do this.
>
>   The whole point of HPKE is to make a callable API out of this process
> that
> had been done ad hoc. Requiring a app that is taking advantage of this API
> to take the output of the API and parse through it, throwing away one half
> of one of the output strings and lopping off the first octet, is defeating
> the whole purpose and is expecting a lot. The more this is a black box the
> better.
>
>   regards,
>
>   Dan.
>
> On 11/6/20 3:19 PM, Mike Hamburg wrote:
>
> Hello Richard,
>
> I haven’t paid much attention to HPKE, so it’s likely I’m missing
> something here, but why not use the x-only Montgomery ladder on NIST
> curves?  That’s the fastest and simplest approach, and it can operate with
> or without the y-coordinates.
>
> Also, some implementations do not compute both the x- and y-coordinates,
> and it would be more convenient not to compute or send even a sign bit if
> you’re intending to use an x-only ladder.
>
> Cheers,
> — Mike
>
> On Nov 6, 2020, at 10:19 PM, Richard Barnes <rlb@ipv.sx> wrote:
>
> Nothing about this says that you have to *send* the keys uncompressed.
> You can use whatever representation you want on the wire.  You just have to
> decompress them before you put them into the key schedule. Which you're
> probably doing anyway, because you need both coordinates to do point
> multiplication with these curves.  So I am inclined not to make this change.
>
> --Richard
>
> On Fri, Nov 6, 2020 at 4:52 PM John Mattsson <john.mattsson=
> 40ericsson.com@dmarc.ietf.org> wrote:
>
>> +1
>>
>> Sending the keys uncompressed makes HPKE unsuitable for constrained IoT.
>>
>> -----Original Message-----
>> From: CFRG <cfrg-bounces@irtf.org> on behalf of Dan Harkins <
>> dharkins@lounge.org>
>> Date: Friday, 6 November 2020 at 21:00
>> To: CFRG <cfrg@irtf.org>
>> Subject: [CFRG] compact representation and HPKE
>>
>>    Hello,
>>
>>    When doing a DH-based KEM with the NIST curves, HPKE specifies that
>> SerializePublicKey and DeserializePublicKey use the uncompressed format
>> from SECG. This ends up using 2*Ndh+1 octets to represent the serial
>> form of the public key.
>>
>>    Since compact output is being used in DH-based KEMs-- that is, the
>> secret result of DH() is the x-coordinate of the resulting EC point--
>> it would also be possible to use compact representation (per RFC 6090)
>> and have SerializePublicKey merely do integer-to-octet string
>> conversions of the x-coordinate. DeserializePublicKey would then
>> do octet string-to-integer conversion for the x-coordinate and use the
>> equation of the curve to choose the y-coordinate. The sign isn't
>> important because we're doing compact output.
>>
>>    This would make the interface for the NIST curves and the Bernstein
>> curves be uniform-- Serialize would produce an octet string of Ndh
>> and Deserialize would consume an octet string of Ndh-- at the cost
>> of some CPU inside DeserializePublicKey.
>>
>>    Please consider this suggestion.
>>
>>    regards,
>>
>>    Dan.
>>
>> --
>> "The object of life is not to be on the side of the majority, but to
>> escape finding oneself in the ranks of the insane." -- Marcus Aurelius
>>
>> _______________________________________________
>> CFRG mailing list
>> CFRG@irtf.org
>>
>> https://protect2.fireeye.com/v1/url?k=513cd874-0ea7e231-513c98ef-867b36d1634c-ce26b08a2499b9a3&q=1&e=4f2b4ce0-8d52-4a80-b41e-0f7537355d35&u=https%3A%2F%2Fwww.irtf.org%2Fmailman%2Flistinfo%2Fcfrg
>>
>> _______________________________________________
>> CFRG mailing list
>> CFRG@irtf.org
>> https://www.irtf.org/mailman/listinfo/cfrg
>>
> _______________________________________________
> CFRG mailing list
> CFRG@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg
>
>
>
> _______________________________________________
> CFRG mailing listCFRG@irtf.orghttps://www.irtf.org/mailman/listinfo/cfrg
>
>
> --
> "The object of life is not to be on the side of the majority, but to
> escape finding oneself in the ranks of the insane." -- Marcus Aurelius
>
>
> _______________________________________________
> CFRG mailing listCFRG@irtf.orghttps://www.irtf.org/mailman/listinfo/cfrg
>
>
> --
> "The object of life is not to be on the side of the majority, but to
> escape finding oneself in the ranks of the insane." -- Marcus Aurelius
>
> _______________________________________________
> CFRG mailing list
> CFRG@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg
>