Re: [IPsec] Quantum Resistance Requirements

[Garcia Morchon O, Oscar]

Hi Scott,

this is a very interesting approach.
Please, find below my feedback.

Kind regards, Oscar.

From: IPsec [mailto:ipsec-boun...@ietf.org] On Behalf Of Scott Fluhrer 
(sfluhrer)
Sent: Tuesday, September 06, 2016 5:10 PM
To: IPsecme WG (ipsec@ietf.org)
Subject: Re: [IPsec] Quantum Resistance Requirements

Last month, I listed a series of potential requirements for a shortterm Quantum 
Resistance solution; several people have commented on these requirements, and 
here are the votes so far (omitting the "no opinion" votes); I've listed the 
voters chiefly so that if I mischaracterized their votes, they can correct me:

From: Scott Fluhrer (sfluhrer)
Sent: Thursday, August 11, 2016 6:01 PM
To: IPsecme WG (ipsec@ietf.org<mailto:ipsec@ietf.org>)
Subject: Quantum Resistance Requirements



-  Simplicity; how large of a change to IKE (and IKE implementations) 
are we willing to contemplate?
Scott Fluhrer: very important
Michael Richardson: very important
Tommy Pauly: very important
Valery Smyslov: not as important as other issues
Oscar Garcia-Morchon: very important.


o   My opinion: minimizing changes to IKE should be given high priority, both 
because "complexity is the enemy of security" and this is a short term 
solution; if we have a solution that we can't implement in a few years, well, 
we might as well wait for the crypto people to give us the long term one.


-  Preserving existing IKE security properties?
Scott Fluhrer: very important
Michael Richardson: very important
Tommy Pauly: very important
Valery Smyslov: important
Oscar Garcia-Morchon: very important.


-  What do we feel needs to protected from someone with a Quantum 
Computer?  Do we feel  the need to protect only the IPsec traffic, or do we 
need to protect the IKE traffic as well.
Tommy Pauly: not clear if IKE traffic needs to be protected.
Valery Smylsov: important
Oscar Garcia-Morchon: it seems to me that IPsec traffic is the most important 
one. If IKE traffic could be easily protected as well, this would be a nice 
addition.


-  What level of identity protection do we need to provide?  If two 
different IKE negotiations use the same shared secret, do we mind if someone 
can deduce that?
Scott Fluhrer: not important
Michael Richardson: very important
Tommy Pauly: not important
Valery Smylsov: this is a nice to have, but not critical
Oscar Garcia-Morchon: this is less important, in particular if we only protect 
the IPsec traffic.


-   PPK management; how much support do we provide for automatically 
managing the secrets?
Scott Fluhrer: not important
Tommy Pauly: not important
Oscar Garcia-Morchon: not important.


-  How much support do we provide for nonstatic secrets, for example, 
by QKD, or via something like HIMMO (a key distribution mechanism that appears 
to be post quantum)?
Scott Fluhrer: not important
Michael Richardson: not important
Tommy Pauly: not important
Oscar Garcia-Morchon: not important at this stage, but it is very important to 
have hook to easily support this capability in the future.


-  Authentication; if someone with a Quantum Computer can break the DH 
in real time, do we care if he can act as a man-in-the-middle?
Scott Fluhrer: not important
Michael Richardson: important, provided that we don't run into the same issues 
that IKEv1 PSKs ran into
Tommy Pauly: not important
Valery Smylsov: this would be nice to have
Oscar Garcia-Morchon: less important, but nice to have and it could be easily 
supported with little effort.


-  Algorithm agility; how important is it that we negotiate any 
cryptoprimitives involved?
Scott Fluhrer: not important
Tommy Pauly: not important
Valery Smylsov: important
Oscar Garcia-Morchon: less important.





The information contained in this message may be confidential and legally 
protected under applicable law. The message is intended solely for the 
addressee(s). If you are not the intended recipient, you are hereby notified 
that any use, forwarding, dissemination, or reproduction of this message is 
strictly prohibited and may be unlawful. If you are not the intended recipient, 
please contact the sender by return e-mail and destroy all copies of the 
original message.
___
IPsec mailing list
IPsec@ietf.org
https://www.ietf.org/mailman/listinfo/ipsec

