IPng Working Group Matt Crawford
Internet Draft Fermilab
Bob Hinden
Ipsilon Networks
March 26, 1997
Router Renumbering for IPv6
<draft-ietf-ipngwg-router-renum-00.txt>
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
Rim).
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
times.
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:
MUST
This word or the adjective "REQUIRED" means that the item is an
absolute requirement of this specification.
MUST NOT
This phrase means the item is an absolute prohibition of this
specification.
SHOULD
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.
SHOULD NOT
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.
MAY
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
Address
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.
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.
Match
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
length;
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
addresses.
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 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Fields:
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.
SegmentNumber
An unsigned 15-bit field which enumerates different
valid RR messages having the same SequenceNumber and
KeyID.
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.
SequenceNumber
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 -+
| |
+- -+
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Fields:
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 -+
| |
+- -+
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Fields:
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
operation.
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
time.
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
THIS SECTION IS NOT YET COMPLETED.
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
compromised.
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]
