Subject: [IPsec] A strategy against DoS/DDoS for IKE responders

From: Yoav Nir <[email-masked]>
Date: Sun, 5 Oct 2014 13:25:49 +0300

Hi

Here are some thoughts about DoS and DDoS protection for an IKE daemon. I think this should be discussed before submitting any drafts, because the acceptance thread reflected that the problem we want to solve is DoS and DDoS, not just the lack of a puzzle mechanism.

If we break down what a responder has to do during an initial exchange, there are four stages:

1. When the Initial request arrives, the responder:
 - generates or re-uses a D-H private part.
 - generates a responder SPI
 - stores the private part and peer public part in a half-open SA database.

2. When the Authentication request arrives, the responder:
 - derives the keys from the half-open SA ([1]).
 - decrypts the request.
 
3. If the Authentication request decrypts properly:
 - validates the certificate chain (if present) in the auth request

Yes, there's a stage 4 where the responder actually derives keys, but when talking about (D)DoS, we never get to this stage.

Stage #1 is pretty light on CPU power, but requires some storage, and it's very light for the initiator as well. Stage #2 includes private-key operations, so it's much heavier CPU-wise. Stage #3 includes a public key operation, and possibly many of them.

To attack such a server, an attacker can attempt to either exhaust memory or to exhaust CPU. Without any protection, the best avenue is to send multiple faked Initial requests, and exhaust memory. This should be easy because those Initial requests are cheap.

There are obvious ways for the responder to protect itself even without changes to the protocol. It can reduce the time that an entry remains in the half-open SA database, and it can limit the amount of concurrent half-open SAs from a particular address or prefix. The attacker can overcome this by using spoofed source addresses.

The stateless cookie mechanism (that is already in the RFC) prevents an attack with spoofed source addresses. This doesn't solve the issue, but it makes the address or prefix limiting work. Puzzles do the same thing only more of it. They make it harder for an attacker to reach the goal of getting a half-open SA. They don't have to be so hard that an attacker can't afford to solve them - it's enough that they increase the cost of a half-open SAs for the attacker. 

Reducing the amount of time an abandoned half-open SA is kept attacks the issue from the other side. It reduces the value the attacker gets from managing to create a half-open SA. So if a half-open SA takes 1 KB and it's kept for 1 minute and the capacity is 60,000 half-open SAs, an attacker would need to create 1,000 half-open SAs per second. Reduce the retention time to 3 seconds, and the attacker needs to create 20,000 half-open SAs per second. Make each of those more expensive, and you're likely to thwart an exhaustion attack against responder memory.

At this point, I'm guessing that this is no longer the most efficient DoS attack. The attacker has two ways to do better:
 1. Go back to spoofed addresses and try to overwhelm the CPU that deals with generating cookies, or
 2. Take the attack to the next level by also sending an Authentication request.
 
I don't think the first thing is something we can deal with at the IKE leve. It's probably better left to IPS technology.

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. Depending on the responder implementation, this can be repeated with the same half-open SA (if the responder does not delete the half-open SA following an unsuccessful decryption). For extra credit, the attacker can send the Authentication request just before the entry expires.

Here too, the number of half-open SAs that the attacker can achieve is crucial, because each one of them allows the attacker to waste some CPU time. So making it hard to make many half-open SAs is important. 

A strategy against DDoS has to rely on at least 4 components:
 1. Hardening the half-open SA database by reducing retention time.
 2. Hardening the half-open SA database by rate-limiting single IPs/prefixes
 3. Guidance on what to do when an Authentication request fails to decrypt.
 4. Increasing cost of half-open SA up to what is tolerable for legitimate clients
 5. Other things?
 
Puzzles have their place as part of #4. I think a WG document should cover all.

Yoav

[1] this could be done in part #1, but that makes the DoS issue worse.

---

From: "Graham Bartlett (grbartle)" <[email-masked]>
Date: Sun, 5 Oct 2014 19:37:22 +0000

Hi Yoav

This is a subject I've spent way too much time thinking about and is close
to my heart. :-) I'm actually surprised a Bot hasn't been used to take
down a VPN service using the Auth attack that you describe, or not one
that I've heard of.

