Subject: [IPsec] NIST question concerning IKEv2 and quantum resistance

From: "Perlner, Ray" <[email-masked]>
Date: Wed, 6 Jan 2016 20:33:10 +0000

Hi all.

NIST is investigating quantum-resistant alternatives to presently standardized public-key algorithms. We are reaching out to the IPSec working group to determine if there are any unique needs associated with trying to add quantum-resistance to IKEv2, which currently only uses variants of the Diffie-Hellman key exchange.

We believe a number of the properties of the Diffie-Hellman construction (such as perfect forward secrecy) can be met using generic constructions based on standard cryptographic primitives and security models (such as IND-CCA2 encryption and EUF-CMA signature) as long as key generation times are fast. If IKEv2 can accommodate such generic constructions, there are likely to be many proposals to choose from. However, there are some additional properties of the Diffie-Hellman exchange which may be difficult to duplicate (such as the property that the responder can compute his key exchange message without seeing the initiator's key-exchange message) and it's not as clear to us what the security model for a key exchange replacing DH should be.

So in summary, we would like to answers to the following questions:

1)      Can IKEv2 can be modified to replace the Diffie-Hellman exchange with a generic construction based on standard encryption, signature, and PRF primitives?

2)       If not, what specific security and correctness requirements should we target to meet the need?

Thanks,
Ray

---

From: Paul Wouters <[email-masked]>
Date: Wed, 6 Jan 2016 15:52:58 -0500 (EST)

On Wed, 6 Jan 2016, Perlner, Ray wrote:

> NIST is investigating quantum-resistant alternatives to presently standardized public-key algorithms. We are
> reaching out to the IPSec working group to determine if there are any unique needs associated with trying to
> add quantum-resistance to IKEv2, which currently only uses variants of the Diffie-Hellman key exchange.

There is:

https://tools.ietf.org/html/draft-nagayama-ipsecme-ipsec-with-qkd-01

It was thrown out of the working group before. I think it is time to
reconsider with everyone focusing on post-quantum worlds.

Paul

---

From: Yoav Nir <[email-masked]>
Date: Thu, 7 Jan 2016 09:27:11 +0200

> On 6 Jan 2016, at 10:33 PM, Perlner, Ray <[email-masked]> wrote:
> 
> Hi all.
>  
> We believe a number of the properties of the Diffie-Hellman construction (such as perfect forward secrecy) can be met using generic constructions based on standard cryptographic primitives and security models (such as IND-CCA2 encryption and EUF-CMA signature) as long as key generation times are fast. If IKEv2 can accommodate such generic constructions, there are likely to be many proposals to choose from. However, there are some additional properties of the Diffie-Hellman exchange which may be difficult to duplicate (such as the property that the responder can compute his key exchange message without seeing the initiator’s key-exchange message) and it’s not as clear to us what the security model for a key exchange replacing DH should be.
>  

Hi, Ray

RFC 7296 describes the key agreement method as “Diffie-Hellman”, the identifier as a “Diffie-Hellman group”, the content of the KE payload as “Diffie-Hellman public value”, and the result of the calculation as g^ir.

The terminology used reflects perhaps a lack of imagination, but just as we’ve substituted ECDH for DH and just as we are working on adding Curve25519 key agreement, the protocol is amenable to adding different key agreement methods which are not even mathematical groups.

The only requirements are:
Negotiate the use of the mechanism in the Initial exchange (that’s as simple as assigning a number to the new method)
Send the initiator’s “part” (that’s the terminology they now use in the TLS working group) in the Initial request
Send the responder’s “part” in the Initial response.
Be able to generate the shared value (which is going to be something other than g^ir in your scheme) based on those two messages alone.

If your method can be done with these constraints, it’s an OK fit for IKE.

IIUC this not-really-specified-above proposal has the Responder’s public value depend on the Initiator’s value. This means that the Responder cannot pre-calculate and cannot re-use something (I won’t say “exponentials”).

These are possible with current key agreement methods, but they are not essential to security or correct operation. They help increase the rate of IKE SA setups that a particular piece of hardware running the Responder can perform. If a particular platform can perform 200 setups per second without pre-calculation and reuse, but 400 with them, that’s a performance gain only. Any new proposed method will be judged on its security as well as the session setup rate on a similar piece of hardware. It is entirely possible and acceptable that performance optimizations will look very different with a new algorithm.

Short version: I think it’s fine.  Now let’s see an actual proposal.

Yoav

---

From: Michael Richardson <[email-masked]>
Date: Thu, 07 Jan 2016 09:16:45 -0500

> Short version: I think it’s fine. Now let’s see an actual proposal.

+1.

A desireable property which we do not presently have, is if the amount of
work the initiator has to do for step 1 is less than what the responder has
to do for step 2, and the responder can cheaply verify the "freshness" of
the work.  During times of attack, there can be an additional step -1/0
where the responder provides a challenge to the initiator.

We have been looking at using puzzle solving to let the responder seperate
the wheat from the DDoS-provided-chaff quickly.   If a new protocol was
quantum resistant, and *also* provided a measure of DDoS resistance, then
that would probably significantly improve the industry interest in it.

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

---

From: "Panos Kampanakis (pkampana)" <[email-masked]>
Date: Tue, 12 Jan 2016 05:44:13 +0000

Hi Ray,

Scott's https://datatracker.ietf.org/doc/draft-fluhrer-qr-ikev2/ is the first take of QC resistant IKEv2. It is still in its early stages and has not been adopted as any WG's item yet.

Feedback is welcome.

Rgs,
Panos

From: IPsec [mailto:[email-masked]] On Behalf Of Perlner, Ray
Sent: Wednesday, January 06, 2016 3:33 PM
To: [email-masked]
Cc: Liu, Yi-Kai <[email-masked]>; Moody, Dustin <[email-masked]>; Frankel, Sheila E. <[email-masked]>; Waltermire, David A. <[email-masked]>
Subject: [IPsec] NIST question concerning IKEv2 and quantum resistance

Hi all.

Thanks,
Ray

---

From: "Valery Smyslov" <[email-masked]>
Date: Tue, 12 Jan 2016 11:09:20 +0300

Hi Panos,

thank you for sharing this draft. A couple of quick comments. 

First, I think that it is better to use a new status Notification to negotiate this feature 
rather than a Vendor ID payload. It is more in line with the way other IKEv2 extensions 
are negotiated and it would allow not to waste 16 bytes in the IKE_SA_INIT messages. 

And second, I'm not comfortable with using fixed algorithms (AES, HMAC_SHA2) and
not addressing algorithm agility. Fortunately, your draft says that this might change
in future versions. I think it is an important feature ant I hope it'll be addressed.

Regards,
Valery Smyslov.

  ----- Original Message ----- 
  From: Panos Kampanakis (pkampana) 
  To: Perlner, Ray ; [email-masked] 
  Cc: Liu, Yi-Kai ; David McGrew (mcgrew) ; Waltermire, David A. ; Frankel, Sheila E. ; Scott Fluhrer (sfluhrer) ; Moody, Dustin 
  Sent: Tuesday, January 12, 2016 8:44 AM
  Subject: Re: [IPsec] NIST question concerning IKEv2 and quantum resistance

  Hi Ray,

  Feedback is welcome.

  Rgs,

  Panos

  Hi all. 

  Thanks,

  Ray

------------------------------------------------------------------------------

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

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Wed, 13 Jan 2016 14:32:32 +0000

From: Valery Smyslov [mailto:[email-masked]]
Sent: Tuesday, January 12, 2016 3:09 AM
To: Panos Kampanakis (pkampana); Perlner, Ray; [email-masked]
Cc: Liu, Yi-Kai; David McGrew (mcgrew); Waltermire, David A.; Frankel, Sheila E.; Scott Fluhrer (sfluhrer); Moody, Dustin
Subject: Re: [IPsec] NIST question concerning IKEv2 and quantum resistance

Hi Panos,

That is certainly a reasonable suggestion.

There are two uses of crypto within the protocol:

-          It defines the transform of the nonce from the on-the-wire version into the one presented to the IKEv2 KDF (mixing in the PPK).

-          The initiator gives an indication of which PPK to use (without leaking any information about it to someone two doesn't know the value).

For the first use, it would be reasonable to have the initiator define a bitmask of the algorithms it supports, and the responder to select one

This second use is rather trickier to have agility; it is sent before the initiator has any contact to the responder.  I don't see how the responder can indicate which algorithms it supports (without adding a round trip to the protocol).  I don't see any really good alternatives:

-          The initiator could send an indication about which algorithm it is used to encode the ppk (and the responder either understands it or rejects it).  I don't see how that is much of an improvement.

-          The initiator could send the indication with multiple algorithms (and the responder selects which one it supports); however that strikes me as secure as the weakest of the supported algorithms (because if one of them leaks any information, the attacker learns that leakage).

We can update the draft to use a status notification, and to have a negotiated nonce transform; I think we'll leave the indication algorithm fixed (as I don't see a good alternative).

