Why has RFC 4941 been designed in such a way, that it might cause address conflicts?

Markus Hanauska <hanauska@equinux.de> Mon, 14 March 2011 11:59 UTC

Return-Path: <hanauska@equinux.de>
X-Original-To: ipv6@core3.amsl.com
Delivered-To: ipv6@core3.amsl.com
Received: from localhost (localhost [127.0.0.1]) by core3.amsl.com (Postfix) with ESMTP id 980403A68E4 for <ipv6@core3.amsl.com>; Mon, 14 Mar 2011 04:59:20 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.599
X-Spam-Level:
X-Spam-Status: No, score=-2.599 tagged_above=-999 required=5 tests=[BAYES_00=-2.599]
Received: from mail.ietf.org ([64.170.98.32]) by localhost (core3.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id JTV6Qyg7NUxz for <ipv6@core3.amsl.com>; Mon, 14 Mar 2011 04:59:19 -0700 (PDT)
Received: from mail.equinux.net (mail.equinux.net [194.145.236.10]) by core3.amsl.com (Postfix) with ESMTP id C4AB93A68C7 for <ipv6@ietf.org>; Mon, 14 Mar 2011 04:59:18 -0700 (PDT)
Received: from mail.equinux.net (127.0.0.1) by mail.equinux.net (MlfMTA v3.2r9) id hfnosa0171ss for <ipv6@ietf.org>; Mon, 14 Mar 2011 11:44:54 +0100 (envelope-from <hanauska@equinux.de>)
Received: from mail.muc.equinux.net ([192.168.40.207]) by mail.equinux.net (equinux Secure Mail Relay) with ESMTP; Mon, 14 Mar 2011 11:44:54 +0100
Received: from anaheim.muc.equinux.net (anaheim.muc.equinux.net [192.168.40.40]) by mail.muc.equinux.net (Postfix) with ESMTPS id 23F9520F4DD6 for <ipv6@ietf.org>; Mon, 14 Mar 2011 13:00:11 +0100 (CET)
From: Markus Hanauska <hanauska@equinux.de>
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
Subject: Why has RFC 4941 been designed in such a way, that it might cause address conflicts?
Date: Mon, 14 Mar 2011 13:00:11 +0100
Message-Id: <C744C51B-F2B0-4137-B39F-54B8D62F1C97@equinux.de>
To: ipv6@ietf.org
Mime-Version: 1.0 (Apple Message framework v1082)
X-Mailer: Apple Mail (2.1082)
X-Mlf-Version: 7.2.1.2841
X-Mlf-UniqueId: o201103141044540078654
X-BeenThere: ipv6@ietf.org
X-Mailman-Version: 2.1.9
Precedence: list
List-Id: "IPv6 Maintenance Working Group \(6man\)" <ipv6.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/listinfo/ipv6>, <mailto:ipv6-request@ietf.org?subject=unsubscribe>
List-Archive: <http://www.ietf.org/mail-archive/web/ipv6>
List-Post: <mailto:ipv6@ietf.org>
List-Help: <mailto:ipv6-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/ipv6>, <mailto:ipv6-request@ietf.org?subject=subscribe>
X-List-Received-Date: Tue, 15 Mar 2011 14:12:42 -0000

Since IPv6 plays an increasingly prominent role in planing network environments, I spent most of the weekend to think about IPv6 distribution strategies for our company and my home Internet connection, re-reading most of the important RFCs and I came across a serious address deployment issue that seems to not be addressed by any of them. I searched the Internet, since I could not believe nobody every came across that issue, but after reading over 100 web pages and over 50 papers regarding IPv6 address deployment, this issue either has not been discovered up to now or has been intentionally ignored. I must admit, the issue is highly unlikely to ever cause a problem in real life scenarios, but as a programmer there is a huge difference between "impossible" and "highly unlikely", and I definitely prefer "impossible".

I assume you are all familiar with all those RFCs in question, thus I don't want to bore you more than necessary, but I have to go into greater detail to make sure my concern is correctly understood. Assuming that you plan address distribution according to the 64/64 rule of RFC 4291, using 64 bit network ID and 64 bit host ID, there are 4 major ways how to distribute the addresses:

A) Manually - definitely necessary for routers and most likely a good idea for permanent services (DNS-, mail-, file-servers, etc.)

B) DHCPv6 according to RFC 3315 - either randomly distribute addresses from available pools or possibly even reserve certain addresses for certain hosts by MAC address.

