Subject: [IPsec] Puzzles draft - another idea

From: Yoav Nir <[email-masked]>
Date: Wed, 30 Jul 2014 17:45:34 +0300

Hi all

After the meeting on Friday, I talked to Tero and Brian Weis, and Tero suggested a different sort of puzzle that could make it easier to support both strong and weak clients. This is sort of like the proof-of-work used by BitCoin.

Calculate the cookie as before. For an example, let’s assume the cookie is fdbcfa5a430d7201282358a2a034de0013cfe2ae (20 octets).
A “legacy” initiator will return this exact cookie.
A newer initiator will return the cookie, with some extra bytes. 
The “value” of a returned cookie is determined by the number of trailing zero bits in the SHA-256 hash of the transmitted cookie:

Cookie || extra data
hash
# trailing zero bits
fdbcfa5a430d7201282358a2a034de0013cfe2ae
ec2f327dae577a31152e3de2ac0f2f798e21f02e1afb04d33ff79bdd5d30eede
1
fdbcfa5a430d7201282358a2a034de0013cfe2ae0182
71d3e8c09fbb8db5315e6364dce3ebd56ad35c96e284296e2ffffa256bdfa800
11
fdbcfa5a430d7201282358a2a034de0013cfe2ae022b3d
3b4bdf201105e059e09f65219021738b8f6a148896b2e1be2fdc726aeb6e0000
17
fdbcfa5a430d7201282358a2a034de0013cfe2ae0aa679
c352e914a41615496e3498e5ecb87b992be1ad40620f48af85428996c1f00000
20
fdbcfa5a430d7201282358a2a034de0013cfe2ae5c2880
155319280d687074d0f78511f63c77c568a5418dd44e6467d8fc37723d800000
23
fdbcfa5a430d7201282358a2a034de0013cfe2ae022bffc8
6469faf4455cf9a51b04edeea8195f27771d56b95f2d874764a71e2948000000
27

Initiators are limited (by the construction of the cookie) in the amount of time they can spend. So powerful clients will manage 23 bits, while weaker clients will only manage 17.
When an Initial request arrives with a cookie, first the first 20 bytes are validated, and then the result is queued by “value”. 
When the responder can handle a packet (has room in the half-open SA table) it processes the entry with the highest value in the queue. Entries expire after some time even if not handled.

I think if this algorithm is chosen, an attacker can still expend little effort, get some 5-6 bits, and use that to push out all legacy clients. We could counter that by having a minimum threshold at something like 10-12 bits, some value that all supported platforms can easily manage in under 0.5 seconds, and consider all values below that to be equal to zero (not enough effort to matter).

This could get some more tweaks. But what do people think of this?

Thanks

Yoav

P.S. This is the first time I tried to send a table pasted into Apple Mail to a mailing list. I apologize in advance if it comes out looking horrific.

---

From: Yaron Sheffer <[email-masked]>
Date: Wed, 30 Jul 2014 08:40:13 -0700

Hi Yoav,

this is a nice idea, but I think it actually performs worse than the 
baseline.

With the previous solution all clients had to expend the same number of 
cycles, but would be served FCFS so from time to time, the "good" ones 
would be served. With this proposal the attacker can push out the 
legitimate weak clients in a *deterministic* way. If I know all Check 
Point iPhone clients do 10 bits (I assume most implementations will 
choose a value and stick to it, because they do not have any information 
about the effort currently needed), I will configure my botnet to always 
do 11, and push out any legitimate clients.

Thanks,
	Yaron

On 07/30/2014 07:45 AM, Yoav Nir wrote:
> Hi all
>
> After the meeting on Friday, I talked to Tero and Brian Weis, and Tero
> suggested a different sort of puzzle that could make it easier to
> support both strong and weak clients. This is sort of like the
> proof-of-work used by BitCoin.
>
>  1. Calculate the cookie as before. For an example, let’s assume the
>     cookie is fdbcfa5a430d7201282358a2a034de0013cfe2ae (20 octets).
>  2. A “legacy” initiator will return this exact cookie.
>  3. A newer initiator will return the cookie, with some extra bytes.
>  4. The “value” of a returned cookie is determined by the number of
>     trailing zero bits in the SHA-256 hash of the transmitted cookie:
>
>     Cookie || extra data
>     	
>     hash
>     	
>     # trailing zero bits
>  5. Initiators are limited (by the construction of the cookie) in the
>     amount of time they can spend. So powerful clients will manage 23
>     bits, while weaker clients will only manage 17.
>  6. When an Initial request arrives with a cookie, first the first 20
>     bytes are validated, and then the result is queued by “value”.
>  7. When the responder can handle a packet (has room in the half-open SA
>     table) it processes the entry with the highest value in the queue.
>     Entries expire after some time even if not handled.
>
>
> I think if this algorithm is chosen, an attacker can still expend little
> effort, get some 5-6 bits, and use that to push out all legacy clients.
> We could counter that by having a minimum threshold at something like
> 10-12 bits, some value that all supported platforms can easily manage in
> under 0.5 seconds, and consider all values below that to be equal to
> zero (not enough effort to matter).
>
> P.S. This is the first time I tried to send a table pasted into Apple
> Mail to a mailing list. I apologize in advance if it comes out looking
> horrific.
>
>
>
> _______________________________________________
> IPsec mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/ipsec
>

