Subject: Re: [TLS] RSA-PSS in TLS 1.3

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Thu, 3 Mar 2016 15:29:37 +0000

Also, wasn't PSS ‎developed before SHA3 and SHAKE were known, let alone available? 

It may be worth asking the authors what's their opinion of FDH vs PSS in view of the state of the art *today*.

Sent from my BlackBerry 10 smartphone on the Verizon Wireless 4G LTE network.
  Original Message  
From: Dang, Quynh (Fed)
Sent: Thursday, March 3, 2016 09:21
To: Hanno Böck; [email-masked]
Subject: Re: [TLS] RSA-PSS in TLS 1.3

Hi Hanno,

I think the PSS uses a random salt to get the hashing probabilistic.

A customized version of a SHAKE can/may take a domain-separation string or/and a random salt.

Quynh. 

________________________________________
From: TLS <[email-masked]> on behalf of Hanno Böck <[email-masked]>
Sent: Thursday, March 3, 2016 8:49 AM
To: [email-masked]
Subject: Re: [TLS] RSA-PSS in TLS 1.3

On Thu, 3 Mar 2016 13:35:46 +0000
"Dang, Quynh (Fed)" <[email-masked]> wrote:

> Why don't we use an even more elegant RSA signature called "
> full-domain hash RSA signature" ?

Full Domain Hashing was originally developed by Rogaway and Bellare and
then later dismissed because they found that they could do better. Then
they developed PSS.

See
http://web.cs.ucdavis.edu/~rogaway/papers/exact.pdf

So in essence FDH is a predecessor of PSS and the authors of both
schemes came to the conclusion that PSS is the superior scheme.

> As you know, a SHAKE (as a variable output-length hash function)
> naturally produces a hash value which fits any given modulus size.
> Therefore, no paddings are needed which avoids any potential issues
> with the paddings and the signature algorithm would be very simple.

You could also use SHAKE in PSS to replace MGF1. This is probably
desirable if you intent to use PSS with SHA-3.

PSS doesn't really have any padding in the traditional sense. That is,
all the padding is somehow either hashed or xored with a hashed value.
I don't think any of the padding-related issues apply in any way to
PSS, if you disagree please explain.

(shameless plug: I wrote my thesis about PSS, in case anyone wants to
read it: https://rsapss.hboeck.de/ - it's been a while, don't be too
hard on me if I made mistakes)

--
Hanno Böck
https://hboeck.de/

mail/jabber: [email-masked]
GPG: BBB51E42

_______________________________________________
TLS mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/tls

---

From: Hanno Böck <[email-masked]>
Date: Thu, 3 Mar 2016 17:11:17 +0100

On Thu, 3 Mar 2016 15:29:37 +0000

> Also, wasn't PSS ‎developed before SHA3 and SHAKE were known, let

Yeah, more than 10 years before.
It's more the other way found: PSS and other constructions showed the
need for hash functions with a defined output length. SHAKE is such a
function. PSS uses a construction called MGF1, which essentially takes
an existing fixed-output-length hash, combines that with a counter and
produces some construction. SHAKE deprecates the need for such a
workaround.

So instead of using PSS+SHA256+MGF1-with-SHA256 you could say you use
PSS+SHA-3-256+SHAKE256. I don't think this changes a whole lot in
regards to security (as long as we assume both sha256 and sha-3-256 are
very secure algorithms).

> 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.

-- 
Hanno Böck
https://hboeck.de/

---

From: "Dang, Quynh (Fed)" <[email-masked]>
Date: Thu, 3 Mar 2016 18:13:22 +0000

PSS+SHAKE128/512+SHAKE128 or PSS+SHAKE256/512+SHAKE256 (as SHAKEs being used as MGF) would be more efficient options. NIST is working on a formal specification for the SHAKEs being used as fixed output-length hash functions such as SHAKE128/256, SHAKE128/512 and SHAKE256/512. 

Prepending a random salt of 512-bit in length (fixed length of 512 bits) to the message should work and this is very simple and efficient.

Quynh. 

________________________________________
From: TLS <[email-masked]> on behalf of Hanno Böck <[email-masked]>
Sent: Thursday, March 3, 2016 11:11 AM
To: Blumenthal, Uri - 0553 - MITLL; [email-masked]
Subject: Re: [TLS] RSA-PSS in TLS 1.3

--
Hanno Böck
https://hboeck.de/

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Fri, 04 Mar 2016 09:09:33 +0100

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*.

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.

regards,
Nikos

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Fri, 4 Mar 2016 13:49:11 +0000

