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

[Daniel Van Geest <[e-mail]>]

Hi Graham and all,

I have a few comments/suggestions on Graham’s idea. They concern two components of this proposal: 1) QS SA negotiation; and 2) QS KE/fragmentation; and one item unaddressed by the proposal 3) Rekeying/Child Creation.

Apologies in advance for the length.

1) QS SA Negotiation

When negotiating a QS SA, it’s not enough to negotiate QS key agreement algorithm(s), one also has to ensure that the algorithms selected by the other transform types are also QS. For example ENCR_AES_CBC (KeyLength = 128) will only provide 64 bits of security against a quantum computer, which is insufficient. If we are only concerned about passive quantum attacks then the choice of integrity algorithm won’t matter as much, however PRF transforms with enough bits of security to be QS will also need to be chosen.

With that in mind, I have concerns about advertising/negotiating the QSKE algorithms along with the KE algorithms in transform type 4. In order to ensure that a QS SA is established, the initiator will have to ensure that the first advertised SA is the QS one. This is fine, as RFC7296 specifies that the proposals are listed in order of preference. However, I don’t see a requirement that the transforms within a proposal have to be listed according to preference, or that the responder has to chose the first or strongest supported transform in a list (the end of section 3.3.5 talks about picking stronger transform *attributes*, but not about transforms). My point here is that if a responder may chose any of the proposed transforms then for the first proposal to be QS it must not contain any quantum-insecure transforms, or the responder must be modified to understand which ENCR/PRF transforms are QS and to pick them when creating a QS connection (and to fail if no QS algorithms are proposed). Then if an initiator wants to create QS SAs, but also wants to interoperate with (very?) old responders who don’t support AES-256 or PRF_HMAC_SHA2_384+ then they will need a second non-QS proposal in their SA list. And if they want to allow non-QS-upgraded, but still recently updated, responders a choice to use non-QR ENCR/PRF transforms (for performance reasons perhaps), they won’t be able to because the responder will have to pick transforms from the first (fully QS) proposal since it supports all the algorithms in the transform.

Now, maybe those concerns above are minor and the WG can live with them. That’s fine, I just want to make sure they’re considered.

I don’t find the re-use of transform 4 in this proposal, and the implicit combination of QS + non-QS algorithms, to be the most elegant, though I can understand it in the context of not wanting to add a new transform type.

But I am curious how strong this opposition to a new transform type is (apologies, I wasn’t in Prague so I don’t know if any other discussions occurred outside the WG timeslot). I fully understand the opposition due to backwards compatibility issues, this is something I came across in my own investigation too. I recall some opposition due to the possibility of the new transform creating additional proposals in the SA list (as new proposals are already needed due to AEAD), though I would imagine this is a lesser issue than backwards  compatibility. If the main concern is backwards compatibility, would the WG be willing to consider an idea which includes the new transform type but avoids backwards compatibility issues? If so, I had a variant on the current proposals which I is more explicit in the separation of QS and non-QS SAs and uses a new transform type in a backwards compatible way.

The idea is to add the new transform type 6 (Q-S-Group) like CJ’s proposal, but don’t include it in the SA payload. Rather, introduce a new QS_SA payload which would be identical in structure to the SA payload except that it would also include the Q-S-Group transform type. An endpoint could configure the proposals in this payload to contain QS and only QS ENCR/PRF algorithms, plus QRKE algorithms in transform type 6 and existing DH algorithms in type 4. The SA payload would still exist, so non-upgraded responders would still be supported, but upgraded responders would give the QS_SA proposals higher priority than SA proposals.

A non-upgraded responder would not recognize the QS_SA payload and so would chose an SA from the SA payload. They would also never see the new transform type, so there would be no backward-compatibility issues. A responder who recognizes the QS_SA payload could respond using a QS_SA payload rather than a SA payload (or if you think there would be implementation problems with this we could say they respond with an SA payload which contains the selected proposal from the QS_SA payload).

