Subject: [IPsec] Call for adoption: Client Puzzles

From: Yaron Sheffer <[email-masked]>
Date: Sun, 21 Sep 2014 22:52:36 +0300

Dear working group,

This is a call for adopting draft-nir-ipsecme-puzzles-00 as a
WG document. Please respond to this mail with a Yes or No
and a short rationale, at latest by Friday Sep. 26.

Thanks,
Yaron

---

From: Tero Kivinen <[email-masked]>
Date: Mon, 22 Sep 2014 14:56:40 +0300

Yaron Sheffer writes:
> This is a call for adopting draft-nir-ipsecme-puzzles-00 as a WG
> document. Please respond to this mail with a Yes or No and a short
> rationale, at latest by Friday Sep. 26.

I think this problem is something we should consider, i.e start
working on the solution to it. I have not yet seen any attacks, but
if we get widespread IKEv2 uses in the future, I would expect all kind
of DoS attacks are going to spread, and it would be good idea if we
already have mechanism for protecting against them.

We had good discussion about this last time, and I think this item
requires bit more research to find out what would be the best way to
do this, especially if we think about those adaptive formats we
discussed in the meeting (i.e. where server can ask some work, and
client can do as much work as he can afford, and server then decides
whether that was enough or not).

For IPv6 we might need to think bit more, as there we cannot blacklist
known attackers that easily, so we might need to do something else
there.

So I think this is item we should work on, but I think there is quite
a lot of research and work in here to get something that would be good
way to solve this, and as we are not in hurry (meaning we are not
seeing such attacks now), we can use some time to get really good
solution out.
-- 
[email-masked]

---

From: Paul Wouters <[email-masked]>
Date: Mon, 22 Sep 2014 12:38:02 -0400 (EDT)

> seeing such attacks now), we can use some time to get really good

I agree with Tero. It's worth thinking about, but the current solution
based on CPU power seems to be in favour of the attacker, not the
legitimate client. It would be nice if we can come up with a better
solution that gives clients a better advantage.

For example, I think currently, you are better of checking for the the
CERTREQ SHA1 payload to determine which is a legitimate client, although
it does take more processing of the payloads. And of course the SHA1 is
not a very well kept secret....

So, I'm in favour of adoption of the document, but not in favour of the
currently proposed CPU-bound puzzle solution.

Paul

---

From: Yaron Sheffer <[email-masked]>
Date: Mon, 22 Sep 2014 20:05:18 +0300

> currently proposed CPU-bound puzzle solution.

With WG chair hat on: We should adopt this document if the problem it 
raises needs to be solved (I would say the problem is, DDoS protection 
in the presence of botnets) AND if the document actually solves the 
problem or can be modified without radical changes to do so.

If radical changes are needed, let's by all means discuss them first on 
the list, and then adopt the document.

Thanks,
	Yaron

---

From: Yoav Nir <[email-masked]>
Date: Mon, 22 Sep 2014 22:56:47 +0300

Hi.

As I’m the document author, it’s no surprise that my vote is Yes.

Much like Paul Wouters, I would have liked to have a kind of puzzle that did not give an advantage to attacking desktops over legitimate smartphones. But all proposals for puzzles have been just as CPU-bound as the partial hash break in the current draft, or the bitcoin-style puzzle that I like better now.

One proposal that I kind of liked (and I’m sorry I’ve forgotten who suggested it) was to relegate the puzzle to a second line of defense, through the use of some kind of anti-dos ticket. The ticket would be a bearer token (perhaps an encrypted timestamp) that would allow the bearer to get by with a much easier version of the puzzle. The responder would make an effort to prevent replay of tickets (as in remembering the last 1000 valid tickets), which would mean that to consistently get the easy version of the puzzle, the attackers would need to collect a greater amount of tickets than the responder stores.

In any case, I think the document should be adopted, and then we can change the puzzle algorithm according to the group’s preference and add a fast path for repeat visitors if we think that’s a good idea.

Yoav

On Sep 21, 2014, at 10:52 PM, Yaron Sheffer <[email-masked]> wrote:

> Dear working group,
> 
> This is a call for adopting draft-nir-ipsecme-puzzles-00 as a WG document. Please respond to this mail with a Yes or No and a short rationale, at latest by Friday Sep. 26.
> 
> Thanks,
> 	Yaron

---

From: Michael Richardson <[email-masked]>
Date: Tue, 23 Sep 2014 14:24:31 -0400

