Subject: [IPsec] Some speculations about puzzles

From: "Valery Smyslov" <[email-masked]>
Date: Mon, 1 Dec 2014 18:34:09 +0300

Hi, this is a long message.

First of all I think that the puzzles mechanism is a great tool
to make DoS attacks harder for attackers and we should
try to incorporate it into IKE. Moreover, I think that
the puzzles could be used not only in IKE_SA_INIT, but also
to defend against DoS attacks in IKE_AUTH exchange (see below).
However, the puzzles mechanism is a controversal thing,
since it requires an additional work from legitimate clients.
It could be particularly troublesome for small battery-powered wireless
devices (smartphones, IoT devices etc) - not only would it delay connection
setup, but it also would decrease battery lifetime.

So think that the puzzles mechanism if incorporated into IKE should follow
some general principles:
1. Puzzles should be optional. It should be possible for client to just 
return
    cookie even if puzzle is given by SGW).
2. The ultimate decision whether to solve puzzle or ignore it should be made 
by client.
3. Those, who ignore puzzles (for any reason - either they are legacy 
clients
    or they decide to save battery) should still have a chance to setup 
connection
    (on "best effort" basis).

In other words, let's consider puzzles mechanizm not as discriminating tool
("those who cannot solve puzzles won't be allowed in"), but as
a "first-class ticket" for those, who are ready to pay for it.
And the price for the first-class service should be high enough to make it
unattractive for attackers.

Concrete proposals.

1. Algorithm agility for puzzles. It is relatively easy to achieve. When
IKE_SA_INIT request comes from the client, the server could quicly parse it,
find SA payload and figure out the list of transforms the client proposes.
Then it could select mutually supported PRF and indicate it to the client
in response containing puzzle. The puzzle in this case would look like:
"please, give me a string of octets such, that if this PRF is applied
to that string of octets using supplied cookie as the key, then the
result would contain this number of trailing zero bits" (another option -
apply PRF to cookie + string of octets using zero key).

Parsing IKE_SA_INIT message is a relatively easy task.
The side advantage of this approach is that the server
could quickly check the structure of the message and
the list of proposed transforms and wouldn't spend more resources
in case the initial message is malformed or no proposals are acceptable
to the responder.

2. Cookie generation. Currently RFC7296 suggestd the following
formula to compute cookie:

    Cookie = <VersionIDofSecret> | Hash(Ni | IPi | SPIi | <secret>)

With puzzles more information should be present in the cookie
to prevent some attacks from initiator. First, when
responder asks initiator to solve the puzzle, it sets puzzle
difficulty to some level and indicates it in the response message.
When the solved puzzle is returned back to the responder,
it must know in a stateless manner what level of difficulty
it has requested. Otherwise the initiator could cheat. So responder
must encode this information into cookie, as the cookie is an entity that
initiator cannot forge. Then, it is desirable to also include
timestamp into cookie to prevent initiator from re-using solved puzzles
and from collecting a lot of puzzles, solving them and then presenting them
all at once. Including timestamp allows the responder
to determine how old this cookie is and, therefore,
how much time it was taken from the initiator to solve the puzzle.
If the results are suspicious (an easy puzzle took too long to be solved),
then the request should be rejected, even in the case it contains
a valid solution for the puzzle. And in case of accepting
algorithm agility method described above the selected PRF
must also be encoded in cookie.

So, the cookie generation would look like:

    Cookie = <VersionIDofSecret> | <Timestamp> | <PuzzleDifficulty> | <PRF> 
|
        Hash(Ni | IPi | SPIi | <Timestamp> | <PuzzleDifficulty> | <PRF> | 
<secret>)

Note, that <PuzzleDifficulty> should be allowed to be zero here -
in case it is just a cookie request with no puzzle request.

To summarize here is a possible sequence of messages in IKE_SA_INIT:

   request             --> HDR, SA, KE, Ni,
                           [N(NAT_DETECTION_SOURCE_IP)+,
                            N(NAT_DETECTION_DESTINATION_IP),]
                           [V+][N+]

   response with puzzle    <-- HDR, N(COOKIE), N(PUZZLE, PRF=<X>, 
DIFFICULTY=<N>)
                           [V+][N+]

