tech-invite   World Map     

3GPP     Specs     Glossaries     Architecture     IMS     UICC       IETF     RFCs     Groups     SIP     ABNFs       Search

RFC 8019

 
 
 

Protecting Internet Key Exchange Protocol Version 2 (IKEv2) Implementations from Distributed Denial-of-Service Attacks

Part 2 of 2, p. 16 to 32
Prev Section

 


prevText      Top      ToC       Page 16 
7.  Using Puzzles in the Protocol

   This section describes how the puzzle mechanism is used in IKEv2.  It
   is organized as follows.  Section 7.1 describes using puzzles in the
   IKE_SA_INIT exchange and Section 7.2 describes using puzzles in the
   IKE_AUTH exchange.  Both sections are divided into subsections
   describing how puzzles should be presented, solved, and processed by
   the Initiator and the Responder.

7.1.  Puzzles in IKE_SA_INIT Exchange

   The IKE Initiator indicates the desire to create a new IKE SA by
   sending an IKE_SA_INIT request message.  The message may optionally
   contain a COOKIE notification if this is a repeated request performed
   after the Responder's demand to return a cookie.

   HDR, [N(COOKIE),] SA, KE, Ni, [V+][N+]   -->

                   Figure 1: Initial IKE_SA_INIT Request

   According to the plan, described in Section 6, the IKE Responder
   monitors incoming requests to detect whether it is under attack.  If
   the Responder learns that a DoS or DDoS attack is likely to be in
   progress, then its actions depend on the volume of the attack.  If
   the volume is moderate, then the Responder requests the Initiator to
   return a cookie.  If the volume is high to such an extent that
   puzzles need to be used for defense, then the Responder requests the
   Initiator to solve a puzzle.

   The Responder MAY choose to process some fraction of IKE_SA_INIT
   requests without presenting a puzzle while being under attack to
   allow legacy clients, that don't support puzzles, to have a chance to
   be served.  The decision whether to process any particular request
   must be probabilistic, with the probability depending on the
   Responder's load (i.e., on the volume of attack).  The requests that
   don't contain the COOKIE notification MUST NOT participate in this
   lottery.  In other words, the Responder must first perform a return
   routability check before allowing any legacy client to be served if
   it is under attack.  See Section 7.1.4 for details.

Top      Up      ToC       Page 17 
7.1.1.  Presenting a Puzzle

   If the Responder makes a decision to use puzzles, then it includes
   two notifications in its response message -- the COOKIE notification
   and the PUZZLE notification.  Note that the PUZZLE notification MUST
   always be accompanied with the COOKIE notification, since the content
   of the COOKIE notification is used as an input data when solving the
   puzzle.  The format of the PUZZLE notification is described in
   Section 8.1.

                             <--   HDR, N(COOKIE), N(PUZZLE), [V+][N+]

             Figure 2: IKE_SA_INIT Response Containing Puzzle

   The presence of these notifications in an IKE_SA_INIT response
   message indicates to the Initiator that it should solve the puzzle to
   have a better chance to be served.

7.1.1.1.  Selecting the Puzzle Difficulty Level

   The PUZZLE notification contains the difficulty level of the puzzle
   -- the minimum number of trailing zero bits that the result of PRF
   must contain.  In diverse environments, it is nearly impossible for
   the Responder to set any specific difficulty level that will result
   in roughly the same amount of work for all Initiators, because
   computation power of different Initiators may vary by an order of
   magnitude, or even more.  The Responder may set the difficulty level
   to 0, meaning that the Initiator is requested to spend as much power
   to solve a puzzle as it can afford.  In this case, no specific value
   of ZBC is required from the Initiator; however, the larger the ZBC
   that the Initiator is able to get, the better the chance is that it
   will be served by the Responder.  In diverse environments, it is
   RECOMMENDED that the Initiator set the difficulty level to 0, unless
   the attack volume is very high.

   If the Responder sets a non-zero difficulty level, then the level
   SHOULD be determined by analyzing the volume of the attack.  The
   Responder MAY set different difficulty levels to different requests
   depending on the IP address the request has come from.