Re: [IPsec] Quantum Resistance Requirements

[Scott Fluhrer (sfluhrer)]

Last month, I listed a series of potential requirements for a shortterm Quantum 
Resistance solution; several people have commented on these requirements, and 
here are the votes so far (omitting the "no opinion" votes); I've listed the 
voters chiefly so that if I mischaracterized their votes, they can correct me:

From: Scott Fluhrer (sfluhrer)
Sent: Thursday, August 11, 2016 6:01 PM
To: IPsecme WG (ipsec@ietf.org)
Subject: Quantum Resistance Requirements



-  Simplicity; how large of a change to IKE (and IKE implementations) 
are we willing to contemplate?
Scott Fluhrer: very important
Michael Richardson: very important
Tommy Pauly: very important
Valery Smyslov: not as important as other issues


o   My opinion: minimizing changes to IKE should be given high priority, both 
because "complexity is the enemy of security" and this is a short term 
solution; if we have a solution that we can't implement in a few years, well, 
we might as well wait for the crypto people to give us the long term one.


-  Preserving existing IKE security properties?
Scott Fluhrer: very important
Michael Richardson: very important
Tommy Pauly: very important
Valery Smyslov: important





-  What do we feel needs to protected from someone with a Quantum 
Computer?  Do we feel  the need to protect only the IPsec traffic, or do we 
need to protect the IKE traffic as well.
Tommy Pauly: not clear if IKE traffic needs to be protected.
Valery Smylsov: important



-  What level of identity protection do we need to provide?  If two 
different IKE negotiations use the same shared secret, do we mind if someone 
can deduce that?
Scott Fluhrer: not important
Michael Richardson: very important
Tommy Pauly: not important
Valery Smylsov: this is a nice to have, but not critical



-   PPK management; how much support do we provide for automatically 
managing the secrets?
Scott Fluhrer: not important
Tommy Pauly: not important



-  How much support do we provide for nonstatic secrets, for example, 
by QKD, or via something like HIMMO (a key distribution mechanism that appears 
to be post quantum)?
Scott Fluhrer: not important
Michael Richardson: not important
Tommy Pauly: not important



-  Authentication; if someone with a Quantum Computer can break the DH 
in real time, do we care if he can act as a man-in-the-middle?
Scott Fluhrer: not important
Michael Richardson: important, provided that we don't run into the same issues 
that IKEv1 PSKs ran into
Tommy Pauly: not important
Valery Smylsov: this would be nice to have



-  Algorithm agility; how important is it that we negotiate any 
cryptoprimitives involved?
Scott Fluhrer: not important
Tommy Pauly: not important
Valery Smylsov: important



___
IPsec mailing list
IPsec@ietf.org
https://www.ietf.org/mailman/listinfo/ipsec

Re: [IPsec] Quantum Resistance Requirements

[Valery Smyslov]

Hi Scott,

thank you for the list of requirements. My answers are inline.
  In Berlin, we decided to take up Quantum Resistance as a work item, and that 
we should start talking about requirements.  I'm starting this thread in a hope 
of kicking off the discussion.

   

  First of all, a solution to Quantum Resistance that is applicable everywhere 