---

From: Yoav Nir <[email-masked]>
Date: Wed, 30 Jul 2014 21:45:13 +0300

Hi, Yaron

Suppose our half-open SA table can hold 100,000 entries and we clear them out after 10 seconds. That allows 10,000 entries per second. More realistic number are 18 bits for the iPhone and 20 bits for the attacker, so to block out those iPhones, the attacker would have to perform 10,000 * 2^20 SHA-256 hashes per second, or about 10 billion hashes. That’s about 400 server-class hardware working full-time, or a 10,000-way botnet. The draft is all about increasing the work for the attacker, and I believe this is doing it well. The baseline is sending 20,000 packets per second while only copying the cookie (no PK or hash operations at all).

It is possible to do as in the current draft, and set a single difficulty level (say, 18 bits). This allows the attacker a nice and deterministic way to keep the half-open SA table full, which blocks out all clients, not just the iPhones. 

Yoav

On Jul 30, 2014, at 6:40 PM, Yaron Sheffer <[email-masked]> wrote:

> Hi Yoav,
> 
> this is a nice idea, but I think it actually performs worse than the baseline.
> 
> With the previous solution all clients had to expend the same number of cycles, but would be served FCFS so from time to time, the "good" ones would be served. With this proposal the attacker can push out the legitimate weak clients in a *deterministic* way. If I know all Check Point iPhone clients do 10 bits (I assume most implementations will choose a value and stick to it, because they do not have any information about the effort currently needed), I will configure my botnet to always do 11, and push out any legitimate clients.
> 
> Thanks,
> 	Yaron
>

---

From: Paul Wouters <[email-masked]>
Date: Wed, 30 Jul 2014 15:02:56 -0400 (EDT)

On Wed, 30 Jul 2014, Yoav Nir wrote:

> Suppose our half-open SA table can hold 100,000 entries and we clear them out after 10 seconds. That allows 10,000 entries per
> second. More realistic number are 18 bits for the iPhone and 20 bits for the attacker, so to block out those iPhones, the attacker
> would have to perform 10,000 * 2^20 SHA-256 hashes per second, or about 10 billion hashes. That’s about 400 server-class hardware
> working full-time, or a 10,000-way botnet. The draft is all about increasing the work for the attacker, and I believe this is doing
> it well. The baseline is sending 20,000 packets per second while only copying the cookie (no PK or hash operations at all).
> 
> It is possible to do as in the current draft, and set a single difficulty level (say, 18 bits). This allows the attacker a nice and
> deterministic way to keep the half-open SA table full, which blocks out all clients, not just the iPhones. 

The iphone (which is only rumored to do IKEv2 with iOS8 likely to be
released in September this year) currently has a
terrible record of continuously re-establishing connections. Like
whenever the screen saver hits it will tear down the tunnel. With
an always-on profile, that means if I unblanc the screen, it will
start a new IKE session.

A scheme like this would drain the battery on top of the current
re-establishing draining, that already prevents me from using an
always-on profile - my iphone won't last for 4 hours.

Perhaps we should look at other types of puzzles that do not depend on
raw CPU power?

Paul

---

From: Yaron Sheffer <[email-masked]>
Date: Wed, 30 Jul 2014 12:12:20 -0700

Makes sense to me.

	Yaron

On 07/30/2014 11:45 AM, Yoav Nir wrote:
> Hi, Yaron
>
> Suppose our half-open SA table can hold 100,000 entries and we clear
> them out after 10 seconds. That allows 10,000 entries per second. More
> realistic number are 18 bits for the iPhone and 20 bits for the
> attacker, so to block out those iPhones, the attacker would have to
> perform 10,000 * 2^20 SHA-256 hashes per second, or about 10 billion
> hashes. That’s about 400 server-class hardware working full-time, or a
> 10,000-way botnet. The draft is all about increasing the work for the
> attacker, and I believe this is doing it well. The baseline is sending
> 20,000 packets per second while only copying the cookie (no PK or hash
> operations at all).
>
> It is possible to do as in the current draft, and set a single
> difficulty level (say, 18 bits). This allows the attacker a nice and
> On Jul 30, 2014, at 6:40 PM, Yaron Sheffer <[email-masked]
> <mailto:[email-masked]>> wrote:
>
>> Hi Yoav,
>>
>> With the previous solution all clients had to expend the same number
>> of cycles, but would be served FCFS so from time to time, the "good"
>> ones would be served. With this proposal the attacker can push out the
>> choose a value and stick to it, because they do not have any
>> information about the effort currently needed), I will configure my
>> botnet to always do 11, and push out any legitimate clients.
>>
>> Thanks,
>> Yaron
>>
>>> [email-masked] <mailto:[email-masked]>