I'd like to add, for 1, if 6989 is employed then I was under the
impression this could become a serious issue as these check can be
resource intensive, also if a unique DH exchange per session this could
considerable increase the workload.

Great summary btw, I've included some comments inline GB>

cheers

On 05/10/2014 11:25, "Yoav Nir" <[email-masked]> wrote:

>Hi
>
>Here are some thoughts about DoS and DDoS protection for an IKE daemon. I
>think this should be discussed before submitting any drafts, because the
>acceptance thread reflected that the problem we want to solve is DoS and
>DDoS, not just the lack of a puzzle mechanism.
>
>Yes, there's a stage 4 where the responder actually derives keys, but
>when talking about (D)DoS, we never get to this stage.
>
>Stage #1 is pretty light on CPU power, but requires some storage, and
>it's very light for the initiator as well. Stage #2 includes private-key
>operations, so it's much heavier CPU-wise. Stage #3 includes a public key
>operation, and possibly many of them.
>
>To attack such a server, an attacker can attempt to either exhaust memory
>or to exhaust CPU. Without any protection, the best avenue is to send
>multiple faked Initial requests, and exhaust memory. This should be easy
>because those Initial requests are cheap.
>
>There are obvious ways for the responder to protect itself even without
>changes to the protocol. It can reduce the time that an entry remains in
>the half-open SA database, and it can limit the amount of concurrent
>half-open SAs from a particular address or prefix. The attacker can
>overcome this by using spoofed source addresses.
>
>The stateless cookie mechanism (that is already in the RFC) prevents an
>attack with spoofed source addresses. This doesn't solve the issue, but
>it makes the address or prefix limiting work. Puzzles do the same thing
>only more of it. They make it harder for an attacker to reach the goal of
>getting a half-open SA. They don't have to be so hard that an attacker
>can't afford to solve them - it's enough that they increase the cost of a
>half-open SAs for the attacker.
>
>Reducing the amount of time an abandoned half-open SA is kept attacks the
>issue from the other side. It reduces the value the attacker gets from
>managing to create a half-open SA. So if a half-open SA takes 1 KB and
>it's kept for 1 minute and the capacity is 60,000 half-open SAs, an
>attacker would need to create 1,000 half-open SAs per second. Reduce the
>retention time to 3 seconds, and the attacker needs to create 20,000
>half-open SAs per second. Make each of those more expensive, and you're
>likely to thwart an exhaustion attack against responder memory.
>
>At this point, I'm guessing that this is no longer the most efficient DoS
>attack. The attacker has two ways to do better:

GB> From experience the cookie mechanism works very well, I have never
seen a need for an IPS or similar.

>I don't think the first thing is something we can deal with at the IKE
>leve. It's probably better left to IPS technology.
>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. Depending on the
>responder implementation, this can be repeated with the same half-open SA
>(if the responder does not delete the half-open SA following an
>unsuccessful decryption). For extra credit, the attacker can send the
>Authentication request just before the entry expires.
>
>Here too, the number of half-open SAs that the attacker can achieve is
>crucial, because each one of them allows the attacker to waste some CPU
>time. So making it hard to make many half-open SAs is important.
>

GB>I'd say this would need to be a number or % of connections, just a
single auth failing - we wouldn't want to bring the whole system into some
locked down state. For a large number of clients it's common for
authentications to fail (from personal experience).

> 4. Increasing cost of half-open SA up to what is tolerable for

GB> This 'sweet spot' is crucial, but seems to vary per implementation.

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

---

From: Yaron Sheffer <[email-masked]>
Date: Sun, 05 Oct 2014 22:56:28 +0300

Hi Yoav,

Thanks for this excellent analysis. A few comments:

- When using ECDH, part of the cost of step #2 is validating the 
incoming DH public key, per RFC 6989. This assumes you are reusing DH 
parameters, which makes sense in a DoS situation. It may be legit (but 
strange) to defer this validation to follow the integrity check of the 
encrypted payload.

- I'm not sure what is special about "[the case] when an Authentication 
request fails to decrypt." Seems to me this is a verified DoS attack 
from a specific IP.

