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