Subject: [IPsec] Fw: [ipsecme] #229 (ddos-protection): Need to decide the nature of the puzzle

From: "Valery Smyslov" <[email-masked]>
Date: Tue, 14 Apr 2015 11:47:14 +0300

Hi all,

Yoav added a couple of new issues into the tracker,
so I'd like to initiate the discussion of these issues.

The first issue (#229) is concerned with the inconsistency of the puzzle
solution time with the current definition of the puzzle.
So the question - should we change the puzzle definition
so that the deviation of the time required to solve it become smaller
(ideally - all equally difficult puzzles should be solved in constant time
by equal hosts).

My opinion is that while this is a desireable property, it is not so 
important
in real life. First, even if we make puzzle constant-time for equal
initiators, it won't help since in real life the initiators are different
and their computational power can differ even more than the deviation
of solution time with the current puzzle definition. In other words,
the real difficulty of any given puzzle is a relative value and it includes
not only the requested number of zero bits, but also the computantional 
power
of the initiator, which is in any case an unknown value for the responder.
And second - the draft is about DDoS protection. It implies that
the attack would involve many thouthands of attackers. In this
situation the deviation of puzzle difficulty becomes less important,
since statistically the puzzle solving time as it is seen from responder's 
point of view
will be close to average. Of course, for any given initiator it will be a 
lottery
and sometimes powerfull attacker will receive easy puzzle and
sometimes weak legacy initiator will receive difficult puzzle.
I see nothing fatal in the former - yes some DoS attacks will be successful.
The protocol doesn't have the goal to completely eliminate the
possibility of DoS attacks (and I don't think it is ever possible),
but to make it harder for attackers. What about the latter -
the protocol should consider such situation and should
leave an initiator a chance to establish IKE SA even if
the initiator is weak and the puzzle appeared to be difficult.

So the conclusion - I don't think we should change puzzle definition so
that it becomes close to constant-time giving the little value that it would
give us (taking into consideration the vast diversity of clients)
and the complexity it would involve and the increasing of the size of IKE 
messages.

Regards,
Valery.

> #229: Need to decide the nature of the puzzle
>
> Current text has PRF based puzzles: for a given cookie and difficulty leve
> l, find a key k, such that PRF(k, cookie) has at least l trailing zero
> bits.
> The problem with this puzzle is that while the expected time to solve this
> puzzle is 2^l, the actual time varies wildly.
>
> Scott Fluhrer suggested ([1]) that we use another kind of puzzle that is
> closer to constant-time. That requires more up-front work on the part of
> the responder (creating a new opportunity for DoS?) and larger IKE_SA_INIT
> requests. IKE_SA_INIT requests are not protected by IKEv2 fragmentation
>
> [1] http://www.ietf.org/mail-archive/web/ipsec/current/msg09601.html
>
> -- 
> -------------------------+-------------------------------------------------
> Reporter:               |      Owner:  draft-ietf-ipsecme-ddos-
>  [email-masked]    |  [email-masked]
>     Type:  task         |     Status:  new
> Priority:  normal       |  Milestone:
> Component:  ddos-        |   Severity:  Active WG Document
>  protection             |
> Keywords:               |
> -------------------------+-------------------------------------------------
>
> Ticket URL: <http://trac.tools.ietf.org/wg/ipsecme/trac/ticket/229>
> ipsecme <http://tools.ietf.org/ipsecme/>

---

From: Tero Kivinen <[email-masked]>
Date: Tue, 14 Apr 2015 15:52:45 +0300

Valery Smyslov writes:
> Of course, for any given initiator it will be a lottery and
> sometimes powerfull attacker will receive easy puzzle and sometimes
> weak legacy initiator will receive difficult puzzle.

I think that is actually wrong way of thinking this. There are no easy
or hard puzzles, all the puzzles are equal hard. You have to find
key that generates that number of zero bits in end. You can whatever
method to go through keys. If someone starts from key 0x00...00 and
counts up he might need to count n numbers. If someone starts from
0xff..ff and counts down he might find suitable key on first try for
the exactly same puzzle.

I.e. the puzzles are of same difficulty, the issue is that one solving
the puzzle might be lucky or not and thats why time to solve a puzzle
is different for different puzzles. Time to solve a puzzle is also
different if different methods of enumerating keys are used. 

> and the complexity it would involve and the increasing of the size of IKE 

I agree. If we make the time constant, then we will with 100%
propability lock out weak clients, as strong attackers can always
solve puzzles faster, so we need to add randomess in the queue system.
Now when we alredy have randomess in the solving time, the weak client
might get lucky and manage to find suitable solution to puzzle on
first try, so we already have randomness needed to allow weak clients
to get in if they try long enough.
-- 
[email-masked]