Re: [TLS] RSA-PSS in TLS 1.3

[Hubert Kario <[e-mail]>]

On Tuesday 08 March 2016 16:53:18 Scott Fluhrer wrote:
> > -----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:
> > 
> > 
> > > 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.

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