Top      Up      ToC       Page 18 
7.1.1.2.  Selecting the Puzzle Algorithm

   The PUZZLE notification also contains an identifier of the algorithm
   that is used by the Initiator to compute the puzzle.

   Cryptographic algorithm agility is considered an important feature
   for modern protocols [RFC7696].  Algorithm agility ensures that a
   protocol doesn't rely on a single built-in set of cryptographic
   algorithms but has a means to replace one set with another and
   negotiate new algorithms with the peer.  IKEv2 fully supports
   cryptographic algorithm agility for its core operations.

   To support crypto-agility in case of puzzles, the algorithm that is
   used to compute a puzzle needs to be negotiated during the
   IKE_SA_INIT exchange.  The negotiation is performed as follows.  The
   initial request message from the Initiator contains an SA payload
   containing a list of transforms of different types.  In that manner,
   the Initiator asserts that it supports all transforms from this list
   and can use any of them in the IKE SA being established.  The
   Responder parses the received SA payload and finds mutually supported
   transforms of type PRF.  The Responder selects the preferred PRF from
   the list of mutually supported ones and includes it into the PUZZLE
   notification.  There is no requirement that the PRF selected for
   puzzles be the same as the PRF that is negotiated later for use in
   core IKE SA crypto operations.  If there are no mutually supported
   PRFs, then IKE SA negotiation will fail anyway and there is no reason
   to return a puzzle.  In this case, the Responder returns a
   NO_PROPOSAL_CHOSEN notification.  Note that PRF is a mandatory
   transform type for IKE SA (see Sections 3.3.2 and 3.3.3 of
   [RFC7296]), and at least one transform of this type is always present
   in the SA payload in an IKE_SA_INIT request message.

7.1.1.3.  Generating a Cookie

   If the Responder supports puzzles, then a cookie should be computed
   in such a manner that the Responder is able to learn some important
   information from the sole cookie, when it is later returned back by
   the Initiator.  In particular, the Responder SHOULD be able to learn
   the following information:

   o  Whether the puzzle was given to the Initiator or only the cookie
      was requested.

   o  The difficulty level of the puzzle given to the Initiator.

   o  The number of consecutive puzzles given to the Initiator.

Top      Up      ToC       Page 19 
   o  The amount of time the Initiator spent to solve the puzzles.  This
      can be calculated if the cookie is timestamped.

   This information helps the Responder to make a decision whether to
   serve this request or demand more work from the Initiator.

   One possible approach to get this information is to encode it in the
   cookie.  The format of such encoding is an implementation detail of
   the Responder, as the cookie would remain an opaque block of data to
   the Initiator.  If this information is encoded in the cookie, then
   the Responder MUST make it integrity protected, so that any intended
   or accidental alteration of this information in the returned cookie
   is detectable.  So, the cookie would be generated as:

   Cookie = <VersionIDofSecret> | <AdditionalInfo> |
                     Hash(Ni | IPi | SPIi | <AdditionalInfo> | <secret>)

   Note that according to Section 2.6 of [RFC7296], the size of the
   cookie cannot exceed 64 bytes.

   Alternatively, the Responder may generate a cookie as suggested in
   Section 2.6 of [RFC7296], but associate the additional information,
   using local storage identified with the particular version of the
   secret.  In this case, the Responder should have different secrets
   for every combination of difficulty level and number of consecutive
   puzzles, and should change the secrets periodically, keeping a few
   previous versions, to be able to calculate how long ago a cookie was
   generated.

   The Responder may also combine these approaches.  This document
   doesn't mandate how the Responder learns this information from a
   cookie.

   When selecting cookie generation, algorithm implementations MUST
   ensure that an attacker gains no or insignificant benefit from
   reusing puzzle solutions in several requests.  See Section 10 for
   details.

7.1.2.  Solving a Puzzle and Returning the Solution

   If the Initiator receives a puzzle but it doesn't support puzzles,
   then it will ignore the PUZZLE notification as an unrecognized status
   notification (in accordance with Section 3.10.1 of [RFC7296]).  The
   Initiator MAY ignore the PUZZLE notification if it is not willing to
   spend resources to solve the puzzle of the requested difficulty, even
   if it supports puzzles.  In both cases, the Initiator acts as
   described in Section 2.6 of [RFC7296] -- it restarts the request and
   includes the received COOKIE notification in it.  The Responder

