Subject: [IPsec] draft-tjhai-ipsecme-hybrid-qske-ikev2-01

From: "Valery Smyslov" <[email-masked]>
Date: Thu, 1 Feb 2018 16:08:26 +0300

Hi, this is a long message...

I've looked through the -01 version of the QSKE draft. The draft has been expanded
and now it covers such aspects as QSKE negotiation, fragmentation and transferring
of payloads larger than 64K. I didn't review the draft in details, however after reading
I have concerns over the technical solutions the draft proposes. In particular, I think that 
the problems of negotiation, fragmentation and representation of large payloads 
could be solved better.

1. Negotiation.

The draft introduces a new negotiation mechanism to be used explicitly with 
multiple QS key exchanges. While the proposed mechanism looks like an ingenious
way to deal with legacy implementations and as a powerful tool to negotiate
complex policies, I don't think it is ever needed, since all this can be done
using existing mechanism. How it can be achieved:

Let's define a bunch of new Transform Types each defining some kind of QSKE:

Transform Type 6 - Lattice QSKE
Transform Type 7 - Code-based QSKE
Transform Type 8 - Isogeny-based QSKE
Transform Type 9 - Symmetric QSKE
...

Each of these Transform Types must then be populated with Transform IDs
for QSKE of corresponding type. It is also important to add NONE into each of these
types.  The Initiator willing to combine QSKEs of specific types would include
corresponding Transform Types populated with the Transform IDs the initiator
deems acceptable. If NONE for some Transform Type is included, it means 
that this Transform Type is optional. IKEv2 requires the responder to select
a combination of transforms such that a single Transform ID of each Transform Type 
is present. It means that the current SA payload syntax is able to represent the policies 
that the new negotiation mechanism in the draft is designed for. For example:

SA:
  Proposal1:
    TransformType1: ENCR_AES_CBC
    TransformType2: PRF_HMAC_SHA2_256
    TransformType3: AUTH_HMAC_SHA2_256_128
    TransformType4: 2048-bit MODP Group
  Proposal2:
    TransformType1: ENCR_AES_CBC
    TransformType2: PRF_HMAC_SHA2_256
    TransformType3: AUTH_HMAC_SHA2_256_128
    TransformType4: 2048-bit MODP Group
    TransformType6: LatticeQSKE_2
    TransformType6: CodebasedQSKE_1, CodebasedQSKE_2
  Proposal3:
    TransformType1: ENCR_AES_CBC
    TransformType2: PRF_HMAC_SHA2_256
    TransformType3: AUTH_HMAC_SHA2_256_128
    TransformType4: 2048-bit MODP Group
    TransformType6: LatticeQSKE_1
    TransformType6: LatticeQSKE_2, NONE
    TransformType6: IsogenybasedQSKE_1, IsogenybasedQSKE_2

In this example the Proposal1 is aimed for the legacy responders.
Proposals  means that the classic MODP_2048 group
must be combined with LatticeQSKE_2 and either CodebasedQSKE_1 or 
CodebasedQSKE_2. Proposal3 means that the classic MODP_2048 group must be 
combined with either IsogenybasedQSKE_1 or IsogenybasedQSKE_2 and may optionally 
be combined with LatticeQSKE_2.

Legacy responders would ignore Proposals 2 and 3 since they contain
unknown Transform Type. However they would pick Proposal1.
QSKE-enabled responders would select either Proposal 2 or 3 depending
on their policy.

Re-using existing mechanism is much easier to implement since the parsing
code is already there, as well as the interface with the local policy.
This mechanism is flexible enough to express the policies from the draft.
It doesn't have a round trip penalty when communicating with legacy
responder. It assumes that classic KE is always present, however I can
see it as a feature, not as a disadvantage (see the next topic in the message).
And in the future it will be possible to add QSKE mechanisms into Transform Type 4,
provided their public key are small enough (and their security is proved, of course).
In this case no classic KE is more needed. 

