Re: [IPsec] AD review of draft-ietf-ipsecme-qr-ikev2-08

[Benjamin Kaduk <[e-mail]>]

On Wed, Nov 06, 2019 at 04:42:27PM +0000, Scott Fluhrer (sfluhrer) wrote:
> > -----Original Message-----
> > From: Valery Smyslov <[e-mail]>
> > Sent: Wednesday, November 06, 2019 2:50 AM
> > To: 'Benjamin Kaduk' <[e-mail]>
> > Cc: [e-mail]; [e-mail]
> > Subject: RE: AD review of draft-ietf-ipsecme-qr-ikev2-08
> > 
> > 
> > > > >    It is an open question whether or not it is feasible to build a
> > > > >    Quantum Computer (and if so, when one might be implemented),
> > > > > but if
> > > > >
> > > > > Feasibility of some quantum computer is becoming much less of an
> > > > > open question; perhaps we want some qualifiers about efficiency,
> > > > > scale, and/or general-purpose-nature.
> > > >
> > > > Do you have any data or pointers?
> > >
> > > I'm mostly just thinking about press releases from D-WAVE and Google
> > > that get turned into articles in the technology press.  We see
> > > headlines about
> > > 60+ q-bit machines, that more likely than not are doing *something*.
> > > 60+ So in
> > > my mind it becomes a question of whether what these machines (that
> > > exist and are being sold) are doing is useful for the problems
> > > relevant to a given technology, rather than whether a quantum computer
> > > exists.  (I'm not even sure that there's a generally accepted
> > > definition for what "quantum computer" means -- some people seem to
> > > use it for just annealing-based
> > > stuff.)
> > 
> > Probably, if we add a qualifier "full-scale Quantum Computer" then the text
> > will become less questionable? Something like this:
> > 
> >      It is an open question whether or not it is feasible to build a large-scale
> > Quantum Computer
> >       (and if so, when one might be implemented), but if it is, many of the
> > cryptographic algorithms
> >       and protocols currently in use would be insecure.
> > 
> > Or are you suggesting to rephrase the sentence completely? E.g.:
> > 
> >     Recent achievements in developing Quantum Computers (QC)
> > demonstrate that
> >     it is probably feasible to build a large scale QC. If such a QC is implemented,
> >     many of the cryptographic algorithms and protocols currently in use would
> > be insecure.
> 
> I'd suggest using the phrase "cryptographically significant Quantum Computer".  The problems that you find in cryptography do need more qubits than current Quantum Computers possess; however they also need to perform millions of operations without significant error, and that would appear to be a more serious hurdle.

This is the best suggestion I've heard so far, thanks.

> > 
> > > > >    would be compromised.  IKEv1 [RFC2409], when used with strong
> > > > >    preshared keys, is not vulnerable to quantum attacks, because those
> > > > >    keys are one of the inputs to the key derivation function.  If the
> > > > >    preshared key has sufficient entropy and the PRF, encryption and
> > > > >    authentication transforms are postquantum secure, then the resulting
> > > > >    system is believed to be quantum resistant, that is, invulnerable to
> > > > >    an attacker with a Quantum Computer.
> > > > >
> > > > > Do we have a reference for this "it is believed", or is it just
> > > > > the outcome of the WG discussions?
> > > >
> > > > I'll let my co-authors comment on this, but I think it is meant that
> > > > according to our best current knowledge nothing better than Grover's
> > > > algorithm can be used to break symmetric key cryptosystem with QC.
> > > > And Grover's algorithm only halves an effective key length, so if
> > > > longer PSK is used, we're safe (we believe we are).
> > >
> > > To be clear: I share this belief! :)
> > > I am just asking if it is sufficiently well-known/widespread that no
> > > reference is needed; that may well be the case.
> > 
> > I believe it is, but I again prefer someone more knowledgeable in QC than
> > myself to comment.
> 
> Breaking it down, we come up with four propositions:
> - Grover's attack would require a huge number of operations against a sufficiently long secret.
> - This huge number of operations is infeasible against any plausible operation.
> - Any attack better than Grovers would require attacking the function at a lower level than a black box
> - No such insight is known.
> 
> The first can easily be cited (e.g. the original Grover paper).  The second one is generally believed, but the exact length of the secret would depend on the eventual speed/scale of a quantum computer, which is somewhat unknown.
> The third is also citable (again, the original Grover paper).  The fourth is problematic, because it is essentially an argument from a lack of knowledge.
> 
> Personally, I believe that this sort of argument is well known enough (at least, to the people who know postquantum cryptography) that it would not be required.

I've heard enough people say this that I'm convinced.

Thanks for having the discussion!

-Ben