Top      Up      ToC       Page 20 
   should be able to distinguish the situation when it just requested a
   cookie from the situation where the puzzle was given to the
   Initiator, but the Initiator for some reason ignored it.

   If the received message contains a PUZZLE notification and doesn't
   contain a COOKIE notification, then this message is malformed because
   it requests to solve the puzzle but doesn't provide enough
   information to allow the puzzle to be solved.  In this case, the
   Initiator MUST ignore the received message and continue to wait until
   either a valid PUZZLE notification is received or the retransmission
   timer fires.  If it fails to receive a valid message after several
   retransmissions of IKE_SA_INIT requests, then this means that
   something is wrong and the IKE SA cannot be established.

   If the Initiator supports puzzles and is ready to solve them, then it
   tries to solve the given puzzle.  After the puzzle is solved, the
   Initiator restarts the request and returns back to the Responder the
   puzzle solution in a new payload called a Puzzle Solution (PS)
   payload (see Section 8.2) along with the received COOKIE
   notification.

   HDR, N(COOKIE), [PS,] SA, KE, Ni, [V+][N+]   -->

         Figure 3: IKE_SA_INIT Request Containing Puzzle Solution

7.1.3.  Computing a Puzzle

   General principles of constructing puzzles in IKEv2 are described in
   Section 4.4.  They can be summarized as follows: given unpredictable
   string S and PRF, find N different keys Ki (where i=[1..N]) for that
   PRF so that the result of PRF(Ki,S) has at least the specified number
   of trailing zero bits.  This specification requires that the puzzle
   solution contains 4 different keys (i.e., N=4).

   In the IKE_SA_INIT exchange, it is the cookie that plays the role of
   unpredictable string S.  In other words, in the IKE_SA_INIT, the task
   for the IKE Initiator is to find the four different, equal-sized keys
   Ki for the agreed upon PRF such that each result of PRF(Ki,cookie)
   where i = [1..4] has a sufficient number of trailing zero bits.  Only
   the content of the COOKIE notification is used in puzzle calculation,
   i.e., the header of the Notify payload is not included.

   Note that puzzles in the IKE_AUTH exchange are computed differently
   than in the IKE_SA_INIT_EXCHANGE.  See Section 7.2.3 for details.

Top      Up      ToC       Page 21 
7.1.4.  Analyzing Repeated Request

   The received request must at least contain a COOKIE notification.
   Otherwise, it is an initial request and in this case, it MUST be
   processed according to Section 7.1.  First, the cookie MUST be
   checked for validity.  If the cookie is invalid, then the request is
   treated as initial and is processed according to Section 7.1.  It is
   RECOMMENDED that a new cookie is requested in this case.

   If the cookie is valid, then some important information is learned
   from it or from local state based on the identifier of the cookie's
   secret (see Section 7.1.1.3 for details).  This information helps the
   Responder to sort out incoming requests, giving more priority to
   those that were created by spending more of the Initiator's
   resources.

   First, the Responder determines if it requested only a cookie or
   presented a puzzle to the Initiator.  If no puzzle was given, this
   means that at the time the Responder requested a cookie, it didn't
   detect the DoS or DDoS attack, or the attack volume was low.  In this
   case, the received request message must not contain the PS payload,
   and this payload MUST be ignored if the message contains a PS payload
   for any reason.  Since no puzzle was given, the Responder marks the
   request with the lowest priority since the Initiator spent little
   resources creating it.

   If the Responder learns from the cookie that the puzzle was given to
   the Initiator, then it looks for the PS payload to determine whether
   its request to solve the puzzle was honored or not.  If the incoming
   message doesn't contain a PS payload, this means that the Initiator
   either doesn't support puzzles or doesn't want to deal with them.  In
   either case, the request is marked with the lowest priority since the
   Initiator spent little resources creating it.

   If a PS payload is found in the message, then the Responder MUST
   verify the puzzle solution that it contains.  The solution is
   interpreted as four different keys.  The result of using each of them
   in the PRF (as described in Section 7.1.3) must contain at least the
   requested number of trailing zero bits.  The Responder MUST check all
   of the four returned keys.

   If any checked result contains fewer bits than were requested, this
   means that the Initiator spent less resources than expected by the
   Responder.  This request is marked with the lowest priority.

   If the Initiator provided the solution to the puzzle satisfying the
   requested difficulty level, or if the Responder didn't indicate any
   particular difficulty level (by setting the ZBC to 0) and the