- Your model talks about a single gateway, or a tight cluster of 
gateways. An advantage of puzzles that goes beyond this model is that 
even if your gateways do not share information about suspicious IPs, a 
puzzle generated by each gateway reduces the attacker's power to attack 
any other gateway. This is much more powerful than rate limiting by any 
particular gateway.

Thanks,
	Yaron

---

From: Yoav Nir <[email-masked]>
Date: Sun, 5 Oct 2014 23:22:29 +0300

Hi, Yaron

On Oct 5, 2014, at 10:56 PM, Yaron Sheffer <[email-masked]> wrote:

> 
> - I'm not sure what is special about "[the case] when an Authentication request fails to decrypt." Seems to me this is a verified DoS attack from a specific IP.

I see I wasn’t clear about this, because both you and Graham missed what I meant.

Suppose we have a responder where half-open SAs time out after 10 seconds. 
This responder receives an Initial Request, and responds with an Initial Response.
It stores its own private value and the peer’s public value in the half-open SA database, keyed by IKE SPIs.
0.5 seconds later, it receives an IKE_AUTH request with the right IKE SPIs.
It derives the keys (making any ECDH check that’s needed)
It tries to decrypt the message
The message fails to decrypt (or more likely, the MAC comparison fails)
Now the responder has two options:
 (1) delete the entry in the half-open SA database, or
 (2) store the derived key, and keep the half-open SA another 9.5 seconds.

(2) has the disadvantage that the attacker can keep sending more junk packets and get the responder to attempt to decrypt all of them.
(1) has the disadvantage that an attacker can inject a junk IKE_AUTH request by just copying the IKE SPIs from the IKE_INIT response, which will prevent the responder from processing the real initiator’s IKE_AUTH request.

So I’m not sure which is worse.

Yoav

---

From: Nico Williams <[email-masked]>
Date: Sun, 5 Oct 2014 20:21:01 -0500

> So I’m not sure which is worse.

Split the difference.  Shorten the amount of time you keep the half-open
SA around.

The amount of time to keep a half-open SA/connection/state around
should be dynamic: based on something like N standard deviations from
the average time to complete a handshake when not under (D)DoS attack.

10 seconds is a lot!!

If you're going to use OTP -any interactive authentication- then that
should really be done as one more round-trip.  Human interface factors
should not be allowed to interfere at this stage.  The old internal Sun
punchin VPN did user authentication and authorization after setting up
SAs; success led to the necessary routing getting setup so the user's
bits moved.

Nico
--

---

From: "Graham Bartlett (grbartle)" <[email-masked]>
Date: Mon, 6 Oct 2014 08:31:38 +0000

Hi

This is a very interesting attack, I would dismiss (1) as it leaves an
implementation open for a semi-easy DOS (just one packet that generates
work rate on both initiator and responder).

Basing the behaviour on (2) the attacker would only have the window from
when the responder sends the SA_INIT, to receiving the (valid) IKE_AUTH.
As Nico said shortening the time is critical, but also once the responder
receives a valid IKE_AUTH it should (IMO) dismiss any more IKE_AUTH
messages it receives.

I guess you could look at rate limiting IKE_AUTH messages if they fail to
decrypt, but then you could drop the legit IKE_AUTH. Unless the attacker
is very very lucky (in their packet generation), or has the authentication
credentials they will not be able to send a valid IKE_AUTH, so the window
that occurs between the responder receiving the valid IKE_AUTH is key.

I see the potential for an attacker dropping, or delaying the legit
IKE_AUTH and then sending many IKE_AUTH as you said, so if the behaviour
was set to 10s if a device detected it was under this attack it should
reduce the window of time to process IKE_AUTH (as Nico said), but once
again this could then drop the legit IKE_AUTH.

As I understand the RFC6989 checks are performed on the public value
received in SA_INIT, no IKE_AUTH. (FROM RFC6989) "A receiving peer MUST
check that its peer's public value is valid;", so these checks (as I
understand) would be performed before the responder sends the SA_INIT.