> -----Original Message-----
> From: TLS [mailto:[email-masked]] On Behalf Of Nikos
> Mavrogiannopoulos
> Sent: Friday, March 04, 2016 3:10 AM
> To: Hanno Böck; Blumenthal, Uri - 0553 - MITLL; [email-masked]
> > 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

---

From: Hubert Kario <[email-masked]>
Date: Mon, 07 Mar 2016 12:42:39 +0100

> > > PSS has an RFC (3447) and has been thoroughly analyzed by
 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.
> > >
> > >
> > >
> > > (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.

-- 
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

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Mon, 07 Mar 2016 14:42:15 +0100

On Fri, 2016-03-04 at 13:49 +0000, Scott Fluhrer (sfluhrer) wrote:
> > > than
> > available, the
> 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

Assuming that we have such algorithms which are practical to manage and
deploy we would first need to enhance existing protocols with them,
including TLS and PKI. Then it is only the (simple) task of
upgrading/replacing every single piece of infrastructure we have today
from certificates to implementations with the new algorithms. 

Unless you can use the quantum computer to complete the above
transition overnight, the quickest way to defend against the presence
of a quantum computer is by allowing larger RSA keys.

regards,
Nikos

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Mon, 7 Mar 2016 15:23:17 +0000

> From: Hubert Kario [mailto:[email-masked]]
> Sent: Monday, March 07, 2016 6:43 AM
> To: [email-masked]
> Cc: Scott Fluhrer (sfluhrer); Nikos Mavrogiannopoulos; Hanno Böck;
> Blumenthal, Uri - 0553 - MITLL
> > > > 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).
> > > > specified in a standards document. If one would want to use FDH or
> > > > anything else one would imho first have to go through some
> > 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...
> 
> 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).

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...

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Mon, 7 Mar 2016 16:34:25 +0000

> From: Nikos Mavrogiannopoulos [mailto:[email-masked]]
> Sent: Monday, March 07, 2016 8:42 AM
> To: Scott Fluhrer (sfluhrer); Hanno Böck; Blumenthal, Uri - 0553 - MITLL;
> [email-masked]
> > > > viable.
> 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
> including TLS and PKI. Then it is only the (simple) task of upgrading/replacing
> every single piece of infrastructure we have today from certificates to
> implementations with the new algorithms.

There are two threats that a Quantum Computer may bring:

- Someone (who might not have a QC now) recording the encrypting traffic, and then (when they do have a QC) decrypting the traffic
- Someone with a QC forging our authentication (certificates),and acting either as an imposter, or as a man-in-the-middle.

The second attack isn't feasible until someone actually has a QC at the time of the attack; for the first attack, that's a threat until the data being protected is no longer of any interest - depending on what that data is, that may be decades.

To defend against the first attack, we don't need to update the entire infrastructure.  Instead, all we need to do is update the client and the server to use a Quantum-Resistant ciphersuite (I'd argue that a QR named group would actually be preferable, however that's an argument for another time).  We know how to do a gradual rollout of this.

To defend against the second attack, yes, that would require changes to PKI, which this WG isn't in charge of.  However, these attacks become a threat later.

So, the points I want to make are:

- Defenses against the first type of attack (passive evesdropping by someone who will build a QC sometime in the future) are something that this WG should address; even if the PKI people don't have an answer, we would at least be secure from someone recording the traffic and decrypting it later
- Large size RSA keys (actually, DH groups; TLS 1.3 doesn't use RSA for key transport) don't necessarily add any protection from a QC (depending on how fast practical QC's ramp up).

> 
> Unless you can use the quantum computer to complete the above transition
> overnight, the quickest way to defend against the presence of a quantum
> computer is by allowing larger RSA keys.

Actually, that brings up a point; if we are worried about some old, unupdatable servers, how are we going to ever upgrade our authentication infrastructure?  A lot of those are built on cryptolibraries that cannot handle 16K RSA keys any more than they can handle Hash Based or BLISS certificates.  However, that's an argument for another time (and probably not by this WG)

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Mon, 7 Mar 2016 17:21:32 +0000

From: Tony Arcieri [mailto:[email-masked]]
Sent: Monday, March 07, 2016 11:40 AM
To: Scott Fluhrer (sfluhrer)
Cc: Nikos Mavrogiannopoulos; Hanno Böck; Blumenthal, Uri - 0553 - MITLL; [email-masked]
Subject: Re: [TLS] RSA-PSS in TLS 1.3

On Mon, Mar 7, 2016 at 8:34 AM, Scott Fluhrer (sfluhrer) <[email-masked]<mailto:[email-masked]>> wrote:
Defenses against the first type of attack (passive evesdropping by someone who will build a QC sometime in the future) are something that this WG should address; even if the PKI people don't have an answer, we would at least be secure from someone recording the traffic and decrypting it later

I think it would make sense to wait for the CFRG to weigh in on post-quantum crypto. Moving to a poorly studied post-quantum key exchange algorithm exclusively runs the risk that when it does receive wider scrutiny new attacks will be found. I think we need to define hybrid pre/post-quantum key exchange algorithms (e.g. ECC+Ring-LWE+HKDF), and that sounds like work better suited for the CFRG than the TLS WG.

I’m sorry that I wasn’t clearer; I agree that *now* isn’t the time to define a postquantum ciphersuite/named group; we’re not ready yet (and this WG probably isn’t the right group to define it).  However, I believe that we will need to do at some point; my guess is that it’ll be sooner rather than later.  What (IMHO) this WG should be doing now is making sure that there isn’t something in TLS 1.3 that’ll make it harder to transition to postquantum crypto when we do have a concrete proposal.

One thing that proposed QR key exchanges have is that they don’t have the full flexibility that (EC)DH have; either they aren’t secure with static key shares, or we can’t use the same key share as both an ‘initiator’ and a ‘responder’ key share.  This would indicate to me that we need to make sure that TLS 1.3 should be engineered to use (EC)DH as only a simple, ephemeral-only key exchange – yes, it has more flexibility than that, however taking advantage of such flexibility might cause us problems in the future

---

From: Hubert Kario <[email-masked]>
Date: Mon, 07 Mar 2016 18:18:30 +0100

On Monday 07 March 2016 15:23:17 Scott Fluhrer wrote:
> > > 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...
> > 
> > 
> > 
> > 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).
> 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

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

and we already aren't using 1024 bit RSA and deprecating 1024 bit DH

> 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.

or the error correction issues may scale in tandem with the number of 
bits that need to be error corrected, or it may be a problem that never 
really gets solved (like 4GHz barrier of silicon)

> 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...

they might also get unicorn horns as a by-product; everything is 
possible in this crazy world /s

probability of that happening is rather low though, looking at the past 
few centuries of scientific development...

yes, they may jump ahead one or two doubles by getting really lucky or 
spending a lot of money, but it won't be sustainable for the whole 
growth between 256 or 384 bit and 16k bit, let alone from the current 16 
bits to 16k bits

while for libraries to go from current 2k RSA and DH to 16k RSA and DH 
is trivial in comparison
-- 
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

---

From: Tony Arcieri <[email-masked]>
Date: Mon, 7 Mar 2016 08:39:58 -0800

On Mon, Mar 7, 2016 at 8:34 AM, Scott Fluhrer (sfluhrer) <[email-masked]
> wrote:

> Defenses against the first type of attack (passive evesdropping by someone
> who will build a QC sometime in the future) are something that this WG
> should address; even if the PKI people don't have an answer, we would at
> least be secure from someone recording the traffic and decrypting it later

I think it would make sense to wait for the CFRG to weigh in on
post-quantum crypto. Moving to a poorly studied post-quantum key exchange
algorithm exclusively runs the risk that when it does receive wider
scrutiny new attacks will be found. I think we need to define hybrid
pre/post-quantum key exchange algorithms (e.g. ECC+Ring-LWE+HKDF), and that
sounds like work better suited for the CFRG than the TLS WG.

-- 
Tony Arcieri

---

From: Rene Struik <[email-masked]>
Date: Mon, 7 Mar 2016 14:48:46 -0500

Hi Scott:

I think it is really premature to speculate on features PQ-secure 
algorithms can or cannot provide (*) and try and have this influence 
*current* TLS1.3 protocol design.  Should one wish to include PQ 
algorithms in a future update of TLS1.3, one can simply specify which 
protocol ingredients those updates relate to. As long as the current 
TLS1.3 specification has some facility for implementing algorithm 
agility, one can shy away from crystal ball gazing for now.

Best regards, Rene

(*) I am not sure everyone would concur with your speculation, but 
crypto conferences may be a better venue to discuss this than a TLS 
mailing list.

On 3/7/2016 12:21 PM, Scott Fluhrer (sfluhrer) wrote:
>
> *From:*Tony Arcieri [mailto:[email-masked]]
> *Sent:* Monday, March 07, 2016 11:40 AM
> *To:* Scott Fluhrer (sfluhrer)
> *Cc:* Nikos Mavrogiannopoulos; Hanno Böck; Blumenthal, Uri - 0553 - 
> MITLL; [email-masked]
> *Subject:* Re: [TLS] RSA-PSS in TLS 1.3
>
> On Mon, Mar 7, 2016 at 8:34 AM, Scott Fluhrer (sfluhrer) 
> <[email-masked] <mailto:[email-masked]>> wrote:
>
> Defenses against the first type of attack (passive evesdropping by 
> someone who will build a QC sometime in the future) are something that 
> this WG should address; even if the PKI people don't have an answer, 
> we would at least be secure from someone recording the traffic and 
> decrypting it later
>
>
> post-quantum crypto. Moving to a poorly studied post-quantum key 
> exchange algorithm exclusively runs the risk that when it does receive 
> wider scrutiny new attacks will be found. I think we need to define 
> hybrid pre/post-quantum key exchange algorithms (e.g. 
> ECC+Ring-LWE+HKDF), and that sounds like work better suited for the 
> CFRG than the TLS WG.
>
> I’m sorry that I wasn’t clearer; I agree that **now** isn’t the time 
> to define a postquantum ciphersuite/named group; we’re not ready yet 
> (and this WG probably isn’t the right group to define it). However, I 
> believe that we will need to do at some point; my guess is that it’ll 
> be sooner rather than later.  What (IMHO) this WG should be doing now 
> is making sure that there isn’t something in TLS 1.3 that’ll make it 
> harder to transition to postquantum crypto when we do have a concrete 
> proposal.
>
> One thing that proposed QR key exchanges have is that they don’t have 
> the full flexibility that (EC)DH have; either they aren’t secure with 
> static key shares, or we can’t use the same key share as both an 
> ‘initiator’ and a ‘responder’ key share.  This would indicate to me 
> that we need to make sure that TLS 1.3 should be engineered to use 
> (EC)DH as only a simple, ephemeral-only key exchange – yes, it has 
> more flexibility than that, however taking advantage of such 
> flexibility might cause us problems in the future
>
>
>

-- 
email: [email-masked] | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Mon, 7 Mar 2016 20:25:21 +0000

> I think it is really premature to speculate on features PQ-secure algorithms
> can or cannot provide (*) and try and have this influence *current* TLS1.3
> protocol design.  Should one wish to include PQ algorithms in a future update
> of TLS1.3, one can simply specify which protocol ingredients those updates
> relate to. As long as the current TLS1.3 specification has some facility for
> implementing algorithm agility, one can shy away from crystal ball gazing for
> now. 

+1

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Mon, 7 Mar 2016 22:05:28 +0000

I'm not precisely sure what you are really saying.  Are you claiming that, even though currently known PQ key exchange don't give all the flexibility that (EC)DH has, you're pretty sure that'll change in the future?  Or, are you saying that relying on the full flexibility of (EC)DH isn't a problem, as the WG will be willing to make changes to the TLS 1.3 0-RTT infrastructure in the future?

The issue really is the 0-RTT infrastructure, and its static key share.  Unlike (EC)DH, known postquantum key agreement protocols either don't securely support static key shares (largely because it is impossible to distinguish a valid client keyshare from an invalid one, and how the server reacts to an invalid client keyshare depends on the server's private keyshare value), or they are really public key encryption systems being used to do key agreement, and the client's key share in the 0-RTT exchange can't be used to negotiate a long term set of keys.

