Re: [TLS] RSA-PSS in TLS 1.3

[Hubert Kario <[e-mail]>]

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

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