Yoav Nir <[email-masked]> wrote:
    > One proposal that I kind of liked (and I’m sorry I’ve forgotten who
    > suggested it) was to relegate the puzzle to a second line of defense,
    > through the use of some kind of anti-dos ticket. The ticket would be a
    > bearer token (perhaps an encrypted timestamp) that would allow the
    > bearer to get by with a much easier version of the puzzle. The

Would this ticket be provided in a Notify, after AUTHentication, in a
previous PARENT-SA?

    > In any case, I think the document should be adopted, and then we can
    > change the puzzle algorithm according to the group’s preference and add
    > a fast path for repeat visitors if we think that’s a good idea.

+1

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

---

From: Yoav Nir <[email-masked]>
Date: Tue, 23 Sep 2014 21:33:13 +0300

> Would this ticket be provided in a Notify, after AUTHentication, in a

Since it’s provided by the responder, it can go in the AUTH response. And yes, it’s a “have an easier time getting in next time” kind of ticket, so we don’t need solid replay protection, just best effort replay protection.

Come to think of it, the mechanisms should only be part of the draft. The purpose of the draft is DDOS protection. So it should cover all aspects: aging policy for the half-open SA database, limiting half-open SAs from single IPv4 addresses or IPv6 prefixes, probably some other things. There’s more to protecting a server on the internet than just implementing a protocol extension.

Yoav

---

From: Tero Kivinen <[email-masked]>
Date: Thu, 25 Sep 2014 14:27:11 +0300

> Would this ticket be provided in a Notify, after AUTHentication, in a

Wouldn't it be better to use IKEv2 session resumption (RFC 5723) for
those clients coming back.

I.e if you resume old existing session then you do not need to do
puzzle... And after the resume, the ticket is usually changed again,
so the ticket would always be fresh.
-- 
[email-masked]

---

From: Yoav Nir <[email-masked]>
Date: Thu, 25 Sep 2014 20:02:38 +0300

> so the ticket would always be fresh.

That’s possible. But session tickets are different from these tickets in two ways:

 1. Session tickets are time-limited with a rather short validity period. If policy requires checking the certificate / password every two hours, then the ticket cannot be valid for more than that. 
 2. Session tickets must not be replayed, so the gateway has to use some very strict anti-replay mechanisms.

The proposed tickets can be valid for a long time, and while replay prevention is desired, it doesn’t need to be very strict.

This laxness has operational benefits. It’s easier to implement in a cluster of gateways, and a ticket will be valid even for a user that hasn’t connected in a while. This makes sense because the prize from a replayed RFC 5723 ticket is great - a valid, authenticated session. OTOH managing to replay this new kind of ticket only gets you a half-open SA without bothering to solve a puzzle. 

Yoav

---

From: Yaron Sheffer <[email-masked]>
Date: Fri, 26 Sep 2014 13:27:04 +0300

I agree that if session resumption is implemented, it is a good way to 
reduce the problem drastically. Resuming clients go to the "fast track", 
and any new connections get the anti-DOS treatment - cookie- or 
puzzle-based.

To answer Yoav's two objections:

1. This is a standard trade-off. We can only hope people will eventually 
find a way to notify the IKE gateway when a password is changed, which 
would enable longer ticket lifetimes.

2. Quoting RFC 5723:

    This document therefore requires that the ticket be presented to the
    IKEv2 responder only once; under normal circumstances (e.g., no
    active attacker), there should be no multiple use of the same ticket.

    We are not aware of additional security issues associated with ticket
    reuse: the protocol guarantees freshness of the generated crypto
    material even in such cases.  As noted in Section 4.3.1, the gateway
    SHOULD prevent multiple uses of the same ticket.  But this is only an
    extra precaution, to ensure that clients do not implement reuse.  In
    other words, the gateway is not expected to cache old tickets for
    extended periods of time.

Thanks,
	Yaron

On 09/25/2014 08:02 PM, Yoav Nir wrote:
> _______________________________________________
> IPsec mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/ipsec
>

---

From: Tero Kivinen <[email-masked]>
Date: Fri, 26 Sep 2014 15:16:44 +0300

Yoav Nir writes:
>  1. Session tickets are time-limited with a rather short validity
>  period. If policy requires checking the certificate / password
>  every two hours, then the ticket cannot be valid for more than
>  that.  

I do not think there is anything fundamental in session resumption
that requires them to have short validity period. The server can of
course remember which cert was uesd to authenticate the connection
originally and do OCSP check or check the cert against CRL when
connection is resumed.

