[Cfrg] Quantum annoyance vs post-quantum preparedness

Hugo Krawczyk <hugokraw@gmail.com> Sun, 27 October 2019 17:28 UTC

Return-Path: <hugokraw@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost []) by ietfa.amsl.com (Postfix) with ESMTP id 3C8B712006B for <cfrg@ietfa.amsl.com>; Sun, 27 Oct 2019 10:28:50 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.998
X-Spam-Status: No, score=-1.998 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id SMfISzDTe_L1 for <cfrg@ietfa.amsl.com>; Sun, 27 Oct 2019 10:28:48 -0700 (PDT)
Received: from mail-io1-xd33.google.com (mail-io1-xd33.google.com [IPv6:2607:f8b0:4864:20::d33]) (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 37A0D120046 for <cfrg@irtf.org>; Sun, 27 Oct 2019 10:28:48 -0700 (PDT)
Received: by mail-io1-xd33.google.com with SMTP id u8so7878654iom.5 for <cfrg@irtf.org>; Sun, 27 Oct 2019 10:28:48 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:from:date:message-id:subject:to; bh=RZSQq6SlSOzpbdcIL79XCdSKN3G4AWJyxnGn8N6vhG8=; b=HxVP0xoMOROKSXzBCiGrsQ60cHSUDq97K4CBLKkBhxr29+ySfHczF0lTVU9QFH86KF JyYbS/2AQc4XBvRj7vvh+R+L5CWN2i6omP2nzzUruOYC323r72qMmEH+N/J4aVO4PdLH RjzOVKvfdJ+sIbFf+xn2dXQtjRRpNREvC2dYKHcyJ9neN8dQlXpVdoGko/Lq2lNH0JVA YYYIm8voMEwelYhQB5TwgHcm6/yUJnm+sJvtT3A5p2gBMJtH8amF3SAaCZWrWjSN9wBQ gI1JMNNLz3zINMnSbCggxB4lNamxwFvKu9pQIp+syoVzVZOc5kB4Q3Rp9FwVlfJtg5g0 wKzw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:from:date:message-id:subject:to; bh=RZSQq6SlSOzpbdcIL79XCdSKN3G4AWJyxnGn8N6vhG8=; b=XYyuJixlgyNUMA/SD1DdxlU60DmZkFY6pduFzMY+emdvcn6UTUvYMNbxmv5BtQifne R8D2uGv4sRsNbi98BTYJXMv7FIDzkH4LRuajEQIXmP9aFbgsaKdBfUW0troMJVbtukjC ZCT2i/DL+zUrR5smrsKNsN4QJAze/FSvmMDtgFVz3GFUU7KpnZ1+DGk5QYl9Q7HpF2ML A4CNWFajsUMZBglH9whxrDck2Yl1UoRSnXXXIbkZgaeYhdKOpIbHoIU+EU3rUhAxjguT /W9cf77RSbwad1uzYViDy82WioYr+IxYJm3W610OcXv/+7j1Q+gy2vdOTARhziAqc6Ck kdMg==
X-Gm-Message-State: APjAAAUnbH9ZEakHhYyH71KCtw+c2DuPcviezDqGr5EaoIcS1J2cHcwv j9Sn+0raRDgkMQMGt51L39ipWPA48RPMR4U0bcSVS1Bv
X-Google-Smtp-Source: APXvYqxw2sPlD8bsmi4eAFtkta3+MvDE4bEEyydeU7D/GDI+Wmy9logLeEf/BK6a/+wEfmFVJKGQbyzhWVKtrxyNTzg=
X-Received: by 2002:a5e:9e0a:: with SMTP id i10mr13736950ioq.172.1572197327024; Sun, 27 Oct 2019 10:28:47 -0700 (PDT)
MIME-Version: 1.0
From: Hugo Krawczyk <hugokraw@gmail.com>
Date: Sun, 27 Oct 2019 13:28:22 -0400
Message-ID: <CADi0yUMLcf1_ack6bv15A6khEDnYSS7Zy-_NkQ=7zOYFSCmzNQ@mail.gmail.com>
To: CFRG <cfrg@irtf.org>
Content-Type: multipart/alternative; boundary="00000000000031b62a0595e7b721"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/nuhjVjWqpsDQMmBPwKAy1ON5KUM>
Subject: [Cfrg] Quantum annoyance vs post-quantum preparedness
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: Sun, 27 Oct 2019 17:28:50 -0000

Sorry for the long email.

The recent discussion on symmetric PAKE candidates highlights quantum
(QA) as a differentiating property of PAKE protocols. I think the
discussion is
interesting but I wanted to express my opinion that QA should NOT be a major
consideration in judging these protocols. Instead quantum preparedness
be a FAR more important property to consider.

Note: It is a purpose of this email to argue that QA should not be seen as a
central property of PAKEs while preparedness for PQ adaptation and
transition is
far more important. I also argue that OPAQUE is better in that sense than
(augmented) schemes but my judgment of the significance of QA should be
independently of my judgment of OPAQUE (where I may be suspect of bias).

If scheme A has QA and scheme B does not, all this tells us is that scheme
A may
be better at protecting your *current* password from disclosure in x years
x is the number of years before we have quantum machines capable of
discrete logarithms over 256-bit (or more) elliptic curves in practical
For concreteness I think of x as 20 but you can use any other estimate your
crystal ball suggests.  So QA tells me that my current password may be in
in 20 years - should I replace it before then? Yes, of course, you should
this has nothing to do with QA).