With this idea a new notification type isn’t necessary, because the existence of the QS_SA payload lets the responder know this extension is supported, and a response SA containing a proposal from QS_SA (and containing transform type 6) lets the initiator know this extension is supported by the responder. An attacker couldn’t remove the QS_SA payload because it will be protected by the IDi/IDr payloads in IKE_AUTH.


2) QR KE / fragmentation

I wrote up this message yesterday to review and send in the morning, but Tero's message last night covered my suggestion for fragmentation, so I’ll just add a few notes to consider in this area.

As mentioned, this PRE_AUTH (I like IKE_QS_KE, but if we think it will be expanded later then PRE_AUTH is more generic) message is encrypted with the classical keys generated in IKE_SA_INIT. The shared secrets generated in PRE_AUTH can use the existing rekeying mechanism to update the SA to be QS:

KEYMAT = prf+(SK_d, QS_SECRET | Ni | Nr)

Something to keep in mind is that many QS key agreement algorithms don’t have exactly the same message flow as Diffie Hellman.  With DH, each endpoint’s public/private keys can be generated independently of each other. But many QS algorithms have an initiator-responder flow, so the responder can only generate its public key once it has processed the initiator’s public key. We just need to keep this in mind when designing the flow of the PRE_AUTH messages. An initiator can’t send the first chunk of a public key, and the responder reply with the first chunk of their public key, the responder would need to process all initiator chunks for that key first. This means the initiator would have to send a special acknowledgement response for chunks that don’t complete a public key rather than responding with a partial key when receiving a partial key.

Also note that StrongSwan’s code assumes that IKE_AUTH will always have a message ID of 1, but this won’t hold if there are one or more PRE_AUTH exchanges. I was able to update StrongSwan to remove that assumption and instead check against IKE_AUTH’s actual message ID. It’s not clear to me whether Graham’s IKE_SA_INIT fragmentation would also suffer from this issue, I suspect that the IKE_SA_INIT fragments would need incrementing message IDs so endpoints don’t discard them? Hopefully other implementations either don’t have this assumption or are equally easy to modify.

Tero says:

Note, that the PRE_AUTH happening between IKE_SA_INIT and IKE_AUTH
would be encrypted, and MACed, but it WILL NOT be authenticated, i.e.,
we have not yet authenticated the other peer, and we will not include
those octets to the AUTH payload calculations, so they will not be
authenticated in AUTH phase, like the IKE_SA_INIT contents will be
authenticated.

Couldn’t the IDi and IDr payloads in IKE_AUTH be modified to sign the PRE_AUTH message in addition to the IKE_SA_INIT message?

Tero says:

I think this kind of step between IKE_SA_INIT and IKE_AUTH might be
easiest and most generic way of transferring the QSKE data.

I definitely agree :-)


3) Rekeying/Child Creation

Graham’s suggestion works entirely in IKE_SA_INIT, so if new SA is created or one is rekeyed it’s not clear how the QS public keys would be exchanged. They could be included in a payload of CREATE_CHILD_SA, but this will run up against the 64K barrier. Similar fragmentation could be added to CREATE_CHILD_SA as would be added to IKE_SA_INIT, however that could make things less elegant and could result in duplication of logic between IKE_SA_INIT and CREATE_CHILD_SA.

As my investigations didn’t account for > 64K QR public keys, I haven’t considered this fully yet, but would adding a IKE_QS_KE exchange after CREATE_CHILD_SA simplify things here? Since CREATE_CHILD_SA already takes advantage of IKEv2’s fragmentation, CREATE_CHILD_SA could handle most QS_KE payloads without additional fragmentation so maybe it would be overkill to move child/rekey QS_KE payloads into a subsequent exchange. But it would still need some way to handle >64K keys.

Tero’s suggestion could probably be extended to cover additional PRE_AUTH (IKE_QS_KE :-) ) exchanges after CREATE_CHILD_SA,

For any solution with multiple exchanges there may be an implementation issue where the endpoints are trying to send application data after the classical rekey is done but before the QS rekey completes.


4) That was long

Hopefully this wasn’t too long-winded. I’d be interested in hearing if anyone thinks any of these ideas are worth further investigation and would be glad to provide any resources to develop these ideas further.