Legacy client or client that don't want to spend recources on puzzle
would ignore N(PUZZLE) and act as if only N(COOKIE) was received.

   request             --> HDR, [N(COOKIE),]
                           SA, KE, Ni,
                           [N(NAT_DETECTION_SOURCE_IP)+,
                            N(NAT_DETECTION_DESTINATION_IP),]
                           [V+][N+]

At this point the responder will:
- check that the cookie is valid
- retrieve timestamp and difficulty level from the cookie and ensures it is
  fresh for that level
- if the level is zero, then it means that no puzzle was requested
- if the level is non-zero then it means that the initiator either
  doesn't support puzzles or is unwilling to solve them; in either
  case the request is processed on "best effort" basis -
  it could be served or dropped depending on current resource availability
  or on some probability (e.g.serve every Nth request in case of attack)

Client, that is solved the puzzle:

   request             --> HDR, [N(COOKIE),], N(PUZZLE_SOLUTION)
                           SA, KE, Ni,
                           [N(NAT_DETECTION_SOURCE_IP)+,
                            N(NAT_DETECTION_DESTINATION_IP),]
                           [V+][N+]

At this point the responder will:
- check that the cookie is valid
- retrieve timestamp and difficulty level from the cookie and ensures it is
  fresh for that level
- if the level is zero, then it means that no puzzle was requested,
  but initiator still supplied some solution; in this case 
N(PUZZLE_SOLUTION)
  is ignored and the message is processed as described above
- if the level is non-zero then responder will retrieve PRF from the cookie
  and verify the correctness of supplied puzzle solution
- if everything is OK then this request is served with higher priority

3. Using puzzles in IKE_AUTH exchange. The draft ipsecme-ddos-protection-00
describes DoS attack on IKE_AUTH exchange:

       Sending an Authentication request is surprisingly cheap.  It requires
       a proper IKE header with the correct IKE SPIs, and it requires a
       single encrypted payload.  The content of the payload might as well
       be junk.  The responder has to perform the relatively expensive key
       derivation, only to find that the Authentication request does not 
decrypt.

I think that the puzzles could be used to make this attack substantially
more expensive for the attacker. The idea is to require the initiator
to supply an additional string of octets in IKE_AUTH request such, that
applying PRF with the Nr as the key to this string of octets
concatenated with the content of the IKE_AUTH message will
result in some number of zero trailing bits. In this case if the attacker
fills in the content of SK payload with garbage, it will be detected
by the responder without performing DH computation. The level of difficulty
in this case must be set so, that the time needed to solve the puzzle is
by the order of magnitude more, than to compute DH, so that
this attack becomes unattractive for potential attacker.

There are some options where to place puzzle solution
in IKE_AUTH message.

  1. It could be explicitely present as Notification payload
      before Encrypted payload:

       HDR, N(PUZZLE_SOLUTION), SK {IDi, [CERT,] [CERTREQ,]
       [IDr,] AUTH, SAi2, TSi, TSr}

  2. It could be placed right after Encrypted payload without
      any header. In this case the length indicated in IKE Header
      would be greater, than the length indicated in Encrypted payload
      header, and the solved puzzle would be placed in this gap.

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

In case of IKE fragmentation every fragment should contain
its own solution for the puzzle. Note also, that puzzles in IKE_AUTH
are mandatory for initiator if they are requested by responder -
the request won't be processed untill the initiator provides
puzzle solution (this is unlike puzzles in IKE_SA_INIT, where
they should be optional).

Regards,
Valery Smyslov.

---

From: "Graham Bartlett (grbartle)" <[email-masked]>
Date: Tue, 2 Dec 2014 23:20:33 +0000

Hi Valery