Also server can also whiteliste the IP after the resumption is
successfull and then immediately require reauthentication from the
client by using RFC4478 AUTH_LIFETIME notification with lifetime of 0. 

>  some very strict anti-replay mechanisms.

The best way would be for the server to reissue now ticket for every
time client comes back. And server needs to check those tickets
anyways and keep track of them and make sure they are not reused... 

> The proposed tickets can be valid for a long time, and while replay
> prevention is desired, it doesn’t need to be very strict.

I would assume each ticket only works once, and once you have
connected successfully you get new ticket. If attacker somehow can get
the ticket from the client (i.e. sees the connection attempt and
blocks the client while at the same time stealing the ticket), then it
can connect the server, but as it does not know the associated keying
material, it will be able to create only half-open SA and in that case
the server can just count such attempt and revoce the ticket after 3rd
failed attempt or so. 

> This laxness has operational benefits. It’s easier to implement in a
> cluster of gateways, and a ticket will be valid even for a user that
> hasn’t connected in a while. This makes sense because the prize from
> a replayed RFC 5723 ticket is great - a valid, authenticated
> session. OTOH managing to replay this new kind of ticket only gets
> you a half-open SA without bothering to solve a puzzle.  

Yes.
-- 
[email-masked]

---

From: "Valery Smyslov" <[email-masked]>
Date: Fri, 26 Sep 2014 17:08:51 +0400

Hi,

I think that the DoS protection is very important problem for IKE
and it needs to be addressed. I have, though, mixed feelings about 
the draft in its current form. The idea is very cute, but it has
IMHO a limited usage in protection against DoS attack. 
It doesn't protect against DDoS performed by botnets
and may even make the situation worse for legitimate clients.
So, I think more research is needed, althouth this idea
should be kept in mind.

Regards,
Valery.

  ----- Original Message ----- 
  From: Yaron Sheffer 
  To: ipsec 
  Sent: Sunday, September 21, 2014 11:52 PM
  Subject: [IPsec] Call for adoption: Client Puzzles

Dear working group,

Thanks,
	Yaron

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

---

From: Paul Hoffman <[email-masked]>
Date: Sun, 28 Sep 2014 19:30:00 -0700

The call for adoption has had mixed results. On the one hand, there is lots of interest in working on the problem. On the other, there is a fair amount of trepidation about whether making things significantly harder for botnets is attainable with the current state of botnets and puzzles is achievable; if it is not, maybe we shouldn't add another extensions that could make IKEv2 more fragile.

Given the interest, though, we will adopt this as a WG item. However, given the trepidation, we might purposely abandon the work later if we think we are not able to make a useful mechanism.

--Paul Hoffman

---

From: Michael Richardson <[email-masked]>
Date: Mon, 29 Sep 2014 09:26:48 -0400

Paul Hoffman <[email-masked]> wrote:
    > Given the interest, though, we will adopt this as a WG item. However,
    > given the trepidation, we might purposely abandon the work later if we
    > think we are not able to make a useful mechanism.

Thank you.

I think that this is the best process;  I think we need to think about the
problem deeper.  It would be nice if it could be made to work; but I suspect
that may be equivalent to the CAPTCHA problem.

---

From: Tero Kivinen <[email-masked]>
Date: Tue, 30 Sep 2014 13:43:49 +0300

> that may be equivalent to the CAPTCHA problem.

I do think the problem is easier than that...

I think the solution is combination of the protocol and the policy
rules. If we make some assumptions:

1) Gateway is NOT constrained device. It is device that can store some
data (few tens of megabytes of data when under attack is possible).

2) Client can be constrained device, which do not have lots of CPU
power or memory. If it is really constrained device, then it usually
isn't interactive connection, so even if it needs to wait for a while
to get connection that is ok. 

3) Client can also be smartphone, i.e. device which have quite a lot
of CPU power and/or memory, but does not want to use it as it would
increase the power usage so much that the battery life will be
shortened.

4) Client can also be desktop, i.e. device with quite a lot of CPU
power and/or memory, and who is not afraid of using those :-)

5) Each connections are usually quite long lived, i.e. devices make
one connection to the gateway, and keep that connection up all the
time, or at least very long time. If they move they use MOBIKE to keep
IKEv2 up and running even when they change IP-addresses. If they go
sleep for long time or disconnect from the network they will use
session resumption to come back.