Top      Up      ToC       Page 22 
   Initiator was free to select any difficulty level it can afford, then
   the priority of the request is calculated based on the following
   considerations:

   o  The Responder MUST take the smallest number of trailing zero bits
      among the checked results and count it as the number of zero bits
      the Initiator solved for.

   o  The higher number of zero bits the Initiator provides, the higher
      priority its request should receive.

   o  The more consecutive puzzles the Initiator solved, the higher
      priority it should receive.

   o  The more time the Initiator spent solving the puzzles, the higher
      priority it should receive.

   After the priority of the request is determined, the final decision
   whether to serve it or not is made.

7.1.5.  Deciding Whether to Serve the Request

   The Responder decides what to do with the request based on the
   request's priority and the Responder's current load.  There are three
   possible actions:

   o  Accept request.

   o  Reject request.

   o  Demand more work from the Initiator by giving it a new puzzle.

   The Responder SHOULD accept an incoming request if its priority is
   high -- this means that the Initiator spent quite a lot of resources.
   The Responder MAY also accept some low-priority requests where the
   Initiators don't support puzzles.  The percentage of accepted legacy
   requests depends on the Responder's current load.

   If the Initiator solved the puzzle, but didn't spend much resources
   for it (the selected puzzle difficulty level appeared to be low and
   the Initiator solved it quickly), then the Responder SHOULD give it
   another puzzle.  The more puzzles the Initiator solves the higher its
   chances are to be served.

   The details of how the Responder makes a decision for any particular
   request are implementation dependent.  The Responder can collect all
   of the incoming requests for some short period of time, sort them out
   based on their priority, calculate the number of available memory

Top      Up      ToC       Page 23 
   slots for half-open IKE SAs, and then serve that number of requests
   from the head of the sorted list.  The remainder of requests can be
   either discarded or responded to with new puzzle requests.

   Alternatively, the Responder may decide whether to accept every
   incoming request with some kind of lottery, taking into account its
   priority and the available resources.

7.2.  Puzzles in an IKE_AUTH Exchange

   Once the IKE_SA_INIT exchange is completed, the Responder has created
   a state and is waiting for the first message of the IKE_AUTH exchange
   from the Initiator.  At this point, the Initiator has already passed
   the return routability check and has proved that it has performed
   some work to complete the IKE_SA_INIT exchange.  However, the
   Initiator is not yet authenticated, and this allows a malicious
   Initiator to perform an attack, as described in Section 3.  Unlike a
   DoS attack in the IKE_SA_INIT exchange, which is targeted on the
   Responder's memory resources, the goal of this attack is to exhaust a
   Responder's CPU power.  The attack is performed by sending the first
   IKE_AUTH message containing arbitrary data.  This costs nothing to
   the Initiator, but the Responder has to perform relatively costly
   operations when computing the DH shared secret and deriving SK_* keys
   to be able to verify authenticity of the message.  If the Responder
   doesn't keep the computed keys after an unsuccessful verification of
   the IKE_AUTH message, then the attack can be repeated several times
   on the same IKE SA.

   The Responder can use puzzles to make this attack more costly for the
   Initiator.  The idea is that the Responder includes a puzzle in the
   IKE_SA_INIT response message and the Initiator includes a puzzle
   solution in the first IKE_AUTH request message outside the Encrypted
   payload, so that the Responder is able to verify a puzzle solution
   before computing the DH shared secret.

   The Responder constantly monitors the amount of the half-open IKE SA
   states that receive IKE_AUTH messages that cannot be decrypted due to
   integrity check failures.  If the percentage of such states is high
   and it takes an essential fraction of the Responder's computing power
   to calculate keys for them, then the Responder may assume that it is
   under attack and SHOULD use puzzles to make it harder for attackers.

Top      Up      ToC       Page 24 
7.2.1.  Presenting the Puzzle

   The Responder requests the Initiator to solve a puzzle by including
   the PUZZLE notification in the IKE_SA_INIT response message.  The
   Responder MUST NOT use puzzles in the IKE_AUTH exchange unless a
   puzzle has been previously presented and solved in the preceding
   IKE_SA_INIT exchange.

                             <--   HDR, SA, KE, Nr, N(PUZZLE), [V+][N+]

         Figure 4: IKE_SA_INIT Response Containing IKE_AUTH Puzzle

