IPng Working Group                                         Matt Crawford
Internet Draft                                                  Fermilab
                                                              Bob Hinden
                                                        Ipsilon Networks
                                                          March 26, 1997

                        Router Renumbering for IPv6

Status of this Memo

    This document is an Internet Draft.  Internet Drafts are working
    documents of the Internet Engineering Task Force (IETF), its Areas,
    and its Working Groups.  Note that other groups may also distribute
    working documents as Internet Drafts.

    Internet Drafts are draft documents valid for a maximum of six
    months.  Internet Drafts may be updated, replaced, or obsoleted by
    other documents at any time.  It is not appropriate to use Internet
    Drafts as reference material or to cite them other than as a
    "working draft" or "work in progress."

    To learn the current status of any Internet-Draft, please check the
    "1id-abstracts.txt" listing contained in the Internet Drafts Shadow
    Directories on ds.internic.net (US East Coast), nic.nordu.net
    (Europe), ftp.isi.edu (US  West  Coast), or munnari.oz.au (Pacific

    Distribution of this memo is unlimited.

1.  Abstract

    IPv6 Neighbor Discovery [ND] and Address Autoconfiguration [AA]
    conveniently make initial assignments of address prefixes to hosts.
    Aside from the problem of connection survival across a renumbering
    event, these two mechanisms also simplify the reconfiguration of
    hosts when the set of valid prefixes changes.

    This document defines a mechanism called Router Renumbering ("RR")
    which allows address prefixes on routers to be configured and
    reconfigured almost as easily as the combination of Neighbor
    Discovery and Address Autoconfiguration works for hosts.  It
    provides a means for a network manager to make updates to the
    prefixes used by and advertised by IPv6 routers throughout a site.

Expires September 26, 1997      Crawford                        [Page 1]

Internet Draft             Router Renumbering             March 26, 1997

2.  Functional Overview

    Router Renumbering packets contain a sequence of Prefix Control
    Operations (PCOs).  Each PCO specifies an operation, a Match-Prefix,
    and zero or more Use-Prefixes.  A router processes each PCO in
    sequence, checking each of its interfaces for an address or prefix
    which matches the match-prefix.  For every interface on which a
    match is found, the operation is applied.  The operation is one of
    ADD, CHANGE, or SET-GLOBAL to instruct the router to respectively
    add the Use-Prefixes to the set of configured prefixes, remove the
    prefix which matched the Match-Prefix and replace it with the Use-
    Prefixes, or replace all global-scope prefixes with the Use-
    Prefixes.  If the set of Use-Prefixes in the PCO is empty, the ADD
    operation does nothing and the other two reduce to deletions.

    Additional information for each use-prefix is included in the Prefix
    Control Operation: the valid and preferred lifetimes to be included
    in Router Advertisement Prefix Information Options [ND], and either
    the L and A flags for the same option, or an indication that they
    are to be copied from the prefix that matched the match-prefix.

    It is possible to instruct routers to create new prefixes by
    combining the use-prefixes in a PCO with some portion of the
    existing prefix which matched the match-prefix.  This simplifies
    certain operations which are expected to be among the most common.
    For every use-prefix, the PCO specifies a number of bits which
    should be copied from the address or prefix which matched the
    match-prefix and appended to the use-prefix prior to configuring the
    new prefix on the interface.  The copied bits are zero or more bits
    from the positions immediately beyond the length of the use-prefix.
    If subnetting information is in the same portion of of the old and
    new prefixes, this synthesis allows a single Prefix Control
    Operation to define a new global prefix on every router on a site,
    while preserving the subnetting structure.

    Because of the power of the Router Renumbering mechanism, each RR
    includes a sequence number and an authenticator to guard against
    replays.  Each RR operation is idempotent and so a given message may
    be retransmitted for improved reliability, as long as its sequence
    number is current, without concern that it may be processed multiple

    Possibly a site's network manager will want to perform more
    renumbering, or exercise more detailed control, than can be
    expressed in a single Router Renumbering packet on the available
    media.  The RR mechanism is most powerful when RR packets are
    multicast, so IP fragmentation is undesirable.  For these reasons,
    each RR packet contains a "segment number".  All RR packets which

Expires September 26, 1997      Crawford                        [Page 2]

Internet Draft             Router Renumbering             March 26, 1997

    have a sequence number equal to the highest value seen, and which
    pass the authentication check, are equally valid and must be
    processed.  However, a router may keep track of the segment numbers
    of RR messages already processed and avoid reprocessing a message
    whose sequence number and segment number match a previously
    processed message.

    There is also a "Dry Run" indicator which indicates that all routers
    should process the RR message, but not perform any reconfiguration.
    It is expected that the effect of an RR message, or the simulated
    effect of a Dry Run RR message, will be reported to network
    management by means outside the scope of this document.

3.  Definitions

3.1.  Requirements

    Throughout this document, the words that are used to define the
    significance of the particular requirements are capitalized.  These
    words are:

       This word or the adjective "REQUIRED" means that the item is an
       absolute requirement of this specification.

       This phrase means the item is an absolute prohibition of this

       This word or the adjective "RECOMMENDED" means that there may
       exist valid reasons in particular circumstances to ignore this
       item, but the full implications should be understood and the case
       carefully weighed before choosing a different course.

       This phrase means that there may exist valid reasons in
       particular circumstances when the listed behavior is acceptable
       or even useful, but the full implications should be understood
       and the case carefully weighed before implementing any behavior
       described with this label.

       This word or the adjective "OPTIONAL" means that this item is
       truly optional.  One vendor may choose to include the item
       because a particular marketplace requires it or because it

Expires September 26, 1997      Crawford                        [Page 3]

Internet Draft             Router Renumbering             March 26, 1997

       enhances the product, for example, another vendor may omit the
       same item.

3.2.  Terminology

       This term always refers to a 128-bit IPv6 address [AARCH].  When
       referring to bits within an address, they are numbered from 0 to
       127, with bit 0 being the first bit of the Format Prefix.

       A prefix can be understood as an address plus a length, the
       latter being an integer in the range 0 to 128 indicating how many
       leading bits are significant.  When referring to bits within a
       prefix, they are numbered in the same way as the bits of an
       address.  For example, the significant bits of a prefix whose
       length is L are the bits numbered 0 through L-1, inclusive.

       An address A "matches" a prefix P whose length is L, if the first
       L bits of A are identical with the first L bits of P.  (Every
       address matches a prefix of length 0.)  A prefix P1 with length
       L1 matches a prefix P2 of length L2 if L1 >=3D L2 and the first L2=

       bits of P1 and P2 are identical.

    Prefix Control Operation, Match-Prefix, Use-Prefix
       These are defined section 2.

    Matched Prefix
       The existing prefix or address which matched a Match-Prefix.

    New Prefix
       A prefix constructed from a Use-Prefix, possibly including some
       of the Matched-Prefix.

    Recorded Sequence Number
       The highest sequence number found in a valid, authenticated
       message with a given key MUST be recorded in non-volatile storage
       along with that key.

3.3.  Authentication Algorithms

    All implementations MUST support Keyed MD5 [MD5] for authentication.
    Additional algorithms MAY be supported.

Expires September 26, 1997      Crawford                        [Page 4]

Internet Draft             Router Renumbering             March 26, 1997

4.  Message Format

     /                                                               /
     |                IPv6 header, extension headers                 |
     /                                                               /
     |                 ICMPv6 RR Header (16 octets)                  |
     /                                                               /
     /                                                               /
     |             Zero or more PCOs (variable length)               |
     /                                                               /
     /                                                               /
     |           Authentication Data (16 octets for MD5)             |
     /                                                               /

    Router Renumbering messages are carried in ICMP packets with Type =3D=

    TBA.  The RR message consists of

        An RR header, containing the sequence and segment numbers and
        information about the authentication key and the location and
        length of the authentication data within the packet;

        A sequence of Prefix Control Operations, each of variable

        The authentication data, with length dependent on the
        authentication type.  For Keyed MD-5, 16 octets.

    All fields marked "unused" MUST be set to zero on generation of an
    RR message.  During processing of the message they MUST be included
    in the authentication check, but otherwise ignored.

    All implementations which generate Router Renumbering messages MUST
    support sending them to the All Routers multicast address with Link
    Local and Site Local scopes, and to unicast addresses of site local
    and link local formats.  All routers MUST be capable of receiving RR
    messages sent to those multicast addresses and to any of their link
    local and site local unicast addresses.  Implementations MAY support
    sending and receiving RR messages addressed to other unicast

Expires September 26, 1997      Crawford                        [Page 5]

Internet Draft             Router Renumbering             March 26, 1997

4.1.  Router Renumbering Header

      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      |     Code      |          Checksum             |
     |         SegmentNumber         |             KeyID             |
     |           AuthLen             |          AuthOffset           |
     |                        SequenceNumber                         |


    Type        TBA, the ICMP type code assigned to Router Renumbering

    Code        0 for a normal RR message
                1 to indicate a "Dry Run" message.  If set to 1, the
                operations specified in this message SHOULD be
                simulated, but MUST NOT be not carried out.

                An unsigned 15-bit field which enumerates different
                valid RR messages having the same SequenceNumber and

    KeyID       An unsigned 16-bit field that identifies the key used to
                create and verify the Authentication Data for this RR
                message.  If multiple authentication algorithms are
                supported by the implementation, the choice of algorithm
                is implicit in the KeyID.

    AuthLen     An unsigned 16-bit field giving the length in octets of
                the Authentication Data.

    AuthOffset  An unsigned 16-bit offset, measured in octets, from the
                beginning of the RR message to the beginning of the
                Authentication Data.

                An unsigned 32-bit sequence number.  The sequence number
                MUST be non-decreasing for all messages sent with the
                same KeyID.

Expires September 26, 1997      Crawford                        [Page 6]

Internet Draft             Router Renumbering             March 26, 1997

4.2.  Prefix Control Operation

    A Prefix Control Operation has one Match-Prefix Part of 24 octets,
    followed by zero or more Use-Prefix Parts of 32 octets each.

4.2.1.  Match-Prefix Part

      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
     |    OpCode     |   OpLength    |     unused    |   MatchLen    |
     |                            unused                             |
     |                                                               |
     +-                                                             -+
     |                                                               |
     +-                         MatchPrefix                         -+
     |                                                               |
     +-                                                             -+
     |                                                               |


    OpCode      An unsigned 8-bit field specifying the operation to be
                performed when the associated MatchPrefix matches an
                interface's prefix or address.  Values are:

                1    the ADD operation

                2    the CHANGE operation

                3    the SET-GLOBAL operation

    OpLength    The total length of this Prefix Control Operation, in
                units of 8 octets.  A valid OpLength will always be of
                the form 4N+3, with N equal to the number of UsePrefix
                parts (possibly zero).

    MatchLen    An 8-bit unsigned integer between 0 and 128 inclusive
                specifying the number of initial bits of MatchPrefix
                which are significant in matching.

    MatchPrefix The 128-bit prefix to be compared with each interface's
                prefix or address.

Expires September 26, 1997      Crawford                        [Page 7]

Internet Draft             Router Renumbering             March 26, 1997

4.2.2.  Use-Prefix Part

      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
     |    UseLen     |    KeepLen    |     Mask      |     Flags     |
     |                        Valid Lifetime                         |
     |                      Preferred Lifetime                       |
     |V|P|                          unused                           |
     |                                                               |
     +-                                                             -+
     |                                                               |
     +-                          UsePrefix                          -+
     |                                                               |
     +-                                                             -+
     |                                                               |


    UseLen      An 8-bit unsigned integer less than or equal to 128
                specifying the number of initial bits of UsePrefix to
                use in creating a new prefix for an interface.

    KeepLen     An 8-bit unsigned integer less than or equal to (128-
                UseLen) specifying the number of bits of the prefix or
                address which matched the associated Match-Prefix which
                should be retained in the new prefix.  The retained bits
                are those at positions UseLen through (UseLen+KeepLen-1)
                in the matched address or prefix, and they are copied to
                the same positions in the New Prefix.

    Mask        An 8-bit mask.  A 1 bit in any position means that the
                corresponding flag bit in a Router Advertisement (RA)
                Prefix Information Option should be set from the Flags
                field in this Use-Prefix Part.  A 0 bit in the Mask
                means that the RA flag bit should be unchanged by this

    Flags       An 8 bit field which, under control of the Mask field,
                may be used to initialize the flags in Router
                Advertisement Prefix Information Options which advertise
                the New Prefix.  Note that only two flags as defined
                meanings to date: the L (on-link) and A (autonomous

Expires September 26, 1997      Crawford                        [Page 8]

Internet Draft             Router Renumbering             March 26, 1997

                configuration) flags.

    Valid Lifetime
                A 32-bit unsigned integer which is the number of seconds
                for which the New Prefix will be valid [ND, SAA].

    Preferred Lifetime
                A 32-bit unsigned integer which is the number of seconds
                for which the New Prefix will be preferred [ND, SAA].

    V           A 1-bit flag indicating that the valid lifetime of the
                New Prefix MUST be effectively decremented in real time.

    P           A 1-bit flag indicating that the preferred lifetime of
                the New Prefix MUST be effectively decremented in real

    UsePrefix   The 128-bit Use-prefix which either becomes or is used
                in forming (if KeepLen is nonzero) the New Prefix.  It
                MUST NOT have the form of a multicast or link-local
                address [AARCH].

4.3.  Authentication -- Keyed MD5

    When the key and algorithm associated with the KeyID indicate that
    Keyed MD5 authentication is to be used, the authentication data is
    generated in accordance with RFC 1321 [MD5]:

    All fields of the RR header and all the PCOs are filled in.  AuthLen
    will be 16 and AuthOffset will be equal to the length in octets of
    the RR packet, not including any IPv6 headers.  Let RRLength denote
    that length, which will always be a multiple of 8.

    The 16 octets of MD5 secret are appended to the RR message, followed
    by 8 to 64 octets of padding, enough to make the sum of the number
    of octets in the message, the secret and the padding equal to 56,
    modulo 64.  (The number of octets of padding will be 8 + ((48-
    RRLength) modulo 64).)  The value of the padding will be a single
    octet with value 80 hexadecimal followed by octets of zeros.

    Next, the MD5 length is appended, as a 64-bit value, with the most
    significant 32-bit word first.  This length is counted in bits and
    includes the secret, but not not the padding.  This it will be equal
    to 8*RRLength+128.

    Finally, the MD5 digest is computed and the result replaces the
    secret in its position immediately afer the last PCO.  The padding

Expires September 26, 1997      Crawford                        [Page 9]

Internet Draft             Router Renumbering             March 26, 1997

    and the MD5 length are discarded, as they can be reconstructed by
    the receiver.  The transmitted message includes everything through
    the MD5 digest only.

5.  Message Processing

    Processing of received Router Renumbering messages consists of three
    parts: header check, authentication check, and execution.

5.1.  Header Check

    First, the existence and validity of the key indicated by the KeyID
    are checked.  If there is no such valid key, or if the value of
    AuthLen is not correct for that key, the message MUST be discarded,
    and SHOULD be logged to network management.

    Next, the SequenceNumber is compared to the Recorded Sequence Number
    for the specified key.  (If no messages have been received using
    this key, the recorded number is zero.)  This comparison is done
    with the two numbers considered as simple non-negative integers, not
    as DNS-style serial numbers.  If the SequenceNumber is less than the
    Recorded Sequence Number for the key, the message MUST be discarded
    and SHOULD be logged to network management.

    Finally, if the SequenceNumber in the message is equal to the
    Recorded Sequence Number, the SegmentNumber MAY be checked.  If a
    correctly authenticated message with the same KeyID, SequenceNumber
    and SegmentNumber has already been processed, the current message
    MAY be discarded.  If it is discarded, it SHOULD NOT be logged to
    network management.

5.2.  Authentication Check

    The authentication check is performed over the RR message, without
    any IPv6 or extension headers.  In the case of Keyed MD5 it proceeds
    as follows.  First, the authentication data octets are saved, then
    that portion of the packet is replaced with the MD5 secret.  The
    padding and length fields are appended just as during message
    generation, and the MD5 digest is computed and compared to the saved
    value.  If the computed digest is not equal to the saved
    authentication data, the authentication check fails.

    If the authentication check fails, the message MUST be discarded and
    SHOULD be logged to network management.

Expires September 26, 1997      Crawford                       [Page 10]

Internet Draft             Router Renumbering             March 26, 1997

    If the authentication check passes, and the SequenceNumber is
    greater than the Recorded Sequence Number for the key, then the list
    of processed SegmentNumbers, if any, MUST be cleared and the
    Recorded Sequence Number MUST be updated to the value used in the
    current message, regardless of subsequent processing errors.

5.3.  Execution


    After succesful processing of all the Prefix Control Operations, an
    implementation MAY record the SegmentNumber of the packet in a list
    associated with the KeyID and SequenceNumber.

6.  Key Management

    As with all security methods using keys, it is necessary to change
    the RR Authentication Key on a regular basis.  To provide RR
    functionality during key changes, implementations MUST be able to
    store and use more than one Authentication Key at the same time.

    The Authentication Keys SHOULD NOT be stored or transmitted using
    algorithms or protocols that have known flaws.  Implementations MUST
    support the storage of more than one key at the same time, MUST
    associate a specific lifetime (start and end times) and a key
    identifier with each key, and MUST support manual key distribution
    (e.g., manual entry of the key, key lifetime, and key identifier on
    the router console).

    An infinite key lifetime SHOULD NOT be allowed.  If infinite
    lifetimes are allowed, manual deletion of valid keys MUST be
    supported; otherwise manual deletion SHOULD be supported.  The
    implementation MAY automatically delete expired keys.

7.  Usage Guidelines

    Using a new authentication key while a previously used key is still
    valid can open the possibility of a replay attack.  The processing
    rules as given in section 5. specify that routers keep track of the
    highest sequence number seen for each key, and that messages with
    that key and seuence number remain valid until either a higher
    sequence number is seen or the key expires.  The difficulty arises
    when a new key is used to send a message which supersedes the last
    message sent with another still-valid key.  That older message can
    still be replayed.

Expires September 26, 1997      Crawford                       [Page 11]

Internet Draft             Router Renumbering             March 26, 1997

    This vulnerability can be avoided in practice by sending a "NO-OP"
    message with the old key and a valid new sequence number before
    using a newer key.  This mesage will then become the only one which
    can be replayed with the old key.  An example of a NO-OP message
    would be one which contains no Prefix Control Operations.

    Cearly a management station must keep track of the highest sequence
    number it has used for any authentication key, at least to the
    extent of being able to generate a larger value when needed.  A
    timestamp may make a good sequence number.

8.  Points for Discussion

         Does the site-local all-routers multicast address exist?
         RFC1884 sort of glosses over that.  If it doesn't, we need
         a new multicast address to be assigned.

         The "unusued" fields of the MatchPart could be used to
         specify another condition in addition to matching a
         prefix.  For example, one of the prefix lifetime timers
         could be tested against a value.

         If the messages of several different protocols use the
         same authentication mechanism, as this draft tries to
         emulate the Keyed-MD5 authentication proposed for RIPv2,
         then it's possible for one authenticated message body to
         be grafted onto a different set of headers and cause at
         least some confusion, and possibly worse.  This can be
         prevented by placing magic numbers or other fixed data in
         the packets so that a packet for one protocol is never
         valid for another.

         Since RR messages will presumably be generated only by a
         set network management stations which is disjoint from the
         set of routers to which they are directed, an asymmetric
         authentication scheme would be desirable.

9.  Security Considerations

    The Router Renumbering mechanism proposed here is very powerful and
    prevention of spoofing it is important.  Replay of old messages must
    be prevented, except in the narrow case of idempotent messages which
    are still valid at the time of replay.  We believe the
    authentication mechanisms included in this specification achieve the
    necessary protections, so long as authentication keys are not

Expires September 26, 1997      Crawford                       [Page 12]

Internet Draft             Router Renumbering             March 26, 1997


    Authentication keys must be as well protected as is any other access
    method that allows reconfiguration of a site's routers.
    Distribution of keys must not expose them or permit alteration, and
    key lifetimes must be limited.

10.  Acknowledgments

    Some of the key management text was borrowed from "RIP-II MD5
    Authentication."  (And the loan was repaid in kind.)

11.  References

    [AARCH] R. Hinden, S. Deering, "IP Version 6 Addressing
            Architecture", RFC 1884.

    [MD5]   R. Rivest, "The MD5 Message-Digest Algorithm", RFC 1321.

    [ND]    T. Narten, E. Nordmark, W. Simpson, "Neighbor Discovery for
            IP Version 6 (IPv6)", RFC 1970.

    [SAA]   S. Thomson, T. Narten, "IPv6 Stateless Address
            Autoconfiguration", RFC 1971.

12.  Authors' Addresses

    Matt Crawford                         Robert M. Hinden
    Fermilab MS 368                       Ipsilon Networks, Inc.
    PO Box 500                            232 Java Drive
    Batavia, IL 60510                     Sunnyvale, CA 94089
    USA                                   USA

    Phone: +1 630 840 3461                Phone: +1 408 990 2004

    Email: crawdad@fnal.gov               Email: hinden@ipsilon.com

Expires September 26, 1997      Crawford                       [Page 13]