would involve replacing the (EC)DH exchange with a postquantum key exchange.  
While this would be ideal, the cryptographical community currently doesn't have 
a solution that is sufficiently trusted and is of reasonable cost.  So, it 
would make sense to divide this into two efforts, a long term solution (which 
we may initially put on the shelf, as the crypto pieces aren't there yet), and 
a short term solution, to address the needs of customers that aren't willing to 
wait; instead, they feel the need to protect traffic that is encrypted now.  
For this short term solution, it's sufficient if we don't necessarily cover all 
cases, a number of interesting cases (in particular, ones for which 
redistributing secrets is doable) would be sufficient.  Does everyone agree 
with that general assessment?

   

  If so, there here is a list of potential requirements (based on Tero's list 
that he gave during the IETF, but with a few of my own), along with my opinion:

   

  -  Simplicity; how large of a change to IKE (and IKE implementations) 
are we willing to contemplate?

Of course it is preferrable if the solution is simple. However, the simplicity 
is difficult to measure,

so it is mostly subjective. I would put the simplicity closer to the end of the 
list of requirements.

In other words - our goal is to provide a (temporary) QC-resistant solution. If 
we manage to 

get it simple - then it's good.

  o   My opinion: minimizing changes to IKE should be given high priority, 
both because "complexity is the enemy of security" and this is a short term 
solution; if we have a solution that we can't implement in a few years, 
well, we might as well wait for the crypto people to give us the long term one.

  -  Preserving existing IKE properties; how important is it that 
our solution do not induce any weaknesses in IKE against an adversary with a 
convention computer; that is, whatever we do, we must not make things 
worse?

This is important.

  o   My opinion: I'm pretty sure that we'll all agree that this is important 
(except for possibly the identity protection, see below); I just want to state 
this as something we need to remember.

  -  What do we feel needs to protected from someone with a Quantum 
Computer?  Do we feel  the need to protect only the IPsec traffic, or do we 
need to protect the IKE traffic as well.

This requirement is related to the previous one. If we we want to 
preserve existing IKE properties.

then we should provide the solution that protects both IPsec and 
IKE traffic. And I think it is important

that IKE traffic is protected. It will allow to re-use this 
solution in G-IKEv2 protocol without the need

to re-invent it.

  o   My opinion: I'm going to abstain on this one, except to note that 
protecting only the IPsec traffic allows for a rather simple implementation; 
now, if the WG decides that protecting the IKE traffic is important, 
this simplicity is irrelevant.

  -  What level of identity protection do we need to provide?  If two 
different IKE negotiations use the same shared secret, do we mind if someone 
can deduce that?

I think the ID protection is a nice thing to have, but I won't 
consider it as the first proirity requirement.

  o   My opinion: identity protection in IKE is rather overrated; I suspect 
there's enough in the data exchange that an advanced adversary (how can look at 
things such as packet length and packet timings) is likely to get a fairly 
decent guess regardless.

  -   PPK management; how much support do we provide for automatically 
managing the secrets?

No strong opinion here. 

  o   My opinion: we already have preshared keys in IKE, and we don't 
define any particular management scheme for them (even though they are used 
quite often in practice).  I don't see why we need to go out of our way when it 
comes to these postquantum secrets.

  -  How much support do we provide for nonstatic secrets, for example, 
by QKD, or via something like HIMMO (a key distribution mechanism that appears 
to be post quantum)?

Again, no strong opinion here.

  o   My opinion: I'd prefer it if we didn't spend a great deal of time 
