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

"Blumenthal, Uri - 0553 - MITLL" <uri@ll.mit.edu> Tue, 13 July 2021 03:38 UTC

Return-Path: <prvs=6828c62e68=uri@ll.mit.edu>
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 817EE3A10E7 for <tls@ietfa.amsl.com>; Mon, 12 Jul 2021 20:38:57 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.895
X-Spam-Level:
X-Spam-Status: No, score=-1.895 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, MIME_QP_LONG_LINE=0.001, SPF_HELO_NONE=0.001, SPF_NONE=0.001, UNPARSEABLE_RELAY=0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
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 i6XBLtK_O8rB for <tls@ietfa.amsl.com>; Mon, 12 Jul 2021 20:38:53 -0700 (PDT)
Received: from llmx3.ll.mit.edu (LLMX3.LL.MIT.EDU [129.55.12.49]) (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 DADD13A10E5 for <tls@ietf.org>; Mon, 12 Jul 2021 20:38:52 -0700 (PDT)
Received: from LLE2K16-HYBRD01.mitll.ad.local (LLE2K16-HYBRD01.mitll.ad.local) by llmx3.ll.mit.edu (unknown) with ESMTPS id 16D3chFn020913; Mon, 12 Jul 2021 23:38:43 -0400
ARC-Seal: i=1; a=rsa-sha256; s=arcselector5401; d=microsoft.com; cv=none; b=sOWvwIA/tXffSkJwNe6WM9n3xmQ2dF+V+KDqABxMYkuPt/3o3NpyEw2x4hry6zNNfYkrwT/v2kq49QjQaOFxcgVBRWAChgH8va5aBQtfbByGgUVac6GpcqU8vbwjl+HMUDUsiOWe7ILpBsPO2l2o9AIgWzWU2uadIPbOZYMBfMXeU4JOlQTl5vUvLBIziB9HOaqp8b/acKHyetp9SS3FaevvOzWeRQjHBRFRV3X1ItByVMpR+jelHvC0AcejUloUbyRhbI1V1pGKwpauPCf0Jk8VMkc16nIKXii2ZpvtK9uaxk8L5ez0gcphVBwgae2oq5tb5UPZQ56OM1K+QUgWbA==
ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector5401; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=q+9qWEX/lNGIgbl1K3zMqmGywY8M+0N58Bq000Bz7tA=; b=IdUfRcd0zBT5DJSF1iPBkHn+0Pjzi6w7IaLd+SrAOOTzEZVqfaU6SoNHF77FakVEk8CL+mCqAWPVobEkHM9HDuy803HFQMn//7ISic3sAP7K+ic90z28tO7Mm6MiYKus0jXmgtC8DQxQfVa4UZ/4wh8/EyEXfSYdLEj5soPET/tOzFsDmZgsrtgaVWifYVOH23vSU5iqojsQY6kBHnnoYCWPOkDpgO/yQ+6AKrAEii+X0IIPhI+6kp+DbW47SHs1E9U82b6wSphzkyQiDwpbrUUq2xG00izmAIOLb9yHdELdMUvrAzD2sR3BklM7UG5mvxrD570SdC7dGlphDmInFQ==
ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=ll.mit.edu; dmarc=pass action=none header.from=ll.mit.edu; dkim=pass header.d=ll.mit.edu; arc=none
From: "Blumenthal, Uri - 0553 - MITLL" <uri@ll.mit.edu>
To: Douglas Stebila <dstebila@gmail.com>, Eric Rescorla <ekr@rtfm.com>
CC: "<tls@ietf.org>" <tls@ietf.org>
Thread-Topic: [TLS] Comments on draft-celi-wiggers-tls-authkem-00.txt
Thread-Index: AQHXd352QdrI+caj/k6SxbnpNPfZiatAFWOA///psQA=
Date: Tue, 13 Jul 2021 03:38:38 +0000
Message-ID: <48CCA06B-B226-4B64-ADC5-1E7841FEE9DA@ll.mit.edu>
References: <CABcZeBN4y40o7T3hx4RH3LogbMDEScxGY4SVuCWuQ67oW+XZ3w@mail.gmail.com> <DF9C8D2D-4B2A-414D-AD7A-0ED424CD98FE@gmail.com>
In-Reply-To: <DF9C8D2D-4B2A-414D-AD7A-0ED424CD98FE@gmail.com>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach: yes
X-MS-TNEF-Correlator:
user-agent: Microsoft-MacOutlook/16.50.21061301
authentication-results: gmail.com; dkim=none (message not signed) header.d=none;gmail.com; dmarc=none action=none header.from=ll.mit.edu;
x-originating-ip: [129.55.200.20]
x-ms-publictraffictype: Email
x-ms-office365-filtering-correlation-id: 1a89751d-303d-4acc-6e90-08d945afb3b1
x-ms-traffictypediagnostic: SN5P110MB0558:
x-microsoft-antispam-prvs: <SN5P110MB05589EB028199E9E56BC212E90149@SN5P110MB0558.NAMP110.PROD.OUTLOOK.COM>
x-ms-oob-tlc-oobclassifiers: OLM:10000;
x-ms-exchange-senderadcheck: 1
x-microsoft-antispam: BCL:0;
x-microsoft-antispam-message-info: 3HmKAUdv0q2LjUpBepnhm3qjWzDk2tXOOzisiaJUBcC6OjtlEu0UNNRtFFr4sRGKNzbyV7l2QI9xOfJRcUS8kHve8pAw4NKP2kyMf4XfyKwIEq23djGbWHJ/GKFL4NKeXqNWW45t6dPk8FM1HPsJevVfX3FUZJVjYRDo1ozsqhlXD9GJT+WRsuAIx6B0/X0IF7s7EzMT0cuwWA+7yDWz35l0Od9U+o7nR3HHJqCpzacu3JGMTo5ellAa3K+aWSJOgJoz0BUtJNlqfxehS1Hszf1FfVEHSQm2lhyFSaVOQhnF5cUFJiTLwBKbdR4MCvMB16zEvP2O9jcNfYl4+sdzv9JOs247PH6pNmFAO/FNM+8Gsb9m6qJUzYkiJILqyKkRhLU6PK6C1iCEz9SRmNtjBS305l7UONMs5yjqcfUBhzm0eatn1WlYAGRTQlRjC44SW7S+7EhnVvs3Tzs/VyxUWeBlftb6CvAFGe1uRSkPMZWeGgEp6bhBmMu4JlzCW3zvmULjDnwTTQhY9sQRncdg9bzRFvWs+fJvt9P8eFEQnSGju7lGdBa90cU0gMZl6b5wu7WGvJ0M9zVoVfsl8oS3DaCdJ0ydssxZ9an5AoTOEqib3YhpG1oKVn3tDofxSMnl
x-forefront-antispam-report: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:SN5P110MB0560.NAMP110.PROD.OUTLOOK.COM; PTR:; CAT:NONE; SFS:(4636009)(396003)(136003)(366004)(346002)(376002)(39850400004)(186003)(76116006)(4326008)(99936003)(6506007)(38100700002)(66556008)(71200400001)(6512007)(478600001)(966005)(66616009)(53546011)(26005)(6486002)(66946007)(66476007)(64756008)(66446008)(122000001)(75432002)(316002)(33656002)(2616005)(83380400001)(110136005)(86362001)(8676002)(8936002)(2906002)(5660300002)(45980500001); DIR:OUT; SFP:1102;
x-ms-exchange-antispam-messagedata: ji3pSaLQx3keKG2XyDqiKMFx0tT2xGEwNA7/2e9v2IatCYWirpD/+wViGVaC2/tnqdd5+Pz/05Lxxq0KOcmNem9vUDL7MTK61yd7d0n8F2/q6UwHD9FUhEbTVY4K4vRCro/qp8q4sS+3Ktiaw5/CtwqiA1l+CNp3yUsa1yEaTmCIf47Ti+iKldiP8d+/hdtNj/qYeZQ1Ce944a5e3bA/JHDMwyAlKj8yz0c2X1MFs8LfdWE8VFLAJMw/S6lx/eZtoZ16V7tImdW1jUjQQXGu56dtN4a1evDxzqoIJAg0I141XqgVVhgiS944wX9KaeUuAg4EPn4EC+xOVmIGQzEpwFZo1N1Kp7NqFUJfjrh4MGCmVmhOCJGIhqBmGb5piZxG6wXYPiEycw7AGfUaOHgs9GtMDL8642ODhDU1OyBu8dGLfvhHl85iK+jO6GkCoeAUiiqe8jxpFdeCgCwkYsi8pbm4V22UYjrSz3BdIyknIa3H9s+NPGBCga9bqxK3Yxo1kY3Sqk/2aNciV++7wLAj3RtyIrCgb231+2/rn2sc1T0n+PX8m/dUUTBjwXqjlGVlSKUmQvDtvknJglukueYNBhdHhGL1d9y/xqgPHLOt6RiPSy1BmmubufF92kAEBYBmc1x/zcAjJ0apzugVWvAtWOCfSGsaSYz9ofi0qIV5l3RwaYAEfw5tDFgSepLsq1/f/SnYblr5mPJlsIlzAdWyGA==
x-ms-exchange-transport-forked: True
Content-Type: multipart/signed; protocol="application/pkcs7-signature"; micalg=sha256; boundary="B_3708977917_1317144464"
MIME-Version: 1.0
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-AuthSource: SN5P110MB0560.NAMP110.PROD.OUTLOOK.COM
X-MS-Exchange-CrossTenant-Network-Message-Id: 1a89751d-303d-4acc-6e90-08d945afb3b1
X-MS-Exchange-CrossTenant-originalarrivaltime: 13 Jul 2021 03:38:38.5329 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 83d1efe3-698e-4819-911b-0a8fbe79d01c
X-MS-Exchange-Transport-CrossTenantHeadersStamped: SN5P110MB0558
X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:6.0.391, 18.0.790 definitions=2021-07-12_14:2021-07-12, 2021-07-12 signatures=0
X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 suspectscore=0 malwarescore=0 phishscore=0 bulkscore=0 spamscore=0 mlxscore=0 mlxlogscore=999 adultscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.0.1-2103310000 definitions=main-2107130020
Archived-At: <https://mailarchive.ietf.org/arch/msg/tls/DVtwyO3IjZCIQ5KyOYv4fj-zkBo>
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: Tue, 13 Jul 2021 03:38:58 -0000

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