tech-invite   World Map     

IETF     RFCs     Groups     SIP     ABNFs    |    3GPP     Specs     Glossaries     Architecture     IMS     UICC    |    search     info

RFC 7298

 
 
 

Babel Hashed Message Authentication Code (HMAC) Cryptographic Authentication

Part 2 of 3, p. 11 to 34
Prev RFC Part       Next RFC Part

 


prevText      Top      Up      ToC       Page 11 
3.  Updates to Protocol Data Structures

3.1.  RxAuthRequired

   RxAuthRequired is a boolean parameter.  Its default value MUST be
   TRUE.  An implementation SHOULD make RxAuthRequired a per-interface
   parameter but MAY make it specific to the whole protocol instance.
   The conceptual purpose of RxAuthRequired is to enable a smooth
   migration from an unauthenticated Babel packet exchange to an
   authenticated Babel packet exchange and back (see Section 7.3).  The
   current value of RxAuthRequired directly affects the receiving
   procedure defined in Section 5.4.  An implementation SHOULD allow the
   operator to change the RxAuthRequired value at runtime or by means of
   a Babel speaker restart.  An implementation MUST allow the operator
   to discover the effective value of RxAuthRequired at runtime or from
   the system documentation.

3.2.  LocalTS

   LocalTS is a 32-bit unsigned integer variable.  It is the TS part of
   a per-interface TS/PC number.  LocalTS is a strictly per-interface
   variable not intended to be changed by the operator.  Its
   initialization is explained in Section 5.1.

3.3.  LocalPC

   LocalPC is a 16-bit unsigned integer variable.  It is the PC part of
   a per-interface TS/PC number.  LocalPC is a strictly per-interface
   variable not intended to be changed by the operator.  Its
   initialization is explained in Section 5.1.

3.4.  MaxDigestsIn

   MaxDigestsIn is an unsigned integer parameter conceptually purposed
   for limiting the amount of CPU time spent processing a received
   authenticated packet.  The receiving procedure performs the most
   CPU-intensive operation -- the HMAC computation -- only at most
   MaxDigestsIn (Section 5.4 item 7) times for a given packet.

   The MaxDigestsIn value MUST be at least 2.  An implementation SHOULD
   make MaxDigestsIn a per-interface parameter but MAY make it specific
   to the whole protocol instance.  An implementation SHOULD allow the
   operator to change the value of MaxDigestsIn at runtime or by means
   of a Babel speaker restart.  An implementation MUST allow the
   operator to discover the effective value of MaxDigestsIn at runtime
   or from the system documentation.

Top      Up      ToC       Page 12 
3.5.  MaxDigestsOut

   MaxDigestsOut is an unsigned integer parameter conceptually purposed
   for limiting the amount of a sent authenticated packet's space spent
   on authentication data.  The sending procedure adds at most
   MaxDigestsOut (Section 5.3 item 5) HMAC results to a given packet.

   The MaxDigestsOut value MUST be at least 2.  An implementation SHOULD
   make MaxDigestsOut a per-interface parameter but MAY make it specific
   to the whole protocol instance.  An implementation SHOULD allow the
   operator to change the value of MaxDigestsOut at runtime or by means
   of a Babel speaker restart, in a safe range.  The maximum safe value
   of MaxDigestsOut is implementation specific (see Section 6.2).  An
   implementation MUST allow the operator to discover the effective
   value of MaxDigestsOut at runtime or from the system documentation.

3.6.  ANM Table

   The ANM (Authentic Neighbours Memory) table resembles the neighbour
   table defined in Section 3.2.3 of [BABEL].  Note that the term
   "neighbour table" means the neighbour table of the original Babel
   specification, and the term "ANM table" means the table defined
   herein.  Indexing of the ANM table is done in exactly the same way as
   indexing of the neighbour table, but its purpose, field set, and
   associated procedures are different.

   The conceptual purpose of the ANM table is to provide longer-term
   replay attack protection than would be possible using the neighbour
   table.  Expiry of an inactive entry in the neighbour table depends on
   the last received Hello Interval of the neighbour and typically
   stands for tens to hundreds of seconds (see Appendixes A and B of
   [BABEL]).  Expiry of an inactive entry in the ANM table depends only
   on the local speaker's configuration.  The ANM table retains (for at
   least the amount of seconds set by the ANM timeout parameter as
   defined in Section 3.7) a copy of the TS/PC number advertised in
   authentic packets by each remote Babel speaker.

Top      Up      ToC       Page 13 
   The ANM table is indexed by pairs of the form (Interface, Source).
   Every table entry consists of the following fields:

   o  Interface

      An implementation-specific reference to the local node's interface
      through which the authentic packet was received.

   o  Source

      The source address of the Babel speaker from which the authentic
      packet was received.

   o  LastTS

      A 32-bit unsigned integer -- the TS part of a remote TS/PC number.

   o  LastPC

      A 16-bit unsigned integer -- the PC part of a remote TS/PC number.

   Each ANM table entry has an associated aging timer, which is reset by
   the receiving procedure (Section 5.4 item 9).  If the timer expires,
   the entry is deleted from the ANM table.

   An implementation SHOULD use persistent memory (NVRAM) to retain the
   contents of the ANM table across restarts of the Babel speaker, but
   only as long as both the Interface field reference and expiry of the
   aging timer remain correct.  An implementation MUST be clear
   regarding if and how persistent memory is used for the ANM table.  An
   implementation SHOULD allow the operator to retrieve the current
   contents of the ANM table at runtime.  An implementation SHOULD allow
   the operator to remove some or all ANM table entries at runtime or by
   means of a Babel speaker restart.