Would the Timestamp be generated every time cycle? If this wasn't a static
figure (per timecycle - maybe when the secret is changed?, but rather a
rolling unix time), then how would the Responder be able to validate this
Cookie (without trying every previous timestamp or having the timestamp
included in the Initiators reply?). Would it not be better to save X
number of Secrets and just try them instead (assuming that the Secret is
changing fairly regularly)? The Secret could also be used to tell (approx)
how old the Cookie is.

I like the two options of the header in the clear.

Many thanks

On 01/12/2014 15:34, "Valery Smyslov" <[email-masked]> wrote:

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

---

From: "Valery Smyslov" <[email-masked]>
Date: Wed, 3 Dec 2014 15:36:02 +0300

Hi Graham,

> included in the Initiators reply?).

Yes, it is included in Initiator's reply. More precisely - it is encoded in 
cookie.
So, the cookie has some structure. The particular encoding is implementation
dependant (since it is a local responder's matter), but the idea is that
the cookie contains some fields, that responder can extract from it
and these fields are also included in Hash(Ni | IPi | SPIi | ... <secret>)
calculation to prevent attacker from manipulating them. For example:
1. First byte of cookie contains VersionIDofSecret
2. Next byte contains requested PuzzleDifficulty
3. Next 2 bytes contain transform ID for selected PRF
4. Next 4 bytes contain timestamp (just unix time())
5. The rest of the cookie contains hash of all these values + Ni + IPi + 
SPIi + <secret>

> Would it not be better to save X

Using the fact that the secret for cookie generation must be changed
periodically is another option to deal with old puzzles. However,
the secret is global and the period of its changes is relatively
long (tens of seconds or even minutes). It is desirable to have finer
mechanism to deal with different puzzle difficulty levels for different
IP-addresses/prefixes. Of course it is possible to change secret every
second, but then we should make the <VersionIDofSecret> long
enough to prevent wrapping and it is desirable that it survives reboots
and so on, so it just becomes a timestamp :-)

Regards,
Valery.

---

From: Yoav Nir <[email-masked]>
Date: Wed, 3 Dec 2014 17:06:08 +0200

I think it’s simpler to keep a short list (a queue actually, but usually with no more than 2-5 entries) or <difficulty-level ; secret> pairs.

Generate a new pair every 10 seconds or whenever the difficulty level needs to change. Remember all entries for the last 20 seconds. Calculate the cookie as described in the RFC.

When receiving a cookie, you try to validate it using all the remembered secret-difficulty pairs (I guess you check for sufficiently many zeros before you check for the hash), and let them in if one such pair validated.

Yoav

---

From: "Valery Smyslov" <[email-masked]>
Date: Wed, 3 Dec 2014 18:36:34 +0300

It is probably a bit simpler, but less efficient.

With this try-and-catch approach you would need to perform
hash (or PRF) computations several times before rejecting
invalid puzzles. I'm in favor to minimize wasting of resourses
for solution, which primary goal is to defend against DoS attack.

----- Original Message ----- 
From: "Yoav Nir" <[email-masked]>
To: "Valery Smyslov" <[email-masked]>
Cc: "Graham Bartlett (grbartle)" <[email-masked]>; "ipsec" 
<[email-masked]>
Sent: Wednesday, December 03, 2014 6:06 PM
Subject: Re: [IPsec] Some speculations about puzzles

I think it’s simpler to keep a short list (a queue actually, but usually 
with no more than 2-5 entries) or <difficulty-level ; secret> pairs.

Generate a new pair every 10 seconds or whenever the difficulty level needs 
to change. Remember all entries for the last 20 seconds. Calculate the 
cookie as described in the RFC.

When receiving a cookie, you try to validate it using all the remembered 
secret-difficulty pairs (I guess you check for sufficiently many zeros 
before you check for the hash), and let them in if one such pair validated.

Yoav

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Wed, 3 Dec 2014 15:38:42 +0000

