Subject: Re: [IPsec] Proposed method to achieve quantum resistant IKEv2

From: "Bruckert, Leonie" <[email-masked]>
Date: Tue, 5 Sep 2017 06:38:01 +0000

Hi,

First, I want to emphasize that we (that is secunet) are highly interested in this topic. Note that we already contributed to the discussion in Prague (Kai Martius had a 5 minute slot).

So what do we expect from a combined key exchange? I listed some high priority issues which I assume we all agree on:

- Protection against future quantum attackers
- Agility (allow multiple quantum resistant algorithms in combination)
- Maintaining security properties of IKEv2
- Backwards compatibility
- Ability to process messages larger than 1500 Byte

Additionally, it would be nice to also protect the identities i.e. to make the AUTH exchange quantum resistant. Particularly with regard to the PPK draft which doesn’t assure this.

I’d like to draw the attention to another aspect associated to the NIST standardization efforts and the assignment of IDs for post quantum algorithms. At present people refuse to specify post quantum algorithms and assign IDs officially – and they’re justified in doing so, because these algorithms are not sufficiently analyzed. On the other hand we somehow need to address the PQ algorithms now. How can we break the vicious circle? Temporarily provide IDs and adjust them later? Or just let the user assign IDs individually in the range that is reserved for private use? 

Just imagine, NIST standardizes a set of well-studied PQ algorithms at some day within the next 5 - 7 years. From that day forward there will be no need for a combined key exchange anymore and it should be possible to use PQ algorithms in IKEv2. But it’s likely that many implementations won’t be upgraded to perform a combined key exchange until then, so designing a post quantum IKEv2 while guaranteeing backwards compatibility to two former versions would be the new challenge. 
So I think we should modify IKEv2 in a way that not only offers a combined key exchange, but also allows the transition from combined modes to the solely use of PQ algorithms. I’m aware that this is a difficult task and might possibly not be solvable at all. However, the anticipated short period of use of a combined key exchange demands a fast solution.

I support Scott’s approach to dynamically assign unused IDs. I came up with a similar idea that makes use of (new) attributes but I think this one is simpler. 

As I understand the main drawback of introducing a new transform type and thus negotiating PQ algorithms in the SA payload is (besides compatibility issues) the fact that the key exchange is then limited to a combination of one classical method and one PQ method. Whereas Scott’s idea allows to combine multiple PQ algorithms.

Regards,
Leonie

-----Ursprüngliche Nachricht-----
Von: IPsec [mailto:[email-masked]] Im Auftrag von Scott Fluhrer (sfluhrer)
Gesendet: Dienstag, 22. August 2017 16:31
An: Cen Jung Tjhai; Valery Smyslov; 'Tero Kivinen'
Cc: [email-masked]
Betreff: Re: [IPsec] Proposed method to achieve quantum resistant IKEv2

> -----Original Message-----
> From: IPsec [mailto:[email-masked]] On Behalf Of Cen Jung Tjhai
> Sent: Tuesday, August 22, 2017 6:43 AM
> To: Valery Smyslov; 'Tero Kivinen'
> Cc: [email-masked]
> Subject: Re: [IPsec] Proposed method to achieve quantum resistant IKEv2
> 
> Hi
> 
> >> Well, that are valid reasons. However, what makes me uncomfortable is
> >> that this design looks like yet another short-term (or medium-term)
> >> solution. We already have
> >> draft-fluhrer-qr-ikev2 that was declared as a temporary short-term
> >> approach to countermeasure immediate threat until cryptography
> >> science gives us new well-studied QC-proof primitives to replace
> >> classic public key cryptography. Now it turns out that we don't have
> >> primitives we are certain in (at least for key exchange), so we
> >> decide to combine several different primitives (which we don't fully trust
> in) with classic DH. That's a valid approach for transition to PQ cryptography,
> but it doesn't look like long-term standard solution.
> 
> On our draft-00, one of the objectives is to deprecate DH key exchange in
> the long-term future. Hence, we thought it would be neater to introduce a
> new transform type and a new PQ key exchange payload (QSKE). The idea is
> that when people are happy to drop KE payloads, they can use QSKE
> payloads instead. Obviously, there are concerns with backward compatibility
> by introducing a new transform type, which I agree.

If we look at the general problem, I see that there are three subproblems that we need to solve:

1. How to introduce a postquantum key exchange to IKE