Regards,
Valery Smyslov.

----- Original Message -----
From: Panos Kampanakis (pkampana)<mailto:[email-masked]>
To: Perlner, Ray<mailto:[email-masked]> ; [email-masked]<mailto:[email-masked]>
Cc: Liu, Yi-Kai<mailto:[email-masked]> ; David McGrew (mcgrew)<mailto:[email-masked]> ; Waltermire, David A.<mailto:[email-masked]> ; Frankel, Sheila E.<mailto:[email-masked]> ; Scott Fluhrer (sfluhrer)<mailto:[email-masked]> ; Moody, Dustin<mailto:[email-masked]>
Sent: Tuesday, January 12, 2016 8:44 AM
Subject: Re: [IPsec] NIST question concerning IKEv2 and quantum resistance

Hi Ray,

Feedback is welcome.

Rgs,
Panos

From: IPsec [mailto:[email-masked]] On Behalf Of Perlner, Ray
Sent: Wednesday, January 06, 2016 3:33 PM
To: [email-masked]<mailto:[email-masked]>
Cc: Liu, Yi-Kai <[email-masked]<mailto:[email-masked]>>; Moody, Dustin <[email-masked]<mailto:[email-masked]>>; Frankel, Sheila E. <[email-masked]<mailto:[email-masked]>>; Waltermire, David A. <[email-masked]<mailto:[email-masked]>>
Subject: [IPsec] NIST question concerning IKEv2 and quantum resistance

Hi all.

Thanks,
Ray

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

---

From: Michael Richardson <[email-masked]>
Date: Wed, 13 Jan 2016 11:59:05 -0500

Scott Fluhrer (sfluhrer) <[email-masked]> wrote:
    > - It defines the transform of the nonce from the on-the-wire version into the
    > one presented to the IKEv2 KDF (mixing in the PPK).

    > - The initiator gives an indication of which PPK to use (without leaking any
    > information about it to someone two doesn’t know the value).

    > For the first use, it would be reasonable to have the initiator define a
    > bitmask of the algorithms it supports, and the responder to select one

That's not very algorithm agile, nor very IKEv2 happy. Don't we already have
IANA values for all the algorithms involved? (shouldn't we have them)

    > This second use is rather trickier to have agility; it is sent before the
    > initiator has any contact to the responder. I don’t see how the
    > responder can
    > indicate which algorithms it supports (without adding a round trip to the
    > protocol).

This is why I suggested... if you have to add a round trip anyway... might as
well solve a puzzle or something along the way.

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Wed, 13 Jan 2016 22:45:40 +0000

> -----Original Message-----
> From: IPsec [mailto:[email-masked]] On Behalf Of Michael
> Richardson
> Sent: Wednesday, January 13, 2016 11:59 AM
> To: [email-masked]

The 'bitmask idea' was off the top of my head; we could certainly give a list of IANA values (such as the IKEv2 PRF).  My chief fear is that we don't overengineer this; this really is a "short term solution" (with the usual caveat that there are no short term solutions), and that a post-quantum DH-like function is the Right Thing (only we haven't agreed on that yet).  The issue with having a complex negotiation process is that may be a lot of rarely executed code, and that in itself may lead to security vulnerabilities.

> well solve a puzzle or something along the way.

One of the constraints that we felt we had to live within was to minimize the changes we made to IKEv2, both from a crypto standpoint, and from a state machine standpoint.  Hence, we decided that adding vendor id payloads (or notification payloads) to existing messages we OK, however adding additional round trips was out of bounds.

If one were to add additional round trips, a cleaner solution would be to negotiate the initial IKE SA as per the RFC, and then if the two sides decide that they need QR, create a child SA (in a PQR manner).  The current approach has the issue that we need to stir in the post-quantum magic before the identities were exchanged (and hence the initiator gives the indication of the ppk). If you establish a secure connection (and exchange identities) first, then it becomes much cleaner (as both sides would know who they are talking to, and which ppk they should use).  However, that was deemed to be too large of an delta.

---

From: "Valery Smyslov" <[email-masked]>
Date: Thu, 14 Jan 2016 15:57:46 +0300

Hi Scott,