But wait. Will my current secrets, keys, and communication be revealed in 20
years because my 20-year old password was found? NO!!
This categorical NO does not depend on the specific PAKE. Protection of past
communication in case the password is revealed is a fundamental definitional
property of PAKE. So what exactly is QA buying us?

In the context of quantum security, the question we should be asking is what
would it take to upgrade the PAKE protocol we choose today to a quantum-safe
scheme. Will we need to invent a completely new protocol? Will we be able to
keep the same design and replace some pieces? Will the quantum-safe
being developed now (e.g., via the NIST competition) be useful for the PAKE
transition to quantum safeness? How will the quantum-safe PAKE interact
with a
quantum-safe (or transitional) TLS or IKE? What will happen during a
period where, for example, TLS will be using classical signatures with a
quantum-safe DH-like KEM?

Most PAKE protocols, especially the more efficient ones, build on a
of techniques that are entangled together to provide PAKE security, as
to building on a  well-understood interaction between generic primitives
such as
a KEM, PKE, etc. (e.g., what is the equivalent of mapping a password to a
generator so central to many PAKE protocols in a generic KEM setting?).
This makes it difficult to see how these schemes evolve to the post-quantum
(and transitional) stages.

In this sense, I believe OPAQUE is better positioned for this PQ evolution.
Of the two main components that form OPAQUE: OPRF and AKE, we already have
quantum-safe AKE built out of NIST KEM candidates (see eprint 2018/928 that
builds on PQ KEMs). We can probably construct now OPRF using quantum-safe
techniques for secure two-party computation but still lack a good efficient
candidate based on lattices, for example. But such candidate is likely to
emerge in the near future given the increasing applications of OPRFs.
Moreover, since OPRF is only used for authentication, not secrecy, then the
span of a classic OPRF is VERY long (it is similar to the case of using
digital signatures in protocols like TLS and IKE during a tranisition

So we can use something like current OPAQUE with non-PQ OPRF for MANY years.
Initially with a classic AKE and, eventually, with a PQ AKE, and at some
in the future with a PQ OPRF too (with adaptation of the proofs to the
setting). Btw, regarding QA, once one moves to a PQ DH-replacement in TLS or
IKE, under which OPAQUE would be run (e.g., as needed to protect user
information) the attacker will need to run a targeted active attack against
victim to be able to run in the very distant future a QA attack (which as
assumes a powerful quantum machine and negligible gains for the attacker).

A much more significant practical attack avenue TODAY (and in the future)
is to
attack protocols that are open to pre-computation attacks. That is a
one should value much much much more significantly than QA.

The bottom line: QA is an interesting notion but of minimal practical
given its cost and the quite negligible gain for the attacker in the very
distant future. Preparedness for PQ evolution is much more significant as is
security against pre-computation attacks.