7.2.1.1.  Selecting Puzzle Difficulty Level

   The difficulty level of the puzzle in the IKE_AUTH exchange should be
   chosen so that the Initiator would spend more time to solve the
   puzzle than the Responder to compute the DH shared secret and the
   keys needed to decrypt and verify the IKE_AUTH request message.  On
   the other hand, the difficulty level should not be too high,
   otherwise legitimate clients will experience an additional delay
   while establishing the IKE SA.

   Note that since puzzles in the IKE_AUTH exchange are only allowed to
   be used if they were used in the preceding IKE_SA_INIT exchange, the
   Responder would be able to roughly estimate the computational power
   of the Initiator and select the difficulty level accordingly.  Unlike
   puzzles in the IKE_SA_INIT, the requested difficulty level for
   IKE_AUTH puzzles MUST NOT be 0.  In other words, the Responder must
   always set a specific difficulty level and must not let the Initiator
   choose it on its own.

7.2.1.2.  Selecting the Puzzle Algorithm

   The algorithm for the puzzle is selected as described in
   Section 7.1.1.2.  There is no requirement that the algorithm for the
   puzzle in the IKE_SA INIT exchange be the same as the algorithm for
   the puzzle in the IKE_AUTH exchange; however, it is expected that in
   most cases they will be the same.

7.2.2.  Solving the Puzzle and Returning the Solution

   If the IKE_SA_INIT regular response message (i.e., the message
   containing SA, KE, NONCE payloads) contains the PUZZLE notification
   and the Initiator supports puzzles, it MUST solve the puzzle.  Note
   that puzzle construction in the IKE_AUTH exchange differs from the
   puzzle construction in the IKE_SA_INIT exchange and is described in
   Section 7.2.3.  Once the puzzle is solved, the Initiator sends the
   IKE_AUTH request message containing the PS payload.

Top      Up      ToC       Page 25 
   HDR, PS, SK {IDi, [CERT,] [CERTREQ,]
               [IDr,] AUTH, SA, TSi, TSr}   -->

      Figure 5: IKE_AUTH Request Containing IKE_AUTH Puzzle Solution

   The PS payload MUST be placed outside the Encrypted payload, so that
   the Responder is able to verify the puzzle before calculating the DH
   shared secret and the SK_* keys.

   If IKE fragmentation [RFC7383] is used in the IKE_AUTH exchange, then
   the PS payload MUST be present only in the first IKE Fragment
   message, in accordance with Section 2.5.3 of [RFC7383].  Note that
   calculation of the puzzle in the IKE_AUTH exchange doesn't depend on
   the content of the IKE_AUTH message (see Section 7.2.3).  Thus, the
   Initiator has to solve the puzzle only once, and the solution is
   valid for both unfragmented and fragmented IKE messages.

7.2.3.  Computing the Puzzle

   A puzzle in the IKE_AUTH exchange is computed differently than in the
   IKE_SA_INIT exchange (see Section 7.1.3).  The general principle is
   the same; the difference is in the construction of the string S.
   Unlike the IKE_SA_INIT exchange, where S is the cookie, in the
   IKE_AUTH exchange, S is a concatenation of Nr and SPIr.  In other
   words, the task for the IKE Initiator is to find the four different
   keys Ki for the agreed upon PRF such that each result of PRF(Ki,Nr |
   SPIr) where i=[1..4] has a sufficient number of trailing zero bits.
   Nr is a nonce used by the Responder in the IKE_SA_INIT exchange,
   stripped of any headers.  SPIr is the IKE Responder's SPI from the
   IKE header of the SA being established.

7.2.4.  Receiving the Puzzle Solution

   If the Responder requested the Initiator to solve a puzzle in the
   IKE_AUTH exchange, then it MUST silently discard all the IKE_AUTH
   request messages without the PS payload.

   Once the message containing a solution to the puzzle is received, the
   Responder MUST verify the solution before performing computationally
   intensive operations, i.e., computing the DH shared secret and the
   SK_* keys.  The Responder MUST verify all four of the returned keys.

   The Responder MUST silently discard the received message if any
   checked verification result is not correct (contains insufficient
   number of trailing zero bits).  If the Responder successfully
   verifies the puzzle and calculates the SK_* key, but the message
   authenticity check fails, then it SHOULD save the calculated keys in
   the IKE SA state while waiting for the retransmissions from the