2. How to have the postquantum key exchange in addition to the classical (EC)DH (so that we can't make security worse)

3. How to handle the greater-than-MTU payloads that are likely to result

(and, of course, how to handle this all in a backwards-compatible way, which minimizes additional complexity, and which allows us to deprecate traditional DH Keyexchanges eventually).

Much of our discussion has been on #3 (which is, indeed, the hardest of the three), however I would like to discuss #1 and #2.

Draft-00 solves #1 by adding a new payload type; one issue with this is, because of the new transform type to negotiate it, existing IKE responders may be confused by it.  They do solve #2 for free (because it's in parallel with the existing KE payloads).

I would suggest a different way; instead of assigning a key payload type, we just issue new group descriptions for the postquantum key exchanges; the traditional 2048 MODP group is 14; we might make NewHope number 32.

One objection to this may to say "but, NewHope isn't a group"; actually, that's just terminology.  As far as the protocol is concerned, all these key exchanges do fundamentally the same thing; the initiator creates a payload and sends it to the responder; the responder then generates a payload and sends it to the initiator; both sides do some computation and create a shared secret (that someone in the middle cannot derive just seeing the payloads).  There are distinctions between the key exchanges (sometimes the intiiator's and responder's keyshares are of different lengths; sometimes the responder's keyshare is a function of the initiator's), but those are distinctions that the protocol doesn't have to care about.

I would argue that this minimizes complexity (the protocol parts of IKE implementations wouldn't have to change at all), and we have good backwards compatibility (as existing IKE implementations already know how to deal with groups they haven't heard of).  However, as it stands, it doesn't address #2 at all.

To solve that, I would suggest adding a way to exchange multiple groups in parallel (and have the shared secret depend on all of them); that way, we can perform both an ECDH (so we're at least as secure as now) and a NewHope exchange (so we have a potential to be secure against a quantum computer).  Ideally, we would be able to allow more than 2 (as some users might not want to trust just one of these new-fangled PQ key exchanges; it would be good if we could give them the option, without adding much complexity on our side).

Here is one possible way to do this; we assign group descriptions 0x7f00-0x7fff (the high end of the IANA unassigned list) to be dynamically assigned by the initiator.  That is, the initiator could include a notify that may specify "group 7f00 is really group 14 and group 32 concatinated", he can then include that within his policy (and the resulting key share would be the group 14 and the group 32 key share concatenated); the responder can either accept this, or reject it in favor of another proposal (just as the current IKE allows fallback to other DH groups).

The idea here is that we try to reuse as much of the existing KE protocol logic (and security logic) as possible; by reusing this logic, we avoid adding complexity, and we also rely on the same security logic that makes the current KE exchange safe.

So, in summary, this idea:

- Allows us to rely on postquantum key exchanges (once they have been defined and accepted)
- Allows us to also rely on traditional groups as well (so we don't make things worse)
- Is backwards compatible (in that someone proposing this to an unupgraded responder will react in the expected way; either downgrading the key exchange, or rejecting the key exchange, based on the initiator policy)
- Allows a clean way to deprecate traditional groups in the future
- Allows someone to rely on multiple postquantum key exchanges, should they be paranoid.
- Does all this while trying to minimize complexity (most of the changes in the implementation will be in the crypto engine and the policy handling; those would have to change in any such solution)

Thoughts?

Credit: this idea was worked out in conjunction with Oscar Garcia-Morchon, Zhenfei Zhang and William Whyte; this idea applied to TLS can be found in draft-whyte-qsh-tls13 

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

---

From: Tero Kivinen <[email-masked]>
Date: Tue, 5 Sep 2017 16:02:32 +0300

Bruckert, Leonie writes:
> Additionally, it would be nice to also protect the identities i.e.
> to make the AUTH exchange quantum resistant. Particularly with
> regard to the PPK draft which doesn’t assure this.

As we discussed earlier, some kind of pseudonym system might be better
for this, especially as it works also for traditional authentication
and Diffie-Hellman against active attacks (it does not work against
attackers who can break Diffie-Hellman for traditional DH).

I.e., in this case we do following exchange:

   Initiator                         Responder
   -------------------------------------------------------------------
   HDR, SAi1, KEi, Ni  -->
                                <--  HDR, SAr1, KEr, Nr, [CERTREQ]

   HDR, SK {IDi(ID_PSEUDONYM,PNi<n>),
       [CERT,] [CERTREQ,]
       AUTH, SAi2,
       TSi, TSr}  -->

                                <--  HDR, SK {IDr(ID_PSEUDONYM, PNr<m>),
                                         [CERT,] AUTH, 
                                         SAr2, TSi, TSr}

And after that we do pseudonym update exchange:

   HDR, SK {N(UPDATE_PSEUDONYM, PNi<n+1>)} ->

   	   			<-- HDR, SK {}

I.e., client will use completely random identity PNi<n> (for example
"SeDOELWhkvX03Xt1s9nh9g") and every time it suspects that identity
might have leaked (i.e., it gets authentication failure, or IKE_AUTH
times out, meaning there might have been active attacker on the link),
it will update the pseudonym to new one.

If we want to make it more complicated we could support multiple
pseudonyms for the client, i.e., make pseudonym update work as
follows:

   HDR, SK {N(CLEAR_PSEUDONUMS),
   	    N(ADD_PSEUDONYM, PNi<n+1>),
   	    N(ADD_PSEUDONYM, PNi<n+2>),
   	    N(ADD_PSEUDONYM, PNi<n+3>)} ->

   	   			<-- HDR, SK {}

And server will associate those new pseudonyms to the same client
until it does CLEAR_PSEUDONUMS again. 

> I’d like to draw the attention to another aspect associated to the
> NIST standardization efforts and the assignment of IDs for post
> quantum algorithms. At present people refuse to specify post quantum
> algorithms and assign IDs officially – and they’re justified in
> doing so, because these algorithms are not sufficiently analyzed. On
> the other hand we somehow need to address the PQ algorithms now. How
> can we break the vicious circle? Temporarily provide IDs and adjust
> them later? Or just let the user assign IDs individually in the
> range that is reserved for private use?  

It depends what IDs you need. Most of the IDs in the IKEv2 are expert
review, so you do not necessarely need any document to get one ID, but
as an expert, I will usually require some kind of stable reference.

On the other hand we do have interested people working on this in the
IPsecME WG, so I think we should just wait for that work to either
finish, or to die out because of lack of interest. 

> Just imagine, NIST standardizes a set of well-studied PQ algorithms
> at some day within the next 5 - 7 years. From that day forward there
> will be no need for a combined key exchange anymore and it should be
> possible to use PQ algorithms in IKEv2. But it’s likely that many
> implementations won’t be upgraded to perform a combined key exchange
> until then, so designing a post quantum IKEv2 while guaranteeing
> backwards compatibility to two former versions would be the new
> challenge.

Quite a lot of people are still using IKEv1, and IKEv2 RFC was
published 2005, and IKEv1 has been obsoleted since...

So it will take decade or two until people start updating their
implementations... :-(

> So I think we should modify IKEv2 in a way that not only offers a
> combined key exchange, but also allows the transition from combined
> modes to the solely use of PQ algorithms. I’m aware that this is a
> difficult task and might possibly not be solvable at all. However,
> the anticipated short period of use of a combined key exchange
> demands a fast solution. 

I think that is something we should aim for, and I do not think it is
impossible task to make. The tradeoffs are more in the case how badly
will broken old IKEv2 implementations break when we define that
extension... 

> I support Scott’s approach to dynamically assign unused IDs. I came
> up with a similar idea that makes use of (new) attributes but I
> think this one is simpler.  

I think that is hack and we should aim for more generic and cleaner
solution. Nobody will be adding support for the PQ algorithms without
heavily modifying the code, thus adding new exchanges or changing the
IKE_AUTH payloads is something we can do. We should try to keep
IKE_SA_INIT compatible as much as possible, and hopefully negotiate
the use of the new features there, so we can be backwards compatible
with old implementations.

I mean if we are going to transfer several tens of kilobytes or even
megabytes of keys inside IKE, adding one more round trip in that case
is no longer an issue... 

> As I understand the main drawback of introducing a new transform
> type and thus negotiating PQ algorithms in the SA payload is
> (besides compatibility issues) the fact that the key exchange is
> then limited to a combination of one classical method and one PQ
> method. Whereas Scott’s idea allows to combine multiple PQ
> algorithms.

Or we can just negotiate the traditional stuff in SA, and use notify
to tell that we support PQ, and if we do support PQ, we do the
intermediate exchange between IKE_SA_INIT and IKE_AUTH and exchange
our PQ stuff there, and do the negotiation of what kind of algorithms
we use there.

Making magic things with transform IDs might look like easy hack, but
usually that will just cause more issues in long run, and might
generate more code than making bigger, but cleaner change.
-- 
[email-masked]

---

From: "Graham Bartlett (grbartle)" <[email-masked]>
Date: Wed, 27 Sep 2017 20:04:41 +0000

Hi Michael

Is the main rational for not having fragmentation in IKE_SA_INIT that it could break the features of IKE that you list below?

The reason I ask, we’re working on the current draft and looking to implement optional fragmentation in the IKE_SA_INIT, but this would be friendly to cookies, TCP encaps, NAT-T etc

cheers

On 09/08/2017, 19:00, "IPsec on behalf of Michael Richardson" <[email-masked] on behalf of [email-masked]> wrote:

    I agree.  All of the DoS (cookie, etc.) defense and switch to TCP, and
    detection of NAT-T, etc. is in the IKE_SA_INIT, and so doing any kind of
    framentation in IKE_SA_INIT is a bad idea.

---

From: Michael Richardson <[email-masked]>
Date: Thu, 28 Sep 2017 12:18:24 -0400

Graham Bartlett (grbartle) <[email-masked]> wrote:
    > Is the main rational for not having fragmentation in IKE_SA_INIT that
    > it could break the features of IKE that you list below?

1) we are currently working on IKE over TCP because we already know that
   IKE packets (and UDP encapsulated IPsec) are not get through.  Adding
   IP fragmentation to the process will just make it worse.

   Adding IP-level fragmentation to the process adds additional state to the
   gateway, often hidden to the IKE daemon itself.

   Adding IKE-level fragmentation to the process adds an additional place
   that DDoS attacks can hit.

   So, one would have to have some mechanism to know what would get through,
   and if to switch to TCP, etc. before even trying.

    > The reason I ask, we’re working on the current draft and looking to
    > implement optional fragmentation in the IKE_SA_INIT, but this would be
    > friendly to cookies, TCP encaps, NAT-T etc

2) I think it's not possible to do fragmentation on IKE_SA_INIT (and any
   level) without opening up gateways up for DDoS attacks.
   So, don't do it in IKE_SA_INIT in my opinion.

If you you want to do something, then it needs to be a new state between
IKE_SA_INIT and IKE_AUTH.

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

---

From: "Valery Smyslov" <[email-masked]>
Date: Fri, 29 Sep 2017 15:58:24 +0300

Hi Michael,

>    gateway, often hidden to the IKE daemon itself.

That's true and that's one of the reason to avoid it by all means 
(the other and probably even more important reason - crippled
middleboxes that don't pass UDP fragments through).

>    that DDoS attacks can hit.

We have DDoS protection mechanisms. I think it's possible to define 
IKE_SA_INIT fragmentation so that these mechanisms be still able to work.

>    and if to switch to TCP, etc. before even trying.

TCP has a lot of shortcomings. It's a last resort.

>    So, don't do it in IKE_SA_INIT in my opinion.

Repeating myself - I don't think it is impossible to define IKE_SA_INIT
fragmentation in such a way, that it won't weaken IKE DDoS protection.
There are two obstacles in my opinion.

1) Complexity. The exchange would most likely become overly complex
and even very unusual comparing to other exchanges (e.g. it is possible to 
acknowledge each fragment individually, this way a better DDoS protection
can be achieved,  but this is non-standard  behavior for IKE and could open 
its own can of worms).

2). Backward compatibility. It's difficult to negotiate using IKE fragmentation
in IKE_SA_INIT. Pre-configuration is a bad option. Most probably the cost 
would be an extra round trip + some tricks playing with invalid syntax and/or
 unknown exchange type).