3.7.  ANM Timeout

   ANM timeout is an unsigned integer parameter.  An implementation
   SHOULD make ANM timeout a per-interface parameter but MAY make it
   specific to the whole protocol instance.  ANM timeout is conceptually
   purposed for limiting the maximum age (in seconds) of entries in the
   ANM table that stand for inactive Babel speakers.  The maximum age is
   immediately related to replay attack protection strength.  The
   strongest protection is achieved with the maximum possible value of
   ANM timeout set, but it may not provide the best overall result for
   specific network segments and implementations of this mechanism.

Top      Up      ToC       Page 14 
   Specifically, implementations unable to maintain the local TS/PC
   number strictly increasing across Babel speaker restarts will reuse
   the advertised TS/PC numbers after each restart (see Section 5.1).
   The neighbouring speakers will treat the new packets as replayed and
   discard them until the aging timer of the respective ANM table entry
   expires or the new TS/PC number exceeds the one stored in the entry.

   Another possible, but less probable, case could be an environment
   that uses IPv6 for the exchange of Babel datagrams and that involves
   physical moves of network-interface hardware between Babel speakers.
   Even when performed without restarting the speakers, these physical
   moves would cause random drops of the TS/PC number advertised for a
   given (Interface, Source) index, as viewed by neighbouring speakers,
   since IPv6 link-local addresses are typically derived from interface
   hardware addresses.

   Assuming that in such cases the operators would prefer to use a lower
   ANM timeout value to let the entries expire on their own rather than
   having to manually remove them from the ANM table each time, an
   implementation SHOULD set the default value of ANM timeout to a value
   between 30 and 300 seconds.

   At the same time, network segments may exist with every Babel speaker
   having its advertised TS/PC number strictly increasing over the
   deployed lifetime.  Assuming that in such cases the operators would
   prefer using a much higher ANM timeout value, an implementation
   SHOULD allow the operator to change the value of ANM timeout at
   runtime or by means of a Babel speaker restart.  An implementation
   MUST allow the operator to discover the effective value of ANM
   timeout at runtime or from the system documentation.

3.8.  Configured Security Associations

   A Configured Security Association (CSA) is a data structure
   conceptually purposed for associating authentication keys and hash
   algorithms with Babel interfaces.  All CSAs are managed in finite
   sequences, one sequence per interface (hereafter referred to as
   "interface's sequence of CSAs").  Each interface's sequence of CSAs,
   as an integral part of the Babel speaker configuration, MAY be
   intended for persistent storage as long as this conforms with the
   implementation's key-management policy.  The default state of an
   interface's sequence of CSAs is empty, which has a special meaning of
   no authentication configured for the interface.  The sending
   (Section 5.3 item 1) and the receiving (Section 5.4 item 1)
   procedures address this convention accordingly.