> -----Original Message-----
> From: IPsec [mailto:[email-masked]] On Behalf Of Yoav Nir
> Sent: Wednesday, December 03, 2014 10:06 AM
> To: Valery Smyslov
> Cc: ipsec; Graham Bartlett (grbartle)
> I think it’s simpler to keep a short list (a queue actually, but usually with no
> more than 2-5 entries) or <difficulty-level ; secret> pairs.
> 
> to change. Remember all entries for the last 20 seconds. Calculate the cookie
> as described in the RFC.
> 
> secret-difficulty pairs (I guess you check for sufficiently many zeros before
> you check for the hash), and let them in if one such pair validated.

You can do it easier than that; encode a 'puzzle id' within the puzzle you send to the client (and which they must send back); that way, you can look up the puzzle you originally asked, and check the answer only against that one.

---

From: "Valery Smyslov" <[email-masked]>
Date: Wed, 3 Dec 2014 18:44:56 +0300

Hi Scott,

this is almost identical to what I proposed in my original e-mail,
if you substitute "difficulty level" with "puzzle id".

In more generic way - responder encodes in cookie/puzzle
all the information that could help him quickly
reject invalid/stale/forged puzzles without
wasting resources.

Valery.

>> with no
>> before
> You can do it easier than that; encode a 'puzzle id' within the puzzle you 
> send to the client (and which they must send back); that way, you can look 
> up the puzzle you originally asked, and check the answer only against that 
> one.
>
>
>

---

From: Yoav Nir <[email-masked]>
Date: Wed, 3 Dec 2014 18:01:09 +0200

> On Dec 3, 2014, at 5:44 PM, Valery Smyslov <[email-masked]> wrote:
> 
> Hi Scott,
> 
> if you substitute "difficulty level" with "puzzle id”.

Or call it “generation id”, and increment it whenever you generate a new secret and/or change the difficulty level.

---

From: "Graham Bartlett (grbartle)" <[email-masked]>
Date: Wed, 3 Dec 2014 23:07:53 +0000

If the 1 byte 'difficulty level' has become the 'puzzle id', could we
break the 1 byte into two 4 bits?

1st 4 bits is 'puzzle/generation id', next 4bits is 'difficulty level',
this allows for 16 cycles for when every secret changes and still allows
16 levels of puzzles..

(just a thought as if the difficulty level disappears you loose the
ability to set a the hardness of the puzzle)

On 03/12/2014 16:01, "Yoav Nir" <[email-masked]> wrote:

>> if you substitute "difficulty level" with "puzzle id².
>
>Or call it ³generation id², and increment it whenever you generate a new
>secret and/or change the difficulty level.

---

From: Yoav Nir <[email-masked]>
Date: Thu, 4 Dec 2014 01:46:31 +0200

Why?  The responder can remember that generation 8 had a 20-bit difficulty level. If the attack then gets worse, than generation 9 is created with a 23-bit difficulty level.

The responder needs only remember the generation and associated difficulty level.

> On Dec 4, 2014, at 1:07 AM, Graham Bartlett (grbartle) <[email-masked]> wrote:
> 
>

---

From: "Valery Smyslov" <[email-masked]>
Date: Thu, 4 Dec 2014 10:20:48 +0300

> Or call it “generation id”, and increment it whenever you generate a new 
> secret and/or change the difficulty level.=

That will work. In this case it is better to make “generation id” long 
enough (4 bytes or longer)
and initialize it with random value after reboot.

Anyway, it doesn't matter how exactly the cookie is constructed and it 
should
not be mandated in RFC, as it doest't affect interoperability. However, some
guidance and examples should be given. In particular, RFC should advise
implementers to construct cookie in such way, that the responder is able to 
quickly detect
invalid/stale/forged cookies/puzzles spending as little resources as 
possible.

---

From: Yoav Nir <[email-masked]>
Date: Thu, 4 Dec 2014 09:45:09 +0200

> On Dec 4, 2014, at 9:20 AM, Valery Smyslov <[email-masked]> wrote:
> 
>>> Hi Scott,
>>> 
>> Or call it “generation id”, and increment it whenever you generate a new secret and/or change the difficulty level.=
> 
> That will work. In this case it is better to make “generation id” long enough (4 bytes or longer)
> Anyway, it doesn't matter how exactly the cookie is constructed and it should
> guidance and examples should be given.

