Re: [Cfrg] likelihood that someone has a quantum computer

William Whyte <wwhyte@securityinnovation.com> Tue, 14 January 2014 02:16 UTC

Return-Path: <wwhyte@securityinnovation.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 71F671AE1B0 for <cfrg@ietfa.amsl.com>; Mon, 13 Jan 2014 18:16:13 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.378
X-Spam-Level:
X-Spam-Status: No, score=-1.378 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FM_FORGED_GMAIL=0.622, HTML_MESSAGE=0.001, SPF_PASS=-0.001] autolearn=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 vIlGi_usr0pf for <cfrg@ietfa.amsl.com>; Mon, 13 Jan 2014 18:16:11 -0800 (PST)
Received: from mail-qe0-x22b.google.com (mail-qe0-x22b.google.com [IPv6:2607:f8b0:400d:c02::22b]) by ietfa.amsl.com (Postfix) with ESMTP id 091D01ADFE4 for <cfrg@irtf.org>; Mon, 13 Jan 2014 18:16:10 -0800 (PST)
Received: by mail-qe0-f43.google.com with SMTP id nc12so1090499qeb.16 for <cfrg@irtf.org>; Mon, 13 Jan 2014 18:15:59 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=securityinnovation.com; s=google; h=from:references:in-reply-to:mime-version:thread-index:date :message-id:subject:to:cc:content-type; bh=XZs46C0gnQ6QAuRpCfWUTunX250QmMMFgPo7Yq9RT0s=; b=VfjPop3y03OkjQpMzI/XhbouTzmmOmFV3Jet5xa9dQEcL45o9WS7abxEC1TNQEwbV0 Qarc82cqjrfMQEHXK0zvlGA57MYwfbOb+HVi8BbHk/vSMwtWzOO/SKDzC9/lKtPcrHr1 iLY0hMLoqTIx5YcAcYR8oqfVfY2jgAoRUJqXU=
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:from:references:in-reply-to:mime-version :thread-index:date:message-id:subject:to:cc:content-type; bh=XZs46C0gnQ6QAuRpCfWUTunX250QmMMFgPo7Yq9RT0s=; b=a2M3KcVydU1/OKXu+O0DaLkYHBRn4dCoQnHT1Y/ZsMviX3nZlaDhPMHXGjE4FYO5hf mkQJsdRq7BTI2J9pDGdXTId3D/oMcJtS3Mlzk1YoXAe/OfQjX3fc3EFD00awIqIwOqSU WoI+Z9/tH4m539lLXog2TspBey/FVFKpRPnqyzHFQcGYQHD5mTJd66a83ELGK0JarDSq 6o5PUTF+ncKEpbrKT6oLQIEEgr3tsbYbKXVUSVvsjpuLUqI9q8zHkpy6MCWIojGtoX09 50kJ6ppzc5CHGrVp5aIU8eIRWLGJQjpc7uWMh7ICO0nk3ObbNu5KB8IBwPNI4bxTgmws iY9A==
X-Gm-Message-State: ALoCoQkAWdiqt2+zaX9EJfk+7c0+LE0NVTfeRuYXDh34hS4a8DP0cRoiB6Bbtlm5q0lhgGbDb+vS
X-Received: by 10.49.73.135 with SMTP id l7mr45418682qev.28.1389665759710; Mon, 13 Jan 2014 18:15:59 -0800 (PST)
From: William Whyte <wwhyte@securityinnovation.com>
References: <52C755AA.70200@cisco.com> <33E0BF53-A331-4646-B080-FD4F6E13916E@ieca.com> <810C31990B57ED40B2062BA10D43FBF5C1BF54@XMB116CNC.rim.net> <52D29B10.4030401@cisco.com> <CACz1E9rsLRwqpA0fS2RNOcpsn7DMqaN=7dcJDQqEi8HDMKKonQ@mail.gmail.com> <52D3D95C.5040902@cisco.com>
In-Reply-To: <52D3D95C.5040902@cisco.com>
MIME-Version: 1.0
X-Mailer: Microsoft Outlook 14.0
Thread-Index: AQJ4x4958Z+19boV+tPFc44KqqvFgQKFSLs2AjIpROUCKyrZpgJv7XkgAgwZdQGY1RWgkA==
Date: Mon, 13 Jan 2014 21:15:57 -0500
Message-ID: <73702d62c620d7ecfd9d4f924c24d1ab@mail.gmail.com>
To: David McGrew <mcgrew@cisco.com>
Content-Type: multipart/alternative; boundary="047d7bdc0c22f701ac04efe4c53a"
Cc: Dan Brown <dbrown@certicom.com>, TurnerS@ieca.com, cfrg@irtf.org
Subject: Re: [Cfrg] likelihood that someone has a quantum computer
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Tue, 14 Jan 2014 02:16:13 -0000

Hi David,



>> I am skeptical about the approach of combining multiple public key
algorithms, especially for postquantum algorithms.  This is partly because
of the complexity of the specification and the implementation, but also
because it would require double the amount of work from authors, reviewers,
and implementers in order to be successful.



I’m not sure it’s necessarily that complex. If we have an asymmetric key
transport mechanism KT that transports key material k and is semantically
secure, and we have a secure KDF, it seems that



Transport: KT1(k1), KT2(k2), KT3(k3), …

Secret k = KDF(k1, k2, k3, …)



..will also be semantically secure. Obviously this would need to be
demonstrated rigorously, but rather than seeing “double the amount of work”
from the standardization point of view, I see one task to define a secure
combination mechanism, and then a series of tasks to standardize individual
key transport mechanisms, where this series of tasks would have to be done
anyway by people who wanted their algorithms adopted.



For signatures, assuming we’re looking only at diversity in public key
algorithms and not hash algorithms, it’s the same: the message simply takes
two signatures, one from each algorithm.  Again, this would have to be
specified rigorously. I think diversity in signatures is less urgent than
for encryption algorithms, because of the risk of an attacker storing
messages for a long time and decrypting them when possible, but it’s worth
considering.



Similarly, implementations have one additional task rather than double the
amount of tasks. Testing may be more complicated if all pairwise
combinations of algorithms are to be tested, but I expect the total number
of algorithms will never be too big.



Finally, authenticating the public keys may require building support for
new algorithms into CAs, which could be laborious (though again, I would
argue that you should do this when you don’t have to).



> Patents could also be a significant issue, as you note.



Yes, agreed. This would need to be looked into.



Cheers,



William



*From:* David McGrew [mailto:mcgrew@cisco.com]
*Sent:* Monday, January 13, 2014 7:18 AM
*To:* William Whyte
*Cc:* Dan Brown; TurnerS@ieca.com; cfrg@irtf.org
*Subject:* Re: [Cfrg] likelihood that someone has a quantum computer



Hi William,

On 01/12/2014 11:16 PM, William Whyte wrote:

Hi all,



Sorry again for top-posting, that's gmail for you.



> I would put it more positively as: let's figure out how to use
post-quantum cryptography in practice, because if there is a breakthrough
in quantum computing, the mad rush will be ugly.



As I mentioned in a previous mail, I think the best way to do this is to
figure out how to avoid depending on a single public key algorithm in any
context, because all public key algorithms are potentially vulnerable to
technological and algorithmic breakthroughs. So combining public key
algorithms seems like a prudent approach. I know there are Certicom patents
on this but it seems that this shouldn't be insuperable.


I am skeptical about the approach of combining multiple public key
algorithms, especially for postquantum algorithms.  This is partly because
of the complexity of the specification and the implementation, but also
because it would require double the amount of work from authors, reviewers,
and implementers in order to be successful.   Patents could also be a
significant issue, as you note.

David