Top      Up      ToC       Page 15 
   A single CSA structure consists of the following fields:

   o  HashAlgo

      An implementation-specific reference to one of the hash algorithms
      supported by this implementation (see Section 2.1).

   o  KeyChain

      A finite sequence of elements (hereafter referred to as "KeyChain
      sequence") representing authentication keys, each element being a
      structure consisting of the following fields:

      *  LocalKeyID

         An unsigned integer of an implementation-specific bit length.

      *  AuthKeyOctets

         A sequence of octets of an arbitrary, known length to be used
         as the authentication key.

      *  KeyStartAccept

         The time that this Babel speaker will begin considering this
         authentication key for accepting packets with authentication
         data.

      *  KeyStartGenerate

         The time that this Babel speaker will begin considering this
         authentication key for generating packet authentication data.

      *  KeyStopGenerate

         The time that this Babel speaker will stop considering this
         authentication key for generating packet authentication data.

      *  KeyStopAccept

         The time that this Babel speaker will stop considering this
         authentication key for accepting packets with authentication
         data.

   Since there is no limit imposed on the number of CSAs per interface,
   but the number of HMAC computations per sent/received packet is
   limited (through MaxDigestsOut and MaxDigestsIn, respectively), it
   may appear that only a fraction of the associated keys and hash

Top      Up      ToC       Page 16 
   algorithms are used in the process.  The ordering of elements within
   a sequence of CSAs and within a KeyChain sequence is important to
   make the association selection process deterministic and transparent.
   Once this ordering is deterministic at the Babel interface level, the
   intermediate data derived by the procedure defined in Section 5.2
   will be deterministically ordered as well.

   An implementation SHOULD allow an operator to set any arbitrary order
   of elements within a given interface's sequence of CSAs and within
   the KeyChain sequence of a given CSA.  Regardless of whether this
   requirement is or isn't met, the implementation MUST provide a means
   to discover the actual element order used.  Whichever order is used
   by an implementation, it MUST be preserved across Babel speaker
   restarts.

   Note that none of the CSA structure fields is constrained to contain
   unique values.  Section 6.4 explains this in more detail.  It is
   possible for the KeyChain sequence to be empty, although this is not
   the intended manner of using CSAs.

   The KeyChain sequence has a direct prototype, which is the "key
   chain" syntax item of some existing router configuration languages.
   If an implementation already implements this syntax item, it is
   suggested that the implementation reuse it, that is, implement a CSA
   syntax item that refers to a key chain item rather than reimplement
   the latter in full.

3.9.  Effective Security Associations

   An Effective Security Association (ESA) is a data structure
   immediately used in sending (Section 5.3) and receiving (Section 5.4)
   procedures.  Its conceptual purpose is to determine a runtime
   interface between those procedures and the deriving procedure defined
   in Section 5.2.  All ESAs are temporary data units managed as
   elements of finite sequences that are not intended for persistent
   storage.  Element ordering within each such finite sequence
   (hereafter referred to as "sequence of ESAs") MUST be preserved as
   long as the sequence exists.

Top      Up      ToC       Page 17 
   A single ESA structure consists of the following fields:

   o  HashAlgo

      An implementation-specific reference to one of the hash algorithms
      supported by this implementation (see Section 2.1).

   o  KeyID

      A 16-bit unsigned integer.

   o  AuthKeyOctets

      A sequence of octets of an arbitrary, known length to be used as
      the authentication key.

   Note that among the protocol data structures introduced by this
   mechanism, the ESA structure is the only one not directly interfaced
   with the system operator (see Figure 1 in Appendix A); it is not
   immediately present in the protocol encoding, either.  However, the
   ESA structure is not just a possible implementation technique but an
   integral part of this specification: the deriving (Section 5.2), the
   sending (Section 5.3), and the receiving (Section 5.4) procedures are
   defined in terms of the ESA structure and its semantics provided
   herein.  The ESA structure is as meaningful for a correct
   implementation as the other protocol data structures.

4.  Updates to Protocol Encoding

4.1.  Justification

   The choice of encoding is very important in the long term.  The
   protocol encoding limits various authentication mechanism designs and
   encodings, which in turn limit future developments of the protocol.

   Considering existing implementations of the Babel protocol instance
   itself and related modules of packet analysers, the current encoding
   of Babel allows for compact and robust decoders.  At the same time,
   this encoding allows for future extensions of Babel by three (not
   excluding each other) principal means as defined in Sections 4.2 and
   4.3 of [BABEL] and further discussed in [BABEL-EXTENSION]:

   a.  A Babel packet consists of a four-octet header followed by a
       packet body, that is, a sequence of TLVs (see Figure 2 in
       Appendix A).  Besides the header and the body, an actual Babel

Top      Up      ToC       Page 18 
       datagram may have an arbitrary amount of trailing data between
       the end of the packet body and the end of the datagram.  An
       instance of the original protocol silently ignores such trailing
       data.

   b.  The packet body uses a binary format allowing for 256 TLV types
       and imposing no requirements on TLV ordering or number of TLVs of
       a given type in a packet.  [BABEL] allocates TLV types 0 through
       10 (see Table 1 in Appendix A), defines the TLV body structure
       for each, and establishes the requirement for a Babel protocol
       instance to ignore any unknown TLV types silently.  This makes it
       possible to examine a packet body (to validate the framing and/or
       to pick particular TLVs for further processing), taking into
       account only the type (to distinguish between a Pad1 TLV and any
       other TLV) and the length of each TLV, regardless of whether any
       additional TLV types are eventually deployed (and if so, how
       many).

   c.  Within each TLV of the packet body, there may be some extra data
       after the expected length of the TLV body.  An instance of the
       original protocol silently ignores any such extra data.  Note
       that any TLV types without the expected length defined (such as
       the PadN TLV) cannot be extended with the extra data.

   Considering each of these three principal extension means for the
   specific purpose of adding authentication data items to each protocol
   packet, the following arguments can be made:

   o  The use of the TLV extra data of some existing TLV type would not
      be a solution, since no particular TLV type is guaranteed to be
      present in a Babel packet.

   o  The use of the TLV extra data could also conflict with future
      developments of the protocol encoding.

   o  Since the packet trailing data is currently unstructured, using it
      would involve defining an encoding structure and associated
      procedures; this would add to the complexity of both specification
      and implementation and would increase exposure to protocol attacks
      such as fuzzing.

   o  A naive use of the packet trailing data would make it unavailable
      to any future extension of Babel.  Since this mechanism is
      possibly not the last extension and since some other extensions
      may allow no other embedding means except the packet trailing
      data, the defined encoding structure would have to enable the
      multiplexing of data items belonging to different extensions.
      Such a definition is out of the scope of this work.

Top      Up      ToC       Page 19 
   o  Deprecating an extension (or only its protocol encoding) that uses
      purely purpose-allocated TLVs is as simple as deprecating the
      TLVs.

   o  The use of purpose-allocated TLVs is transparent for both the
      original protocol and any its future extensions, regardless of the
      embedding technique(s) used by the latter.

   Considering all of the above, this mechanism uses neither the packet
   trailing data nor the TLV extra data but uses two new TLV types:
   type 11 for a TS/PC number and type 12 for an HMAC result (see
   Table 1 in Appendix A).

4.2.  TS/PC TLV

   The purpose of a TS/PC TLV is to store a single TS/PC number.  There
   is exactly one TS/PC TLV in an authenticated Babel packet.

    0                   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
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |   Type = 11   |     Length    |         PacketCounter         |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                           Timestamp                           |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   Fields:

   Type            Set to 11 to indicate a TS/PC TLV.

   Length          The length, in octets, of the body, exclusive of the
                   Type and Length fields.

   PacketCounter   A 16-bit unsigned integer in network byte order --
                   the PC part of a TS/PC number stored in this TLV.

   Timestamp       A 32-bit unsigned integer in network byte order --
                   the TS part of a TS/PC number stored in this TLV.

   Note that the ordering of PacketCounter and Timestamp in the TLV
   structure is the opposite of the ordering of TS and PC in the TS/PC
   number and the 48-bit equivalent (see Section 2.3).

   Considering the expected length and the extra data as mentioned in
   Section 4.3 of [BABEL], the expected length of a TS/PC TLV body is
   unambiguously defined as 6 octets.  The receiving procedure would
   correctly process any TS/PC TLV with body length not less than the
   expected length, ignoring any extra data (Section 5.4 items 3 and 9).

Top      Up      ToC       Page 20 
   The sending procedure produces a TS/PC TLV with body length equal to
   the expected length and the Length field, respectively, set as
   described in Section 5.3 item 3.

   Future Babel extensions (such as sub-TLVs) MAY modify the sending
   procedure to include the extra data after the fixed-size TS/PC TLV
   body defined herein, making adjustments to the Length TLV field, the
   "Body length" packet header field, and output buffer management (as
   explained in Section 6.2) necessary.

4.3.  HMAC TLV

   The purpose of an HMAC TLV is to store a single HMAC result.  To
   assist a receiver in reproducing the HMAC computation, LocalKeyID
   modulo 2^16 of the authentication key is also provided in the TLV.
   There is at least one HMAC TLV in an authenticated Babel packet.

    0                   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
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |   Type = 12   |    Length     |             KeyID             |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |   Digest...
   +-+-+-+-+-+-+-+-+-+-+-+-

   Fields:

   Type            Set to 12 to indicate an HMAC TLV.

   Length          The length, in octets, of the body, exclusive of the
                   Type and Length fields.

   KeyID           A 16-bit unsigned integer in network byte order.

   Digest          A variable-length sequence of octets that is at least
                   16 octets long (see Section 2.2).

   Considering the expected length and the extra data as mentioned in
   Section 4.3 of [BABEL], the expected length of an HMAC TLV body is
   not defined.  The receiving and padding procedures process every
   octet of the Digest field, deriving the field boundary from the
   Length field value (Section 5.4 item 7 and Section 2.2,
   respectively).  The sending procedure produces HMAC TLVs with the
   Length field precisely sizing the Digest field to match the digest
   length of the hash algorithm used (Section 5.3 items 5 and 8).

   The HMAC TLV structure defined herein is final.  Future Babel
   extensions MUST NOT extend it with any extra data.

Top      Up      ToC       Page 21 
5.  Updates to Protocol Operation

5.1.  Per-Interface TS/PC Number Updates

   The LocalTS and LocalPC interface-specific variables constitute the
   TS/PC number of a Babel interface.  This number is advertised in the
   TS/PC TLV of authenticated Babel packets sent from that interface.
   There is only one property that is mandatory for the advertised TS/PC
   number: its 48-bit equivalent (see Section 2.3) MUST be strictly
   increasing within the scope of a given interface of a Babel speaker
   as long as the protocol instance is continuously operating.  This
   property, combined with ANM tables of neighbouring Babel speakers,
   provides them with the most basic replay attack protection.

   Initialization and increment are two principal updates performed on
   an interface TS/PC number.  The initialization is performed when a
   new interface becomes a part of a Babel protocol instance.  The
   increment is performed by the sending procedure (Section 5.3 item 2)
   before advertising the TS/PC number in a TS/PC TLV.

   Depending on the particular implementation method of these two
   updates, the advertised TS/PC number may possess additional
   properties that improve the replay attack protection strength.  This
   includes, but is not limited to, the methods below.

   a.  The most straightforward implementation would use LocalTS as a
       plain wrap counter, defining the updates as follows:

       initialization  Set LocalPC to 0, and set LocalTS to 0.

       increment       Increment LocalPC by 1.  If LocalPC wraps
                       (0xFFFF + 1 = 0x0000), increment LocalTS by 1.

       In this case, the advertised TS/PC numbers would be reused after
       each Babel protocol instance restart, making neighbouring
       speakers reject authenticated packets until the respective ANM
       table entries expire or the new TS/PC number exceeds the old (see
       Sections 3.6 and 3.7).

Top      Up      ToC       Page 22 
   b.  A more advanced implementation could make use of any 32-bit
       unsigned integer timestamp (number of time units since an
       arbitrary epoch), such as the UNIX timestamp, if the timestamp
       itself spans a reasonable time range and is guaranteed against a
       decrease (such as one resulting from network time use).  The
       updates would be defined as follows:

       initialization  Set LocalPC to 0, and set LocalTS to 0.

       increment       If the current timestamp is greater than LocalTS,
                       set LocalTS to the current timestamp and LocalPC
                       to 0, then consider the update complete.
                       Otherwise, increment LocalPC by 1, and if LocalPC
                       wraps, increment LocalTS by 1.

       In this case, the advertised TS/PC number would remain unique
       across the speaker's deployed lifetime without the need for any
       persistent storage.  However, a suitable timestamp source is not
       available in every implementation case.

   c.  Another advanced implementation could use LocalTS in a way
       similar to the "wrap/boot count" suggested in Section 4.1 of
       [OSPF3-AUTH-BIS], defining the updates as follows:

       initialization  Set LocalPC to 0.  If there is a TS value stored
                       in NVRAM for the current interface, set LocalTS
                       to the stored TS value, then increment the stored
                       TS value by 1.  Otherwise, set LocalTS to 0, and
                       set the stored TS value to 1.

       increment       Increment LocalPC by 1.  If LocalPC wraps, set
                       LocalTS to the TS value stored in NVRAM for the
                       current interface, then increment the stored TS
                       value by 1.

       In this case, the advertised TS/PC number would also remain
       unique across the speaker's deployed lifetime, relying on NVRAM
       for storing multiple TS numbers, one per interface.

   As long as the TS/PC number retains its mandatory property stated
   above, it is up to the implementor to determine which methods of TS/
   PC number updates are available and whether the operator can
   configure the method per interface and/or at runtime.  However, an
   implementation MUST disclose the essence of each update method it
   includes, in a comprehensible form such as natural language
   description, pseudocode, or source code.  An implementation MUST
   allow the operator to discover which update method is effective for
   any given interface, either at runtime or from the system

Top      Up      ToC       Page 23 
   documentation.  These requirements are necessary to enable the
   optimal (see Section 3.7) management of ANM timeout in a network
   segment.

   Note that wrapping (0xFFFFFFFF + 1 = 0x00000000) of LastTS is
   unlikely, but possible, causing the advertised TS/PC number to be
   reused.  Resolving this situation requires replacing all
   authentication keys of the involved interface.  In addition to that,
   if the wrap was caused by a timestamp reaching its end of epoch,
   using this mechanism will be impossible for the involved interface
   until some different timestamp or update implementation method is
   used.

5.2.  Deriving ESAs from CSAs

   Neither receiving nor sending procedures work with the contents of an
   interface's sequence of CSAs directly; both (Section 5.4 item 4 and
   Section 5.3 item 4, respectively) derive a sequence of ESAs from the
   sequence of CSAs and use the derived sequence (see Figure 1 in
   Appendix A).  There are two main goals achieved through this
   indirection:

   o  Elimination of expired authentication keys and deduplication of
      security associations.  This is done as early as possible to keep
      subsequent procedures focused on their respective tasks.

   o  Maintenance of particular ordering within the derived sequence of
      ESAs.  The ordering deterministically depends on the ordering
      within the interface's sequence of CSAs and the ordering within
      the KeyChain sequence of each CSA.  The particular correlation
      maintained by this procedure implements a concept of fair
      (independent of the number of keys contained by each) competition
      between CSAs.

   The deriving procedure uses the following input arguments:

   o  input sequence of CSAs

   o  direction (sending or receiving)

   o  current time (CT)

Top      Up      ToC       Page 24 
   The processing of input arguments begins with an empty output
   sequence of ESAs and consists of the following steps:

   1.  Make a temporary copy of the input sequence of CSAs.

   2.  Remove all expired authentication keys from each KeyChain
       sequence of the copy, that is, any keys such that:

       *  for receiving: KeyStartAccept is greater than CT or
          KeyStopAccept is less than CT

       *  for sending: KeyStartGenerate is greater than CT or
          KeyStopGenerate is less than CT

       Note well that there are no special exceptions.  Remove all
       expired keys, even if there are no keys left after that (see
       Section 7.4).

   3.  Use the copy to populate the output sequence of ESAs as follows:

       3.1.  When the KeyChain sequence of the first CSA contains at
             least one key, use its first key to produce an ESA with
             fields set as follows:

             HashAlgo       Set to HashAlgo of the current CSA.

             KeyID          Set to LocalKeyID modulo 2^16 of the current
                            key of the current CSA.

             AuthKeyOctets  Set to AuthKeyOctets of the current key of
                            the current CSA.

             Append this ESA to the end of the output sequence.

       3.2.  When the KeyChain sequence of the second CSA contains at
             least one key, use its first key the same way, and so forth
             until all first keys of the copy are processed.

       3.3.  When the KeyChain sequence of the first CSA contains at
             least two keys, use its second key the same way.

       3.4.  When the KeyChain sequence of the second CSA contains at
             least two keys, use its second key the same way, and so
             forth until all second keys of the copy are processed.

       3.5.  ...and so forth, until all keys of all CSAs of the copy are
             processed, exactly once each.

Top      Up      ToC       Page 25 
       In the description above, the ordinals ("first", "second", and so
       on) with regard to keys stand for an element position after the
       removal of expired keys, not before.  For example, if a KeyChain
       sequence was { Ka, Kb, Kc, Kd } before the removal and became
       { Ka, Kd } after, then Ka would be the "first" element and Kd
       would be the "second".

   4.  Deduplicate the ESAs in the output sequence; that is, wherever
       two or more ESAs exist that share the same (HashAlgo, KeyID,
       AuthKeyOctets) triplet value, remove all of these ESAs except the
       one closest to the beginning of the sequence.

   The resulting sequence will contain zero or more unique ESAs, ordered
   in a way deterministically correlated with the ordering of CSAs
   within the original input sequence of CSAs and the ordering of keys
   within each KeyChain sequence.  This ordering maximizes the
   probability of having an equal amount of keys per original CSA in any
   N first elements of the resulting sequence.  Possible optimizations
   of this deriving procedure are outlined in Section 6.3.

5.3.  Updates to Packet Sending

   Perform the following authentication-specific processing after the
   instance of the original protocol considers an outgoing Babel packet
   ready for sending, but before the packet is actually sent (see
   Figure 1 in Appendix A).  After that, send the packet, regardless of
   whether the authentication-specific processing modified the outgoing
   packet or left it intact.

   1.  If the current outgoing interface's sequence of CSAs is empty,
       finish authentication-specific processing and consider the packet
       ready for sending.

   2.  Increment the TS/PC number of the current outgoing interface, as
       explained in Section 5.1.

   3.  Add to the packet body (see the note at the end of this section)
       a TS/PC TLV with fields set as follows:

       Type            Set to 11.

       Length          Set to 6.

       PacketCounter   Set to the current value of the LocalPC variable
                       of the current outgoing interface.

Top      Up      ToC       Page 26 
       Timestamp       Set to the current value of the LocalTS variable
                       of the current outgoing interface.

       Note that the current step may involve byte order conversion.

   4.  Derive a sequence of ESAs, using the procedure defined in
       Section 5.2, with the current interface's sequence of CSAs as the
       input sequence of CSAs, the current time as CT, and "sending" as
       the direction.  Proceed to the next step even if the derived
       sequence is empty.

   5.  Iterate over the derived sequence, using its ordering.  For each
       ESA, add to the packet body (see the note at the end of this
       section) an HMAC TLV with fields set as follows:

       Type     Set to 12.

       Length   Set to 2 plus the digest length of HashAlgo of the
                current ESA.

       KeyID    Set to KeyID of the current ESA.

       Digest   Size exactly equal to the digest length of HashAlgo of
                the current ESA.  Pad (see Section 2.2), using the
                source address of the current packet (see Section 6.1).

       As soon as there are MaxDigestsOut HMAC TLVs added to the current
       packet body, immediately proceed to the next step.

       Note that the current step may involve byte order conversion.

   6.  Increment the "Body length" field value of the current packet
       header by the total length of TS/PC and HMAC TLVs appended to the
       current packet body so far.

       Note that the current step may involve byte order conversion.

   7.  Make a temporary copy of the current packet.

