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

["Scott Fluhrer (sfluhrer)" <[e-mail]>]

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