So to summarise, I think that (1) is worse, (2) should be implemented
(maybe with a different timer), but with guidance on what to do should a
device become under attack.

cheers

On 05/10/2014 21:22, "Yoav Nir" <[email-masked]> wrote:

>I see I wasn¹t clear about this, because both you and Graham missed what
>I meant.
>
>It stores its own private value and the peer¹s public value in the
>half-open SA database, keyed by IKE SPIs.
>It derives the keys (making any ECDH check that¹s needed)
>(2) has the disadvantage that the attacker can keep sending more junk
>packets and get the responder to attempt to decrypt all of them.
>(1) has the disadvantage that an attacker can inject a junk IKE_AUTH
>request by just copying the IKE SPIs from the IKE_INIT response, which
>will prevent the responder from processing the real initiator¹s IKE_AUTH
>request.
>
>So I¹m not sure which is worse.
>
>Yoav
>

---

From: Yaron Sheffer <[email-masked]>
Date: Mon, 06 Oct 2014 22:31:49 +0300

It seems to me the difference between the two options is not very 
important (assuming reasonable rate limits), because the cost of 
receiving an IKE_AUTH message and detecting an incorrect MAC is not very 
high, after the initial generation of the IKE SA key material.

But Yoav's model also demonstrates that we could get the same effect by 
attaching the puzzle to IKE_AUTH - though I don't see an advantage.

Re: RFC 6989, yes, the test refers to IKE_SA_INIT. But the response 
message does not depend on the received DH public key, so IMHO it's fine 
to postpone the test until IKE_AUTH is received, and before generating 
the IKE shared key.

Thanks,
	Yaron

---

From: "Graham Bartlett (grbartle)" <[email-masked]>
Date: Fri, 10 Oct 2014 11:31:58 +0000

Hi Yaron / Yoav

I'm summarising my thoughts below, I've spoken to a few folk offlist and
hopefully the following will help my understanding and also theirs.

So assuming a device is under potential attack by devices using their own
addresses (botnet or similar), the cookie notification is not going to
give any benefit (as they are using a legitimate IP address), but Yoav's
puzzle will slow the attack down.

If an attacker sent a legitimate DH public value (that would pass the 6989
checks) and we held off checking this until IKE_AUTH, as you say no
benefit would be gained from detecting this at SA_INIT. The only point in
this attack that we detect an attacker is when the AUTH value is known to
be incorrect so even if they send correct DH public values.

Now the only issue I can see is alluded to in the draft, where a VPN
headend is serving clients with varying resource. So say a botnet attacks
this headend and the puzzle is enabled, you have some clients with a lot
of resource (that require a hard puzzle) and some mobile devices with
minimal (that require an easier puzzle). How do you identify each? The
only way I can think is you must do this once the device has authenticated
itself - else how do you know who they are?

An idea - for example the minimum difficulty of the puzzle is sent by
responder and this is selected by the client and confirmed by the headend
based on IKE ID/certificate attribute? For IKE ID/cert that knows it
should perform a harder puzzle it will (manual local setting).

I know this is a bit of a corner case, but seems to be an easy attack for
someone to start disrupting a remote-access VPN solution that serves
clients with different processing resource.

So to summarise; Because of the attack(s) described in 6989 I personally
feel that this should always be implemented - it's a must. Cookie
notification gives no benefit (only mitigates blind spoofing), but Yoav's
puzzle will help slow down an attack using a devices own IP address.

So I'm all for Yoav's puzzle. :-)

cheers 

On 06/10/2014 20:31, "Yaron Sheffer" <[email-masked]> wrote:

>>> This responder receives an Initial Request, and responds with an
>>>Initial
>>> Response.

---

From: Michael Richardson <[email-masked]>
Date: Fri, 10 Oct 2014 14:25:16 -0400

Graham Bartlett (grbartle) <[email-masked]> wrote:
    > headend is serving clients with varying resource. So say a botnet
    > attacks this headend and the puzzle is enabled, you have some clients
    > with a lot of resource (that require a hard puzzle) and some mobile
    > devices with minimal (that require an easier puzzle). How do you
    > identify each? The only way I can think is you must do this once the
    > device has authenticated itself - else how do you know who they are?