Top      Up      ToC       Page 27 
   8.  Iterate over the derived sequence again, using the same order and
       number of elements.  For each ESA (and, respectively, for each
       HMAC TLV recently appended to the current packet body), compute
       an HMAC result (see Section 2.4), using the temporary copy (not
       the original packet) as Text, HashAlgo of the current ESA as H,
       and AuthKeyOctets of the current ESA as K.  Write the HMAC result
       to the Digest field of the current HMAC TLV (see Table 4 in
       Appendix A) of the current packet (not the copy).

   9.  After this point, allow no more changes to the current packet
       header and body, and consider it ready for sending.

   Note that even when the derived sequence of ESAs is empty, the packet
   is sent anyway, with only a TS/PC TLV appended to its body.  Although
   such a packet would not be authenticated, the presence of the sole
   TS/PC TLV would indicate authentication key exhaustion to operators
   of neighbouring Babel speakers.  See also Section 7.4.

   Also note that it is possible to place the authentication-specific
   TLVs in the packet's sequence of TLVs in a number of different valid
   ways so long as there is exactly one TS/PC TLV in the sequence and
   the ordering of HMAC TLVs relative to each other, as produced in
   step 5 above, is preserved.

   For example, see Figure 2 in Appendix A.  The diagrams represent a
   Babel packet without (D1) and with (D2, D3, D4) authentication-
   specific TLVs.  The optional trailing data block that is present in
   D1 is preserved in D2, D3, and D4.  Indexing (1, 2, ..., n) of the
   HMAC TLVs means the order in which the sending procedure produced
   them (and, respectively, the HMAC results).  In D2, the added TLVs
   are appended: the previously existing TLVs are followed by the TS/PC
   TLV, which is followed by the HMAC TLVs.  In D3, the added TLVs are
   prepended: the TS/PC TLV is the first and is followed by the HMAC
   TLVs, which are followed by the previously existing TLVs.  In D4, the
   added TLVs are intermixed with the previously existing TLVs and the
   TS/PC TLV is placed after the HMAC TLVs.  All three packets meet the
   requirements above.

   Implementors SHOULD use appending (D2) for adding the authentication-
   specific TLVs to the sequence; this is expected to result in more
   straightforward implementation and troubleshooting in most use cases.

Top      Up      ToC       Page 28 
5.4.  Updates to Packet Receiving

   Perform the following authentication-specific processing after an
   incoming Babel packet is received from the local network stack but
   before it is acted upon by the Babel protocol instance (see Figure 1
   in Appendix A).  The final action conceptually depends not only upon
   the result of the authentication-specific processing but also on the
   current value of the RxAuthRequired parameter.  Immediately after any
   processing step below accepts or refuses the packet, either deliver
   the packet to the instance of the original protocol (when the packet
   is accepted or RxAuthRequired is FALSE) or discard it (when the
   packet is refused and RxAuthRequired is TRUE).

   1.   If the current incoming interface's sequence of CSAs is empty,
        accept the packet.

   2.   If the current packet does not contain exactly one TS/PC TLV,
        refuse it.

   3.   Perform a lookup in the ANM table for an entry having Interface
        equal to the current incoming interface and Source equal to the
        source address of the current packet.  If such an entry does not
        exist, immediately proceed to the next step.  Otherwise, compare
        the entry's LastTS and LastPC field values with the Timestamp
        and PacketCounter values, respectively, of the TS/PC TLV of the
        packet.  That is, refuse the packet if at least one of the
        following two conditions is true:

        *  Timestamp is less than LastTS

        *  Timestamp is equal to LastTS and PacketCounter is not greater
           than LastPC

        Note that the current step may involve byte order conversion.

   4.   Derive a sequence of ESAs, using the procedure defined in
        Section 5.2, with the current interface's sequence of CSAs as
        the input sequence of CSAs, current time as CT, and "receiving"
        as the direction.  If the derived sequence is empty, refuse the
        packet.

   5.   Make a temporary copy of the current packet.

   6.   Pad (see Section 2.2) every HMAC TLV present in the temporary
        copy (not the original packet), using the source address of the
        original packet.

