Re: [TLS] RSA-PSS in TLS 1.3

"Scott Fluhrer (sfluhrer)" <sfluhrer@cisco.com> Mon, 07 March 2016 15:23 UTC

Return-Path: <sfluhrer@cisco.com>
X-Original-To: tls@ietfa.amsl.com
Delivered-To: tls@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 92CE21B42B1 for <tls@ietfa.amsl.com>; Mon, 7 Mar 2016 07:23:21 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -12.202
X-Spam-Level:
X-Spam-Status: No, score=-12.202 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, MANGLED_BACK=2.3, RCVD_IN_DNSWL_HI=-5, RP_MATCHES_RCVD=-0.001, SPF_PASS=-0.001, USER_IN_DEF_DKIM_WL=-7.5] autolearn=ham
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 UBtJ8s4MOzEz for <tls@ietfa.amsl.com>; Mon, 7 Mar 2016 07:23:19 -0800 (PST)
Received: from alln-iport-1.cisco.com (alln-iport-1.cisco.com [173.37.142.88]) (using TLSv1.2 with cipher DHE-RSA-SEED-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 946C41B42AE for <tls@ietf.org>; Mon, 7 Mar 2016 07:23:19 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=cisco.com; i=@cisco.com; l=6614; q=dns/txt; s=iport; t=1457364199; x=1458573799; h=from:to:cc:subject:date:message-id:references: in-reply-to:content-transfer-encoding:mime-version; bh=cEMjHpIv3BUYQ7cYfiWRFGGpzzOikjy8wyGU021x9Gc=; b=dwvmNfRua9BO+SM9jFg1KkGYvrw21wCfi9lUhlKxH8iDv8KrQP1C0tCB 6EIUmxWI+rYTMMEQXpE3Sr95IPs9iMBJLFOC4kis2RVjmP1mr8jVh2cn4 YBKG0fT9y7eLQuSd1OmUWM0vAwN3+kA6nwerjStB/38gTBN62JRjG4yIm I=;
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: =?us-ascii?q?A0D9AQAtnN1W/51dJa1dgzpSbQa6OgENg?= =?us-ascii?q?WkdhXICHIENOBQBAQEBAQEBZCeEQQEBAQQdBhEVKQIFDAQCAQgOAwQBAQECAiM?= =?us-ascii?q?DAgICMBQBCAgBAQQBDQUIDIgOsBCOXAEBAQEBAQEBAQEBAQEBAQEBAQEBARV7h?= =?us-ascii?q?RyEPYRQgmqBOgWXKgGIUYUUjwGOVAEeAQFCg2RqAYg+fgEBAQ?=
X-IronPort-AV: E=Sophos;i="5.22,551,1449532800"; d="scan'208";a="246653366"
Received: from rcdn-core-6.cisco.com ([173.37.93.157]) by alln-iport-1.cisco.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 07 Mar 2016 15:23:18 +0000
Received: from XCH-ALN-007.cisco.com (xch-aln-007.cisco.com [173.36.7.17]) by rcdn-core-6.cisco.com (8.14.5/8.14.5) with ESMTP id u27FNI6D010039 (version=TLSv1/SSLv3 cipher=AES256-SHA bits=256 verify=FAIL); Mon, 7 Mar 2016 15:23:18 GMT
Received: from xch-rcd-006.cisco.com (173.37.102.16) by XCH-ALN-007.cisco.com (173.36.7.17) with Microsoft SMTP Server (TLS) id 15.0.1104.5; Mon, 7 Mar 2016 09:23:17 -0600
Received: from xch-rcd-006.cisco.com ([173.37.102.16]) by XCH-RCD-006.cisco.com ([173.37.102.16]) with mapi id 15.00.1104.009; Mon, 7 Mar 2016 09:23:17 -0600
From: "Scott Fluhrer (sfluhrer)" <sfluhrer@cisco.com>
To: Hubert Kario <hkario@redhat.com>, "tls@ietf.org" <tls@ietf.org>
Thread-Topic: [TLS] RSA-PSS in TLS 1.3
Thread-Index: AdF1YX6hVOviuew0z0qjJ4Wpjso/6gAOBziAACF3k4AAAP03AACdU9uAAAV12dA=
Date: Mon, 7 Mar 2016 15:23:17 +0000
Message-ID: <720dc8ee9c9a49209c1e76271d0dd403@XCH-RCD-006.cisco.com>
References: <20160303152945.18296912.40009.55386@ll.mit.edu> <1457078973.19296.1.camel@redhat.com> <3611ab23e3f948b4bfa0bdd0b348bcc2@XCH-RCD-006.cisco.com> <5209728.bPpGhxeIz8@pintsize.usersys.redhat.com>
In-Reply-To: <5209728.bPpGhxeIz8@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/kKWsFVT6ofOqCxW2f5IXsxmFgl4>
Subject: Re: [TLS] RSA-PSS in TLS 1.3
X-BeenThere: tls@ietf.org
X-Mailman-Version: 2.1.15
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: Mon, 07 Mar 2016 15:23:21 -0000

> -----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:
> > > -----Original Message-----
> > > From: TLS [mailto:tls-bounces@ietf.org] On Behalf Of Nikos
> > > Mavrogiannopoulos
> > > Sent: Friday, March 04, 2016 3:10 AM
> > > To: Hanno Böck; Blumenthal, Uri - 0553 - MITLL; tls@ietf.org
> > > Subject: Re: [TLS] RSA-PSS in TLS 1.3
> > >
> > > On Thu, 2016-03-03 at 17:11 +0100, Hanno Böck wrote:
> > >
> > > > It may be worth asking the authors what's their opinion of FDH vs
> > > >
> > > > > PSS
> > > > > in view of the state of the art *today*.
> > > >
> > > > You may do that, but I doubt that changes much.
> > > >
> > > >
> > > >
> > > > I think FDH really is not an option at all here. It may very well
> > > > be that there are better ways to do RSA-padding, but I don't think
> > > > that this is viable for TLS 1.3 (and I don't think FDH is better).
> > > > PSS has an RFC (3447) and has been thoroughly analyzed by
> > > > research. I
>  think there has been far less analyzing effort
> > > > towards FDH (or any other construction) and it is not in any way
> > > > specified in a standards document. If one would want to use FDH or
> > > > anything else one would imho first have to go through some
> > > > standardization process (which could be CFRG or NIST or someone
> > > > else) and call for a thorough analysis of it by the cryptographic
> > > > community. Which would take at least a couple of years.
> > > >
> > > >
> > > >
> > > > Given that there probably is no long term future for RSA anyway
> > > > (people want ECC and postquantum is ahead) I doubt anything else
> > > > than the primitives we already have in standards will ever be
> > > > viable.>
> > >
> > > On the contrary. If we have a future with quantum computers
> > > available, the only thing that we have now and would work is RSA
> > > with larger keys, not ECC.
> >
> > RSA isn't *that* much more secure against a Quantum Computer than ECC.
> >  It would appear to take a larger Quantum Computer to break RSA than
> > it would to break ECC (for reasonable moduli/curve sizes), however not
> > that much more.  It is possible that, at one stage, we'll be able to
> > build a QC that's just large enough to break EC curves, but not larger
> > RSA keys - however, we would be likely to be able to scale up our QC
> > to be a bit larger; possibly in a few months, quite likely in a year
> > or two.  Hence, moving back to RSA would appear likely to buy us only
> > a short window...
> 
> > 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).

However, right now one of the chief problems in building a Quantum Computer is error correction; catching when decoherence has occurred, and fixing it before it spoils the entire operation.  Once they have that solved, practical Quantum Computers may get much bigger very fast.

Might they, after the initial explosive growth (to 1000 qbits or 1,000,000 qbits, I don't think anyone knows where that point would be), might it continue to grow in a Moore's law fashion?  It might; however we're not sure.  Using RSA keys which are 5 times larger might not buy us any time at all...

> 
> --
> Regards,
> Hubert Kario
> Senior Quality Engineer, QE BaseOS Security team
> Web: www.cz.redhat.com
> Red Hat Czech s.r.o., Purkyňova 99/71, 612 45, Brno, Czech Republic