Re: [lamps] Which PQC KEMs can be used for composite encryption?
"Markku-Juhani O. Saarinen" <mjos@pqshield.com> Thu, 16 September 2021 10:49 UTC
Return-Path: <mjos@pqshield.com>
X-Original-To: spasm@ietfa.amsl.com
Delivered-To: spasm@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id B44863A23B1 for <spasm@ietfa.amsl.com>; Thu, 16 Sep 2021 03:49:03 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.898
X-Spam-Level:
X-Spam-Status: No, score=-1.898 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, HTML_MESSAGE=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=pqshield-com.20210112.gappssmtp.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 RavprqHe7d9i for <spasm@ietfa.amsl.com>; Thu, 16 Sep 2021 03:48:58 -0700 (PDT)
Received: from mail-vs1-xe2a.google.com (mail-vs1-xe2a.google.com [IPv6:2607:f8b0:4864:20::e2a]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id E0EDF3A2436 for <spasm@ietf.org>; Thu, 16 Sep 2021 03:48:57 -0700 (PDT)
Received: by mail-vs1-xe2a.google.com with SMTP id p24so5741993vsg.0 for <spasm@ietf.org>; Thu, 16 Sep 2021 03:48:57 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pqshield-com.20210112.gappssmtp.com; s=20210112; h=mime-version:from:date:message-id:subject:to; bh=/xQ+fMdPI3UEPbejsRFHmlpXRTS/Oz3vGH/CeucWLfk=; b=vuX0L4bT3jAibniALhM1XpZwa3d+aBK1jcu8QeVIpZboNY9V3FewXO23flZ1PcCXSV 8hze+fcWjcu0wKp9x9DdZ6zzgJB3xlVvdwkQJ6C0t5mZRiiLTVHzyqor6Z0PSvGbOysr YXlXdCKgh0gQxSk58PPegELne07DsdTBk8Y/E2A2kXFnNlMb37Xg6x7YDdpOZAFOyL41 47SMA90aVa3YmFk7PvLSS9Up4lcR5wqoreUXkPBTcs5nWzE+QDyQTCfPpmXio/VHUwTb rCzSqY1tPvC/vKSRKklAHByKyuySpe9AJKkgmpPWIm708IOYrXQj+Ai7tfbFZbhhZu9w lpIw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:from:date:message-id:subject:to; bh=/xQ+fMdPI3UEPbejsRFHmlpXRTS/Oz3vGH/CeucWLfk=; b=Y4x820k+UcRpJ5D/MNRGdhTrPjeXDl/hoLlHoe2c4xJuvrbrohd06HcX3x0tn2WXcP ZYas0ylkJb86mH1JKC2Ml0WRI6Q3+bspBNAwNJaEYC9SMohaV0HDIhM2GFspWpue7hLq hTybeSKiVzrxg3hWs2ss7zcGE8K3Mb1YyBC58/KazFlT11l+IFjjJLvkssDKb9YfXW8G xUDxXHMzV7GFSxvZatsy+VGOC8rTCMmp7WjLWx0fypabnZx+AFdXA/mDQVIDmxtt/7CB iyhqQlBdiSAqBKw4SSOlemQHv/0F2Vb2ycBYlX6XdmDgPxpyBnHRtHdwdtAQGLZ02COe LiSg==
X-Gm-Message-State: AOAM530vyA9uwE7queUsb8zfnGcHkKFIKjRyRKem6i8PQPuT+aL2A1ky P+wBpSea9VVB4spjIMEOHT+vvNwqe9rFbN0EzG6oDE6a3dysPg==
X-Google-Smtp-Source: ABdhPJzyociRuiN1leO2ODVFJBm1WqQyeFrsFMPvPaLcE5i2i/1hWZb1B+g/L8Df7tlNU9gzF3TErUHwwjB5qQEfDlM=
X-Received: by 2002:a05:6102:3112:: with SMTP id e18mr3150328vsh.50.1631789335820; Thu, 16 Sep 2021 03:48:55 -0700 (PDT)
MIME-Version: 1.0
From: "Markku-Juhani O. Saarinen" <mjos@pqshield.com>
Date: Thu, 16 Sep 2021 11:48:45 +0100
Message-ID: <CAPwdP4PatZiJPUR+7y6S-U1ERJN-zATSwPA2KUcce5MX6Bn2Vg@mail.gmail.com>
To: Leonie.Bruckert@secunet.com, "spasm@ietf.org" <spasm@ietf.org>, Mike Ounsworth <Mike.Ounsworth@entrust.com>
Content-Type: multipart/alternative; boundary="000000000000b5d35b05cc1a8fa0"
Archived-At: <https://mailarchive.ietf.org/arch/msg/spasm/TKgMILk_2fA0-Dl5mZ9szDkUQ_U>
Subject: Re: [lamps] Which PQC KEMs can be used for composite encryption?
X-BeenThere: spasm@ietf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: "This is a venue for discussion of doing Some Pkix And SMime \(spasm\) work." <spasm.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/spasm>, <mailto:spasm-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/spasm/>
List-Post: <mailto:spasm@ietf.org>
List-Help: <mailto:spasm-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/spasm>, <mailto:spasm-request@ietf.org?subject=subscribe>
X-List-Received-Date: Thu, 16 Sep 2021 10:49:04 -0000
From: Mike Ounsworth <Mike.Ounsworth@entrust.com> > I think (but could be wrong) that CCA security is orthogonal to whether > the KEM output (ie shared secret) can be used directly as a symmetric key, > or if it needs to be run through a KDF first. For example, I could imagine > a KEM that outputs an IND-CCA shared secret prefixed with a fixed version > byte; you can't use that directly as a one-time-pad key because of the > fixed version byte. > Hi Mike and Others, Yes .. fortunately contemporary (PQC) KEMs do not output such version bytes; all output bits are significant "full entropy". This is due to the Fujisaki-Okamoto transform generally used for CCA security and the related QROM proofs. With "RSA KEMs" things were perhaps a bit different. If you look at the implementations, the shared secret output is usually directly from SHA3/SHAKE via the FO transform select logic. This mechanism is very carefully designed by cryptographers. And as Uri noted, it is a "part of the algorithm" and KAT test vectors, etc. On the implementation front, much attention has been paid specifically to shared secret output due to "decryption failure oracles". Implementations of a couple of NIST PQC round 3 finalists were broken this way. It is okay for encapsulation to fail in case of an invalid public key, but decapsulation "never fails" explicitly, even in case of obviously invalid ciphertext; a synthetic ("implicit failure") shared secret is generated instead. So decapsulation actually produces a "uniform" output even in the case of nonsense ciphertext. If the shared secret is used with something like AEAD (for purposes of public-key message encryption/decryption), the decryption failure occurs only during MAC verification. Having an additional hash or KDF there is possible, but it needs to be constant time. Hardware implementations use the SHAKE/SHA3 output to their advantage, as a masked Keccak module can output the shared secret in masked shares, which is precisely what one needs for side-channel secure on-chip management of SSPs. In software, there's a generic attack on decryption failure oracles (in shared secret generation). For timing oracles: https://eprint.iacr.org/2020/743 The algorithm design teams made a bad fix that timing attack.. that allowed key recovery even without the timing oracle on Round 3 FrodoKem and SIKE reference implementations. https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/kSUKzDNc5ME/m/EMFYz9RNCAAJ https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/QvhRo7T2OL8/m/4gSe5coAAwAJ Note that both implementations still passed "normal KATs" that do not have decryption failures. So I urge people to avoid messing with the internals of KEMs such as shared secret generation, ciphertext serialization, or key serialization. I can almost promise you that an innocent-looking functional "optimization" will lead to security problems unless you're familiar with the security proofs.. (.. Mike's Kyber and SIKE examples..) > > So we have two examples of compatible KEMs, and one that isn't directly > but could be made compatible. But we're not sufficiently expert in KEMs to > know if this applies only to some PQC KEMs, to all PQC KEMs, or all KEMs > present and future. Or, to your point, whether this is actually how KEM > outputs are intended to be used, or if you need to hash them with protocol > context values first. We believed, from looking at the Kyber and SIKE > construction that an extra KDF step (and parameter) was unnecessary, but > we're happy to add it if it improves security or makes this mode more > generally applicable to more KEM primitives. > "Full entropy output" is an assumption that we're also making in the hardware interface designs, and it seems to apply to all relevant NIST finalist PQC KEM algorithms. Cheers, - Markku Dr. Markku-Juhani O. Saarinen <mjos@pqshield.com> PQShield, Oxford UK.
- [lamps] Which PQC KEMs can be used for composite … Bruckert, Leonie
- Re: [lamps] Which PQC KEMs can be used for compos… Ilari Liusvaara
- Re: [lamps] Which PQC KEMs can be used for compos… Mike Ounsworth
- Re: [lamps] Which PQC KEMs can be used for compos… Blumenthal, Uri - 0553 - MITLL
- Re: [lamps] Which PQC KEMs can be used for compos… Bruckert, Leonie
- Re: [lamps] Which PQC KEMs can be used for compos… Markku-Juhani O. Saarinen
- Re: [lamps] Which PQC KEMs can be used for compos… Kris Kwiatkowski
- Re: [lamps] Which PQC KEMs can be used for compos… Scott Fluhrer (sfluhrer)
- Re: [lamps] Which PQC KEMs can be used for compos… Mike Ounsworth
- Re: [lamps] Which PQC KEMs can be used for compos… Scott Fluhrer (sfluhrer)
- Re: [lamps] Which PQC KEMs can be used for compos… Mike Ounsworth
- Re: [lamps] Which PQC KEMs can be used for compos… Scott Fluhrer (sfluhrer)