One disadvantage of using SA payload comparing with the new mechanism from 
the draft is that it is less compact and complex policies can lead to the situation 
when SA payload size will become too large. However, there is a draft describing compact 
representation of IKE payloads that allows to significantly decrease SA payload size
(https://datatracker.ietf.org/doc/draft-smyslov-ipsecme-ikev2-compact/)

One more consideration. I assume that existing implementations are conformant with 
RFC 7296, which states (Section 3.3.6):

   If the responder receives a proposal that contains a Transform Type
   it does not understand, or a proposal that is missing a mandatory
   Transform Type, it MUST consider this proposal unacceptable; however,
   other proposals in the same SA payload are processed as usual.

There were a concerns that some implementations could incorrectly
reject the whole SA payload if they encountered an unknown Transform Type.
To deal with such (crippled) implementations one more round trip and an
additional logic would be needed (if we decide to deal with them ever),
but I think that it'll be no more complex than the negotiation mechanism from
the draft.

Am I missing something here?

2. Fragmentation

I think that defining a new fragmentation mechanism for IKE_SA_INIT is bad choice. 
We already have IKE fragmentation and it is more appropriate to re-use
existing mechanism. It is possible to do it in a way suggested by Tero:
https://www.ietf.org/mail-archive/web/ipsec/current/msg11563.html
I've published a draft defining auxiliary exchange for this purpose:
https://datatracker.ietf.org/doc/draft-smyslov-ipsecme-ikev2-aux/

Comparing with a new fragmentation mechanism for IKE_SA_INIT defined in the draft,
re-using the existing IKE fragmentation via an auxiliary exchange has the following advantages.

- It is easier to implement. The IKE fragmentation is already supported by many vendors
   and it is easier to add a new simple exchange than to complicate IKE_SA_INIT, that is already
   quite complex. Note, that with the draft's proposal IKE_SESSION_RESUME exchange would
   need to be modified as well. With auxiliary exchanges resumption will be supported for free.

- It is substantially more secure. The way the draft deals with fragmentation is susceptible to DoS 
   attacks when an attacker injects bogus fragments poisoning reassembly buffer. Adding
   cookie to the fragments. as the draft suggests to prevent this attack, doesn't help at all: 
   to inject bogus fragments an attacker need to know IKE SPIs, so he/she must be able
   to view messages from the peers, and if he/she is able to do it, then he/she will also
   know the cookie. So, the proposed defense never works. This attack is impossible
   with the standard IKE fragmentation unless an attacker is able to break key exchange 
   in the IKE_SA_INIT in real time. I presume he/she would need QC for that and I hope
   by the time it is possible we'll already have some QC-proof key exchange with small
   public keys, so that it can be used in the IKE_SA_INIT and thwart the attack.

- It is more robust. The problem with the approach suggested in the draft is that it
   works very poorly in case of packet loss, because all the fragments are sent simultaneously.
   If the number of fragments is small enough, then it doesn't cause major problems.
   However, as the number of fragment grows, single packet loss results in resending
   the whole bunch of fragments. If the packet loss is caused by congestion, then
   momentary resending all the fragments would result in more congestion, that 
   would only make things worse. Standard IKE fragmentation is also susceptible 
   to this problem, since it wasn't designed to deal with more than a handful fragments.
   This is no more true with QC-safe huge public keys. Ideally, each fragment 
   should be acknowledged individually, however in is generally impossible with IKE 
   request-reply paradigm (since reply fragments must also be acknowledged).
   Fortunately, using several auxiliary exchanges for transferring QC-safe public keys
   make it possible to at least make this problem less significant. The idea is
   to perform several QC-safe key exchanges utilizing large public keys one by one:

  HDR (IKE_SA_INIT, MID=0), SAi1, KEi, Ni,
       [N(AUX_EXCHANGE_SUPPORTED)]  -->
                                    <--  HDR (IKE_SA_INIT, MID=0), SAr1, KEr, Nr,
                                             [N(AUX_EXCHANGE_SUPPORTED)]

   HDR (IKE_AUX, MID = 1), SK {QSKE1i}  -->
                                     <--  HDR (IKE_AUX, MID = 1), SK { QSKE1ir}

   HDR (IKE_AUX, MID = 2), SK {QSKE2i}  -->
                                     <--  HDR (IKE_AUX, MID = 2), SK { QSKE2ir}   

   HDR (IKE_AUTH, MID = 3), SK {SA, TSi, TSr}  -->
                                     <--  HDR (IKE_AUTH, MID = 3), SK { SA, TSi, TSr}   

  So each of negotiated QSKEs is performed in a separate exchange,
  thus reducing the number of fragments in case it is fragmented.
  It is even possible to split any single QS key exchange in a several
  IKE_AUX exchanges if the exchange is DH-like, i.e. if public keys are 
  of the same size and are generated independently.

  [Actually the same problem with reliable transferring of large number
  of fragments in case of QSKE will also arise in case of re-keying...
  There are several possible solutions, but I think they can be discussed
  separately.]

So, I see no advantages of the new IKE_SA_INIT fragmentation mechanism 
over the re-using of existing one. Again, am I missing something here?

3. Large KE payloads

The draft makes it possible to deal with public keys greater than 64K
by means of a complex pointer-like system (integrated with proposed
fragmentation mechanism). I think that it is too complex. I'd rather
use simple approach, that is aligned with the re-using of standard
IKE fragmentation described above. 

I propose that in case the public key is greater than 64K, it is 
split into several consecutive KE payloads in a single message.
If several long public keys are present in the message, then
all the payloads each key is split into must be grouped together.
An example:

   HDR (IKE_AUX, MID = 1), SK {QSKE1i, QSKE1i, QSKE1i, QSKE2i, QSKE2i }  -->
    <--  HDR (IKE_AUX, MID = 1), SK { QSKE1ir, QSKE1ir, QSKE1ir, QSKE2ir, QSKE2ir }

Here we have 2 large public key in a single message, QSKEi1 is split
into 3 payloads and QSKEi2 is split into 2 payloads. Actually, I don't think
it is a good idea to send several large public keys in a single message given
the problems outlined above, but it is a possible construction.
A better way would be:

   HDR (IKE_AUX, MID = 1), SK {QSKE1i, QSKE1i, QSKE1i}  -->
                     <--  HDR (IKE_AUX, MID = 1), SK { QSKE1ir, QSKE1ir, QSKE1ir}

   HDR (IKE_AUX, MID = 2), SK {QSKE2i, QSKE2i}  -->
                     <--  HDR (IKE_AUX, MID = 2), SK { QSKE2ir, QSKE2ir}   

And even better way would be (provided the QSKEs are DH-like):

   HDR (IKE_AUX, MID = 1), SK {QSKE1i}  -->
                                     <--  HDR (IKE_AUX, MID = 1), SK { QSKE1ir}

   HDR (IKE_AUX, MID = 2), SK {QSKE1i}  -->
                                     <--  HDR (IKE_AUX, MID = 2), SK { QSKE1ir}

   HDR (IKE_AUX, MID = 3), SK {QSKE1i}  -->
                                     <--  HDR (IKE_AUX, MID = 3), SK { QSKE1ir}

   HDR (IKE_AUX, MID = 4), SK {QSKE2i}  -->
                                     <--  HDR (IKE_AUX, MID = 4), SK { QSKE2ir}   

   HDR (IKE_AUX, MID = 5), SK {QSKE2i}  -->
                                     <--  HDR (IKE_AUX, MID = 5), SK { QSKE2ir}   

[And I still hope that cryptographers won't leave us with only 
those QC safe key exchange methods that use huge public keys.
I really don't want to transfer megabytes of keys just to create an SA
to read my one hundred bytes long e-mail...]

So, the bottom line. I think that the QSKE draft goes into wrong
direction, suggesting over-complicated and insecure solutions
and ignoring existing mechanisms that can be used instead.
I hope the authors will re-consider this.

Regards,
Valery.

---

From: CJ Tjhai <[email-masked]>
Date: Fri, 9 Feb 2018 00:41:14 +0000

Hi Valery,

Many thanks for your email and also your interest in our draft.

As we explain in detail below, we don't agree with your conclusion
that our proposal is overcomplicated, does not take into account what
is out there, and insecure. Even if some of the features that we
introduce deviate from standard operation, we did so after checking
with clients and vendors. One of the features that they are keen on is
the possibility of reusing KE payload to negotiate hybrid post-quantum
groups or proposals.

Please find below our response regarding the points you made.

1. Negotiation

We are glad to see that you also appreciate the need to negotiate a
hybrid group. As you may remember, we introduced a new Transform Type
in our version 00 of our draft and it had not been well-received in
IETF 99 Prague. We accept this push-back and it makes sense; since the
introduction of IKEv2, there has not been any new Transform Type
introduced. In fact, after IETF 99 Prague, we found out that there
exists IKEv2 implementations out there that will error out if they
receive an unknown Transform Type.

As you pointed out, according to RFC 7296, if a responder receives a
proposal with Transform Type that it doesn't understand, it MUST
reject the proposal. However, we found that this is not true in
practice. StrongSwan is a good example; consider you have two peers
running StrongSwan where the initiator introduces a proposal
containing a new Transform Type:

SA:
  Proposal 1:
    Transform Type 1: ENCR_AES_CBC
    Transform Type 2: PRF_HMAC_SHA2_256
    Transform Type 3: AUTH_HMAC_SHA2_256_128
    Transform Type 4: P-256
    Transform Type 6: New Transform Type
  Proposal 2:
    Transform Type 1: ENCR_AES_CBC
    Transform Type 2: PRF_HMAC_SHA2_256
    Transform Type 3: AUTH_HMAC_SHA2_256_128
    Transform Type 4: MODP-3072

It is assumed that the responder runs StrongSwan implementing standard
RFC 7296, hence it does not understand Transform Type 6. Instead of
rejecting Proposal 1 and considering Proposal 2, the responder ignores
Transform Type 6 (i.e. selecting ENCR_AES_CBC, PRF_HMAC_SHA2_256,
AUTH_HMAC_SHA2_256_128, P-256). The initiator clearly does not propose
this proposal. This particular case would only be okay if Proposal 2
offers P-256. This is one particular implementation peculiarity, there
will be others that behaves oddly. The point is, if we introduce a new
Transform Type, it is very likely that backward compatibility can no
longer be achieved.

Hence, we pick a DH group that denotes a hybrid group and negotiate it
using the existing KE payload.

On your email, you also mentioned that in the future, we could use KE
payload to carry small PQ KE payload. Then, some logic is required to
distinguish what is carried in IKE_SA_INIT and what is carried in
IKE_AUX; it looks messy.

2. Fragmentation

We remember that Tero did suggest to use an intermediary exchange
between IKE_SA_INIT and IKE_AUTH. However, after soliciting inputs
from a number of parties (both vendors and clients), it appeared that
the majority didn't like the idea of having this extra exchange as
introduced a considerable deviation from standard IKEv2 flow and felt
that we would just be introducing an IKE_SA_INIT fragmentation which
could be achieved by other mechanisms.

While IKE_AUX would be useful in environment where network is lossy,
we also need to consider the requirements for applications such as VPN
concentrator where connection rate is important, or peers that have a
considerable route trip time. We acknowledge that we have not included
any mechanisms to deal with loss packets in version 01 of our draft.
This is intentional as we would like to get the WG input on which
direction we should take our draft before going deeper.

In terms of DoS attacks, we do not mandate the use of cookie
mechanism, but when implemented, the responder can check that incoming
messages corresponding to the second round of our protocol (note that
this is the expensive round in which public-key operations are
performed and space is allocated) have been agreed previously in a
first round of the protocol. We also believe that your comment that
what you propose is substantially more secure is not true. An attacker
who can monitor exchange of messages and inject packets, can trivially
DoS a connection (e.g. when the initiator sends the initial "HDR,
SAi1, KEi, Ni", the attacker immediately responds with a "HDR, SAr1,
KEr, Nr" of his choosing before the real responder does). An attacker
who can modify the initial packets is not detected until later in the
exchange. Of course, this could require a significant amount of
resource allocation for post-quantum public data exchange. In our
approach, we could detect it before IKE_AUTH phase.

3. Large payload

We also hope that we don't end up having PQC ciphers with large
public-key. We don't mandate our proposed draft to support payloads
larger than 64KB. In fact, it is an added bonus of how we do
fragmentation.

Best regards,
Authors of draft-tjhai-ipsecme-hybrid-qske-ikev2-01

On 1 February 2018 at 13:08, Valery Smyslov <[email-masked]> wrote:
> _______________________________________________
> IPsec mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/ipsec

---

From: "Valery Smyslov" <[email-masked]>
Date: Mon, 12 Feb 2018 16:11:27 +0300

Hi,

thank you for the explanation. See my comments inline.

> receive an unknown Transform Type.

I'm not sure it justifies introducing yet another negotiation mechanism. 
I understand that we live in non-ideal world, however adding 
one more mechanism for solving exactly the same problem
due to existence of buggy implementations looks far too expensive for me.
Unless these buggy implementations dominate...

> offers P-256. 

This behavior is wrong, however I don't think it cannot be dealt with.
Just always define your policies so that all PSKE proposals contain the same 
"classic" transforms, as "classic" proposal. This is an additional requirement
for policy, but Is there any reason this is wrong from security  point of view?

> This is one particular implementation peculiarity, there

Again, it depends. If the majority of implementations immediately crash once they
receive unknown transform, then I agree that we need another mechanism...
Most of other cases usually can be dealt with. Probably not all and probably
not as elegant as we wish, but still I believe they can.

> using the existing KE payload.

Well, if you are so determined to deal with buggy implementations, then
there are more natural alternatives. For example you may 
introduce a new SA-like payload, which would have the same syntax as 
SA payload, but different Payload Type, and put all PSQE stuff there. 
Since Critical Bit is not set in this payload, the existing implementations must 
ignore it. 

And if you find implementations that won't behave correctly even
in this case, then put SA-like syntax in a new notify - I'm sure
every existing implementation can handle this.

So, my main concern is that with your proposal a new code is needed
to parse, form, log etc. all the QSQE stuff, since it is presented in a completely
new way. It is not a big deal if the amount of negotiation stuff 
is small (say, you define only one QSKE group). In your case,
you want to express a complex combinations of different QSKE methods,
which I, as implementer, would need to parse, form, log, match to policy etc.
I prefer to reuse existing code for this and I see no reason why it cannot be done.

> distinguish what is carried in IKE_SA_INIT and what is carried in

It is easy. "Classic" KE is always done in the IKE_SA_INIT. 
All PQ KEs are done in the IKE_AUX. However, once one (or few) of the 
PQ KEs is considered cryptographically matured and this PQ KE 
has small enough public key, we'll add it as a new "classic" one,
so that in done in the IKE_SA_INIT. No mess here.

> could be achieved by other mechanisms.

I'm puzzled here... The whole idea of QSKE is a considerable deviation
from standard IKEv2. Comparing to the amount of needed changes
to the protocol, introducing a new exchange that follows standard IKEv2 
rules looks like a simple task. I believe it is easier than making all 
the modifications from the draft to the IKE_SA_INIT (that is already quite complex).

> considerable route trip time. 

If you put all the QSKE payloads in a single IKE_AUX (and won't do them
one by one in a series of IKE_AUX), you'll have the same number of round trips 
as in your proposal. I see no advantage of your proposal here.
Am I missing something?

> We acknowledge that we have not included
> first round of the protocol. 

It won't help you against poisoning reassembly queue with a bogus packets,
since an attacker would know the correct cookie from the first round.
And this attack is not possible at all with IKE_AUX (unless an attacker breaks
classic DH in a real time). Please, see ipsecme mail archives from 2012-2013
where all these things concerning possible attacks on IKE fragmentation were 
discussed in detail.

> We also believe that your comment that
> exchange. 

This is a different kind of attack and your proposal is susceptible to it as well. 
Moreover, the attack is described in the RFC7296 (Section 2.4, page 29)
and some countermeasures are suggested.

> Of course, this could require a significant amount of

Please, elaborate. Unless you mandate requesting cookie, your 
proposal is no more secure against this attack than classic IKEv2 or IKE_AUX.
And mandating requesting cookie can be an option for all of them.

When I was talking about DoS attack on your proposal that are not 
possible in IKE_AUX approach, I meant an reassembly queue poisoning
attacks. Besides your proposal is more complex and less robust...

> larger than 64KB. In fact, it is an added bonus of how we do

Well, with IKE_AUX we have this bonus almost for free too.
However I agree that we'd better to avoid such huge KE payloads...

Regards,
Valery.

---

From: Paul Wouters <[email-masked]>
Date: Mon, 12 Feb 2018 10:26:27 -0500 (EST)

> not as elegant as we wish, but still I believe they can.

We still have plenty of time to get the word out to those
implementations to fix their problem. By the time we have a
document ready for post quantum transforms, those implementations
should have been fixed. It's a little early now to deem this
an unsurmountable problem.

> I prefer to reuse existing code for this and I see no reason why it cannot be done.

I agree.

Paul

---

From: Tero Kivinen <[email-masked]>
Date: Wed, 14 Feb 2018 00:20:37 +0200

> an unsurmountable problem.

Yes. Also there is big difference in requirements for
draft-ietf-ipsecme-qr-ikev2 and requirements for proposal doing proper
quantum safe algorithms. The draft-ietf-ipsecme-qr-ikev2 is intended
to be deployed now, and should work with existing implementations
without fatal interoperability errors with them. 

As quantum safe algorithms itself are so much in ongoing research now,
I do not think we will be having implementations out there using any
of the quantum safe algorithms now, and so there will be time for
broken implementations to get fixes installed to them. I.e., if you
still plan on running completely broken strongswan implementation
which do not implement MUSTs in IKEv2 for example in year 2019, then
you are not interested in security, thus you are not really going to
be even try to use anything like quantum safe algorithms to talk to
them...

I mean, if you plan not to install security updates to your IPsec
products for years to come, it does not matter what we do, you most
likely have big security holes in your gateways anyways.

Even RFC4306 said you "MUST contain exactly one transform of each type
included in the proposal" in section 2.7, so what they are doing has
never been allowed in the IKEv2.

In the RFC5996 we did add text saying:

    If the responder receives a proposal that contains a Transform
    Type it does not understand, or a proposal that is missing a
    mandatory Transform Type, it MUST consider this proposal
    unacceptable; however, other proposals in the same SA payload are
    processed as usual.

and if they have not updated IPsec implemenation since 2010, again
there will most likely be so many holes in it that there is no point
of talking about quantum safe algorithms...

We have discussed several times of adding new transform types, and
in most cases we have found better ways of doing that. On the other
hand there is nothing that would make it impossible to add new
transform types. IKEv2 has been designed so that new things can be
added without breaking old implementations (provided old
implementations actually follow what was written in the IKEv2 RFCs).

In this case I think I agree with Valery that adding new transform
types might be good option, and we should investigate that option too. 

> > I prefer to reuse existing code for this and I see no reason why

Making IKE_SA_INIT more complicated than what is now, is something we
do not really want to do. It is first exchange with the peer, it has
all kind of denial of service properties which we should try to cope.
We do not want to make it so big it will get larger than one kilobyte
in size, so it will not get fragmented by the IP layer etc. Doing
fragmentation on that layer is very hard if we want to protect that
also against DoS.

I am very much suprised that some of the vendors really said that they
wanted to change the IKE_SA_INIT instead than add new exchange between
IKE_SA_INIT and IKE_AUTH.
-- 
[email-masked]