Re: [CFRG] compact representation and HPKE

Mike Hamburg <mike@shiftleft.org> Fri, 06 November 2020 23:19 UTC

Return-Path: <mike@shiftleft.org>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 2813E3A0C50 for <cfrg@ietfa.amsl.com>; Fri, 6 Nov 2020 15:19:30 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.305
X-Spam-Level:
X-Spam-Status: No, score=-1.305 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, HTML_MESSAGE=0.001, RDNS_NONE=0.793, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=no autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=shiftleft.org
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id XbWJSEVZexkn for <cfrg@ietfa.amsl.com>; Fri, 6 Nov 2020 15:19:28 -0800 (PST)
Received: from astral.shiftleft.org (unknown [54.219.126.124]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 53B513A0E2E for <cfrg@irtf.org>; Fri, 6 Nov 2020 15:19:27 -0800 (PST)
Received: from [192.168.1.4] (51-171-112-90-dynamic.agg2.kny.prp-wtd.eircom.net [51.171.112.90]) (Authenticated sender: mike) by astral.shiftleft.org (Postfix) with ESMTPSA id D9457BD19B; Fri, 6 Nov 2020 23:19:25 +0000 (UTC)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=shiftleft.org; s=sldo; t=1604704766; bh=wMCOktzAKE9UPonzebsUOFFZ27bN5frEX6JwytBV8D0=; h=From:Subject:Date:In-Reply-To:Cc:To:References:From; b=A7LoRRpxD/qX8cmSmXm5HVWJ0h2YWcGw9Q6+IZKG+SD+vGgpPnxe/ri/G/SN0VFqm P0qTwfgYQn7oMQtnst3O8WSKpFA5jpgYzSXn/WoiAd7QHmVkhePJkyu6ZY52UULR9b n7t0pvJFsY1lRahvEeBSscuVWfHGA7KbUUtgvFTU=
From: Mike Hamburg <mike@shiftleft.org>
Message-Id: <5C12F8B7-99E2-40DA-8A3C-8930E652C77F@shiftleft.org>
Content-Type: multipart/alternative; boundary="Apple-Mail=_87F803AD-1C62-4FAD-BC84-5FE454F236CC"
Mime-Version: 1.0 (Mac OS X Mail 13.4 \(3608.120.23.2.4\))
Date: Fri, 06 Nov 2020 23:19:23 +0000
In-Reply-To: <CAL02cgQFGcWjpFV1nFVg2T3aCat6U-uuzUQ_YsUYLHvQq+ZuiQ@mail.gmail.com>
Cc: John Mattsson <john.mattsson=40ericsson.com@dmarc.ietf.org>, CFRG <cfrg@irtf.org>
To: Richard Barnes <rlb@ipv.sx>
References: <0fcfb0ed-249b-7cd3-09ba-ed1c73122383@lounge.org> <4C4DE4EC-1A5B-48F5-871E-B7D323EF63D5@ericsson.com> <CAL02cgQFGcWjpFV1nFVg2T3aCat6U-uuzUQ_YsUYLHvQq+ZuiQ@mail.gmail.com>
X-Mailer: Apple Mail (2.3608.120.23.2.4)
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/wColvhcAGa1hMCD35HPgCZ9igD0>
Subject: Re: [CFRG] compact representation and HPKE
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Fri, 06 Nov 2020 23:19:30 -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 <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 <mailto: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 <mailto:cfrg-bounces@irtf.org>> on behalf of Dan Harkins <dharkins@lounge.org <mailto:dharkins@lounge.org>>
> Date: Friday, 6 November 2020 at 21:00
> To: CFRG <cfrg@irtf.org <mailto: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 <mailto: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 <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 <mailto:CFRG@irtf.org>
> https://www.irtf.org/mailman/listinfo/cfrg <https://www.irtf.org/mailman/listinfo/cfrg>
> _______________________________________________
> CFRG mailing list
> CFRG@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg