Re: [TLS] Comments on draft-celi-wiggers-tls-authkem-00.txt

"Kampanakis, Panos" <kpanos@amazon.com> Thu, 22 July 2021 04:46 UTC

Return-Path: <prvs=8302bfa12=kpanos@amazon.com>
X-Original-To: tls@ietfa.amsl.com
Delivered-To: tls@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id ABE173A37B3 for <tls@ietfa.amsl.com>; Wed, 21 Jul 2021 21:46:27 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -10.049
X-Spam-Level:
X-Spam-Status: No, score=-10.049 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIMWL_WL_HIGH=-0.452, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_MSPIKE_H4=0.001, RCVD_IN_MSPIKE_WL=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001, USER_IN_DEF_SPF_WL=-7.5] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=amazon.com
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 2w0iFHqwbZY7 for <tls@ietfa.amsl.com>; Wed, 21 Jul 2021 21:46:22 -0700 (PDT)
Received: from smtp-fw-33001.amazon.com (smtp-fw-33001.amazon.com [207.171.190.10]) (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 2E4433A37AF for <tls@ietf.org>; Wed, 21 Jul 2021 21:46:16 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=amazon.com; i=@amazon.com; q=dns/txt; s=amazon201209; t=1626929182; x=1658465182; h=from:to:cc:subject:date:message-id: content-transfer-encoding:mime-version; bh=YRZZlpYdPdNF0WKCgYsIDNWohMunC41jXQbJ3AGTQAA=; b=X6QKCtQqYzhfMLHMuTl0k2LPUmfUEb9DQxMhpQkK2xHUTGM/KvzIUP8i gJbIRI9WDxZTzDvMrxgYFs8Zk4WHAP1gWLbfFc+M3uPUotEfQe5zjRmw8 VWRarsUisNAwncbqKBb0Kquv5Ab4IaOoO+PFXhhXovQ691nIIltN1Wdnt Y=;
X-IronPort-AV: E=Sophos;i="5.84,260,1620691200"; d="scan'208";a="137535322"
Received: from iad12-co-svc-p1-lb1-vlan2.amazon.com (HELO email-inbound-relay-1d-e69428c4.us-east-1.amazon.com) ([10.43.8.2]) by smtp-border-fw-33001.sea14.amazon.com with ESMTP; 22 Jul 2021 04:46:08 +0000
Received: from EX13MTAUWB001.ant.amazon.com (iad55-ws-svc-p15-lb9-vlan3.iad.amazon.com [10.40.159.166]) by email-inbound-relay-1d-e69428c4.us-east-1.amazon.com (Postfix) with ESMTPS id 2504DC0486; Thu, 22 Jul 2021 04:46:06 +0000 (UTC)
Received: from EX13D01ANC004.ant.amazon.com (10.43.157.237) by EX13MTAUWB001.ant.amazon.com (10.43.161.207) with Microsoft SMTP Server (TLS) id 15.0.1497.23; Thu, 22 Jul 2021 04:46:06 +0000
Received: from EX13D01ANC003.ant.amazon.com (10.43.157.68) by EX13D01ANC004.ant.amazon.com (10.43.157.237) with Microsoft SMTP Server (TLS) id 15.0.1497.23; Thu, 22 Jul 2021 04:46:05 +0000
Received: from EX13D01ANC003.ant.amazon.com ([10.43.157.68]) by EX13D01ANC003.ant.amazon.com ([10.43.157.68]) with mapi id 15.00.1497.023; Thu, 22 Jul 2021 04:46:05 +0000
From: "Kampanakis, Panos" <kpanos@amazon.com>
To: "Blumenthal, Uri - 0553 - MITLL" <uri@ll.mit.edu>
CC: "<tls@ietf.org>" <tls@ietf.org>, Douglas Stebila <dstebila@gmail.com>, Eric Rescorla <ekr@rtfm.com>
Thread-Topic: [TLS] Comments on draft-celi-wiggers-tls-authkem-00.txt
Thread-Index: Add+tHdLT0JcZqpyTOWwQ+3dwbToQg==
Date: Thu, 22 Jul 2021 04:46:04 +0000
Message-ID: <8674700eb241430cb5d09d46ba331e1b@EX13D01ANC003.ant.amazon.com>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
x-ms-exchange-transport-fromentityheader: Hosted
x-originating-ip: [10.43.157.38]
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: base64
MIME-Version: 1.0
Archived-At: <https://mailarchive.ietf.org/arch/msg/tls/Zem2pc9bUNCs114elkpxrOM1_Y0>
Subject: Re: [TLS] Comments on draft-celi-wiggers-tls-authkem-00.txt
X-BeenThere: tls@ietf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: "This is the mailing list for the Transport Layer Security working group of the IETF." <tls.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/tls>, <mailto:tls-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/tls/>
List-Post: <mailto:tls@ietf.org>
List-Help: <mailto:tls-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/tls>, <mailto:tls-request@ietf.org?subject=subscribe>
X-List-Received-Date: Thu, 22 Jul 2021 04:46:28 -0000

Hi Uri,

Thank you for the clarifications. 

So you have a usecase that 
- want to use PQ algorithms
- is significantly affected by an extra 1-2 or 4-5KB on the link
- does not send a cert chain, only leaf certs
- can cache or fetch the peer public keys in order to do KEMTLS

Although I don't consider it the general usecase, maybe KEMTLS is the way to go there. 

Other good options imo for it would be draft-ietf-tls-ctls and rfc7924 to save even more on data put on the link.



-----Original Message-----
From: Blumenthal, Uri - 0553 - MITLL <uri@ll.mit.edu> 
Sent: Tuesday, July 13, 2021 1:17 AM
To: Kampanakis, Panos <kpanos@amazon.com>
Cc: <tls@ietf.org> <tls@ietf.org>rg>; Douglas Stebila <dstebila@gmail.com>om>; Eric Rescorla <ekr@rtfm.com>
Subject: RE: [EXTERNAL] [TLS] Comments on draft-celi-wiggers-tls-authkem-00.txt

> If we are talking NIST Level 5 (and I am assuming you are
> discussing mTLS), 

Yes. ;-)