Top      Up      ToC       Page 26 
   Initiator.  In this case, the Responder may skip verification of the
   puzzle solution and ignore the PS payload in the retransmitted
   messages.

   If the Initiator uses IKE fragmentation, then it sends all fragments
   of a message simultaneously.  Due to packets loss and/or reordering,
   it is possible that the Responder receives subsequent fragments
   before receiving the first one that contains the PS payload.  In this
   case, the Responder MAY choose to keep the received fragments until
   the first fragment containing the solution to the puzzle is received.
   In this case, the Responder SHOULD NOT try to verify authenticity of
   the kept fragments until the first fragment with the PS payload is
   received, and the solution to the puzzle is verified.  After
   successful verification of the puzzle, the Responder can then
   calculate the SK_* key and verify authenticity of the collected
   fragments.

8.  Payload Formats

8.1.  PUZZLE Notification

   The PUZZLE notification is used by the IKE Responder to inform the
   Initiator about the need to solve the puzzle.  It contains the
   difficulty level of the puzzle and the PRF the Initiator should use.

                        1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   | Next Payload  |C|  RESERVED   |         Payload Length        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |Protocol ID(=0)| SPI Size (=0) |      Notify Message Type      |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |              PRF              |  Difficulty   |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   o  Protocol ID (1 octet) -- MUST be 0.

   o  SPI Size (1 octet) -- MUST be 0, meaning no SPI is present.

   o  Notify Message Type (2 octets) -- MUST be 16434, the value
      assigned for the PUZZLE notification.

   o  PRF (2 octets) -- Transform ID of the PRF algorithm that MUST be
      used to solve the puzzle.  Readers should refer to the "Transform
      Type 2 - Pseudorandom Function Transform IDs" subregistry on
      [IKEV2-IANA] for the list of possible values.

Top      Up      ToC       Page 27 
   o  Difficulty (1 octet) -- Difficulty level of the puzzle.  Specifies
      the minimum number of trailing zero bits (ZBC) that each of the
      results of PRF must contain.  Value 0 means that the Responder
      doesn't request any specific difficulty level, and the Initiator
      is free to select an appropriate difficulty level on its own (see
      Section 7.1.1.1 for details).

   This notification contains no data.

8.2.  Puzzle Solution Payload

   The solution to the puzzle is returned back to the Responder in a
   dedicated payload, called the PS payload.

                        1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   | Next Payload  |C|  RESERVED   |         Payload Length        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                                                               |
   ~                     Puzzle Solution Data                      ~
   |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   o  Puzzle Solution Data (variable length) -- Contains the solution to
      the puzzle -- four different keys for the selected PRF.  This
      field MUST NOT be empty.  All of the keys MUST have the same size;
      therefore, the size of this field is always a multiple of 4 bytes.
      If the selected PRF accepts only fixed-size keys, then the size of
      each key MUST be of that fixed size.  If the agreed upon PRF
      accepts keys of any size, then the size of each key MUST be
      between 1 octet and the preferred key length of the PRF
      (inclusive).  It is expected that in most cases, the keys will be
      4 (or even less) octets in length; however, it depends on puzzle
      difficulty and on the Initiator's strategy to find solutions, and
      thus the size is not mandated by this specification.  The
      Responder determines the size of each key by dividing the size of
      the Puzzle Solution Data by 4 (the number of keys).  Note that the
      size of Puzzle Solution Data is the size of the Payload (as
      indicated in the Payload Length field) minus 4 -- the size of the
      Payload header.

   The payload type for the PS payload is 54.

