Subject: [CFRG] compact representation and HPKE

From: Dan Harkins <[email-masked]>
Date: Fri, 06 Nov 2020 10:19:46 -0800

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

---

From: John Mattsson <[email-masked]>
Date: Fri, 6 Nov 2020 21:51:35 +0000

+1

Sending the keys uncompressed makes HPKE unsuitable for constrained IoT.

-----Original Message-----
From: CFRG <[email-masked]> on behalf of Dan Harkins <[email-masked]>
Date: Friday, 6 November 2020 at 21:00
To: CFRG <[email-masked]>
Subject: [CFRG] compact representation and HPKE

   Hello,

   regards,

   Dan.

_______________________________________________
CFRG mailing list
[email-masked]
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

---

From: Richard Barnes <[email-masked]>
Date: Fri, 6 Nov 2020 17:19:23 -0500

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=
[email-masked]> wrote:

> https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Mike Hamburg <[email-masked]>
Date: Fri, 6 Nov 2020 23:19:23 +0000

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 <[email-masked]> 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=[email-masked] <mailto:[email-masked]>> wrote:
> +1
> 
> From: CFRG <[email-masked] <mailto:[email-masked]>> on behalf of Dan Harkins <[email-masked] <mailto:[email-masked]>>
> To: CFRG <[email-masked] <mailto:[email-masked]>>
> [email-masked] <mailto:[email-masked]>
> 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 <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>
> 
> [email-masked] <mailto:[email-masked]>
> https://www.irtf.org/mailman/listinfo/cfrg <https://www.irtf.org/mailman/listinfo/cfrg>

---

From: Dan Harkins <[email-masked]>
Date: Fri, 06 Nov 2020 16:44:29 -0800

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 <[email-masked] 
>> <mailto:[email-masked]>> 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=[email-masked] 
>> <mailto:[email-masked]>> wrote:
>>
>>     +1
>>
>>     From: CFRG <[email-masked] <mailto:[email-masked]>>
>>     on behalf of Dan Harkins <[email-masked]
>>     <mailto:[email-masked]>>