Outside of 0-RTT, there doesn't appear to be an issue.  In those cases, the client gives an ephemeral key share, the server responds with an ephemeral key share, they both derive a shared secret, and everyone (other than the NSA, who can't listen in :-) is happy.  However, 0-RTT is an important part of the protocol; we can't forbid it in a postquantum setting.

Of course, we can in the future, we can revise the TLS 1.3 protocol to adapt to the functionality that postquantum algorithms will give us.  However (based on the protocols we know about) the changes required by the protocol would be nontrivial.  My hope is to make it so that algorithm agility is enough; that all the protocol needs to know is that there's this additional ciphersuite that, from a blackbox standpoint, does precisely the same job as the other ciphersuites, and that nothing outside of the crypto code needs to change.  However, given that the postquantum algorithms we know about can't do everything that (EC)DH can do, it would appear to be prudent not to assume (in either our protocol or in our proofs) this additional functionality.

From: Rene Struik [mailto:[email-masked]]
Sent: Monday, March 07, 2016 2:49 PM
To: Scott Fluhrer (sfluhrer); Tony Arcieri
Cc: [email-masked]
Subject: (TLS1.3 - algorithm agility support is enough; no need to crystal ball gaze PQ right now, except as pass-time) Re: [TLS] RSA-PSS in TLS 1.3

Hi Scott:

I think it is really premature to speculate on features PQ-secure algorithms can or cannot provide (*) and try and have this influence *current* TLS1.3 protocol design.  Should one wish to include PQ algorithms in a future update of TLS1.3, one can simply specify which protocol ingredients those updates relate to. As long as the current TLS1.3 specification has some facility for implementing algorithm agility, one can shy away from crystal ball gazing for now.

Best regards, Rene

(*) I am not sure everyone would concur with your speculation, but crypto conferences may be a better venue to discuss this than a TLS mailing list.

Cc: Nikos Mavrogiannopoulos; Hanno Böck; Blumenthal, Uri - 0553 - MITLL; [email-masked]<mailto:[email-masked]>

I'm sorry that I wasn't clearer; I agree that *now* isn't the time to define a postquantum ciphersuite/named group; we're not ready yet (and this WG probably isn't the right group to define it).  However, I believe that we will need to do at some point; my guess is that it'll be sooner rather than later.  What (IMHO) this WG should be doing now is making sure that there isn't something in TLS 1.3 that'll make it harder to transition to postquantum crypto when we do have a concrete proposal.

One thing that proposed QR key exchanges have is that they don't have the full flexibility that (EC)DH have; either they aren't secure with static key shares, or we can't use the same key share as both an 'initiator' and a 'responder' key share.  This would indicate to me that we need to make sure that TLS 1.3 should be engineered to use (EC)DH as only a simple, ephemeral-only key exchange - yes, it has more flexibility than that, however taking advantage of such flexibility might cause us problems in the future

TLS mailing list

[email-masked]<mailto:[email-masked]>

--

email: [email-masked]<mailto:[email-masked]> | Skype: rstruik

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Tue, 8 Mar 2016 16:53:18 +0000

> Sent: Monday, March 07, 2016 12:18 PM
> Cc: [email-masked]; Nikos Mavrogiannopoulos; Hanno Böck; Blumenthal, Uri -
> 0553 - MITLL

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.

> 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).

---

From: Hubert Kario <[email-masked]>
Date: Tue, 08 Mar 2016 19:24:37 +0100

On Tuesday 08 March 2016 16:53:18 Scott Fluhrer wrote:
> > Cc: [email-masked]; Nikos Mavrogiannopoulos; Hanno Böck; Blumenthal,
> > Uri - 0553 - MITLL
> > 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.

No, I said that we have no reason to believe that quantum computers 
won't follow exponential increase in number of qbits they can handle, 
with the highest increase not exceeding doubling every year, but more 
likely doubling every two years (as every other technological 
development did till now).

I'd really like to hear an expert that will say that building a 1,000 
qbit QC will be just as easy as building a 100,000 qbit one.

> 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.

I said that this exponential growth in quantum computers most likely 
*won't* provide us 20 years of RSA/DH unbreakability after ECC falls. 
How is that saying that RSA will not be broken by quantum computers?

> > 
> > 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.

RSA of what size? and what about ECC?

Using currently known algorithms, to break 256 bit ECC you need 384 qbit 
quantum computer

To break 15360 bit RSA or DH you need 23040 qbit quantum computer.

Assuming explosive growth of quantum computer sizes (doubling every 
year), RSA of that size will be broken 6 years after the above ECC.

Does that mean that ECC will fall in 4 to 6 years?

> 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.
 
Quantum Computers are all or nothing, you can't use a 256 qbit QC to 
break 512 bit RSA, you need a 768 qbit QC to break it. Any smaller one 
won't be more effective than classical computer.

> 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).
 
I said quite explicitly that this is just a short term solution, 5 years 
almost certainly, 10 years probably and 20 years being highly unlikely.

and 10 years is not nothing in academia, protocol design or deployment

it buys little time, but it does buy time, nothing else does
-- 
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

---

From: Viktor Dukhovni <[email-masked]>
Date: Tue, 8 Mar 2016 18:41:32 +0000

> development did till now).

There's reason to be skeptical of such analogies.  Moore's law was
neither a theorem nor a law of nature.  It was an observation about
progress in feature-size shrink of silicon transistors.  It is far
from clear that evolution of silicon fabrication is a relevant model.

-- 
	Viktor.

---

From: Hubert Kario <[email-masked]>
Date: Wed, 09 Mar 2016 12:05:16 +0100

> from clear that evolution of silicon fabrication is a relevant model.

That's why I'm not saying that it will be exactly like Moore's law.

My point is, that processes which have super-exponential growth are the 
exception, not the rule (if they exist at all). And you would be hard 
pressed to find any process in history that experienced exponential 
growth over a long time span and be at the same time vastly faster than 
the Moore's law.
-- 
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