> ...have you calculated the total CertVerify+cert chain sizes
> there assuming 2 ICAs let's say? 

More or less. ;-)

My use case has all the ICAs pre-loaded - the transmitted chain contains only one entity cert. I'm sacrificing flexibility for performance under constraints. Size is the real enemy here.


> And would constrained devices or mediums that sweat about 5KB
> really be able to support PQ KEMs and Sigs at NIST Level 5?

My tests showed that they *do* support PQ KEMs (NTRU and Kyber - haven't tried McEliece ;) and Sigs (Falcon and Dilithium - haven't tried Rainbow ;) at Level 5. Caveat - they do only Sig *verification* (which suits me fine).

(I posted benchmarks from Intel Core i9, but they work acceptably well on the "smaller" chips.)

Also, sorry if I did not make it clear - it's not the *devices* themselves that sweat 5KB, it's their austere links.



    -----Original Message-----
    From: TLS <tls-bounces@ietf.org> On Behalf Of Blumenthal, Uri - 0553 - MITLL
    Sent: Monday, July 12, 2021 11:39 PM
    To: Douglas Stebila <dstebila@gmail.com>om>; Eric Rescorla <ekr@rtfm.com>
    Cc: <tls@ietf.org> <tls@ietf.org>
    Subject: RE: [EXTERNAL] [TLS] Comments on draft-celi-wiggers-tls-authkem-00.txt

    CAUTION: This email originated from outside of the organization. Do not click links or open attachments unless you can confirm the sender and know the content is safe.



    Let me emphasize the reasons Douglas brought up. Note that I need to use NIST Sec Level 5 algorithms. So, Kyber-1024 and Dilithium5 (other algorithms show even worse ratio between KEM and signature!).

    Communications costs:
    - Difference in public key sizes: 1568 bytes of Kyber vs. 2592 bytes of Dilithium => 1024 extra bytes to carry over channel each way;
    - Signature: extra 4595 bytes each way, because in addition to exchanging certs (aka "signed public keys", which is inevitable) you need to sign the exchange and communicate that signature across;
    - Total: 5619 extra bytes each way. For peer-to-peer broadband connections, you can say "so what?". But my links are *very* austere.

    Computation costs (ballpark, on a powerful CPU):
    - KEM: keygen 15us, encap 18us, decap 14us (say, double encap and decap for PFS-providing exchange);
    - Signature: sign 113us, verify 55us;
    - Comparison: 134us for signature-less KEM vs. 215us for TLS-like exchange => almost twice as long;
    - Difference may be negligible for Intel Xeon, but for my much weaker hardware it matters.

    So, for constrained environments with austere comm links, signature-less "authkem" is God-sent.
    Big servers that need to support many clients (so they care how much CPU cycles and comm bytes they spend on every connection) would appreciate these savings too.

    @ekr,I hope this provides convincing explanation why "authkem" is needed.

    P.S. I know that Falcon has much more favorable sizes - but (a) it takes three times as long to sign, and (b) it uses FP calculations, which isn't great to implement in my environment.
    --
    Regards,
    Uri

    There are two ways to design a system. One is to make is so simple there are obviously no deficiencies.
    The other is to make it so complex there are no obvious deficiencies.
                                                                                                                                         -  C. A. R. Hoare


    On 7/12/21, 20:59, "TLS on behalf of Douglas Stebila" <tls-bounces@ietf.org on behalf of dstebila@gmail.com> wrote:

        Hi Eric,

        The main motivation is that, in some cases, post-quantum signatures are larger in terms of communication size compared to a post-quantum KEM, under the same cryptographic assumption.

        For example, the KEM Kyber (based on module LWE) at the 128-bit security level has 800-byte public keys and 768-byte ciphertexts.  The matching signature scheme Dilithium (also based on module LWE) has 1312-byte public keys and 2420-byte signatures.  Doing KEM-based server authentication rather than signature-based server authentication would thus save 2164 bytes per handshake.

        We would still need digital signatures for a PKI (i.e., the root and intermediate CAs would sign certificates using PQ digital signature schemes), but the public key of the endpoint server can be a KEM public key, not a digital signature public key.

        Douglas


        > On Jul 12, 2021, at 20:30, Eric Rescorla <ekr@rtfm.com> wrote:
        >
        > Hi folks,
        >
        > I have just given draft-celi-wiggers-tls-authkem-00.txt a quick
        > read. I'm struggling a bit with the rationale, which I take to be
        > these paragraphs:
        >
        >    In this proposal we use the DH-based KEMs from [I-D.irtf-cfrg-hpke].
        >    We believe KEMs are especially worth discussing in the context of the
        >    TLS protocol because NIST is in the process of standardizing post-
        >    quantum KEM algorithms to replace "classic" key exchange (based on
        >    elliptic curve or finite-field Diffie-Hellman [NISTPQC]).
        >
        >    This proposal draws inspiration from [I-D.ietf-tls-semistatic-dh],
        >    which is in turn based on the OPTLS proposal for TLS 1.3 [KW16].
        >    However, these proposals require a non-interactive key exchange: they
        >    combine the client's public key with the server's long-term key.
        >    This imposes a requirement that the ephemeral and static keys use the
        >    same algorithm, which this proposal does not require.  Additionally,
        >    there are no post-quantum proposals for a non-interactive key
        >    exchange currently considered for standardization, while several KEMs
        >    are on the way.
        >
        > I see why this motivates using a KEM for key establishment, but I'm
        > not sure it motivates this design, which seems like a fairly radical
        > change to TLS. As I understand the situation, in the post-quantum
        > world we're going to have:
        >
        > - non-interactive KEMs (as you indicate above)
        > - some sort of signature system (otherwise we won't have certificates).
        >
        > This certainly argues that we need a KEM for key establishment, but
        > not for authentication. Instead, why can't we use signatures for
        > authentication, as TLS does today? I.e., the certificates would have a
        > (potentially post-quantum) signing key in them and you then use the
        > KEM for key establishment and the signing key for authentication.
        > That would give us a design much closer to the present TLS 1.3
        > (effectively just defining a new group for the KEM).
        >
        > What am I missing?
        >
        > -Ekr
        >
        >
        > _______________________________________________
        > TLS mailing list
        > TLS@ietf.org
        > https://www.ietf.org/mailman/listinfo/tls

        _______________________________________________
        TLS mailing list
        TLS@ietf.org
        https://www.ietf.org/mailman/listinfo/tls