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.
_______________________________________________
IPsec mailing list
IPsec@ietf.org
https://www.ietf.org/mailman/listinfo/ipsec

Reply via email to