Top      Up      ToC       Page 29 
   7.   Iterate over all the HMAC TLVs of the original input packet (not
        the copy), using their order of appearance in the packet.  For
        each HMAC TLV, look up all ESAs in the derived sequence such
        that 2 plus the digest length of HashAlgo of the ESA is equal to
        Length of the TLV and KeyID of the ESA is equal to the value of
        KeyID of the TLV.  Iterate over these ESAs in the relative order
        of their appearance on the full sequence of ESAs.  Note that
        nesting the iterations the opposite way (over ESAs, then over
        HMAC TLVs) would be wrong.

        For each of these ESAs, compute an HMAC result (see
        Section 2.4), using the temporary copy (not the original packet)
        as Text, HashAlgo of the current ESA as H, and AuthKeyOctets of
        the current ESA as K.  If the current HMAC result exactly
        matches the contents of the Digest field of the current HMAC
        TLV, immediately proceed to the next step.  Otherwise, if the
        number of HMAC computations done for the current packet so far
        is equal to MaxDigestsIn, immediately proceed to the next step.
        Otherwise, follow the normal order of iterations.

        Note that the current step may involve byte order conversion.

   8.   Refuse the input packet unless there was a matching HMAC result
        in the previous step.

   9.   Modify the ANM table, using the same index as for the entry
        lookup above, to contain an entry with LastTS set to the value
        of Timestamp and LastPC set to the value of PacketCounter fields
        of the TS/PC TLV of the current packet.  That is, either add a
        new ANM table entry or update the existing one, depending on the
        result of the entry lookup above.  Reset the entry's aging timer
        to the current value of ANM timeout.

        Note that the current step may involve byte order conversion.

   10.  Accept the input packet.

   Before performing the authentication-specific processing above, an
   implementation SHOULD perform those basic procedures of the original
   protocol that don't take any protocol actions on the contents of the
   packet but that will discard the packet if it is not sufficiently
   well formed for further processing.  Although the exact composition
   of such procedures belongs to the scope of the original protocol, it
   seems reasonable to state that a packet SHOULD be discarded early,
   regardless of whether any authentication-specific processing is due,
   unless its source address conforms to Section 3.1 of [BABEL] and is
   not the receiving speaker's own address (see item (e) of Section 8).

Top      Up      ToC       Page 30 
   Note that RxAuthRequired affects only the final action but not the
   defined flow of authentication-specific processing.  The purpose of
   this is to preserve authentication-specific processing feedback (such
   as log messages and event-counter updates), even with RxAuthRequired
   set to FALSE.  This allows an operator to predict the effect of
   changing RxAuthRequired from FALSE to TRUE during a migration
   scenario (Section 7.3) implementation.

5.5.  Authentication-Specific Statistics Maintenance

   A Babel speaker implementing this mechanism SHOULD maintain a set of
   counters for the following events, per protocol instance and per
   interface:

   a.  Sending an unauthenticated Babel packet through an interface
       having an empty sequence of CSAs (Section 5.3 item 1).

   b.  Sending an unauthenticated Babel packet with a TS/PC TLV but
       without any HMAC TLVs, due to an empty derived sequence of ESAs
       (Section 5.3 item 4).

   c.  Sending an authenticated Babel packet containing both TS/PC and
       HMAC TLVs (Section 5.3 item 9).

   d.  Accepting a Babel packet received through an interface having an
       empty sequence of CSAs (Section 5.4 item 1).

   e.  Refusing a received Babel packet due to an empty derived sequence
       of ESAs (Section 5.4 item 4).

   f.  Refusing a received Babel packet that does not contain exactly
       one TS/PC TLV (Section 5.4 item 2).

   g.  Refusing a received Babel packet due to the TS/PC TLV failing the
       ANM table check (Section 5.4 item 3).  With possible future
       extensions in mind, in implementations of this mechanism, this
       event SHOULD leave out some small amount, per current (Interface,
       Source, LastTS, LastPC) tuple, of the packets refused due to the
       Timestamp value being equal to LastTS and the PacketCounter value
       being equal to LastPC.

   h.  Refusing a received Babel packet missing any HMAC TLVs
       (Section 5.4 item 8).

   i.  Refusing a received Babel packet due to none of the processed
       HMAC TLVs passing the ESA check (Section 5.4 item 8).

Top      Up      ToC       Page 31 
   j.  Accepting a received Babel packet having both TS/PC and HMAC TLVs
       (Section 5.4 item 10).

   k.  Delivery of a refused packet to the instance of the original
       protocol due to the RxAuthRequired parameter being set to FALSE.

   Note that the terms "accepting" and "refusing" are used in the sense
   of the receiving procedure; that is, "accepting" does not mean a
   packet delivered to the instance of the original protocol purely
   because the RxAuthRequired parameter is set to FALSE.  Event-counter
   readings SHOULD be available to the operator at runtime.

6.  Implementation Notes

6.1.  Source Address Selection for Sending

   Section 3.1 of [BABEL] allows for the exchange of protocol datagrams,
   using IPv4, IPv6, or both.  The source address of the datagram is a
   unicast (link-local in the case of IPv6) address.  Within an address
   family used by a Babel speaker, there may be more than one address
   eligible for the exchange and assigned to the same network interface.
   The original specification considers this case out of scope and
   leaves it up to the speaker's network stack to select one particular
   address as the datagram source address, but the sending procedure
   requires (Section 5.3 item 5) exact knowledge of the packet source
   address for proper padding of HMAC TLVs.

   As long as a network interface has more than one address eligible for
   the exchange within the same address family, the Babel speaker SHOULD
   internally choose one of those addresses for Babel packet sending
   purposes and then indicate this choice to both the sending procedure
   and the network stack (see Figure 1 in Appendix A).  Wherever this
   requirement cannot be met, this limitation MUST be clearly stated in
   the system documentation to allow an operator to plan network address
   management accordingly.

6.2.  Output Buffer Management

   An instance of the original protocol will buffer produced TLVs until
   the buffer becomes full or a delay timer has expired.  This is
   performed independently for each Babel interface, with each buffer
   sized according to the interface MTU (see Sections 3.1 and 4 of
   [BABEL]).