trying to come up with a solution that covers everything.  However, if we could 
include a hook that these schemes could take advantage of (such as an 
opaque identifier that's passed that has meaning to the PPK manager), that 
might be reasonable.

  -  Authentication; if someone with 

Re: [IPsec] Quantum Resistance Requirements

[Tero Kivinen]

Scott Fluhrer (sfluhrer) writes:
> > Or could we introduce some things now that would make "dropping in" a
> > replacement easier?
> 
> Nothing comes to mind; according to the above wild speculation, the
> difficulties that people are likely to encounter are more to do with
> the implementations, and less with the protocol.
> 
> Actually, there are some interesting postquantum protocols (e.g.
> McEliece) which look good, except that they have massively large key
> shares.  I've considered them impractical; however if there was
> something easy we could do to make those more practical, that may
> help.  I'm not suggesting that we do; you just asked if there was
> anything we might do that would help...

Combining those two above, i.e., some postquantum protocols require
too big packets so they are not usable in IKE context directly, but
they do generate out some kind of shared secret which can be used to
derive keys, we might implement our drop in postquantum protcols in
way where the postquantum protocol is run outside the IKE context, and
it just generates the shared secret to be used in the IKE.

I.e., now we have shared PPK configured in and used in the KDF. After
postquantum protocols are there, instead of having preconfigured
shared PPK, we first run the postquantum protocol over some other
channel (over tcp? or something, if it requires big packets etc), and
the output of that process is the shared PPK we can use for IKE, just
like our short term solution uses.

I.e., if the postquantum protocols are going to be something that
mimics Diffie-Hellman in away that they provide some shared secret we
can mix in to KDF then we should be able to use that output with our
short term PPK solution too.
-- 
kivi...@iki.fi

___
IPsec mailing list
IPsec@ietf.org
https://www.ietf.org/mailman/listinfo/ipsec

Re: [IPsec] Quantum Resistance Requirements

[Tommy Pauly]

Hi Scott,

Great list! Responses inline.

Best,
Tommy


> On Aug 11, 2016, at 3:00 PM, Scott Fluhrer (sfluhrer)  
> wrote:
> 
> In Berlin, we decided to take up Quantum Resistance as a work item, and that 
> we should start talking about requirements.  I’m starting this thread in a 
> hope of kicking off the discussion.
>  
> First of all, a solution to Quantum Resistance that is applicable everywhere 
> would involve replacing the (EC)DH exchange with a postquantum key exchange.  
> While this would be ideal, the cryptographical community currently doesn’t 
> have a solution that is sufficiently trusted and is of reasonable cost.  So, 
> it would make sense to divide this into two efforts, a long term solution 
> (which we may initially put on the shelf, as the crypto pieces aren’t there 
> yet), and a short term solution, to address the needs of customers that 
> aren’t willing to wait; instead, they feel the need to protect traffic that 
> is encrypted now.  For this short term solution, it’s sufficient if we don’t 
> necessarily cover all cases, a number of interesting cases (in particular, 
> ones for which redistributing secrets is doable) would be sufficient.  Does 
> everyone agree with that general assessment?
>  
> If so, there here is a list of potential requirements (based on Tero’s list 
> that he gave during the IETF, but with a few of my own), along with my 
> opinion:
>  
> -  Simplicity; how large of a change to IKE (and IKE implementations) 
> are we willing to contemplate?
> o   My opinion: minimizing changes to IKE should be given high priority, both 
> because “complexity is the enemy of security” and this is a short term 
> solution; if we have a solution that we can’t implement in a few years, well, 
> we might as well wait for the crypto people to give us the long term one.

Simplicity is definitely crucial to whatever solution we choose, and I think 
the current proposal of a pre shared key that gets mixed into the crypto is the 
simplest option we have now without really knowing what true QR algorithms will 
entail for IKE.

> -  Preserving existing IKE properties; how important is it that our 
> solution do not induce any weaknesses in IKE against an adversary with a 
> convention computer; that is, whatever we do, we must not make things worse?
> o   My opinion: I’m pretty sure that we’ll all agree that this is important 
> (except for possibly the identity protection, see below); I just want to 
> state this as something we need to remember.

Definitely important. 

> -  What do we feel needs to protected from someone with a Quantum 
> Computer?  Do we feel  the need to protect only the IPsec traffic, or do we 
> need to protect the IKE traffic as well.
> o   My opinion: I’m going to abstain on this one, except to note that 
> protecting only the IPsec traffic allows for a rather simple implementation; 
> now, if the WG decides that protecting the IKE traffic is important, this 
> simplicity is irrelevant.

My first reaction would be to focus on the IPSec traffic, which is clearly 
important. It's not clear yet if IKE being protected is useful; exactly how 
much more complicated will the exchange be, and is it worth it?

> -  What level of identity protection do we need to provide?  If two 
> different IKE negotiations use the same shared secret, do we mind if someone 
> can deduce that?
> o   My opinion: identity protection in IKE is rather overrated; I suspect 
> there’s enough in the data exchange that an advanced adversary (how can look 
> at things such as packet length and packet timings) is likely to get a fairly 
> decent guess regardless.

I agree that the aspect of identity protection is already a bit of a lost cause 
for this, and the new key will not significantly worsen the situation.


> -   PPK management; how much support do we provide for automatically 
> managing the secrets?
> o   My opinion: we already have preshared keys in IKE, and we don’t define 
> any particular management scheme for them (even though they are used quite 
> often in practice).  I don’t see why we need to go out of our way when it 
> comes to these postquantum secrets.

The management seems like a separate issue for deployments to figure out. I can 
imagine guidelines being published later, but let's just get the crypto spec 
out first.

> -  How much support do we provide for nonstatic secrets, for example, 
> by QKD, or via something like HIMMO (a key distribution mechanism that 
> appears to be post quantum)?
> o   My opinion: I’d prefer it if we didn’t spend a great deal of time trying 
> to come up with a solution that covers everything.  However, if we could 
> include a hook that these schemes could take advantage of (such as an opaque 
> identifier that’s passed that has meaning to the PPK manager), that might be 
> reasonable.
> -  Authentication; if someone with a Quantum Computer can break the 
> DH 

Re: [IPsec] Quantum Resistance Requirements

[Scott Fluhrer (sfluhrer)]

> -Original Message-
> From: Michael Richardson [mailto:mcr+i...@sandelman.ca]
> Sent: Friday, August 12, 2016 10:13 AM
> To: Scott Fluhrer (sfluhrer)
> Cc: IPsecme WG (ipsec@ietf.org)
> Subject: Re: [IPsec] Quantum Resistance Requirements
> 
> 
> Scott Fluhrer (sfluhrer) <sfluh...@cisco.com> wrote:
> > - Simplicity; how large of a change to IKE (and IKE implementations)
> > are we willing to contemplate?
> 
> > o My opinion: minimizing changes to IKE should be given high priority,
> > both because “complexity is the enemy of security” and this is a short
> > term solution; if we have a solution that we can’t implement in a few
> > years, well, we might as well wait for the crypto people to give us the
> > long term one.
> 
> Still, I'd like to know what the properties are of the cryptographically long
> term solution.It seems to me, having read your email and a few of the
> documents that the long-term solutions are architecturally least disruptive,
> and the short-term "hacks" are more disruptive.
> 
> Is this a fair characterisation?

Since we don't have a long term solution in hand, to answer that would require 
speculation; if I do indulge in that, I'd have to say that it's a bit on the 
murky side

As I mentioned earlier, the "long term" solution would be to define another 
"Diffie-Hellman group", which is not really DH at all (or at least, not only 
DH), but includes some other key exchange protocol; the group is negotiated 
just like any other group, and the initiator sends its KE payload, the 
responder sends its KE payload, and both sides generate the shared secret.  So, 
at a protocol level, everything remains essentially the same (and the protocol 
always makes it clear for each KE payload whether it's an initiator KE payload, 
or a response (and if it's a response, which KE payload it's in response to).

However, at an implementation level, that's not necessarily as clean.  I've 
gone through a number of (believed) postquantum key exchanges; one thing I have 
noticed is those protocols are all asymmetric in some way.  With (EC)DH, both 
sides do exactly the same thing; each side picks a secret value 'x', computes 
'g**x', and that's its KE value; it receives the 'g**y' KE payload, and after 
optionally validating it, computes the shared secret in a uniform manner.  This 
symmetry is not there in any postquantum key exchange I've looked at:

- With LWE-based key exchanges, both sides select a secret value and an error 
vector; however the responder also sends some additional data along to the 
initiator ("masking bits") which allow both sides to derive the same secret 
(even though both sides add random error vectors); this additional data needs 
to be computed in response to the initiator's KE payload, which implies that 
(unlike DH) the responder's crypto code needs access to the initiator's KE 
payload when generating its KE payload

- There are a number of schemes that are really public key encryption methods; 
the initiator's KE payload really is a public encryption key, and the 
responder's KE payload is a random value encrypted with that public key.  This 
works just fine; however it is obviously asymmetric.

- The closest to true symmetry I've come across is Supersingular EC Isogeny; 
there, both side's KE payload can be produced without access to the other 
side's KE payload.  On the other hand, both sides necessarily need to be in 
distinct roles (the references I've seen called them the "Alice" and "Bob" 
role), and so the responder's crypto code needs to know that it's acting as a 
responder.

My take-away from this speculation; while it's quite clean from the protocol 
perspective, it might not end up being quite clean from the implementation 
perspective, especially if the assumption that we can generate a key share 
without reference to much else (which is true with DH) is buried fairly deep in 
the implementation.  On the other hand, if the responder implementation has a 
single 'here's a KE payload, generate a response KE payload and the shared 
secret' primitive, it might not be that bad.



As for the disruptiveness of the short term idea, well, from a crypto 
perspective, it's actually fairly clean; once we have the secret, we stir that 
as an input to the KDF, and we're good; what's actually disruptive is the 
negotiation of the secret (are we using a secret with this negoatiion?  If so, 
which one?); if we go with the idea that only the IPsec SAs need to be QR, then 
when we compute the KDF for the IPsec SAs, we know the other side's identity, 
and so that would be rather straight-forward.



> 
> Or could we introduce some things now that would make "dropping in" a
> replacement easier?

Nothing comes to mind; according to the above wild speculation, the 

Re: [IPsec] Quantum Resistance Requirements

[Michael Richardson]

Scott Fluhrer (sfluhrer)  wrote:
> - Simplicity; how large of a change to IKE (and IKE implementations)
> are we willing to contemplate?

> o My opinion: minimizing changes to IKE should be given high priority,
> both because “complexity is the enemy of security” and this is a short
> term solution; if we have a solution that we can’t implement in a few
> years, well, we might as well wait for the crypto people to give us the
> long term one.

Still, I'd like to know what the properties are of the cryptographically long
term solution.It seems to me, having read your email and a few of the
documents that the long-term solutions are architecturally least disruptive,
and the short-term "hacks" are more disruptive.

Is this a fair characterisation?

Or could we introduce some things now that would make "dropping in" a
replacement easier?

> - Preserving existing IKE properties; how important is it that our
> solution do not induce any weaknesses in IKE against an adversary with
> a convention computer; that is, whatever we do, we must not make things
> worse?

> o My opinion: I’m pretty sure that we’ll all agree that this is
> important (except for possibly the identity protection, see below); I
> just want to state this as something we need to remember.

Yes, very very important.

> - What do we feel needs to protected from someone with a Quantum
> Computer? Do we feel the need to protect only the IPsec traffic, or do
> we need to protect the IKE traffic as well.

> o My opinion: I’m going to abstain on this one, except to note that
> protecting only the IPsec traffic allows for a rather simple
> implementation; now, if the WG decides that protecting the IKE traffic
> is important, this simplicity is irrelevant.

I think it depends upon what the affect on the IKE traffic is.

> - What level of identity protection do we need to provide? If two
> different IKE negotiations use the same shared secret, do we mind if
> someone can deduce that?

> o My opinion: identity protection in IKE is rather overrated; I suspect
> there’s enough in the data exchange that an advanced adversary (how can
> look at things such as packet length and packet timings) is likely to
> get a fairly decent guess regardless.

I think you didn't answer the question you posed.
You asked, "different IKE negotiations use the same shared secret, do we mind if
   someone can deduce that?"

which I don't think it strictly about identity protection.
I also think that leaking the identity of a mobile end point effectively
could be painting a target on them.  Consider how much effort is going into
IPv6 privacy extensions.

> - PPK management; how much support do we provide for automatically
> managing the secrets?

> o My opinion: we already have preshared keys in IKE, and we don’t
> define any particular management scheme for them (even though they are
> used quite often in practice). I don’t see why we need to go out of our
> way when it comes to these postquantum secrets.

> - How much support do we provide for nonstatic secrets, for example, by
> QKD, or via something like HIMMO (a key distribution mechanism that
> appears to be post quantum)?

> o My opinion: I’d prefer it if we didn’t spend a great deal of time
> trying to come up with a solution that covers everything. However, if
> we could include a hook that these schemes could take advantage of
> (such as an opaque identifier that’s passed that has meaning to the PPK
> manager), that might be reasonable.

Yes, I agree.

> - Authentication; if someone with a Quantum Computer can break the DH
> in real time, do we care if he can act as a man-in-the-middle?

> o My opinion: this draft is here mainly to protect
> ‘store-and-decrypt-later’ attacks, and so this attack isn’t as large of
> a concern. On the other hand, we may very well get this for free; if we
> include our ‘post quantum secret’ as an input to the KDF, then an
> active attacker is foiled just like a passive attacker.

I think that this is important, if we can do it without getting into IKEv1
PSK stupids.

> - Algorithm agility; how important is it that we negotiate any
> cryptoprimitives involved?

> o My opinion: this is of lesser importance, as this is a short term
> solution. On the other hand, I am quite aware that others on this list
> would disagree with me…

> Well, here’s my list of requirements (and my opinions); did I miss any
> requirement that you think is important? What are you opinions about
> these requirements?

We have to be able to negotiate to use of these extensions.
I want to suggest something further: that we might want to negotiate use of
some of these extensions as a *rekey* of a "conventional" IKEv2 PARENT.
I.e. even the use of these extensions