4.1) A note on "Quantum-Safe” (QS) vs “Quantum-Resistant” (QR)

I’ve tried to use QS in my response to be consistent with Graham & CJ’s initial messages and draft, however in my experience “Quantum-Safe” has been used to refer to anything that can’t be broken by a quantum computer, meaning both algorithms which aren’t vulnerable to Shor’s or Grover’s algorithms but are running on classical computers, as well as true quantum processes like quantum key distribution (QKD). “Quantum-Resistant” has been used to refer to QS without QKD, i.e. just algorithms running on classical computers which aren’t vulnerable to quantum attack. So in my opinion all of the work we are doing here should be labeled Quantum Resistant rather than Quantum Safe. YMMV.


—
Daniel Van Geest ([e-mail]<mailto:[e-mail]>)
https://www.isara.com/

On Aug 3, 2017, at 7:57 AM, Graham Bartlett (grbartle) <[e-mail]<mailto:[e-mail]>> wrote:

Hi

After listening to the Prague meeting Dan Harkins raised the point that the Quantum Resistant IKEv2 implementation should protect passive attacks, where traffic that traffic that is sent and is captured today should be resilient to an adversary with a quantum computer in the future. But the Quantum Resistant IKEv2 does not have to protect against an adversary with a quantum computer in the future who can perform an active attack.

Someone else (can’t remember who) suggested the quantum resistant ‘blob’ be sent in IKE_AUTH as it will be large and probably fragmentation. Obviously for this the natural choice is to use the IKEv2 Fragmentation mechanism defined in RFC7383.

A few weeks ago I developed a method to send the quantum resistant ‘blob’ in IKE_SA_INIT, this is to amend https://tools.ietf.org/html/draft-tjhai-ipsecme-hybrid-qske-ikev2-00. After hearing the discussion described above I was going to park this idea and never speak of it again, however before I do this I’d like to share with the group for comments.

I personally feel this is an elegant and simple method to achieve sending one or more quantum resistant ‘blobs’. The main benefits being;


1.      The IKE_AUTH exchange is protected using the quantum secure algorithms. So all attributes within the IKE exchange are protected against passive attacks, which wouldn’t be the case should the quantum resistant ‘blob’ be sent in IKE_AUTH.



2.      This allows for a quantum resistant authentication method to be introduced into IKE_AUTH in the future, therefore protecting against active attacks with a quantum computer should this occur.



3.      A simple method to fragment the quantum secure key exchange data in IKE_SA_INIT is included, however this is not mandatory. From personal experience I’ve seen a few cases where RFC 7383 fragmentation is required today, however the vast majority of customer implementations do not experience issues with IP fragments being denied and so do not require the functionality provided by RFC7383 (but for the cases where it’s needed, it’s a lifesaver).



4.      The large quantum resistant ‘blob’ of data is only sent when it is known that the peer will accept this. This minimises delays when establishing IKEv2 SAs and minimises the risk of DoS (see point 7).



5.      Backwards compatibility is maintained, with minimal risk that the addition of a quantum resistant exchange could cause abnormal behaviour with devices that do not support the new attributes. The QSKE are advertised using a transform type 4 groups.



6.      This idea allows for algorithm agility, where multiple quantum resistant algorithms can be used in addition to a single classic DH (as per RFC7296). PQ algorithms with public data size larger than 65,536 octets are also supported.



7.      With regards to fragmentation attacks, the use of fragmentation in this idea has the same security as of RFC7383. Whereby an attacker that reveals her true IP address can send multiple fragments, but not the complex chain.


The following is the idea, any questions, please feel free to ask.





QSKE Notify