Top      Up      ToC       Page 28 
9.  Operational Considerations

   The puzzle difficulty level should be set by balancing the
   requirement to minimize the latency for legitimate Initiators with
   making things difficult for attackers.  A good rule of thumb is
   taking about 1 second to solve the puzzle.  At the time this document
   was written, a typical Initiator or botnet member can perform
   slightly less than a million hashes per second per core, so setting
   the number of zero bits to 20 is a good compromise.  It should be
   noted that mobile Initiators, especially phones, are considerably
   weaker than that.  Implementations should allow administrators to set
   the difficulty level and/or be able to set the difficulty level
   dynamically in response to load.

   Initiators SHOULD set a maximum difficulty level beyond which they
   won't try to solve the puzzle and log or display a failure message to
   the administrator or user.

   Until the widespread adoption of puzzles happens, most Initiators
   will ignore them, as will all attackers.  For puzzles to become a
   really powerful defense measure against DDoS attacks, they must be
   supported by the majority of legitimate clients.

10.  Security Considerations

   Care must be taken when selecting parameters for the puzzles, in
   particular the puzzle difficulty.  If the puzzles are too easy for
   the majority of attackers, then the puzzle mechanism wouldn't be able
   to prevent DoS or DDoS attacks and would only impose an additional
   burden on legitimate Initiators.  On the other hand, if the puzzles
   are too hard for the majority of Initiators, then many legitimate
   users would experience unacceptable delays in IKE SA setup (and
   unacceptable power consumption on mobile devices) that might cause
   them to cancel the connection attempt.  In this case, the resources
   of the Responder are preserved; however, the DoS attack can be
   considered successful.  Thus, a sensible balance should be kept by
   the Responder while choosing the puzzle difficulty -- to defend
   itself and to not over-defend itself.  It is RECOMMENDED that the
   puzzle difficulty be chosen, so that the Responder's load remains
   close to the maximum it can tolerate.  It is also RECOMMENDED to
   dynamically adjust the puzzle difficulty in accordance to the current
   Responder's load.

   If the cookie is generated as suggested in Section 2.6 of [RFC7296],
   then an attacker can use the same SPIi and the same Ni for several
   requests from the same IPi.  This will result in generating the same

Top      Up      ToC       Page 29 
   cookies for these requests until the Responder changes the value of
   its cookie generation secret.  Since the cookies are used as an input
   data for puzzles in the IKE_SA_INIT exchange, generating the same
   cookies allows the attacker to reuse puzzle solutions, thus bypassing
   the proof-of-work requirement.  Note that the attacker can get only
   limited benefit from this situation -- once the half-open SA is
   created by the Responder, all the subsequent initial requests with
   the same IPi and SPIi will be treated as retransmissions and
   discarded by the Responder.  However, once this half-open SA is
   expired and deleted, the attacker can create a new one for free if
   the Responder hasn't changed its cookie generation secret yet.

   The Responder can use various countermeasures to completely eliminate
   or mitigate this scenario.  First, the Responder can change its
   cookie generation secret frequently especially if under attack, as
   recommended in Section 2.6 of [RFC7296].  For example, if the
   Responder keeps two values of the secret (current and previous) and
   the secret lifetime is no more than a half of the current half-open
   SA retention time (see Section 4.1), then the attacker cannot get
   benefit from reusing a puzzle solution.  However, short cookie
   generation secret lifetime could have a negative consequence on weak
   legitimate Initiators, since it could take too long for them to solve
   puzzles, and their solutions would be discarded if the cookie
   generation secret has been already changed few times.

   Another approach for the Responder is to modify the cookie generation
   algorithm in such a way that the generated cookies are always
   different or are repeated only within a short time period.  If the
   Responder includes a timestamp in <AdditionalInfo> as suggested in
   Section 7.1.1.3, then the cookies will repeat only within a short
   time interval equal to timestamp resolution.  Another approach for
   the Responder is to maintain a global counter that is incremented
   every time a cookie is generated and include this counter in
   <AdditionalInfo>.  This will make every cookie unique.

   Implementations MUST use one of the above (or some other)
   countermeasures to completely eliminate or make insignificant the
   possible benefit an attacker can get from reusing puzzle solutions.
   Note that this issue doesn't exist in IKE_AUTH puzzles (Section 7.2)
   since the puzzles in IKE_AUTH are always unique if the Responder
   generates SPIr and Nr randomly in accordance with [RFC7296].

   Solving puzzles requires a lot of CPU usage that increases power
   consumption.  This additional power consumption can negatively affect
   battery-powered Initiators, e.g., mobile phones or some Internet of
   Things (IoT) devices.  If puzzles are too hard, then the required
   additional power consumption may appear to be unacceptable for some
   Initiators.  The Responder SHOULD take this possibility into