> The 'bitmask idea' was off the top of my head; we could certainly give a list of
> IANA values (such as the IKEv2 PRF).  My chief fear is that we don't overengineer
> this; this really is a "short term solution" (with the usual caveat that there are no
> short term solutions), and that a post-quantum DH-like function is the Right Thing
> (only we haven't agreed on that yet).  The issue with having a complex negotiation
> process is that may be a lot of rarely executed code, and that in itself may lead
> to security vulnerabilities.

Is it possible to use the already negotiated IKEv2 prf inside the modified crypto formulas?
In this case they would look like:

    SKEYSEED = prf(prf(ppk, Ni) | prf(ppk, Nr), g^ir)
    (SK_d | SK_ai | SK_ar | SK_ei | SK_er | SK_pi | SK_pr) =
          prf+(SKEYSEED, prf(ppk, Ni) | prf(ppk, Nr) | SPIi | SPIr)

and so on. I'm not a cryptographer, but it seems to me that this is safe, isn't it?
In this case no additional negotiation is required since prf is negotiated in IKEv2
anyway and thus we would have algorithm agility in KDF for free.

> One of the constraints that we felt we had to live within was to minimize
> the changes we made to IKEv2, both from a crypto standpoint, and from
> a state machine standpoint.  Hence, we decided that adding vendor
> id payloads (or notification payloads) to existing messages we OK,
> however adding additional round trips was out of bounds.

Note, that IKEv2 state machine has already accomodated the possibility
of an additional round trip in case the initiator has incorrectly guessed the
DH group. Introducing one more condition for additional round trip
should not be too hard, however I agree that it adds some complexity
and thus may be considered inappropriate for a short-term solution.

However, if no better solution exists I'd prefer to live with a single
fixed crypto primitive, than with two. Is it possible to get rid of
AES and to change the indication of the ppk to use to something
like the following?

HMAC_SHA256(HMAC_SHA256(ppk, "A"), random_bytes)

(disclaimer: I'm not a cryptographer)

> If one were to add additional round trips, a cleaner solution would be
> to negotiate the initial IKE SA as per the RFC, and then if the two sides
> decide that they need QR, create a child SA (in a PQR manner).
> The current approach has the issue that we need to stir in the post-quantum
> magic before the identities were exchanged (and hence the initiator gives
> the indication of the ppk). If you establish a secure connection (and exchange
> identities) first, then it becomes much cleaner (as both sides would know who
> they are talking to, and which ppk they should use).  However, that was
> deemed to be too large of an delta.

I'm not sure this approach is easier than approch with additional round trip.
I understand that it has some advantages (e.g. no need for linear key search),
but from state machine point of view it may appear to be more complex.

Regards,
Valery.

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Thu, 14 Jan 2016 15:02:19 +0000

> From: IPsec [mailto:[email-masked]] On Behalf Of Valery Smyslov
> Sent: Thursday, January 14, 2016 7:58 AM
> To: Scott Fluhrer (sfluhrer); Michael Richardson; [email-masked]
> >> That's not very algorithm agile, nor very IKEv2 happy. Don't we
> >> already have IANA values for all the algorithms involved? (shouldn't
> >> we have them)
> >
> > The 'bitmask idea' was off the top of my head; we could certainly give
> > a list of IANA values (such as the IKEv2 PRF).  My chief fear is that
> > we don't overengineer this; this really is a "short term solution"
> > (with the usual caveat that there are no short term solutions), and
> > that a post-quantum DH-like function is the Right Thing (only we
> > haven't agreed on that yet).  The issue with having a complex
> > negotiation process is that may be a lot of rarely executed code, and that in
> itself may lead to security vulnerabilities.
> 
> In this case no additional negotiation is required since prf is negotiated in
> IKEv2 anyway and thus we would have algorithm agility in KDF for free.

I like this -- I'm stealing this idea.

> >> This is why I suggested... if you have to add a round trip anyway...
> >> might as well solve a puzzle or something along the way.
> >
> > One of the constraints that we felt we had to live within was to
> > minimize the changes we made to IKEv2, both from a crypto standpoint,
> > and from a state machine standpoint.  Hence, we decided that adding
> > vendor id payloads (or notification payloads) to existing messages we
> > OK, however adding additional round trips was out of bounds.
> 
> Note, that IKEv2 state machine has already accomodated the possibility of an
> additional round trip in case the initiator has incorrectly guessed the DH
> group. Introducing one more condition for additional round trip should not
> be too hard, however I agree that it adds some complexity and thus may be
> considered inappropriate for a short-term solution.
> 
> However, if no better solution exists I'd prefer to live with a single fixed
> crypto primitive, than with two. Is it possible to get rid of AES and to change
> the indication of the ppk to use to something like the following?
> 

Your proposal is perfectly sound from a cryptography perspective.  Actually, the reason we proposed the "entry in the AES codebook" approach, rather than something like the above structure, is due to practical reasons.  When the responder receives the hint, he has no idea which ppk the initiator is referring to (and he doesn't know the identity yet); our model is that the responder has a list of ppk's that he knows about, and checks to see if the one that the initiator had is on the list.  It'd be nice if there was a way for the responder to search through his databases of known ppk's quickly, however I don't know how to let him do it in sublinear time (without leaking whether two exchanges used the same ppk, which would leak information about the identities).  So, what we settled on is to make the linear scan for the right PPK as fast as possible.  With our proposed solution, an aggressive responder could have all the AES keys corresponding to the ppk preexpanded, and just check each potential ppk by doing one AES block encryption (or decryption, if they prefer); if the implementation has AES-NI, that is fairly fast.  With your proposal, they could preexpand the HMAC keys, but would still need to do two SHA256 compression function evaluations.

> > to negotiate the initial IKE SA as per the RFC, and then if the two
> > sides decide that they need QR, create a child SA (in a PQR manner).
> > The current approach has the issue that we need to stir in the
> > post-quantum magic before the identities were exchanged (and hence the
> > initiator gives the indication of the ppk). If you establish a secure
> > connection (and exchange
> > identities) first, then it becomes much cleaner (as both sides would
> > know who they are talking to, and which ppk they should use).
> > However, that was deemed to be too large of an delta.
> 
> I understand that it has some advantages (e.g. no need for linear key
> search), but from state machine point of view it may appear to be more
> complex.

It would get rid of the linear scan issue.

---

From: Paul Wouters <[email-masked]>
Date: Thu, 14 Jan 2016 11:28:00 -0500 (EST)

> I like this -- I'm stealing this idea.

Note that using a hash of a hash is frowned upon. See the latest SLOTH
on TLS for an example of a collision attack that used the fact that a
hashed message got hashed again (unlike IKE which hashes only the data)

Paul

---

From: "Valery Smyslov" <[email-masked]>
Date: Fri, 15 Jan 2016 10:34:14 +0300

Hi Paul,

> hashed message got hashed again (unlike IKE which hashes only the data)

Not really. IKE does use prf inside prf. Let's expand SK_* computation formula:

SK_* = prf+ (SKEYSEED, Ni | Nr | SPIi | SPIr) = 
prf (prf(Ni | Nr, g^ir), Ni | Nr | SPIi | SPIr | 0x01) | 
prf (prf(Ni | Nr, g^ir), prf (prf(Ni | Nr, g^ir), Ni | Nr | SPIi | SPIr | 0x01) | Ni | Nr | SPIi | SPIr | 0x02)
and so on.

I don't think it's wrong from cryptography point of view if the prf is not broken 
(usual disclaimer: I'm not a cryptographer).

However, thank you for bringing in the SLOTH attack.
As fas as I understand from the paper http://www.mitls.org/downloads/transcript-collisions.pdf 
it is based on the ability for an attacker to find collisions in a weak hashes 
(md5 and sha1). In particular the authors uses chosen-prefix collision attacks
to break some security protocols. They mostly focused on breaking TLS,
but Section VI contains description of a possible attack on IKEv2.

As far as I understnd the attack on IKEv2 it is based on the cookie request
feature. The attacker makes a cookie request to the initiator
with the cookie crafted in such a way, that the hash of the IKE_SA_INIT message
containing this cookie would collide with the hash of the IKE_SA_INIT message
containing attacker-chosen KE payload. It would allow the attacker
to impersonate the initiator.

If I got it right the ability for an attacker to quickly find a hash collision
is based (besides using weak hashes) on presumption that 
the cookie is always the very first payload in the message,
as depicted in the Section 2.6 in the RFC 7296. So it is
presumed that the cookie always preceedes any unpredictable
for the attacker values in the message, that allows to perform
an effective chosen-prefix attack on a hash.

So, I think that we can completely thwart this attack (regardless
on the possible weakness of the used hashes) if we make
a recommendation for implementers to put the cookie at the
end of the message. RFC 7296 doesn't imply any restrictions
on the payloads order. However the Section 2.6 states:

   If the IKE_SA_INIT response
   includes the COOKIE notification, the initiator MUST then retry the
   IKE_SA_INIT request, and include the COOKIE notification containing
   the received data as the first payload, and all other payloads
   unchanged.  

It's a bit unclear for me whether this MUST is concerned with 
the requirement to retry request only, in which case it is only
a recommendation to place the COOKIE before other payloads,
or the MUST is also applied to the text that COOKIE is the 
first payload (that would be unfortunate).

What does IPsec community think of it? Should we fix the protocol
to thwart this attack completely? Is the recommendation to 
move the COOKIE to the end of the message enough to achive that?
Will this change break many existing implementations?

Regards,
Valery Smyslov.

---

From: "Valery Smyslov" <[email-masked]>
Date: Fri, 15 Jan 2016 11:48:03 +0300

Hi Scott, 

> Your proposal is perfectly sound from a cryptography perspective.  
> Actually, the reason we proposed the "entry in the AES codebook" approach, 
> rather than something like the above structure, is due to practical reasons.  
> When the responder receives the hint, he has no idea which ppk the initiator 
> is referring to (and he doesn't know the identity yet); our model is that the responder 
> has a list of ppk's that he knows about, and checks to see if the one that the initiator 
> had is on the list.  It'd be nice if there was a way for the responder to search through 
> his databases of known ppk's quickly, however I don't know how to let him do it 
> in sublinear time (without leaking whether two exchanges used the same ppk, 
> which would leak information about the identities).  So, what we settled on is to make 
> the linear scan for the right PPK as fast as possible.  With our proposed solution, 
> an aggressive responder could have all the AES keys corresponding to the ppk preexpanded, 
> and just check each potential ppk by doing one AES block encryption (or decryption, 
> if they prefer); if the implementation has AES-NI, that is fairly fast.  
> With your proposal, they could preexpand the HMAC keys, but would still need 
> to do two SHA256 compression function evaluations.

I see the point, thank you. However AES support in hardware is not 
always available, so I still think that having a single crypto primitive
is better in this situation.

But your explanations brings me to a conclusion, that the protocol
could me modified. Please see my logical chain.

The necessity to perform a linear serach of the ppk keys (and thus spending
some CPU power) makes a responder more succeptible to DoS attack,
because it must spend resources in response to any IKE_SA_INIT exchange
even from spoofed IP address. In this situation a sane responder would try 
to defend itself sending a cookie request - this would guarantee that
the initiator is alive and the IP address is not spoofed. So, if the cookie
request is to be sent in most cases when the IKE_SA_INIT message
contains ppk extension anyway, then the protocol could be modified
to make cookie request mandatory in this situation. Then the IKE_SA_INIT
exchange would look like:

   HDR, SAi1, KEi, Ni, N(PPK_SUPPORTED)  -->
                                <--  HDR, N(COOKIE), N(PPK_SUPPORTED, crypto=xxx, random_data=zzz)

The responder selects prf (and encryption, if it is used) algorithms from the SAi1
payload. It also supplies random_data that the initiator must use when it encodes
the ppk. The initiator computes an encoded ppk and retries the request.

   HDR, N(COOKIE), SAi1, KEi, Ni, N(PPK_KEY)  -->
                                <--  HDR, SAr1, KEr, Nr, [CERTREQ]

This variant has a disadvantage that ppk will always require an additional round trip.
However it has the following benefits:
1. Full support for algorithms agility
2. No need to perform CPU-intensive operations until the initiator's IP is confirmed
3. In this variant it is the responder who supplies random_data to initiator to encode ppk,
    so it is on the responder discretion how to choose them. For example,
    it may precompute the encoded ppk values when it is idle, or it can
    reuse random_data several times. This allow the responder to perform
    the ppk search in sub-linear time in some circumstances.
4. The additional round trip requires a minimum change to IKEv2,
    since cookie request must be supported anyway.

What do you think?

Regards,
Valery.

---

From: Yaron Sheffer <[email-masked]>
Date: Fri, 15 Jan 2016 10:55:44 +0200

> As fas as I understand from the paper 
> http://www.mitls.org/downloads/transcript-collisions.pdf it is based 
> on the ability for an attacker to find collisions in a weak hashes 
> is based (besides using weak hashes) on presumption that the cookie is 
> always the very first payload in the message,
> It's a bit unclear for me whether this MUST is concerned with the 
> requirement to retry request only, in which case it is only
> or the MUST is also applied to the text that COOKIE is the first 
> payload (that would be unfortunate).
>
> to thwart this attack completely? Is the recommendation to move the 
> COOKIE to the end of the message enough to achive that?

As far as I can tell, the cookie hash algorithm is an implementation 
decision of the responder and (despite what's implied in the paper) is 
never specified in the protocol. It would be much simpler to add a 
section to the new 4307bis saying that this hash is security-critical, 
and recommending SHA-256 or stronger.

The experience with TLS is that making small protocol changes to protect 
against weak algorithms is not a good long-term strategy. It's just a 
challenge for researchers to come up with better attacks.

I believe the hash-and-URL mechanism is not used in practice. But if it 
is, that's another place where we have hardcoded SHA-1, and maybe we 
should start worrying about it.

Thanks,
     Yaron

---

From: Yoav Nir <[email-masked]>
Date: Fri, 15 Jan 2016 11:19:07 +0200

> On 15 Jan 2016, at 10:55 AM, Yaron Sheffer <[email-masked]> wrote:
> 
>> As fas as I understand from the paper http://www.mitls.org/downloads/transcript-collisions.pdf it is based on the ability for an attacker to find collisions in a weak hashes (md5 and sha1). In particular the authors uses chosen-prefix collision attacks
>> is based (besides using weak hashes) on presumption that the cookie is always the very first payload in the message,
>> It's a bit unclear for me whether this MUST is concerned with the requirement to retry request only, in which case it is only
>> or the MUST is also applied to the text that COOKIE is the first payload (that would be unfortunate).
>> 
>> to thwart this attack completely? Is the recommendation to move the COOKIE to the end of the message enough to achive that?
> As far as I can tell, the cookie hash algorithm is an implementation decision of the responder and (despite what's implied in the paper) is never specified in the protocol. It would be much simpler to add a section to the new 4307bis saying that this hash is security-critical, and recommending SHA-256 or stronger.

The SLOTH paper does not depend at all on the hash used to break the cookie. They use the cookie mechanism to inject a prefix (Because the Initiator dutifully repeats the cookie that the MITM gave them) to control the hash of the entire packet to create a collision. They also rely on neither Initiator nor responder checking cookie lengths or even validating the cookies if a DoS attack is not underway. Maybe we should specify that in the anti-ddos draft.

> The experience with TLS is that making small protocol changes to protect against weak algorithms is not a good long-term strategy. It's just a challenge for researchers to come up with better attacks.
> 
> I believe the hash-and-URL mechanism is not used in practice. But if it is, that's another place where we have hardcoded SHA-1, and maybe we should start worrying about it.

AFAIK a second pre-image attack on SHA-1 where the second pre-image looks like a valid X509 certificate is still far. Even if it were not, what is the attack? the real Initiator fetches the wrong certificate and the authentication fails?  This happens even if you don’t match the SHA-1.

Yoav

---

From: Tero Kivinen <[email-masked]>
Date: Fri, 15 Jan 2016 13:11:46 +0200

Valery Smyslov writes:
> However, thank you for bringing in the SLOTH attack. As fas as I
> understand from the paper
> (md5 and sha1). In particular the authors uses chosen-prefix
> collision attacks to break some security protocols. They mostly
> focused on breaking TLS, but Section VI contains description of a
> possible attack on IKEv2.
> 
> As far as I understnd the attack on IKEv2 it is based on the cookie
> request feature. The attacker makes a cookie request to the
> initiator with the cookie crafted in such a way, that the hash of
> the IKE_SA_INIT message containing this cookie would collide with
> the hash of the IKE_SA_INIT message containing attacker-chosen KE
> payload. It would allow the attacker to impersonate the initiator.
> 
> If I got it right the ability for an attacker to quickly find a hash
> collision is based (besides using weak hashes) on presumption that
> the cookie is always the very first payload in the message, as
> depicted in the Section 2.6 in the RFC 7296. So it is presumed that
> the cookie always preceedes any unpredictable for the attacker
> values in the message, that allows to perform an effective
> chosen-prefix attack on a hash.

They also assume that everything before the cookie is fixed, i.e. that
the IKEv2 HDR is also fixed. IKEv2 HDR contains the SPIi and SPIr. The
SPIr in the first message is all zeros, but the SPIi is selected by
the initiator to be random. If the SPIi from the initiator is
unpredictable, i.e. not fixed constant, then this changes the attack
from offline 2^77 hash collision attack against SHA1 to online 2^77
hash collision attack, i.e. the attacker needs to fix SHA1 hash
collision during the negotiation, without any precalculations.

I have already sent an email to the authors of the paper about this
and I think they agree on that.

The problem is that RFC7296 does not require SPIs to be random or
unpredictable. RFC7296 just requires them to be unique, so there is
nothing wrong in the implementation which would use fixed SPIi of
0x0000 0000 0000 0001 for all IKE SAs (and would only support one IKE
SA).

Fortunately I have not seen any implementations doing that, I think
all implementations I have seen use random IKEv2 SPIi.

In the IKEv1 things were different as the SPIi and SPIr were actually
cookies, and they were sometimes generated using hashing of the
addresses etc and some random secret, and then there might have been
some kind of secret generation counter or similar. 

> first payload (that would be unfortunate).

There is no point of changing the cookie location, as this attack does
not really work. If attacker are able to do hash collision attacks
during the exchange against the hash we are using then I think the
hash needs to be considered broken. I do not think even NSA can find
SHA-1 hash collision during the few seconds they have time during the
exchange.

Also this attack do require that the user use the groups with small
subgroups, like groups 22-24 (and their previous paper the authors of
this paper said that curve25519 has one small subgroup with size of 8,
see page 9 of [1]) so they can make the g^xy' same as g^x'y by forcing
both ends to use same small subgroup and trying so many times that the
g^xy' and g^x'y happened to be same. If the size of subgroup is less
than then there is good change that will happen with few tries.

> Will this change break many existing implementations?

I would recommend that we make sure our SPIs are unpredicatable and
random instead of only being unique, and that we always do small
subgroup checks regardless whether we reuse the private Diffie-Hellman
values or not for those groups that have small subgroups (22-24,
curve25519).

[1] https://alfredo.pironti.eu/research/sites/default/files/ndss15.pdf
-- 
[email-masked]

---

From: "Valery Smyslov" <[email-masked]>
Date: Fri, 15 Jan 2016 16:42:46 +0300

Hi Tero,

> collision during the negotiation, without any precalculations.

Ah, that's right.

> SHA-1 hash collision during the few seconds they have time during the

That's right, however I have an impression that we are close 
to the safety margins here. IKE SPI is relatively short and even
if it is chosen at random it is often generated using non-cryptographically
strong RNG, for example by invocation rand(), so that the 
attacker may have a chance to predict it. This makes me 
think that with a progress in hash analysys the attack may
become practical. Moving COOKIE to the end of the message would make 
the attack much more difficult, probably infeasible. And note,
that this change wouldn't violate RFC 7296, since it explicitely 
allows payloads to appear in the message in any order.

However, I understand that it may break some existing implementations,
and taking into considerations that the attack seems to be
impractical currently, I tend to agree with Tero that
we may do nothing right now. Probably postpone it to 
some future protocol update.

Regards,
Valery.

---

From: "Valery Smyslov" <[email-masked]>
Date: Fri, 15 Jan 2016 16:55:46 +0300

Hi Yoav,

>> As far as I can tell, the cookie hash algorithm is an implementation decision
>> of the responder and (despite what's implied in the paper) is never specified
>> in the protocol. It would be much simpler to add a section to the new 4307bis
>>saying that this hash is security-critical, and recommending SHA-256 or stronger.
>
> The SLOTH paper does not depend at all on the hash used to break the cookie.
> They use the cookie mechanism to inject a prefix (Because the Initiator dutifully repeats
> the cookie that the MITM gave them) to control the hash of the entire packet to create a collision.
> They also rely on neither Initiator nor responder checking cookie lengths or even validating
> the cookies if a DoS attack is not underway. Maybe we should specify that in the anti-ddos draft.

The initiator cannot validate the cookie - it is an opaque blob for him. Should he reject
the cookie if its length is more than 64 bytes? Possibly. I don't know.
It's a bit strange to check an opaque object...

What about the responder - he doesn't see any cookie in this attack - the attacker
sends the crafted cookie only to the initiator and sends a crafted
IKE_SA_INIT message w/o cookie to the responder (as far as I understand the attack).

Regards,
Valery.

---

From: Paul Wouters <[email-masked]>
Date: Fri, 15 Jan 2016 09:41:26 -0500 (EST)

>> > >  Will this change break many existing implementations?

We (libreswan) did a little hardening on the cookie that will verify
unexpected cookies anyway, contrary to current RFC:

https://securityblog.redhat.com/2016/01/13/the-sloth-attack-and-ikeipsec/

Paul

---

From: Paul Wouters <[email-masked]>
Date: Fri, 15 Jan 2016 10:18:26 -0500 (EST)

> some kind of secret generation counter or similar.

We use random for the SPIi but use this latter described method for
SPIr. This ensures an attacker cannot empty your entropy pool, or see
the raw bytes of your entropy pool when you happened to use a bad PRNG
like DUAL_EC or something. We use the same methods for IKEv1 and IKEv2.

> than then there is good change that will happen with few tries.

I did not know curve25519 also has that problem :/

> random instead of only being unique

See my above concern about an attacker depleting the entropy pool.

> , and that we always do small

We should, as NIST already requires it anyway.

I am curious though why people re-use DH values. Is that really still
needed on busy servers? This has never been in freeswan, openswan or
libreswan and we have never heard people complain (and yes we do have
big deployment servers too, but not on shitty 1995 hardware :)

Paul

---

From: Paul Wouters <[email-masked]>
Date: Fri, 15 Jan 2016 10:21:33 -0500 (EST)

On Fri, 15 Jan 2016, Yoav Nir wrote:

> They use the cookie mechanism to inject a prefix (Because the Initiator dutifully repeats the cookie that the MITM gave them) to control the hash of the entire packet to create a collision. They also rely on neither Initiator nor responder checking cookie lengths or even validating the cookies if a DoS attack is not underway. Maybe we should specify that in the anti-ddos draft.

So we added that patch to libreswan. It will now always verify the
cookie even when it isnt sending out ddos cookies itself. We might
tweak it a little bit with a timer to limit the damage attackers
can do by sending many spoofed IKE_INIT packets with COOKIES that
we'd be burning our hasher on.

> AFAIK a second pre-image attack on SHA-1 where the second pre-image looks like a valid X509 certificate is still far. Even if it were not, what is the attack? the real Initiator fetches the wrong c…

Similarly for their proposed IKEv1 attack using the ID payload.

Paul

---

From: Yoav Nir <[email-masked]>
Date: Fri, 15 Jan 2016 21:24:30 +0200

> On 15 Jan 2016, at 3:55 PM, Valery Smyslov <[email-masked]> wrote:
> 
> Hi Yoav,
> 
> It's a bit strange to check an opaque object…

It’s an opaque object that the RFC says should be up to 64 bytes.

> IKE_SA_INIT message w/o cookie to the responder (as far as I understand the attack).

There is a cookie. See Figure 12 in Paul’s blog post:
https://securityblog.redhat.com/2016/01/13/the-sloth-attack-and-ikeipsec/

The responder accepts a cookie that it never sent. It doesn’t check the cookie because there is, in fact, no DoS attack. That seems wrong.

Yoav

---

From: "Valery Smyslov" <[email-masked]>
Date: Fri, 15 Jan 2016 23:32:25 +0300

> It’s an opaque object that the RFC says should be up to 64 bytes.

I know that. However it doesn make this check less strange for me.
In my opinion this restriction is mostly for a responder, who generates a cookie.

> https://securityblog.redhat.com/2016/01/13/the-sloth-attack-and-ikeipsec/

Ah, you are right. I missed that in a quick read.

After second read it seems to me that there is one more  obstacle to that attack in real world.
It seems that attacker appends original initiator's SAi, KEi, Ni payloads to its
message sent to responder (as info`). So, this message would contain two SA payloads,
two KE payloads etc. I believe the responder must return INVALID_SYNTAX in this case.

> attack. That seems wrong.

Agreed. The proper action would be to request another cookie.
And in this case the attack would fail.

Regards,
Valery.

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Fri, 15 Jan 2016 21:07:32 +0000

> From: IPsec [mailto:[email-masked]] On Behalf Of Paul Wouters
> Sent: Friday, January 15, 2016 10:18 AM
> To: Tero Kivinen
> Cc: [email-masked] WG
> Subject: Re: [IPsec] SLOTH & IKEv2
> 
> 

Actually, if you implement curve25519 as specified in irtf-cfrg-curves draft, you don't have that problem

With that curve, each side selects private x, y values which are a multiple of 8 (as specified in the irtf-cfrg-curves draft,  see section 5)

Because of that, if someone passes you an element of the size-8 subgoup, you'll always generate the identity element (aka the netural element aka the point at infinity) for that curve

And, the draft requires you to check for that value (and reject it if it occurs); see section 6.1

   The check for the all-zero value results from the fact that the
   X25519 function produces that value if it operates on an input
   corresponding to a point with order dividing the co-factor, h, of the
   curve.  This check is cheap and so MUST always be carried out.  The
   check may be performed by ORing all the bytes together and checking
   whether the result is zero as this eliminates standard side-channels
   in software implementations.

Hence, if Curve25519 is implemented as stated in the draft, the problem doesn't occur; if someone introduces such a low-order point, the connection will fail.

> I am curious though why people re-use DH values. Is that really still needed
> on busy servers? This has never been in freeswan, openswan or libreswan
> and we have never heard people complain (and yes we do have big
> deployment servers too, but not on shitty 1995 hardware :)
> 
> Paul
>

---

From: Paul Wouters <[email-masked]>
Date: Fri, 15 Jan 2016 16:15:04 -0500 (EST)

> It’s an opaque object that the RFC says should be up to 64 bytes.

I tried to find a reference that the cookie is max 64 bytes and coul not
find it. So I concluded the valid max is a regular Notify payload length
specified in two octets, so 65535 bytes. I'm happy to be proven wrong :P

> The responder accepts a cookie that it never sent. It doesn’t check the cookie because there is, in fact, no DoS attack. That seems wrong.

As I also explain, it is probably motivated by supporting the server
switching to "no longer need cookies" and clients coming with a cookie
not getting denied. I agree that the server should still check any
cookie it receives, or after a timer reject all connections with
a (guaranteed false) cookie. But that would need to be an update to
RFC 7296.

Paul

---

From: Yaron Sheffer <[email-masked]>
Date: Fri, 15 Jan 2016 23:21:09 +0200

Sec. 2.6: When a responder detects a large number of half-open IKE SAs, 
it SHOULD reply to IKE_SA_INIT requests with a response containing the 
COOKIE notification.  The data associated with this notification MUST be 
between 1 and 64 octets in length (inclusive), and its generation is 
described later in this section.

On 01/15/2016 11:15 PM, Paul Wouters wrote:
>> The responder accepts a cookie that it never sent. It doesn’t check 
>> the cookie because there is, in fact, no DoS attack. That seems wrong.
>

---

From: Paul Wouters <[email-masked]>
Date: Fri, 15 Jan 2016 16:24:08 -0500 (EST)

On Fri, 15 Jan 2016, Yaron Sheffer wrote:

> Sec. 2.6: When a responder detects a large number of half-open IKE SAs, it 
> SHOULD reply to IKE_SA_INIT requests with a response containing the COOKIE 
> notification.  The data associated with this notification MUST be between 1 
> and 64 octets in length (inclusive), and its generation is described later in 
> this section.

Wow you are right. I searched multiple times and missed it. Clearly it
should not have been thrown in as an afterthought for "When a responder
detects a large number of ....".

:(

Okay, I'll update the blog post and our code :P

Paul

---

From: Yoav Nir <[email-masked]>
Date: Fri, 15 Jan 2016 23:37:18 +0200

> On 15 Jan 2016, at 11:15 PM, Paul Wouters <[email-masked]> wrote:
> 

Section 2.6, top of page 33 in RFC 7296:

  When a responder detects a large number of half-open IKE SAs, it
  SHOULD reply to IKE_SA_INIT requests with a response containing the
  COOKIE notification.  The data associated with this notification MUST
  be between 1 and 64 octets in length (inclusive), and its generation
  is described later in this section. 
> a (guaranteed false) cookie. But that would need to be an update to

We will be making this even more murky with puzzles. A cookie should be seen again after about 1 RTT, but an initiator may take a while to return a solved puzzle. How long do we set the timer for a solved puzzle?

Yoav

---

From: "HU, Jun (Jun)" <[email-masked]>
Date: Sat, 16 Jan 2016 00:12:37 +0000

> It seems that attacker appends original initiator's SAi, KEi, Ni
> payloads to its message sent to responder (as info`). So, this message
> would contain two SA payloads, two KE payloads etc. I believe the
> responder must return INVALID_SYNTAX in this case.

[HJ] agree, however I can't find any text in RFC7296 states responder need to reject the request and return INVALID_SYNTAX in such case; an implementation might choose to just simply ignore the subsequent redundant payload and proceed...

---

From: Yoav Nir <[email-masked]>
Date: Sat, 16 Jan 2016 06:14:50 +0200

> On 15 Jan 2016, at 10:32 PM, Valery Smyslov <[email-masked]> wrote:
> 
> 

IIUC there are no two SA payloads and two KE payloads. All of those are part of the “cookie” sent to the real Responder. That is why it’s so large.

---

From: "HU, Jun (Jun)" <[email-masked]>
Date: Sat, 16 Jan 2016 05:17:15 +0000

> From: IPsec [mailto:[email-masked]] On Behalf Of EXT Yoav Nir
> Sent: Friday, January 15, 2016 8:15 PM
> To: Valery Smyslov
> Cc: [email-masked]; Paul Wouters; Scott Fluhrer (sfluhrer)
> >>> What about the responder - he doesn't see any cookie in this attack
> >>> - the attacker sends the crafted cookie only to the initiator and
> >>> sends a crafted IKE_SA_INIT message w/o cookie to the responder (as
> far as I understand the attack).
> >>
> IIUC there are no two SA payloads and two KE payloads. All of those are
> part of the “cookie” sent to the real Responder. That is why it’s so
> large.

[HJ] according to this figure(https://securityblog.redhat.com/wp-content/uploads/2016/01/sloth-ike-2.png):
The IKE_INIT request(m1') send to real responder contain infoi' at the end, which equals=SAi|g^x|Ni|infoi, so the actual m1'=HDR|C2|SAi'|g^x'|ni|SAi|g^x|ni|infoi; thus two SA, tw KE, two Ni payloads; C2 is the cookie payload in m1', it doesn't contain any payload. while the cookie payload in m1(IKE_INIT request from release initiator) does contain C1|SAi'|g^x'|ni

---

From: "Valery Smyslov" <[email-masked]>
Date: Sat, 16 Jan 2016 09:02:38 +0300

Hi,

>[HJ] agree, however I can't find any text in RFC7296 states responder need 
> to reject the request and return INVALID_SYNTAX in such case; an implementation 
> might choose to just simply ignore the subsequent redundant payload and proceed...

Sure, there is no such text in the RFC. However this requirement is implicit, since
the pictures in the Appendix C.1 show those payloads that may appear multiple
times in the messages as PLD+. It is assumed that those payloads that don't have 
the plus sign must appear only once (or not appear at all).

And if an implementation chooses to ignore the redundant payload, then
there is a  question - which payload is redundant? There is no requirements
in the RFC that payloads come in a specific order, so one implementation may
think that the first payload is actual and the subsequent is redundant, while the
other may think otherwise.

So I think INVALID syntax is the only proper response here.

Regards,
Valery.

---

From: "HU, Jun (Jun)" <[email-masked]>
Date: Sat, 16 Jan 2016 07:16:14 +0000

> From: EXT Valery Smyslov [mailto:[email-masked]]
> Sent: Friday, January 15, 2016 10:03 PM

[HJ] 
> To: HU, Jun (Jun); Yoav Nir

> >[HJ] agree, however I can't find any text in RFC7296 states responder
> >need  to reject the request and return INVALID_SYNTAX in such case; an
> >implementation  might choose to just simply ignore the subsequent
> redundant payload and proceed...
> 
> Sure, there is no such text in the RFC. However this requirement is
> implicit, since the pictures in the Appendix C.1 show those payloads
> that may appear multiple times in the messages as PLD+. It is assumed
> that those payloads that don't have the plus sign must appear only once
> (or not appear at all).
> 
> there is a  question - which payload is redundant? There is no
> requirements in the RFC that payloads come in a specific order, so one
> implementation may think that the first payload is actual and the
> subsequent is redundant, while the other may think otherwise.
> 

[HJ] I agree that sending INVALID_SYNTAX is the right behavior, just wish the RFC could be more clear about it.

---

From: Yoav Nir <[email-masked]>
Date: Sat, 16 Jan 2016 10:55:26 +0200

> On 16 Jan 2016, at 7:17 AM, HU, Jun (Jun) <[email-masked]> wrote:
> 
> 
> 
> The IKE_INIT request(m1') send to real responder contain infoi' at the end, which equals=SAi|g^x|Ni|infoi, so the actual m1'=HDR|C2|SAi'|g^x'|ni|SAi|g^x|ni|infoi; thus two SA, tw KE, two Ni payloads; C2 is the cookie payload in m1', it doesn't contain any payload. while the cookie payload in m1(IKE_INIT request from release initiator) does contain C1|SAi'|g^x’|ni

OK, but if those extra payloads are disguised as some notification (there is no payload actually called “info”), then responders do tend to ignore notifications they don’t recognize. 

Yoav

---

From: "Valery Smyslov" <[email-masked]>
Date: Sat, 16 Jan 2016 12:58:45 +0300

>> The IKE_INIT request(m1') send to real responder contain infoi' at the end, which equals=SAi|g^x|Ni|infoi,
>> so the actual m1'=HDR|C2|SAi'|g^x'|ni|SAi|g^x|ni|infoi; thus two SA, tw KE, two Ni payloads; C2 is the cookie
>> payload in m1', it doesn't contain any payload. while the cookie payload in m1(IKE_INIT request from release
>> initiator) does contain C1|SAi'|g^x’|ni
>
> OK, but if those extra payloads are disguised as some notification (there is no payload actually called “info”),
> then responders do tend to ignore notifications they don’t recognize.

True, but in this case the inputs to the hash function will be different (you need to insert Notification
payload header in the m`), so the attack will fail.

Regards,
Valery.

---

From: "Valery Smyslov" <[email-masked]>
Date: Sat, 16 Jan 2016 13:20:54 +0300

> payload header in the m`), so the attack will fail.

I must correct myself - if attacker takes care and puts the Notify payload header at the end of ck
it sends to initiator (and he must correctly guess the length of info`), then it will work - all the
original payloads from the initiator will appear inside Notification payload and will be ignored by responder.

Regards,
Valery.

---

From: "HU, Jun (Jun)" <[email-masked]>
Date: Fri, 15 Jan 2016 23:48:12 +0000

---

From: "HU, Jun (Jun)" <[email-masked]>
Date: Sat, 16 Jan 2016 16:44:54 +0000

> >> OK, but if those extra payloads are disguised as some notification
> >> (there is no payload actually called “info”), then responders do tend
> to ignore notifications they don’t recognize.
> >
> > True, but in this case the inputs to the hash function will be
> > different (you need to insert Notification payload header in the m`),
> so the attack will fail.
> 
> I must correct myself - if attacker takes care and puts the Notify
> payload header at the end of ck it sends to initiator (and he must
> correctly guess the length of info`), then it will work - all the
> original payloads from the initiator will appear inside Notification
> payload and will be ignored by responder.
> 

[HJ] how would this work? even attack append a notification header in ck, and return a ck= C1|SAi'|g^x'|ni| notify_header, then m1(from real initiator)=HDR|(C1|SAi'|g^x'|ni| notify_header)_as_ck|SAi|g^x|ni|nat-t, notify header is part of ck, won't be parsed as actual notify payload header.

---

From: "Valery Smyslov" <[email-masked]>
Date: Sun, 17 Jan 2016 11:32:19 +0300

> [HJ] how would this work? even attack append a notification header in ck, 
> and return a ck= C1|SAi'|g^x'|ni| notify_header, then 
> m1(from real initiator)=HDR|(C1|SAi'|g^x'|ni| notify_header)_as_ck|SAi|g^x|ni|nat-t, 
> notify header is part of ck, won't be parsed as actual notify payload header.

Yes, but when the attacker sends a message to the responder it replaces
ck with C2 and the message will look like

mi'=HDR | ck'=C2 | SAi' | g^xi' | ni' | notify_header | SAi | g^xi | ni | info_i

If the length indicated in the notify_header will be equal to the length of SAi | g^xi | ni | info_i,
then the responder will treat these payloads as a notify payload content and will ignore them.
So, for the responder the message will look like:

mi'=HDR | cookie | SA | KE | NONCE | Nx

where Nx is some unknown notification.

---

From: "HU, Jun (Jun)" <[email-masked]>
Date: Sun, 17 Jan 2016 23:18:08 +0000

> If the length indicated in the notify_header will be equal to the length
> of SAi | g^xi | ni | info_i, then the responder will treat these
> payloads as a notify payload content and will ignore them.
[HJ] yes, you are right. So to summary what has been discussed previous in this thread:
On Initiator side:
	-  This attack is impractical if the initiator's SPIi is unpredictable, since it is infeasible for attacker to compute C1/C2 offline for all possible SPIi. And it is impossible to compute C1/C2 online before client switch to a different SPIi.

-  On responder side:
	- if responder is expecting a cookie, then the C2 won't match the expecting cookie, responder will return the expecting cookie, this attack won't work in this case.
	- if responder is not expecting a cookie, then it could still verify the cookie to prevent this attack. One of the checks could be done is a legit cookie length must be <=64B.

---

From: "Valery Smyslov" <[email-masked]>
Date: Mon, 18 Jan 2016 09:50:39 +0300

> [HJ]So to summary what has been discussed previous in this thread:
> On Initiator side:
-  This attack is impractical if the initiator's SPIi is unpredictable, since it is infeasible 
> for attacker to compute C1/C2 offline for all possible SPIi. And it is impossible 
> to compute C1/C2 online before client switch to a different SPIi.
> 
> -  On responder side:
> - if responder is expecting a cookie, then the C2 won't match the expecting cookie, 
> responder will return the expecting cookie, this attack won't work in this case.
> - if responder is not expecting a cookie, then it could still verify the cookie to prevent this attack. 
> One of the checks could be done is a legit cookie length must be <=64B.

I think that responder must verify the cookie if it is present, regardless
on whether it is expected to be present or not. And it must request
another cookie if the verification failed.

Regards,
Valery.

---

From: Paul Wouters <[email-masked]>
Date: Mon, 18 Jan 2016 10:05:01 -0500 (EST)

> another cookie if the verification failed.

That would allow an initiator to trigger the cookie generating mechanism
on the responder on demand. I don't think that's a good idea.

I do agree the cookie if received must validate against the "current" or
"last secret before we disabled cookies". If not, I think that's a good
reason to not even answer the request - it's clearly malicious. I don't
think it should request a new cookie.

Paul

---

From: "Valery Smyslov" <[email-masked]>
Date: Mon, 18 Jan 2016 18:28:57 +0300

> on the responder on demand. I don't think that's a good idea.

And what then? I think the cookie generating mechanism is a local
matter and you have all means to make it secure.

---

From: Paul Wouters <[email-masked]>
Date: Mon, 18 Jan 2016 10:48:07 -0500 (EST)

> matter and you have all means to make it secure.

Sure, but why give attackers a chance at all?

Paul

---

From: "Valery Smyslov" <[email-masked]>
Date: Tue, 19 Jan 2016 10:01:27 +0300

Hi, 

few more thoughts on this attack.

> One of the checks could be done is a legit cookie length must be <=64B.

While all these checks on responder side are useful, they cannot really prevent 
this attack. The attack can be easily modified so that the message sent from 
the attacker to the responder looks unsuspicious. All that attacker need to do 
is to find C1 and C2 so, that the COOKIE notification type  in C1 is changed to 
any unused status notification type in C2. It is just a little bit harder than the current
version of attack. However after that the message sent from the attacker to
the responder will look like:

M' = HDR | Nx=C2 | SAi' | KEi' | NONCEi' | Ny=(SAi | KEi | NONCEi | info_i)

So the responder will see two unknown status notifications (Nx and Ny)
and will just ignore them. Nothing suspicious.

So the only real defense against this attack is an unpredictability of SPIi.
Is it enough? I don't know. I would feel more comfortable if initiator
puts the cookie at the end of the message, thus making this attack
infeasible:

   HDR, SAi1, KEi, Ni  -->
                                                            <--  HDR, N(COOKIE)
   HDR, SAi1, KEi, Ni, N(COOKIE) -->

Note that this doesn't violate RFC 7296, since the payloads may come
in any order. However it may break some existing implementations...

Regards,
Valery.

---

From: Michael Richardson <[email-masked]>
Date: Tue, 19 Jan 2016 10:23:15 -0500

> in any order. However it may break some existing implementations...

It seems like good advice.
Perhaps this is worth a IKE 2.1 value --- an initiator that says 2.1
is saying that it will always put the COOKIE last.

---

From: Tero Kivinen <[email-masked]>
Date: Tue, 19 Jan 2016 18:25:44 +0200

Valery Smyslov writes:
> While all these checks on responder side are useful, they cannot
> really prevent this attack.

Actually it does. 

> The attack can be easily modified so that the message sent from the
> attacker to the responder looks unsuspicious. All that attacker need
> to do is to find C1 and C2 so, that the COOKIE notification type in
> C1 is changed to any unused status notification type in C2. It is
> just a little bit harder than the current version of attack. However
> after that the message sent from the attacker to the responder will
> look like:
> 

Attacker cannot do that, as attacker will not be able to get original
initiator to reflect the Nx=C1 back in the m1. Cookies notifications
are used because are required from the initiator to be copied from the
original SA_INIT reply to the retry SA_INIT request.

For that unknown notification that would not work, i.e. when the
attacker sends back the

SA_INIT(ck=|C1|SA',gx'|ni|)

the initiator will ignore the first notification if it not cookie, and
will not retry with message sending cookie notification. 

> and will just ignore them. Nothing suspicious.

If the attacker changes the m1' to contain some other notification in
the beginning that cookie notification he needs to find different type
of collison where the prefix is no longer constant, i.e., he needs to
modify that. 

> So the only real defense against this attack is an unpredictability

And checking the small subgroups in Diffie-Hellman, i.e., not using
groups 22-24.

> in any order. However it may break some existing implementations...

I think using random SPIis is enough. Even if you SPI only contained
2^32 different values, that means that attacker needs to do expensive
precalculations for each of those different values, making the cost of
attack 2^32 times harder. 
-- 
[email-masked]

---

From: "Valery Smyslov" <[email-masked]>
Date: Tue, 19 Jan 2016 20:48:06 +0300

Hi Tero,

> will not retry with message sending cookie notification. 

You missed the point. The attacker finds a collision so that
C1 (sent to initiator) contains COOKIE notification (with
SAi', KEi', NONCEi' included), while in C2 (sent to responder) 
the notification type is changed from COOKIE to smth unknown
(and of course the length changed too, as in original attack).

> of collison where the prefix is no longer constant, i.e., he needs to

He need to do that anyway. Note, that the ck and ck' cookie
length in the original attack must be correct and different 
(ck = C1 | SAi' | g^xi' |NONCEi, while ck' = C2). The other option
for the attacker is to make the length of ck and ck' equal, but in this
case the length of m and m' will be different and he must
find a collision so that the length field in HDR and HDR' 
be correct (m' will be longer than m). The authors
write about this on p.13:

    We also observe that the two prefixes are very similar:
    we only need the length of the cookie to be different.

    Following the format of IKE message, the length field

    is on bytes 22 and 23 of the hashed transcript, and

    all previous bytes must have a fixed value. Hence, we

    can _almost_ use a common-prefix collision attack, if the

    collision algorithm introduces a difference in bytes 22-

    23, and no difference in preceding bytes.

So it is not a pure collision attack. In the modified attack the 

additional requirement is that not only length of the notification be different, 

but also the type of notification in C2 changes from COOKIE in C1 to 

any unused status notification. It makes finding a collision harder, 

but I think not too much.

> And checking the small subgroups in Diffie-Hellman, i.e., not using

Sure.

Regards,
Valery.

---

From: Tero Kivinen <[email-masked]>
Date: Tue, 19 Jan 2016 21:14:29 +0200

> (and of course the length changed too, as in original attack).

The attack finds common-prefix-collision, i.e. where everything before
the C1 and C2 is same. If the C1 and C2 requires some kind of
structure (i.e. other needs to start with 0x2100009600004006..., and
the other starts with 0x210000960000A006) then the attack is no longer
common prefix collision.

If I remember right, I think that common-prefix-collions worked on
blocks, so it would require full hash-blocks for prefix, but that is
of course easy to take, as we can pad C1 and C2 with zeros or
something until next block size.

I.e. it is not as easy to find C1 and C2 so that hash(P1 || C1) ==
hash(P2 || C2) where P1 and P2 are different. 

> (ck = C1 | SAi' | g^xi' |NONCEi, while ck' = C2).

Hmm... yes, I think that also makes the attack impossible, as the
length needs to be modified, thus it is no longer common prefix
attack.

> The other option for the attacker is to make the length of ck and
> ck' equal, but in this case the length of m and m' will be different
> and he must find a collision so that the length field in HDR and
> HDR' be correct (m' will be longer than m). The authors write about
> this on p.13:
> 

You should have read the rest of that paragraph:

	For MD5, the most efficient collision attacks do not have a
	compatible message difference, but it seems possible to build
	a dedicated attack with complexity below 2^39. However, for
	SHA-1, all known collision attacks use differences in every
	message words, and are thus unsuitable.

I.e. they say that this attack is impossible with SHA-1 too for now,
as they cannot use the 2^77 attack for SHA-1, as it only works with
chosen-prefix collisions where this requires almost-common-prefix
collision attack, and that does not work for SHA. To be able to attack
SHA-1 they need to find new ways to make almost chosen-prefix attacks
against SHA1.

[1] https://www.mitls.org/downloads/transcript-collisions.pdf

> additional requirement is that not only length of the notification
> be different, but also the type of notification in C2 changes from
> COOKIE in C1 to any unused status notification. It makes finding a
> collision harder, but I think not too much.

For MD5 they say that it might be possible, for SHA-1 they say all
known collision attacks are unsuitable...

I would consider that makeing it much harder in general..

-- 
[email-masked]

---

From: "Valery Smyslov" <[email-masked]>
Date: Wed, 20 Jan 2016 09:28:19 +0300

> SHA-1 they need to find new ways to make almost chosen-prefix attacks

At the beginning of the paper the authors write that the attack against
IKEv2 is _almost_ practical. So, it is infeasible today, but taking
into considerations fast progress in hash analysis can become feasible 
tomorrow. That's why it's better to have an additional defense
on the protocol level (like moving COOKIE at the end of the message).
It is not an urgent action that we should do in a rush, but it is an option
we should comsider for next major protocol update (if it happens).

Regards,
Valery.

---

From: Paul Wouters <[email-masked]>
Date: Wed, 20 Jan 2016 06:40:23 -0500

If you want to harden things, it would be better to do it much differently. If we depend on cookie being at the end, we would be way too fragile.

IKEv1 started where payload order didn't matter and I still believe that should remain true as much as possible.

It doesn't stop you from putting COOKIE at the end though.

Sent from my iPhone

On Jan 20, 2016, at 01:28, Valery Smyslov <[email-masked]> wrote:

> into considerations fast progress in hash analysis can become feasible tomorrow. That's why it's better to have an additional defense

---

From: Tero Kivinen <[email-masked]>
Date: Wed, 20 Jan 2016 16:21:19 +0200

> we should comsider for next major protocol update (if it happens).

Moving cookie to the end does not help to protect against this attack.
Using random SPI do protect.

If they are able to do attacks against SHA-1 without chosen-prefix in
the beginning, then it does not matter where the cookie is. If they
cannot do that, then their attack does not work as long as either SPIi
and SPIr is random.

I mean if they can do attack even when the SPIs are random, then they
can also do the attack when the cookie is in the end, as only thing
they need to change durign the exchange is to change the g^x with
g^x' so they can just then force the hash to be same where the

	HASH(SA_INIT(SAi | g^x | ni | infoi | ck(C1)) ==
	HASH(SA_INIT(SAi | g^x' | ni | infoi | ck(C2))

where C1 and C2 are just selected so that they make hash same even
when the SPIi and SPIr, and g^x are different...

So moving cookie to the end does not offer any more protection against
this attack, thus not needed. Using random SPIi and SPIr will protect
against this attack, and when attacks against SHA-1 are so good that
it will not protect anymore, then we say MUST NOT for SHA-1.
-- 
[email-masked]

---

From: "Valery Smyslov" <[email-masked]>
Date: Wed, 20 Jan 2016 18:28:28 +0300

> the beginning, then it does not matter where the cookie is. 

Right.

> If they

Note, that the attacker must do that online and g^x is unpredictable 
(in addition to SPIi). If finding a collision depends on the amount
of unpredictable data, then moving ck to the end would help. If not - it won't.

Regards,
Valery.

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Thu, 21 Jan 2016 15:39:31 +0000

> Sent: Friday, January 15, 2016 3:48 AM
> >> However, if no better solution exists I'd prefer to live with a
> >> single fixed crypto primitive, than with two. Is it possible to get
> >> rid of AES and to change the indication of the ppk to use to something like
> the following?
> >>
> > Actually, the reason we proposed the "entry in the AES codebook"
> > approach, rather than something like the above structure, is due to
> practical reasons.
> > When the responder receives the hint, he has no idea which ppk the
> > initiator is referring to (and he doesn't know the identity yet); our
> > model is that the responder has a list of ppk's that he knows about,
> > and checks to see if the one that the initiator had is on the list.
> > It'd be nice if there was a way for the responder to search through
> > his databases of known ppk's quickly, however I don't know how to let
> > him do it in sublinear time (without leaking whether two exchanges
> > used the same ppk, which would leak information about the identities).
> > So, what we settled on is to make the linear scan for the right PPK as
> > fast as possible.  With our proposed solution, an aggressive responder
> > could have all the AES keys corresponding to the ppk preexpanded, and
> just check each potential ppk by doing one AES block encryption (or
> decryption, if they prefer); if the implementation has AES-NI, that is fairly
> fast.
> > With your proposal, they could preexpand the HMAC keys, but would
> > still need to do two SHA256 compression function evaluations.
> 
> I see the point, thank you. However AES support in hardware is not always
> available, so I still think that having a single crypto primitive is better in this
> situation.
> 
> But your explanations brings me to a conclusion, that the protocol could me
> modified. Please see my logical chain.
> 
> even from spoofed IP address. In this situation a sane responder would try to
> defend itself sending a cookie request - this would guarantee that the
> initiator is alive and the IP address is not spoofed. So, if the cookie request is
> to be sent in most cases when the IKE_SA_INIT message contains ppk
> extension anyway, then the protocol could be modified to make cookie
> request mandatory in this situation. Then the IKE_SA_INIT exchange would
> look like:
> 
> The responder selects prf (and encryption, if it is used) algorithms from the
> SAi1 payload. It also supplies random_data that the initiator must use when it
> encodes the ppk. The initiator computes an encoded ppk and retries the
> request.
> 
> 2. No need to perform CPU-intensive operations until the initiator's IP is
> confirmed 3. In this variant it is the responder who supplies random_data to
> initiator to encode ppk,

I like it.  Someone acting as an active server could determine if two people have the same ppk (by giving them the same random data); however an active server can determine their identities anyways, and so that's not a concern.  That does mean that we're allowing the server to make the trade-off between computational complexity and client privacy; if everyone else is OK with that, so am I.

The one part that I would ask is that the crypto=xxx be a simple field (for example, it's a 32 bit value in the payload), and not a more complicated payload.  My fear is that if we make that parsing more complex, that would add little-used complexity to the protocol (and parts of the protocol that are little used/tested are just havens for exploitable bugs).

Ok, I think I'll got ahead and (with my coauthors) revise the draft...

---

From: "Valery Smyslov" <[email-masked]>
Date: Fri, 22 Jan 2016 14:48:00 +0300

Hi Scott,

> I like it.  Someone acting as an active server could determine if two people have the same ppk 
> (by giving them the same random data); however an active server can determine their identities 
> anyways, and so that's not a concern.  That does mean that we're allowing the server to make 
> the trade-off between computational complexity and client privacy; if everyone else is OK with that, 
> so am I.
> 
> The one part that I would ask is that the crypto=xxx be a simple field (for example, it's a 32 bit value 
> in the payload), and not a more complicated payload.  My fear is that if we make that parsing 
> more complex, that would add little-used complexity to the protocol (and parts of the protocol 
> that are little used/tested are just havens for exploitable bugs).

By crypto=xxx I meant a generic indication of what crypto primitive(s) are to be used by initiator.
In your original proposal you used two primitives: encryption (AES) and prf (HMAC_SHA256).
If you accept my proposal then I think it is better to simplify things and use only one
primitive - prf (for two reasons - first now server can choose a sutable tradeoff between
client's privacy and the server's CPU load, and second - with generic encryption you
won't always get any speed benefit from using both encryption and prf). 

So I'd suggest to use only prf. In this case crypto=xxx becomes prf=xxx, where prf is a 16-bit 
integer containing one of the the values defined in IANA-IKEv2 table "Transform Type 2 - 
Pseudo-random Function Transform IDs", and the server selects it from what is present
in the initiator's SA payload in transfoms of type 2. This guarantees that the initiator
supports that prf (otherwise he wouldn't include it in the SA payload).
In this case the initiator would then compute prf(prf(ppk, "A"), random_bytes).

And there is no need that this selected prf is equal to the prf that is negotiated
later and used in all SKEYSEED etc claculations - they are not related.
The fact that they are not related simplifies their selection (for example,
you don't need to look at the local policy when selecting mutually supported
prf for ppk).

Regards,
Valery.