> IKE_SA_INIT and IKE_AUTH.

Having an intermediate exchange that will reuse existing IKE Fragmentation
mechanism is a very attractive idea. It is even possible to leave out MessageID = 1 
for IKE_AUTH. The main problem with this approach is that it doesn't allow
to completely get rid of traditional DH in the future - we need to exchange 
KE to compute SK_* to use IKE fragmentation.

Regards,
Valery.

---

From: Paul Wouters <[email-masked]>
Date: Fri, 29 Sep 2017 11:01:49 -0400 (EDT)

> IKE_SA_INIT fragmentation so that these mechanisms be still able to work.

That would be tricky. Either a new exchange or an untrusted stream of
fragments. Either way, a lot of complexity for a rather moving target
goal that we don't understand yet. I'd personally rather wait until we
know a bit more about the direction that quantum safe protocols are
really going to.

> TCP has a lot of shortcomings. It's a last resort.

Agreed. It's the emergency backup parachute, not the real parachute.

People are suggesting a lot of complicated bells and whistles. I wish we
would not compete with TLS on which can be more complicated :P

Paul

---

From: "Valery Smyslov" <[email-masked]>
Date: Fri, 29 Sep 2017 18:21:43 +0300

Hi Paul,

> That would be tricky. 

Sure. But not impossible, I think.

> Either a new exchange or an untrusted stream of

Fully agree. And the size of the quantum safe KE payload is really important for IKE.
When I hear that it could be several MB, it makes me nervous - it seems
that transferring so much unauthenticated data will become a good target for DoS attacks.
Several KB is a bit better, at least it seems that we can deal with this amount.

> would not compete with TLS on which can be more complicated :P

Haven't we already won? :-)

Regards,
Valery.

---

From: Cen Jung Tjhai <[email-masked]>
Date: Fri, 29 Sep 2017 15:37:39 +0000

Hi Paul and Valery,

> Several KB is a bit better, at least it seems that we can deal with this amount.

There is a type of PQ key-exchange primitive (the oldest one) whose public key is around 1MB. Whether or not this primitive needs to be considered, we can wait until we have more information. However, for the rest of known PQ the primitives (except one) so far, their public key size is still larger than 1KB. So fragmentation may still occur for nodes whose MTU is set to around 1KB.

Best regards,
CJ