Re: [TLS] RSA-PSS in TLS 1.3

"Scott Fluhrer (sfluhrer)" <sfluhrer@cisco.com> Tue, 08 March 2016 16:53 UTC

Return-Path: <sfluhrer@cisco.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 7C89412D835 for <tls@ietfa.amsl.com>; Tue, 8 Mar 2016 08:53:22 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -14.522
X-Spam-Level:
X-Spam-Status: No, score=-14.522 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, RCVD_IN_DNSWL_HI=-5, RCVD_IN_MSPIKE_H4=-0.01, RCVD_IN_MSPIKE_WL=-0.01, RP_MATCHES_RCVD=-0.001, SPF_PASS=-0.001, USER_IN_DEF_DKIM_WL=-7.5] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=cisco.com
Received: from mail.ietf.org ([127.0.0.1]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id lUrEinToIhDh for <tls@ietfa.amsl.com>; Tue, 8 Mar 2016 08:53:20 -0800 (PST)
Received: from rcdn-iport-1.cisco.com (rcdn-iport-1.cisco.com [173.37.86.72]) (using TLSv1.2 with cipher DHE-RSA-SEED-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 8BD6E12D811 for <tls@ietf.org>; Tue, 8 Mar 2016 08:53:20 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=cisco.com; i=@cisco.com; l=6570; q=dns/txt; s=iport; t=1457456000; x=1458665600; h=from:to:cc:subject:date:message-id:references: in-reply-to:content-transfer-encoding:mime-version; bh=GPToE96h+Y+DsMnyeK5XMMyBHWjCDwHaicre/aPDAg8=; b=AwUsLza5zuYnRkSyQRtIsoS1PPi9h4tPRKnWfAh/dexc3frtHi7O55Nr cMvZBh2GErRMO6lr3wDRrFHJVdIXNDwt8zZ+w8NywQYRJ83AzB4ejvZzL eZi8YrG9GleNryJXjoEbF6WmwCUBjOHxjuMty7NgZEjMS6eDHDnRoOKfr Y=;
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: =?us-ascii?q?A0B/BQC3At9W/49dJa1cgzqBPwa6VoFph?= =?us-ascii?q?g8CHIEoORMBAQEBAQEBZCeEQQEBAQMBIxE3BwcMBAIBCA4DBAEBAQICIwMCAgI?= =?us-ascii?q?wFAEICAIEDgUIE4gBCK57jyMBAQEBAQEBAQEBAQEBAQEBAQEBAQEVe4UchEKEU?= =?us-ascii?q?IJqgToFjTCJegGIUoUUjwKOVQEiAT+DZGqJAX4BAQE?=
X-IronPort-AV: E=Sophos;i="5.22,557,1449532800"; d="scan'208";a="84479971"
Received: from rcdn-core-7.cisco.com ([173.37.93.143]) by rcdn-iport-1.cisco.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 08 Mar 2016 16:53:19 +0000
Received: from XCH-RTP-010.cisco.com (xch-rtp-010.cisco.com [64.101.220.150]) by rcdn-core-7.cisco.com (8.14.5/8.14.5) with ESMTP id u28GrJm4002662 (version=TLSv1/SSLv3 cipher=AES256-SHA bits=256 verify=FAIL); Tue, 8 Mar 2016 16:53:19 GMT
Received: from xch-rtp-006.cisco.com (64.101.220.146) by XCH-RTP-010.cisco.com (64.101.220.150) with Microsoft SMTP Server (TLS) id 15.0.1104.5; Tue, 8 Mar 2016 11:53:18 -0500
Received: from xch-rtp-006.cisco.com ([64.101.220.146]) by XCH-RTP-006.cisco.com ([64.101.220.146]) with mapi id 15.00.1104.009; Tue, 8 Mar 2016 11:53:18 -0500
From: "Scott Fluhrer (sfluhrer)" <sfluhrer@cisco.com>
To: Hubert Kario <hkario@redhat.com>
Thread-Topic: [TLS] RSA-PSS in TLS 1.3
Thread-Index: AdF1YX6hVOviuew0z0qjJ4Wpjso/6gAOBziAACF3k4AAAP03AACdU9uAAAV12dAABkTjAAAjYV5w
Date: Tue, 8 Mar 2016 16:53:18 +0000
Message-ID: <e9de214d3a494cb4bd95935533ce8832@XCH-RTP-006.cisco.com>
References: <20160303152945.18296912.40009.55386@ll.mit.edu> <5209728.bPpGhxeIz8@pintsize.usersys.redhat.com> <720dc8ee9c9a49209c1e76271d0dd403@XCH-RCD-006.cisco.com> <1780021.yiLHCh9FZ9@pintsize.usersys.redhat.com>
In-Reply-To: <1780021.yiLHCh9FZ9@pintsize.usersys.redhat.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.98.2.61]
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: base64
MIME-Version: 1.0
Archived-At: <http://mailarchive.ietf.org/arch/msg/tls/1PD9WD4236wXKRFSaJhfFaRk5Is>
Cc: "tls@ietf.org" <tls@ietf.org>
Subject: Re: [TLS] RSA-PSS in TLS 1.3
X-BeenThere: tls@ietf.org
X-Mailman-Version: 2.1.17
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, 08 Mar 2016 16:53:22 -0000

> -----Original Message-----
> From: Hubert Kario [mailto:hkario@redhat.com]
> Sent: Monday, March 07, 2016 12:18 PM
> To: Scott Fluhrer (sfluhrer)
> Cc: tls@ietf.org; Nikos Mavrogiannopoulos; Hanno Böck; Blumenthal, Uri -
> 0553 - MITLL
> Subject: Re: [TLS] RSA-PSS in TLS 1.3
> 
> On Monday 07 March 2016 15:23:17 Scott Fluhrer wrote:
> > > -----Original Message-----
> > > From: Hubert Kario [mailto:hkario@redhat.com]
> > > Sent: Monday, March 07, 2016 6:43 AM
> > > To: tls@ietf.org
> > > Cc: Scott Fluhrer (sfluhrer); Nikos Mavrogiannopoulos; Hanno Böck;
> > > Blumenthal, Uri - 0553 - MITLL
> > > Subject: Re: [TLS] RSA-PSS in TLS 1.3
> > >
> > > On Friday 04 March 2016 13:49:11 Scott Fluhrer wrote:
> > >
> > > > I agree with Hanno; if we're interested in defending against a
> > > > Quantum Computer, post Quantum algorithms are the way to go
> > >
> > >
> > > except that using RSA keys nearly an order of magnitude larger than
> > > the biggest ECC curve that's widely supported (secp384) is the
> > > current recommended minimum by ENISA and long term minimum by
> NIST
> > > (3072).
> > > Using keys 5 times larger still is not impossible, so while it may
> > > not buy us extra 20 years after ECC is broken, 10 years is not
> > > impossible and 5 is almost certain (if Moore's law holds for
> > > quantum computers).
> > > It's not much, but it may be enough to make a difference.
> >
> >
> > If we believe that growth in Moore's law will be accurate for Quantum
> > Computers, then no one has to worry about Quantum Computers for the
> > next millennia.
> 
> > In 2001, a Quantum Computer factored a 4 bit number.  In 2014, the
> > factorization of a 16 bit number was announced (however, the
> > factorization used a special relationship between the factors, so I
> > don’t think it counts as a general factorization, but let's ignore
> > that for now).  That's not too far off from a Moore's law type
> > expansion.  If this rate continues, well see the first 1024 bit
> > factorization circa the year 3100 AD (aka CE).
> 
> GIGO, you're extrapolating from two data points when we have no idea how
> fast or how slow will be the progress in general

Actually, that sort of logic is what you're using.  You have no idea how fast or slow will the progress be in general, however you assure us that it'll be take significantly longer to create a Quantum Computer that can break large key RSA than it would be to break ECC.

If you don't believe the oversimplified logic I showed above, you must assume that, at some point in the future, that Quantum Computers must increase much more rapidly than a simple Moore's law prediction (based on simple extrapolation from what we have now).  However, you assume that this rapid expansion will stop at a point insufficient to break large key RSA.

> 
> and I meant Moore's 18-24 months per double, not the idea of exponential
> growth in general; in other words P-256 succumbing to quantum computers
> 4 to 8 years before 1024 bit RSA

As you are making assertions on the likely progress in building Quantum Computers, I have to ask: what expertise do you have in the design and construction of Quantum Computers?  How up to date are you on the theory?  Are you familiar with Toffoli gates or Clifford gates?  How about magic state factories [real name]?

I'm not an expert in this field either - however, I have talked to experts; the opinions I've heard is that a realistic computer that can break RSA is perhaps 10-15 years off (estimates differ between experts); once it's been built, scaling it up isn't likely to be much of an issue (largely because we already know how to etch quite large construction onto Silicon).  In essence, the problem isn't the actual construction process, but knowing what to build.

Might they be wrong?  Might they be overoptimistic about their technology?  Might there be a practical bump in the road that they don't foresee yet?  Perhaps; however it wouldn't appear prudent to assume that.

And, I would argue that 10-15 years isn't that far off, since we need to worry about someone storing the encrypted data now, and decrypting them later.


The bottom line: am I saying that you shouldn't start supporting large key RSA as a short term solution, in the hopes that it might fend off a Quantum Computer for a bit?  No, as that's not likely to be harmful, go ahead and knock yourself out.  However, I am saying that it would be foolish to pretend that is anything but a shortterm patch at best; it might end up providing no additional protection.  If we're interested in a longer term solution, we would need to eventually go with real postquantum cryptography (and I would argue that 'eventually' isn't that far in the future).