Top      Up      ToC       Page 32 
   Since TS/PC TLVs, HMAC TLVs, and any other TLVs -- and most likely
   the TLVs of the original protocol -- share the same packet space (see
   Figure 2 in Appendix A) and, respectively, the same buffer space, a
   particular portion of each interface buffer needs to be reserved for
   one TS/PC TLV and up to MaxDigestsOut HMAC TLVs.  The amount (R) of
   this reserved buffer space is calculated as follows:

                    R = St + MaxDigestsOut * Sh
                    R = 8  + MaxDigestsOut * (4 + Lmax)

   St      The size of a TS/PC TLV.

   Sh      The size of an HMAC TLV.

   Lmax    The maximum possible digest length in octets for a particular
           interface.  It SHOULD be calculated based on the particular
           interface's sequence of CSAs but MAY be taken as the maximum
           digest length supported by a particular implementation.

   An implementation allowing for a per-interface value of MaxDigestsOut
   or Lmax has to account for a different value of R across different
   interfaces, even interfaces having the same MTU.  An implementation
   allowing for a runtime change to the value of R (due to MaxDigestsOut
   or Lmax) has to take care of the TLVs already buffered by the time of
   the change -- specifically, when the value of R increases.

   The maximum safe value of the MaxDigestsOut parameter depends on the
   interface MTU and maximum digest length used.  In general, at least
   200-300 octets of a Babel packet should always be available to data
   other than TS/PC and HMAC TLVs.  An implementation following the
   requirements of Section 4 of [BABEL] would send packets of 512 octets
   or larger.  If, for example, the maximum digest length is 64 octets
   and the MaxDigestsOut value is 4, the value of R would be 280,
   leaving less than half of a 512-octet packet for any other TLVs.  As
   long as the interface MTU is larger or the digest length is smaller,
   higher values of MaxDigestsOut can be used safely.

6.3.  Optimizations of Deriving Procedure for ESAs

   The following optimizations of the deriving procedure for ESAs can
   reduce the amount of CPU time consumed by authentication-specific
   processing, preserving an implementation's effective behaviour.

   a.  The most straightforward implementation would treat the deriving
       procedure as a per-packet action, but since the procedure is
       deterministic (its output depends on its input only), it is
       possible to significantly reduce the number of times the
       procedure is performed.

Top      Up      ToC       Page 33 
       The procedure would obviously return the same result for the same
       input arguments (sequence of CSAs, direction, CT) values.
       However, it is possible to predict when the result will remain
       the same, even for a different input.  That is, when the input
       sequence of CSAs and the direction both remain the same but CT
       changes, the result will remain the same as long as CT's order on
       the time axis (relative to all critical points of the sequence of
       CSAs) remains unchanged.  Here, the critical points are
       KeyStartAccept and KeyStopAccept (for the receiving direction),
       and KeyStartGenerate and KeyStopGenerate (for the sending
       direction), of all keys of all CSAs of the input sequence.  In
       other words, in this case the result will remain the same as long
       as (1) none of the active keys expire and (2) none of the
       inactive keys enter into operation.

       An implementation optimized in this way would perform the full
       deriving procedure for a given (interface, direction) pair only
       after an operator's change to the interface's sequence of CSAs or
       after reaching one of the critical points mentioned above.

   b.  Considering that the sending procedure iterates over at most
       MaxDigestsOut elements of the derived sequence of ESAs
       (Section 5.3 item 5), there would be little sense, in the case of
       the sending direction, in returning more than MaxDigestsOut ESAs
       in the derived sequence.  Note that a similar optimization would
       be relatively difficult in the case of the receiving direction,
       since the number of ESAs actually used in examining a particular
       received packet (not to be confused with the number of HMAC
       computations) depends on additional factors besides just
       MaxDigestsIn.

6.4.  Duplication of Security Associations

   This specification defines three data structures as finite sequences:
   a KeyChain sequence, an interface's sequence of CSAs, and a sequence
   of ESAs.  There are associated semantics to take into account during
   implementation, in that the same element can appear multiple times at
   different positions of the sequence.  In particular, none of the CSA
   structure fields (including HashAlgo, LocalKeyID, and AuthKeyOctets),
   alone or in a combination, have to be unique within a given CSA, or
   within a given sequence of CSAs, or within all sequences of CSAs of a
   Babel speaker.

   In the CSA space defined in this way, for any two authentication
   keys, their one field (in)equality would not imply another field
   (in)equality.  In other words, it is acceptable to have more than one
   authentication key with the same LocalKeyID or the same
   AuthKeyOctets, or both at a time.  It is a conscious design decision

Top      Up      ToC       Page 34 
   that CSA semantics allow for duplication of security associations.
   Consequently, ESA semantics allow for duplication of intermediate
   ESAs in the sequence until the explicit deduplication (Section 5.2
   item 4).

   One of the intentions of this is to define the security association
   management in a way that allows the addressing of some specifics of
   Babel as a mesh routing protocol.  For example, a system operator
   configuring a Babel speaker to participate in more than one
   administrative domain could find each domain using its own
   authentication key (AuthKeyOctets) under the same LocalKeyID value,
   e.g., a "well-known" or "default" value like 0 or 1.  Since
   reconfiguring the domains to use distinct LocalKeyID values isn't
   always feasible, the multi-domain Babel speaker, using several
   distinct authentication keys under the same LocalKeyID, would make a
   valid use case for such duplication.

   Furthermore, if the operator decided in this situation to migrate one
   of the domains to a different LocalKeyID value in a seamless way, the
   respective Babel speakers would use the same authentication key
   (AuthKeyOctets) under two different LocalKeyID values for the time of
   the transition (see also item (f) of Section 8).  This would make a
   similar use case.

   Another intention of this design decision is to decouple security
   association management from authentication key management as much as
   possible, so that the latter, be it manual keying or a key-management
   protocol, could be designed and implemented independently (as the
   respective reasoning made in Section 3.1 of [RIP2-AUTH] still
   applies).  This way, the additional key-management constraints, if
   any, would remain out of the scope of this authentication mechanism.
   A similar thinking justifies the LocalKeyID field having a bit length
   in an ESA structure definition, but not in that of the CSA.



(page 34 continued on part 3)

Next RFC Part