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

["Bruckert, Leonie" <[e-mail]>]

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:[e-mail]] Im Auftrag von Scott Fluhrer (sfluhrer)
Gesendet: Dienstag, 22. August 2017 16:31
An: Cen Jung Tjhai; Valery Smyslov; 'Tero Kivinen'
Cc: [e-mail]
Betreff: Re: [IPsec] Proposed method to achieve quantum resistant IKEv2


> -----Original Message-----
> From: IPsec [mailto:[e-mail]] On Behalf Of Cen Jung Tjhai
> Sent: Tuesday, August 22, 2017 6:43 AM
> To: Valery Smyslov; 'Tero Kivinen'
> Cc: [e-mail]
> 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
[e-mail]
https://www.ietf.org/mailman/listinfo/ipsec