ossp-pkg/uuid/HISTORY
1.1
_ ___ ____ ____ ____ _ _
|_|_ _ / _ \/ ___/ ___|| _ \ _ _ _ _(_) __| |
_|_||_| | | | \___ \___ \| |_) | | | | | | | | |/ _` |
|_||_|_| | |_| |___) |__) | __/ | |_| | |_| | | (_| |
|_|_|_| \___/|____/____/|_| \__,_|\__,_|_|\__,_|
OSSP uuid - Universally Unique Identifier
HISTORY
During OSSP uuid we were totally puzzled by a subtle bug in the UUID
standards related to the generation of multi-cast MAC addresses.
This part of the history shows a very interesting technical bug,
the unusual way of having to fix a standard (which was multiple
times revised by different standard authorities, including the
IETF, the OpenGroup and ISO/IEC) afterwards plus the fixing of six
implementations into which the bug was inherited similarly. Below are
some snapshot of this part of history: the first implementation fix
(for FreeBSD) and the notification of the IETF standards authors.
___________________________________________________________________________
Date: Fri, 13 Feb 2004 16:09:31 +0100
From: "Ralf S. Engelschall" <rse@en1.engelschall.com>
To: paulle@microsoft.com, michael@neonym.net, rsalz@datapower.com
Subject: [PATCH] draft-mealling-uuid-urn-02.txt
Message-ID: <20040213150931.GA7656@engelschall.com>
During implementation of OSSP uuid (a flexible CLI and C API for
generation and partial decoding of version 1, 3 and 4 UUIDs, see
http://www.ossp.org/pkg/lib/uuid/ for details), I discovered a nasty bug
in the generation of random multicast MAC addresses. It is present in
all standards and drafts (both expired ones and current ones) and was
also inherited (until I fixed it by submitting patches to the authors
recently) by all six freely available UUID implementations (Apache APR,
FreeBSD uuidgen(2), Java JUG, Linux's libuuid from e2fsutil, Perl's
Data::UUID and WINE's UUID generator)).
In case no real/physical IEEE 802 address is available, both the
expired "draft-leach-uuids-guids-01" (section "4. Node IDs when no IEEE
802 network card is available"), RFC 2518 (section "6.4.1 Node Field
Generation Without the IEEE 802 Address") and now even your current
"draft-mealling-uuid-urn-02.txt" (section "4.5 Node IDs that do not
identify the host") recommend:
"A better solution is to obtain a 47-bit cryptographic quality
random number, and use it as the low 47 bits of the node ID, with
the _most_ significant bit of the first octet of the node ID set to
one. This bit is the unicast/multicast bit, which will never be set
in IEEE 802 addresses obtained from network cards; hence, there can
never be a conflict between UUIDs generated by machines with and
without network cards."
Unfortunately, this incorrectly explains how to implement this and even
the example implementation (draft-mealling-uuid-urn-02.txt, "Appendix
A. Appendix A - Sample Implementation") inherited this. Correct is
"the _least_ significant bit of the first octet of the node ID" as the
multicast bit in a memory and hexadecimal string representation of a
48-bit IEEE 802 MAC address.
This standards bug arised from a false interpretation, as the multicast
bit is actually the _most_ significant bit in IEEE 802.3 (Ethernet)
_transmission order_ of an IEEE 802 MAC address. But you forgot that the
bitwise order of an _octet_ from a MAC address _memory_ and hexadecimal
string representation is still always from left (MSB, bit 7) to right
(LSB, bit 0). And the standard deals with memory representations only,
so the transmission order of a MAC doesnt' matter here.
As mentioned, OSSP uuid already implements this correctly. The FreeBSD
uuidgen(2) and Apache APR generators I've also fixed myself recently in
CVS. And for the remaining implementations I've submitted patches to the
authors and they all (except for WINE) responded that they took over the
patch. So the results of this long-standing bug we were able to fix --
at least for the free software world ;-). What is now remaining is that
you finally also should fix this in your standard so the bug does not
spread any longer into other implementations.
Here is the minimal required patch against your draft:
--- draft-mealling-uuid-urn-02.txt.orig Mon Feb 2 21:50:35 2004
+++ draft-mealling-uuid-urn-02.txt Fri Feb 13 15:41:49 2004
@@ -751,7 +751,7 @@
[6], and the cost was US$550.
A better solution is to obtain a 47-bit cryptographic quality random
- number, and use it as the low 47 bits of the node ID, with the most
+ number, and use it as the low 47 bits of the node ID, with the least
significant bit of the first octet of the node ID set to one. This
bit is the unicast/multicast bit, which will never be set in IEEE 802
addresses obtained from network cards; hence, there can never be a
@@ -1369,7 +1369,7 @@
}
else {
get_random_info(seed);
- seed[0] |= 0x80;
+ seed[0] |= 0x01;
memcpy(&saved_node, seed, sizeof saved_node);
fp = fopen("nodeid", "wb");
if (fp) {
But I recommend you to perhaps also add one or two sentences which
explain what I explained above (the difference between memory and
transmission order), just to make sure people are not confused in the
other direction and then think there is a bug (in the then fixed and
correct) standard, because they know about the transmission order of MAC
addresses.
Yours,
Ralf S. Engelschall
rse@engelschall.com
www.engelschall.com
Date: Fri, 13 Feb 2004 11:05:51 -0500
From: Rich Salz <rsalz@datapower.com>
To: rse@engelschall.com
Cc: paulle@microsoft.com, michael@neonym.net
Message-ID: <402CF5DF.4020601@datapower.com>
Subject: Re: [PATCH] draft-mealling-uuid-urn-02.txt
References: <20040213150931.GA7656@engelschall.com>
Content-Length: 431
Lines: 11
Thanks for writing, Ralf.
You're correct, and this has been noted by the IESG and will be fixed in
the next draft. It's unfortunate we made it this far with the bug.
/r$
--
Rich Salz, Chief Security Architect
DataPower Technology http://www.datapower.com
XS40 XML Security Gateway http://www.datapower.com/products/xs40.html
XML Security Overview http://www.datapower.com/xmldev/xmlsecurity.html
Date: Thu, 22 Jan 2004 05:34:11 -0800 (PST)
From: "Ralf S. Engelschall" <rse@FreeBSD.org>
Message-Id: <200401221334.i0MDYB1K018137@repoman.freebsd.org>
To: src-committers@FreeBSD.org, cvs-src@FreeBSD.org, cvs-all@FreeBSD.org
Subject: cvs commit: src/sys/kern kern_uuid.c
X-FreeBSD-CVS-Branch: HEAD
X-Loop: FreeBSD.ORG
Content-Length: 1907
Lines: 42
rse 2004/01/22 05:34:11 PST
FreeBSD src repository
Modified files:
sys/kern kern_uuid.c
Log:
Fix generation of random multicast MAC address.
In case no real/physical IEEE 802 address is available, both the expired
"draft-leach-uuids-guids-01" (section "4. Node IDs when no IEEE 802
network card is available") and RFC 2518 (section "6.4.1 Node Field
Generation Without the IEEE 802 Address") recommend (quoted from RFC
2518):
"The ideal solution is to obtain a 47 bit cryptographic quality random
number, and use it as the low 47 bits of the node ID, with the _most_
significant bit of the first octet of the node ID set to 1. This bit
is the unicast/multicast bit, which will never be set in IEEE 802
addresses obtained from network cards; hence, there can never be a
conflict between UUIDs generated by machines with and without network
cards."
Unfortunately, this incorrectly explains how to implement this and
the FreeBSD UUID generator code inherited this generation bug from
the broken reference code in the standards draft. They should instead
specify the "_least_ significant bit of the first octet of the node ID"
as the multicast bit in a memory and hexadecimal string representation
of a 48-bit IEEE 802 MAC address.
This standards bug arised from a false interpretation, as the multicast
bit is actually the _most_ significant bit in IEEE 802.3 (Ethernet)
_transmission order_ of an IEEE 802 MAC address. The standards authors
forgot that the bitwise order of an _octet_ from a MAC address _memory_
and hexadecimal string representation is still always from left (MSB,
bit 7) to right (LSB, bit 0).
Fortunately, this UUID generation bug could have occurred on systems
without any Ethernet NICs only.
Revision Changes Path
1.7 +1 -1 src/sys/kern/kern_uuid.c
Date: Thu, 22 Jan 2004 15:20:22 -0800
From: Marcel Moolenaar <marcel@xcllnt.net>
To: "Ralf S. Engelschall" <rse@FreeBSD.org>
Cc: src-committers@FreeBSD.org, cvs-src@FreeBSD.org, cvs-all@FreeBSD.org
Subject: Re: cvs commit: src/sys/kern kern_uuid.c
Message-ID: <20040122232022.GA77798@ns1.xcllnt.net>
References: <200401221334.i0MDYB1K018137@repoman.freebsd.org>
Content-Length: 380
Lines: 14
On Thu, Jan 22, 2004 at 05:34:11AM -0800, Ralf S. Engelschall wrote:
> rse 2004/01/22 05:34:11 PST
>
> FreeBSD src repository
>
> Modified files:
> sys/kern kern_uuid.c
> Log:
> Fix generation of random multicast MAC address.
An excellent catch and an outstanding commit log. Chapeau!
--
Marcel Moolenaar USPA: A-39004 marcel@xcllnt.net