Definitely agree. If a document doesn’t give an example of how to do this non-stupidly, implementers will come up with multiple creative ways of doing this wrong.

> In particular, RFC should advise
> implementers to construct cookie in such way, that the responder is able to quickly detect
> invalid/stale/forged cookies/puzzles spending as little resources as possible.

Yoav

---

From: "Graham Bartlett (grbartle)" <[email-masked]>
Date: Thu, 4 Dec 2014 11:25:57 +0000

Hi Yoav

As I understand this, changing the concept from 'difficulty level' to
'puzzle/generation id' doesn't allow for a responder to hand out some
puzzles weaker than others at the same time? (Unless it's tracked locally
as you said), but then the Responder would need to remember all previous
Puzzles up to the last point where a certain GenerationID was used if it's
to issue Puzzles of different difficulty at the same time. (Otherwise I
see an attack where someone can potentially just make all new connections
have the most difficult puzzles, there might be a need for some random
un-fairness with 1 in X having hard puzzles?).

Also if the 'difficulty level' is no longer used, how does the client know
what difficulty this is ? Generation 9 could be 23-bit one day and 0 the
next.

If both are included this allows for the Responder to change secret and
also allow for multiple difficulty types.

Cookie = <VersionIDofSecret> | <Timestamp> | <GenerationID> |
<PuzzleDifficulty> | <PRF> |

        Hash(Ni | IPi | SPIi | <Timestamp> | <GenerationID> |
<PuzzleDifficulty> | <PRF> |
<secret>)

thanks

On 03/12/2014 23:46, "Yoav Nir" <[email-masked]> wrote:

>Why?  The responder can remember that generation 8 had a 20-bit
>difficulty level. If the attack then gets worse, than generation 9 is
>created with a 23-bit difficulty level.
>

---

From: "Valery Smyslov" <[email-masked]>
Date: Thu, 4 Dec 2014 14:50:18 +0300

Hi Graham,

I'm not Yoav, but I'll try to clarify.

> as you said), but then the Responder would need to remember all previous

Yes, in Yoav's approach the responder should remember
last N pairs "generation_id : difficulty: secret".

> what difficulty this is ? Generation 9 could be 23-bit one day and 0 the