For devices that are operating in a mesh network, where many devices have multiple peers, where peers are using varying QSKE groups. In these instances the QSKE that is preferred by the Initiator might not be available or preferred on the Responder. To overcome scenarios where the Initiator will send a QSKE which is large in size and not supported by the Responder, (therefore wasting time and resource), the QSKE Notify payload can be used to query the responder to determine the supported security association attributes. The QSKE Notify payload is sent by the Initiator, which also excludes the QSKE payload (however a single KE payload should be included for backwards compatibility). If the Responder supports the QSKE notify payload it replies with the accepted security associations (which includes one classic DH group and >=1 QSKE group, these are sent as groups within transform type 4. Most of the time, we will be using one PQ algorithm, rather than multiple. The Responder will also includes the COOKIE notification, note the Responder does not send the KE or QSKE payload. The Initiator can now select the correct security association algorithms it intends to use, including the correct classic DH and QSKE and reply using the COOKIE.

Although the COOKIE does not provide protection against DoS attacks, whereby an attacker sends many fragments but does not complete the fragment chain, it does ensure that the attacker reveals their own IP address. Note that RFC 7383 is also prone to this attack which is described within the security considerations.

Should an IKE gateway be under a fragmentation attack, dropping traffic from a peer that does not complete the fragment chain can be used as a simple protective mechanism to minimise the impact of future attacks.

For implementations that do not support the use of the QSKE, the QSKE Notify payload will be ignored and the IKEv2 exchange will continue as per RFC7296. The QSKE Notify payload can be used to minimise inter-op issues with QSKE and non QSKE implementations.

The QSKE Notify payload can be marked as critical for devices that mandate the use of QSKE to protect IKE.

QSKE Notification Payload

                        1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   | Next Payload  |C|  RESERVED   |         Payload Length        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |  Protocol ID  |   SPI Size    |      Notify Message Type      |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                                                               |
   ~                       Notification Data                       ~
   |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

————
A Quantum Safe Key Exchange Payload

The quantum-safe key exchange payload, denoted QSKE in this document, is used to exchange a quantum-safe shared secret between two IKE peers.  The QSKE payload consists of the IKE generic payload header, a two-octet value denoting the Quantum-Safe Group number, and followed by the quantum-safe data itself.

The Fragment bit, denoted F (below), specifies if the QSKE is fragmented. If this is set to '1', meaning the QSKE is fragmented the Fragment Number and Total Fragments fields will be populated. If the Fragment bit is not set (set to '0'), then the Fragment Number and Total Fragments fields will not exist. The Fragment Number is used should the Quantum-Safe Data be too large to fit within a single payload. The Fragment Number is the first fragment, increasing by one for every other fragment that is sent. The Total Fragments field denotes the maximum number of fragments that contain the Quantum-Safe Data.

The QSKE is nearly identical to the KE payload, however the Fragment bit identifies if the receiver should handle this in a different manner to the KE payload. The KE and QSKE are negotiated/advertised using the transform type 4 (Diffie Hellman groups).  By including the QSKE in the same transform type 4 as classic DH allows for minimal configuration changes for current implementations when configuring both DH and QSKE Groups.

                           1                   2                   3
       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      | Next Payload  |C|F| Reserved  |            Payload Length     |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |    Quantum-Safe Group Num     |           RESERVED            |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      ~        Fragment Number            |     Total Fragments       ~
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                                                               |
      ~                       Quantum-Safe Data                       ~
      |                                                               |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

The size of the Quantum-Safe Data can be the total fragments * payload length = ~ 4GB, which seems sufficient for the size of the QSKE payloads discussed so far.

The use of the Fragmentation bit is not mandatory. Implementations can attempt to send the IKE_SA_INIT payload containing the QSKE payload without fragmentation at the IKE layer, opting for fragmentation at the IP layer instead. Implementations can initially exclude the the use of fragmentation in the QSKE payload, however if connectivity fails when not using fragmentation of the QSKE, it is assumed that that traffic has been denied due to fragmentation at the IP layer and fragmentation of the QSKE should be used instead.


——

In the following example the Initiator will propose DH Groups 14,19,21 and 30,32 and 35 (fictitious QSKE groups). The Initiator sends the N(QSKE), which informs the responder to choose >=1 QSKE groups along with a classic DH group.

The responder will return the N(QSKE) payload, indicating it supports the QSKE, the security association includes DH Groups 14, 30 and 35 which informs the initiator of the QSKE groups it selects to use.

The Initiator then sends the QSKE's and KE for the groups it wishes to use, plus the identical security associations as was sent in the first exchange (to mitigate downgrade attacks). Note: The Responder should check that the received QSKE's in the security association match with its preferred secure QSKE's. This is to mitigate the following attack, Initiator sends SA contains certain QSKE in the security association Responder responds, but attacker modifies this response to remove the said QSKE. The Initiator then performs the IKE_SA_INIT excluding the QSKE that was removed by the attacker,  in the QSKE (but it's included in the security associations). Hence if the responder verifies that the received QSKE match the received security associations, it will mitigate this attack.


    Initiator                   Responder
   -----------                 -----------
   HDR, SAi1, Ni,KEi    -->                                 (DH Groups 14,19,21 and 30,32 and 35)
      N(QSKE)

                       <--   HDR, SAr1, N(COOKIE),[N(QSKE)]       (DH Groups 14, 30 and 35)


   HDR, N(COOKIE), SAi1,                                    (SA contains DH Groups 14,19,21 and 30,32 and 35)
    KEi, Ni, QSKEi-1/3  -->                                 (KE is Group 14, QSKE1 is Group 30, fragment 1 of 3)

   HDR, QSKEi-2/3       -->                                 (QSKE1 is Group 30, fragment 2 of 3)

   HDR, QSKEi-3/3       -->                                 (QSKE1 is Group 30, fragment 3 of 3)

   HDR, QSKEi2-1/4      -->                                 (QSKE2 is Group 35, fragment 1 of 4)

   HDR, QSKEi2-2/4      -->                                 (QSKE2 is Group 35, fragment 2 of 4)

   HDR, QSKEi2-3/4      -->                                 (QSKE2 is Group 35, fragment 3 of 4)

   HDR, QSKEi2-4/4      -->                                 (QSKE2 is Group 35, fragment 4 of 4)


                  <--  HDR, SAr1, Nr, KEr,                  (KE is Group 14, QSKE1 is Group 30, fragment 1 of 3)
                        QSKEi-1/3

                  <--  HDR,QSKEi-2/3                        (QSKE1 is Group 30, fragment 2 of 3)

                  <--  HDR,QSKEi-3/3                        (QSKE1 is Group 30, fragment 3 of 3)

                  <--  HDR,QSKEi2-1/4                       (QSKE2 is Group 35, fragment 1 of 4)

                  <--  HDR,QSKEi2-2/4                       (QSKE2 is Group 35, fragment 2 of 4)

                  <--  HDR,QSKEi2-3/4                       (QSKE2 is Group 35, fragment 3 of 4)

                  <--  HDR,QSKEi2-4/4                       (QSKE2 is Group 35, fragment 4 of 4)


