Subject: [IPsec] Quantum Resistance Requirements

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Thu, 11 Aug 2016 22:00:40 +0000

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.

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

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

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

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

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

-          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?

Thanks!

---

From: Michael Richardson <[email-masked]>
Date: Fri, 12 Aug 2016 10:12:38 -0400

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

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

    > 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 might be too big a red flag.

--
Michael Richardson <[email-masked]>, Sandelman Software Works
 -= IPv6 IoT consulting =-

---

From: Yaron Sheffer <[email-masked]>
Date: Fri, 12 Aug 2016 16:33:23 +0200

> I.e. even the use of these extensions might be too big a red flag.

I really don't like the idea of a mandatory rekey to use these 
extensions, for two reasons:

- This smells too much like SSL renegotiation, with issues like 
QR-security of the original SA vs. the new SA coming up.

- I am sure a passive observer can distinguish an immediate rekey from 
normal IPsec traffic, just using packet lengths and timing. So the red 
flag is still there.

Thanks,
	Yaron

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Fri, 12 Aug 2016 16:41:46 +0000

> -----Original Message-----
> From: Michael Richardson [mailto:[email-masked]]
> Sent: Friday, August 12, 2016 10:13 AM
> To: Scott Fluhrer (sfluhrer)
> Cc: IPsecme WG ([email-masked])
> Subject: Re: [IPsec] Quantum Resistance Requirements
> 
> 

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.

</WildSpeculation>

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

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

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

Do we care if someone with a Quantum Computer can decrypt the IKE traffic?

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

Here's what I'm concerned with; Alice connects (from Starbucks) to Bob, using their jointly shared PPK.  Alice then goes to McDonald, then also connects to Bob, using their jointly shared PPK.  My question: are we concerned if someone listening into the IKE negotiations, could determine whether the PPK Alice used from Starbucks is the same as the one she used from McDonalds (and from that, deduce that it's likely that the same person was at both Starbucks and McDonalds)?

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

That brings up another potential requirement (although I'm not certain how to express it); something like "how important is it to avoid the problems that IKEv1 had with preshared keys" (although a correct statement of the requirement would list exactly what problems we're seeking to avoid)

> I.e. even the use of these extensions might be too big a red flag.

Another potential requirement: do we care if someone listening in can determine whether we're using this extension?

---

From: Tommy Pauly <[email-masked]>
Date: Fri, 12 Aug 2016 17:45:36 -0700

Hi Scott,

Great list! Responses inline.

Best,
Tommy

> On Aug 11, 2016, at 3:00 PM, Scott Fluhrer (sfluhrer) <[email-masked]> 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:
>  
> 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.

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

> 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?

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

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

> 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.
> 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.
> 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…

I generally agree with Scott on these points.

>  
> 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?
>  
> Thanks!
> _______________________________________________
> IPsec mailing list
> [email-masked] <mailto:[email-masked]>
> https://www.ietf.org/mailman/listinfo/ipsec <https://www.ietf.org/mailman/listinfo/ipsec>

---

From: Tero Kivinen <[email-masked]>
Date: Fri, 19 Aug 2016 15:45:04 +0300

Scott Fluhrer (sfluhrer) writes:
> 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.
-- 
[email-masked]

---

From: "Valery Smyslov" <[email-masked]>
Date: Wed, 24 Aug 2016 20:08:00 +0300

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.

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.

This is important.

            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.

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

            No strong opinion here. 

            Again, no strong opinion here.

            It would be nice if authentication is protected also. At least to some extent (by the way, the curent

            draft seems to achive that, because the SKEYSEED is dependant on the PPK, so any authentication

            method would be "augmented" by PPK).

            I think it is important. I don't buy the argument that the solution is intended to be temporary,

            so we can sacrifice the algorith agility. As far as I understand the situation with "persistent"

            solution is currently very moot, so it is unpredictable for how long this "temporary" solution

            will be in use. Probably it is 1-2 years, probably it is 10-20 years. I definitely don't want

            to have a 20-year long solution without algorithm agility.

      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.

  Thanks!

Regards,

Valery.

------------------------------------------------------------------------------

  _______________________________________________
  IPsec mailing list
  [email-masked]
  https://www.ietf.org/mailman/listinfo/ipsec