Re: [TLS] RSA-PSS in TLS 1.3

["Scott Fluhrer (sfluhrer)" <[e-mail]>]

> -----Original Message-----
> From: Hubert Kario [mailto:[e-mail]]
> Sent: Monday, March 07, 2016 12:18 PM
> To: Scott Fluhrer (sfluhrer)
> Cc: [e-mail]; 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:[e-mail]]
> > > Sent: Monday, March 07, 2016 6:43 AM
> > > To: [e-mail]
> > > 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).