6) Gateway can use IKEv2 redirect to distribute the attackers, i.e. it
could even use some cloud service which provides first level
protection, i.e. first redirect client during IKE_SA_INIT to cloud
service with LOTS of computing power. Then the cloud service will
authenticate client but might not authenticate the server (for example
using one way authentication). When the server then redirect client
back to real server using redirect, it will provide some kind of
VIP-pass cookie, that allows client to get past the queue... Or if the
SGW is willing to give authentication information to the cloud, the
server authentication can be done normally in cloud service, and
resumption token given to the client, and then client can be
redirected back to the original server. There are probably some open
issues how this all is done and how to combine redirect, resumption
and all those, but the protocol elements are there (except VIP-pass
cookie).

7) Botnets have huge amount of CPU power and lots of memory, but still
limited number of distinguished IPv4-addresses or IPv6-prefixes (it
might be millions, but most likely around thousands or tens of
thousands IP-addresses).

So I think those above make it easier than the captcha problem...

Also the gateway can blacklist all failed attempts by clients, i.e. do
not accept new connections from the same IP-address for some amount of
seconds, or move them to end of queue.

This assume that the blacklist for each failed attempt by IP-address
would be few tens of megabytes of memory, if attacker has about
million IP-addresses/prefixes. Note, that we can also make the prefix
length adjustable, i.e. assume attackers are not too close (related to
the IP-addresses) to the real users, and instead of /64 we could use
/56 or /48 for IPv6-addresses and /28 or /24 for IPv4 addresses. This
would reduce the size of the blacklist table. 

I would expect the processing rules being so that we collect new
connections for some amount of time, for example 100 ms, then we sort
the new connection attemps using special rules for that. We would move
everybody having valid resumption ticket or VIP-pass to the front,
then we would move everybody with IP-address blacklisted to the end
(ordered by number of failed attempts), and finally sort rest using
some kind of sorting order which would include whether they have
cookie or not, how long puzzle they have solved etc.

Now after we have the sorted list, we take first connection from the
list, start processing it, after that take next etc. While we are
processing current queue, we collect next batch of request. Then after
interval is passed again (i.e. after 100 ms), we throw the old queue
away (or keep the resumption and VIP-pass clients still in queue),
create new queue, and start over.

So I think the solution is something we can get working, and it will
be combination of differnet protocols we already have, and some new
protocols like the puzzle, and then it also includes description how
to combine all of those.
-- 
[email-masked]

---

From: Paul Wouters <[email-masked]>
Date: Tue, 30 Sep 2014 09:54:08 -0400 (EDT)

On Tue, 30 Sep 2014, Tero Kivinen wrote:

> time, or at least very long time.

Can I have a pony with that? :)

My experience is seeing many many short lives connections. Stupidly
short, sucking the life out of the battery short.

> protection

Interesting, but very scary....

> seconds, or move them to end of queue.

That's too easy a DOS to abuse.

> protocols like the puzzle, and then it also includes description how

Moar bells and whistles! :)

Paul

---

From: Michael Richardson <[email-masked]>
Date: Tue, 30 Sep 2014 13:43:13 -0400

Tero Kivinen <[email-masked]> wrote:
    > 3) Client can also be smartphone, i.e. device which have quite a lot of
    > CPU power and/or memory, but does not want to use it as it would

Except that client being smartphone/etc. is behind NAT44, and along with
ten thousand other smartphones, all have the same IP address... this matters

    > might be millions, but most likely around thousands or tens of

a situation where there is an enterprise of compromised systems behind
the enterprise firewall. (University lab networks come to mind...)

Further, the botnets don't need to present thousands of distinguished IPv4
addresses, they can present a small number of attack nodes, spreading the
work across the botnet?

So this tells me that we are looking for puzzles which are *not*
parallelizable.   I know little about this kind of stuff...

    > seconds, or move them to end of queue.

Move them to the end of the queue makes most sense.

    > everybody having valid resumption ticket or VIP-pass to the front, then
    > we would move everybody with IP-address blacklisted to the end (ordered
    > by number of failed attempts), and finally sort rest using some kind of
    > sorting order which would include whether they have cookie or not, how
    > long puzzle they have solved etc.

    > So I think the solution is something we can get working, and it will be
    > combination of differnet protocols we already have, and some new
    > protocols like the puzzle, and then it also includes description how to
    > combine all of those.

I think if the gateway has multiple CPUs, that it can collect and process at
the same time, it just has to never commit more than n-2 CPUs towards
processing so that it can have CPU left over for the collecting/sorting, and
of course, for other stuff like, say, IPsec...

I suspect, however, that the simplest machines to DDoS will be the smallest
gateways.

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