In any case (with mine or Yoav's approach) the difficulty level must be
indicated to initiator explicitely, in a separate field (it presumably
must be in (to be defined) PUZZLE Notification). Difficulty level
in cookie (as I suggested) is for responder's use only.
For initiator the cookie is an opaque blob in any case,
but responder must be able to determine which difficulty
level was requested with any particular cookie. In my approach
the level is encoded in the cookie itself, in Yoav's approach it is
locally accociated with "generation_id", which is encoded
in the cookie.

Both approaches are workable. There are some advantages
and drawbacks in each, but they are insignificant, IMHO.

Regards,
Valery.

On 03/12/2014 23:46, "Yoav Nir" <[email-masked]> wrote:

>>>> if you substitute "difficulty level" with "puzzle id©ч.
>>>
>>> Or call it ©шgeneration id©ч, and increment it whenever you generate a
>>>new

---

From: Yaron Sheffer <[email-masked]>
Date: Thu, 04 Dec 2014 22:27:15 +0200

Hi Valery,

Going back to your original message (I guess not everyone read it to the 
end :-)

I don't understand how puzzles for IKE_AUTH can be mandatory without 
breaking the protocol. The responder doesn't even know that the 
initiator supports puzzles. At the very least, we would need to add a 
"puzzles supported" notification.

And again for IKE_AUTH, I don't see why with fragmentation you need one 
puzzle solution per fragment. The major CPU cost (DH computation, 
certificate stuff and decryption) comes once, after the message is 
re-assembled. So it seems to me only one puzzle response is needed for 
the entire message.

Thanks,
	Yaron

---

From: "Valery Smyslov" <[email-masked]>
Date: Fri, 5 Dec 2014 10:40:40 +0300

Hi Yaron,

> Going back to your original message (I guess not everyone read it to the 

If your guess is correct then it's a pity :-(

> breaking the protocol. The responder doesn't even know that the initiator 
> supports puzzles. At the very least, we would need to add a "puzzles 
> supported" notification.

I probably wasn't clear enough. I meant that if client supports
puzzles and accepts puzzle in IKE_SA_INIT, then it must also
solve puzzle in IKE_AUTH. In other words, the puzzles in IKE_SA_INIT
are optional for the client, but if they are accepted by client in 
IKE_SA_INIT,
then they must also be used in IKE_AUTH.

The reason for such a strong requirement is that in the situation
when responder has already created the state but has not yet
authenticated the initiator it becomes an easy target
for DoS attack (as it is mentioned in the draft).

> re-assembled. So it seems to me only one puzzle response is needed for the 
> entire message.

In this case the responder would become succeptible to the attack
when attacker emits forged fragments, that takes place of
good fragments from legitimate initiator in the reassembly queue.
To detect the forgery responder needs to check fragment
authenticity before inserting it into the reassembly queue.
That would require performing DH and calculating
SK_a*, but that is what we are willing to defer unless peer
proves that it is really really wants to setup connection and
is ready to spend quite a lot of resources to do it.

It would be possible to protect with puzzle only the very
first fragment, because as we have calculated SK_a*
it takes very little resources to verify the other fragments,
but fragments can arrive in any order, so puzzle must be
in each fragment. That is a bit unfortunate for the initiator, I admit.

Regards,
Valery.

---

From: "Graham Bartlett (grbartle)" <[email-masked]>
Date: Fri, 5 Dec 2014 08:44:37 +0000

Hi Valery

Thanks again.

I interoperated the thread as your approach would have 'difficulty'
replaced with 'generation_id'. (I now know this isn't the case).

thanks

On 04/12/2014 11:50, "Valery Smyslov" <[email-masked]> wrote:

>In my approach

---

From: Yaron Sheffer <[email-masked]>
Date: Fri, 05 Dec 2014 11:22:38 +0200

>> And again for IKE_AUTH, I don't see why with fragmentation you need
>> one puzzle solution per fragment. The major CPU cost (DH computation,

I get your point, but I think this is more than unfortunate, this is 
real ugly. RFC 7383 is primarily about IKE_AUTH, and now, in the case of 
those broken networks that limit the MTU, we are reducing the effective 
MTU yet again.

But I think we're looking at the wrong problem. Let us look at why we 
might need to add puzzles to IKE_AUTH at all. There are two cases:
- The IKE SA is set up by a valid initiator.
- The IKE SA is set up by an attacker.

In the first case, the responder needs to compute SKEYSEED anyway. It 
should compute it once and cache it, even if it sees multiple bogus 
IKE_AUTH messages sent by attackers. Verifying IKE_AUTH messages is 
cheap once SKEYSEED has been computed, because you only need to verify 
that the SK integrity protection is valid. The (valid) initiator "pays 
the price" once, in the form of an IKE_SA_INIT puzzle.

In the second case, the attacker also pays the price if we have a puzzle 
attached to IKE_SA_INIT. And the responder only computes SKEYSEED once, 
and caches the result. Since SKEYSEED is known to the attacker, it can 
send valid SK payloads, and the responder is forced to validate the 
certificate (expensive). So attaching a puzzle to IKE_AUTH is justified, 
to make the attacker pay for each certificate validation.

But this also shows that the IKE_SA_INIT puzzle is sufficient to 
counteract the cost of computing SKEYSEED (which is all you need for 
reassembly), and when even using fragmentation, this is only done once.

Thanks,
	Yaron

---

From: "Valery Smyslov" <[email-masked]>
Date: Fri, 5 Dec 2014 16:19:00 +0300

> those broken networks that limit the MTU, we are reducing the effective 

Not much, a dozen of bytes.

> reassembly), and when even using fragmentation, this is only done once.

I agree with your analysis. However I'm not sure I agree with conclusion.

IKE_SA_INIT puzzle defends from exhausting responder's
memory, while IKE_AUTH puzzle defends from exhausting CPU power.
My primary concern is distributed DoS attack when attackers
are indistinguishable from legitimate clients. In this case 
attacker does pay the price of IKE_SA_INIT puzzle,
but after that it is free to attack responder's CPU by
sending bogus messages or valid messages 
with bogus content. I agree, that once SKEYSEED is computed
the bogus messages are easy to detect. However 
performing DH is relatively expensive for responder,
while sending bogus message is free for attacker
(once it has paid an "entrance fee"), that makes this
attack attractive. Another option - sending valid 
messages with bogus auth content, that will require
responder to do a lot of work. It will require from attacker
to compute SKEYSEED, but the responder 
would have to spend much more resources,
so the attack is also attractive. IKE_AUTH puzzle
eliminates the first attack and makes the second 
expensive for attacker.

IKE_AUTH puzzle is just a "second line of defense".
You are probably right that we can get rid of it
and raise the difficulty level of the "first line",
but I'm not yet sure that we will gain an equal effect.

Regards,
Valery.

---

From: Yaron Sheffer <[email-masked]>
Date: Fri, 05 Dec 2014 15:51:54 +0200

>> In the second case, the attacker also pays the price if we have a
>> puzzle attached to IKE_SA_INIT. And the responder only computes
>> SKEYSEED once, and caches the result. Since SKEYSEED is known to the
>> attacker, it can send valid SK payloads, and the responder is forced
>> to validate the certificate (expensive). So attaching a puzzle to
>> IKE_AUTH is justified, to make the attacker pay for each certificate
>> validation.
>>
> are indistinguishable from legitimate clients. In this case attacker
> does pay the price of IKE_SA_INIT puzzle,
> sending bogus messages or valid messages with bogus content. I agree,
> that once SKEYSEED is computed
> the bogus messages are easy to detect. However performing DH is
> relatively expensive for responder,
> attack attractive. Another option - sending valid messages with bogus
> auth content, that will require
> to compute SKEYSEED, but the responder would have to spend much more
> resources,
> eliminates the first attack and makes the second expensive for attacker.
>

We are almost in agreement. My understanding is that both the 
IKE_SA_INIT and IKE_AUTH puzzles are needed, and each one has a 
different goal:

- IKE_SA_INIT puzzle: should counteract the responder's memory cost of 
keeping the half-open SA, and its CPU cost in computing DH.

- IKE_AUTH puzzle: should counteract the responder's CPU cost of 
validating the AUTH payload.

Thanks,
	Yaron

---

From: "Valery Smyslov" <[email-masked]>
Date: Tue, 9 Dec 2014 15:41:51 +0300

Hi Yaron,

> validating the AUTH payload.

Thank you, now I better understand your position. Let me rephrase it.

You propose that IKE_AUTH puzzle resides inside SK payload
and its verifications takes place after computing DH
and verifying authenticity of IKE_AUTH messag, but before
any actionts dealing with peer authentication take place.
Am I right?

This will allow attacker to perform an attack on responder's CPU power
by sending single garbage message in IKE_AUTH,
which will be partially counteracted by IKE_SA_INIT
puzzle. But this will definitely ease legitimate client's burden
in case of IKE fragmentation.

I still prefer IKE_AUTH puzzle to reside outside SK payload
and to be verified before performing DH and computing SKEYSEED.
However, after some thoughts, I think that in case of IKE
fragmentation, puzzle must only present in the very first
fragment (outside SKF payload), not in the every fragment,
as I proposed before. The responder in this case will pay no attention
on the other fragments untill it receives the first one and verifies the 
puzzle.
Fragments that were received before this event
could be dropped (in a hope that they will be eventually
retransmitted) or just collected with no action. In the latter case
after the puzzle is vefified and DH is computed all the
collected fragments must be verified for theit authenticity.

This approach would still require legitimate client to re-solve
puzzle in case it first sends unfragmented message and then
switches IP fragmentation on (or in case it refragments
the message with smaller MTU), but it would provide better
defense against attacks on CPU exhausting in IKE_AUTH.

Regards,
Valery.