I have two observations here.

The first is that while the botnet can pull in potentially hundreds of
teraflops of computation in order to solve a harder puzzle, it has
communication overhead in order to do that;

The second observation is that the puzzle has to be trivially parallelizable
in order for the botnet (or even the multi-core mobile phone!) to do better
than a single CPU.

The question is: can we design puzzles and the puzzle parameters such that
multiple threads of execution do not benefit a single client system?

The second part is, can we design the time limit to solve the puzzle such
that there becomes very little budget for multi-processor botnet
communication.  I suspect that this second part is impossible and/or easily
spoofed, as we don't know the actual RTT between client and gateway.
(Or rather, any RTT estimation could be spoofed by a botnet to give itself
more time)

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

---

From: Yoav Nir <[email-masked]>
Date: Fri, 10 Oct 2014 22:58:13 +0300

Hi, Graham.

Thanks for the endorsement, but see below.

> puzzle will slow the attack down.

The cookie mechanism helps in one way. If my IPsec gateway is up against an X-node botnet, the cookie mechanism limits the botnet to X unique IP addresses (or IPv6 prefixes).

This in itself doesn’t help much, but we can limit the amount of concurrent half-open SAs that the gateway is willing to store from a particular IP address or prefix. So if, for example, we hold a half-open SA for 10 seconds and allow an IPv4 address / IPv6 prefix to have at most 5 half-open SAs, this limits each node in the botnet to 1 half-open SA every two seconds, even if their bandwidth is sufficient to create many more. It also limits the total half-open SAs that they can hold on the gateway to 5X. The limit mechanism doesn’t work without either cookies or puzzles.

Reducing the time an half-open SA is held doesn’t really help in this scenario, because I’m assuming that the attackers have enough bandwidth. So if we reduce the hold time to 1 second, they should be able to create 5 half-open SAs per second. This is where puzzles come in. They can reduce the rate that these attacking nodes can create new half-open SAs.

Yoav

---

From: Yoav Nir <[email-masked]>
Date: Fri, 10 Oct 2014 23:00:23 +0300

> in order for the botnet (or even the multi-core mobile phone!) to do better

I don’t think this is the best strategy for the botnet. Rather than pool all their resources to solve a single puzzle (bitcoin-style), wouldn’t it be better for each node to act like a legitimate client and solve its own puzzle in however long it takes?

Yoav

---

From: Yaron Sheffer <[email-masked]>
Date: Fri, 10 Oct 2014 23:33:22 +0300

> I don’t think this is the best strategy for the botnet. Rather than pool all their resources to solve a single puzzle (bitcoin-style), wouldn’t it be better for each node to act like a legitimate c…
Yoav, I don't see your point. Suppose I have a 1,000 node botnet, and 
only 100 of them are currently busy with a DoS attack on Yoav's favorite 
gateway. The other 900 nodes are idling, waiting for the next batch of 
spam to arrive. Why not use them to compute hashes so that I can create 
10X as many half-open SAs?

Thanks,
	Yaron

---

From: Michael Richardson <[email-masked]>
Date: Sat, 11 Oct 2014 17:39:11 -0400

Yoav Nir <[email-masked]> wrote:
    >> The second observation is that the puzzle has to be trivially
    >> parallelizable in order for the botnet (or even the multi-core mobile
    >> phone!) to do better than a single CPU.

    > I don’t think this is the best strategy for the botnet. Rather than
    > pool all their resources to solve a single puzzle (bitcoin-style),
    > wouldn’t it be better for each node to act like a legitimate client and
    > solve its own puzzle in however long it takes?

I agree that this might be a better strategy for the botnet, and I think
that we can more easily defend against.

So the goal here is to make sure that we select puzzles which drive the
botnet towards this.

-- 
]               Never tell me the odds!                 | ipv6 mesh networks [ 
]   Michael Richardson, Sandelman Software Works        | network architect  [ 
]     [email-masked]  http://www.sandelman.ca/        |   ruby on rails    [

---

From: "Graham Bartlett (grbartle)" <[email-masked]>
Date: Sun, 12 Oct 2014 22:04:22 +0000