Top      Up      ToC       Page 30 
   consideration while choosing the puzzle difficulty and while
   selecting which percentage of Initiators are allowed to reject
   solving puzzles.  See Section 7.1.4 for details.

   If the Initiator uses NULL Authentication [RFC7619], then its
   identity is never verified.  This condition may be used by attackers
   to perform a DoS attack after the IKE SA is established.  Responders
   that allow unauthenticated Initiators to connect must be prepared to
   deal with various kinds of DoS attacks even after the IKE SA is
   created.  See Section 5 for details.

   To prevent amplification attacks, implementations must strictly
   follow the retransmission rules described in Section 2.1 of
   [RFC7296].

11.  IANA Considerations

   This document defines a new payload in the "IKEv2 Payload Types"
   registry:

     54       Puzzle Solution                   PS

   This document also defines a new Notify Message Type in the "IKEv2
   Notify Message Types - Status Types" registry:

     16434    PUZZLE

12.  References

12.1.  Normative References

   [IKEV2-IANA]
              IANA, "Internet Key Exchange Version 2 (IKEv2)
              Parameters",
              <http://www.iana.org/assignments/ikev2-parameters>.

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119,
              DOI 10.17487/RFC2119, March 1997,
              <http://www.rfc-editor.org/info/rfc2119>.

   [RFC5723]  Sheffer, Y. and H. Tschofenig, "Internet Key Exchange
              Protocol Version 2 (IKEv2) Session Resumption", RFC 5723,
              DOI 10.17487/RFC5723, January 2010,
              <http://www.rfc-editor.org/info/rfc5723>.

Top      Up      ToC       Page 31 
   [RFC7296]  Kaufman, C., Hoffman, P., Nir, Y., Eronen, P., and T.
              Kivinen, "Internet Key Exchange Protocol Version 2
              (IKEv2)", STD 79, RFC 7296, DOI 10.17487/RFC7296, October
              2014, <http://www.rfc-editor.org/info/rfc7296>.

   [RFC7383]  Smyslov, V., "Internet Key Exchange Protocol Version 2
              (IKEv2) Message Fragmentation", RFC 7383,
              DOI 10.17487/RFC7383, November 2014,
              <http://www.rfc-editor.org/info/rfc7383>.

12.2.  Informative References

   [BITCOINS] Nakamoto, S., "Bitcoin: A Peer-to-Peer Electronic Cash
              System", October 2008, <https://bitcoin.org/bitcoin.pdf>.

   [RFC7619]  Smyslov, V. and P. Wouters, "The NULL Authentication
              Method in the Internet Key Exchange Protocol Version 2
              (IKEv2)", RFC 7619, DOI 10.17487/RFC7619, August 2015,
              <http://www.rfc-editor.org/info/rfc7619>.

   [RFC7696]  Housley, R., "Guidelines for Cryptographic Algorithm
              Agility and Selecting Mandatory-to-Implement Algorithms",
              BCP 201, RFC 7696, DOI 10.17487/RFC7696, November 2015,
              <http://www.rfc-editor.org/info/rfc7696>.

Acknowledgements

   The authors thank Tero Kivinen, Yaron Sheffer, and Scott Fluhrer for
   their contributions to the design of the protocol.  In particular,
   Tero Kivinen suggested the kind of puzzle where the task is to find a
   solution with a requested number of zero trailing bits.  Yaron
   Sheffer and Scott Fluhrer suggested a way to make puzzle difficulty
   less erratic by solving several weaker puzzles.  The authors also
   thank David Waltermire and Paul Wouters for their careful reviews of
   the document, Graham Bartlett for pointing out the possibility of an
   attack related to "Hash & URL", Stephen Farrell for catching the
   repeated cookie issue, and all others who commented on the document.

Top      Up      ToC       Page 32 
Authors' Addresses

   Yoav Nir
   Check Point Software Technologies Ltd.
   5 Hasolelim st.
   Tel Aviv  6789735
   Israel

   Email: ynir.ietf@gmail.com


   Valery Smyslov
   ELVIS-PLUS
   PO Box 81
   Moscow (Zelenograd)  124460
   Russian Federation

   Phone: +7 495 276 0211
   Email: svan@elvis.ru