As three groups were used, the keymat is generated with the combination of the output from the three public values.

KEYMAT = prf+(SK_d, QSSS2 (Group 35) | QSS1 (Group 30) | g^ir (Group 14) | Ni | Nr)


   HDR SK {IDi, [CERT,]
       [CERTREQ,] [IDr,] AUTH,
       SAi2, TSi, TSr}  -->




————


In the following the Initiator will propose DH Groups 14,19,21 and 30,32 and 35 (fictitious QSKE groups). The Initiator sends N(QSKE), which tells responder to choose a DH group and >=1 QSKE groups  .

The Responder in this case does not support QSKE and assuming the N(QSKE) was non critical, will ignore this Notify Payload.

The exchange will continue as per RFC7296.


    Initiator                   Responder
   -----------                 -----------
   HDR, SAi1, Ni,KEi    -->                           KE=Group 14 (SA: DH Groups 14,19,21 and 30,32 and 35)
      N(QSKE)

                       <--   HDR, SAr1,Nr,KEr         (DH Groups 14)


  HDR SK {IDi, [CERT,]
       [CERTREQ,] [IDr,] AUTH,
       SAi2, TSi, TSr}  -->


———————



_______________________________________________
IPsec mailing list
[e-mail]<mailto:[e-mail]>
https://www.ietf.org/mailman/listinfo/ipsec