Hi Yoav

Thanks for the explanation, just for my understanding, why does this
rate-limiting have to (strictly) rely on the cookie (or puzzle)
notification? Is it more of the case that it guarantees that the attacker
is the attacker (prevents blind-spoofing) and as you say limits the
attacker to using their own IP address?

So say our bot would send 5 requests a second and always get to IKE_AUTH
and transmit a random value attempting to authenticate, it would never
leave any half open SAs. I presume enabling the cookie notification will
prevent the bot attempting to masquerade as another legitimate address at
the same time (where your rate-limiting would help prevent a DOS
condition). As the attacker would never leave any half-open SA's (as they
get to IKE_AUTH and then Authentication would fail), so strictly speaking
the cookie notification might never be employed (if it's enabled to be
activated when half open SA's are detected) and you could (and should)
rate-limit without enabling cookies.

I'm not knocking the cookie-notification (I'm all for it), but I think
that rate-limiting should occur even if the headend isn't detecting a
large number of half-open SA's.

cheers

On 10/10/2014 20:58, "Yoav Nir" <[email-masked]> wrote:

>The cookie mechanism helps in one way. If my IPsec gateway is up against
>an X-node botnet, the cookie mechanism limits the botnet to X unique IP
>addresses (or IPv6 prefixes).
>
>This in itself doesn¹t help much, but we can limit the amount of
>concurrent half-open SAs that the gateway is willing to store from a
>particular IP address or prefix. So if, for example, we hold a half-open
>SA for 10 seconds and allow an IPv4 address / IPv6 prefix to have at most
>5 half-open SAs, this limits each node in the botnet to 1 half-open SA
>every two seconds, even if their bandwidth is sufficient to create many
>more. It also limits the total half-open SAs that they can hold on the
>gateway to 5X. The limit mechanism doesn¹t work without either cookies or
>puzzles.
>
>Reducing the time an half-open SA is held doesn¹t really help in this
>scenario, because I¹m assuming that the attackers have enough bandwidth.
>So if we reduce the hold time to 1 second, they should be able to create
>5 half-open SAs per second. This is where puzzles come in. They can
>reduce the rate that these attacking nodes can create new half-open SAs.
>
>Yoav
>

---

From: Yoav Nir <[email-masked]>
Date: Mon, 13 Oct 2014 10:09:01 +0300

> attacker to using their own IP address?

I think you got it. Without something that guarantees return routability such as the cookie or the puzzle, an attacker can sent IKE_INIT requests, one from each and every Internet address, quickly exhausting the half-open SA database. It doesn’t help to rate-limit if the attacker has a nearly-infinite supply of source addresses. At least the cookies limit the attacker to the actual size of her botnet.

> rate-limit without enabling cookies.

The cookie mechanism prevents the blind spoofing, so it’s forcing the attacker to this kind of attack, where rate-limiting is helping.

> large number of half-open SA’s.

Sure. But as long as we’re not preventing spoofed requests, the attacker can still use the other strategy.

Yoav

---

From: Tero Kivinen <[email-masked]>
Date: Mon, 13 Oct 2014 17:22:16 +0300

> Split the difference.  Shorten the amount of time you keep the half-open

After we have received first IKE_AUTH message, we have already done
all the expensive calculations already. I.e we have done the other
half of Diffie-Hellman, and there is no point of throwing away that
context, even if we get some packets which fail to decrypt.

Note, that throwing away packets after this is just one MAC and
compare, thus it is very fast compared to the Diffie-Hellman setup. 

> the average time to complete a handshake when not under (D)DoS attack.

No it is not. If you are using EAP, it might be that there is some
userinteraction during the IKE_AUTH time. There should not be anything
for the first packet, but for later ones there might be.

I.e. the pre-shared key needed to send the first IKE_AUTH packet
should already be asked from user before even sending first
IKE_SA_INIT...

Also for small devices might take 10 seconds to actually do the other
half of the Diffie-Hellman...

I would expect that most timeouts during this phase are in order of
minutes... Especially as there might be crappy networks between.
-- 
[email-masked]