C) Stateless Address Autoconfiguration according to RFC 4862 - currently the auto configuration scheme supported by most operating systems and devices. This major case has four important major sub-cases that people tend to ignore in general (there are some more minor sub-cases, but I'd like to ignore those here as well):

	C1) Device has a globally unique EU-/MAC-48 identifier
	C2) Device has NO globally unique EU-/MAC-48 identifier, but one manually assigned by a network admin
	C3) Device has a globally unique EU-64 identifier
	C4) Device has no globally unique EU-64 identifier, but one manually assigned by a network admin

D) Stateless Address Autoconfiguration with Privacy Extension according to RFC 4941

You can pick either scheme above or you can pick multiple at the same time. The second case implies that all these four schemes must peacefully coexist within the same network at the same time, and exactly this is *NOT* the case. Let me explain my concerns to you:

Mixing (A) and (B) shouldn't be a problem, just like in case of IPv4 admins only have to make sure that the manual addresses never overlap any DHCP address pool; this should be easily enforceable. E.g. reserve <prefix>::1 to <prefix>::FF (sorry for using upper case hex, it just reads better on my screen) for manual assignment (254 addresses) and <prefix>::100 to <prefix>::FF:FFFF as DHCP pool (over 16 mio DHCP addresses).

Adding (C) to the mix is no problem either, but only if you are aware of some border cases that are to be avoided. In most cases (C) means (C1) or (C3) and that means no conflicts are to be expected, since (C1)+(C3) have addresses which have the "u"-bit set to indicate global uniqueness, while this bit is never set in cases (A) and (B) - this is the original intention behind "inverting" the bit according to the RFC. 

What most people tend to ignore are the cases (C2) and (C4), where the "u" bit will not be set after inverting it and those cases are not plain hypothetical, I have seen them in real-life more than once. There exists still no problem in case of (C2), since FFFE will be added to the address and network admins are thus advised to not choose manual and DHCP address ranges in such a way, that they might ever have FFFE at the same position. This leaves only (C4) addresses that might potentially conflict with cases (A) and (B) and this is easily to be avoided by making sure network admins never manually assign local hardware identifiers where the vendor ID (the first three bytes of the identifier) are all zero. Not that it would be forbidden to do so, but considering the case of potential conflicts, it is just not advisable and also avoidable.

So far all these standards peacefully coexist with each other... however, case (D) does not. Case (D) can conflict with all other cases, except the cases (C1) and (C3). And that even though a tiny modification of RFC 4941 could entirely avoid this issue. A modification that would lead to maybe four lines of code in most IPv6 implementations out there. All that was necessary was adding the rule, that those random addresses must never start with three zero bytes and the address generation process must be repeated if such an address is generated on the first attempt. I must admit, an MD5 hash where the first three byte are all zero is rather unlikely but it is not impossible; unless someone can prove to me mathematically, that given the possible input data, such an outcome is absolutely impossible. However, bear in mind that the RFC does not require the usage of MD5, it only suggests it and even if it is impossible for MD5, who can guarantee it will be impossible for all other existing hash functions in the world that will ever be used for IPv6 address generation? I don't think I have to explain here how case (D) can conflict with all the other cases, since the address is unpredictable, any result is possible. And bear in mind, that other RFCs even mention cases where a device might create its 64 bit host ID entirely "random"; which is even worse than using a hash function.

I know what people will probably reply up to this point: No conflict can ever arise, duplicate address detection (DAD) is going to prevent that. And here is my reply: How is DAD preventing this problem if the device with the conflicting address in question is not connected to the network the moment DAD is performed? E.g. the address of type (D) conflicts with a DHCP address (very unlikely, but possible), a DHCP address that has been reserved for a certain mobile device, which currently is not connected to the network. DAD will not see any conflict and assign the IP to some other device. If now the mobile device is added to the network, it cannot obtain its reserved DHCP address. Of course the same is true for server with an manually assigned IP address that is only turned on at certain times of the day for example. And the same problem arises for a mobile device with a manual assigned interface ID as in cases (C2) or (C4).

I think we can safely ignore any security aspects here, since an attacker can always manually assign any address to any interface he likes, possibly using a manipulated IPv6 implementation that will simply never perform DAD. If someone wants to create address collisions by intention, there is no easy way to stop him and there are other standards that deal with host authentication. I'm only concerned about the fact that a couple of address deployment schemes that were designed to be simple and to ease the life of all network admins and home users, were not designed to always peacefully coexist within a single network, where hosts might come and go any time. Has this issue really been intentionally ignored, because given 2^64 addresses, the likeliness of a collision was seen as too unlikely to ever take place in real-life?

Regards,
Markus Hanauska