1 _ ___ ____ ____ ____ _ _ 2 |_|_ _ / _ \/ ___/ ___|| _ \ _ _ _ _(_) __| | 3 _|_||_| | | | \___ \___ \| |_) | | | | | | | | |/ _` | 4 |_||_|_| | |_| |___) |__) | __/ | |_| | |_| | | (_| | 5 |_|_|_| \___/|____/____/|_| \__,_|\__,_|_|\__,_| 6 7 OSSP uuid - Universally Unique Identifier 8 9 HISTORY 10 11 During OSSP uuid we were totally puzzled by a subtle bug in the UUID 12 standards related to the generation of multi-cast MAC addresses. 13 This part of the history shows a very interesting technical bug, 14 the unusual way of having to fix a standard (which was multiple 15 times revised by different standard authorities, including the 16 IETF, the OpenGroup and ISO/IEC) afterwards plus the fixing of six 17 implementations into which the bug was inherited similarly. Below are 18 some snapshot of this part of history: the first implementation fix 19 (for FreeBSD) and the notification of the IETF standards authors. 20 21 ___________________________________________________________________________ 22 23 Date: Fri, 13 Feb 2004 16:09:31 +0100 24 From: "Ralf S. Engelschall" <rse@en1.engelschall.com> 25 To: paulle@microsoft.com, michael@neonym.net, rsalz@datapower.com 26 Subject: [PATCH] draft-mealling-uuid-urn-02.txt 27 Message-ID: <20040213150931.GA7656@engelschall.com> 28 29 During implementation of OSSP uuid (a flexible CLI and C API for 30 generation and partial decoding of version 1, 3 and 4 UUIDs, see 31 http://www.ossp.org/pkg/lib/uuid/ for details), I discovered a nasty bug 32 in the generation of random multicast MAC addresses. It is present in 33 all standards and drafts (both expired ones and current ones) and was 34 also inherited (until I fixed it by submitting patches to the authors 35 recently) by all six freely available UUID implementations (Apache APR, 36 FreeBSD uuidgen(2), Java JUG, Linux's libuuid from e2fsutil, Perl's 37 Data::UUID and WINE's UUID generator)). 38 39 In case no real/physical IEEE 802 address is available, both the 40 expired "draft-leach-uuids-guids-01" (section "4. Node IDs when no IEEE 41 802 network card is available"), RFC 2518 (section "6.4.1 Node Field 42 Generation Without the IEEE 802 Address") and now even your current 43 "draft-mealling-uuid-urn-02.txt" (section "4.5 Node IDs that do not 44 identify the host") recommend: 45 46 "A better solution is to obtain a 47-bit cryptographic quality 47 random number, and use it as the low 47 bits of the node ID, with 48 the _most_ significant bit of the first octet of the node ID set to 49 one. This bit is the unicast/multicast bit, which will never be set 50 in IEEE 802 addresses obtained from network cards; hence, there can 51 never be a conflict between UUIDs generated by machines with and 52 without network cards." 53 54 Unfortunately, this incorrectly explains how to implement this and even 55 the example implementation (draft-mealling-uuid-urn-02.txt, "Appendix 56 A. Appendix A - Sample Implementation") inherited this. Correct is 57 "the _least_ significant bit of the first octet of the node ID" as the 58 multicast bit in a memory and hexadecimal string representation of a 59 48-bit IEEE 802 MAC address. 60 61 This standards bug arised from a false interpretation, as the multicast 62 bit is actually the _most_ significant bit in IEEE 802.3 (Ethernet) 63 _transmission order_ of an IEEE 802 MAC address. But you forgot that the 64 bitwise order of an _octet_ from a MAC address _memory_ and hexadecimal 65 string representation is still always from left (MSB, bit 7) to right 66 (LSB, bit 0). And the standard deals with memory representations only, 67 so the transmission order of a MAC doesnt' matter here. 68 69 As mentioned, OSSP uuid already implements this correctly. The FreeBSD 70 uuidgen(2) and Apache APR generators I've also fixed myself recently in 71 CVS. And for the remaining implementations I've submitted patches to the 72 authors and they all (except for WINE) responded that they took over the 73 patch. So the results of this long-standing bug we were able to fix -- 74 at least for the free software world ;-). What is now remaining is that 75 you finally also should fix this in your standard so the bug does not 76 spread any longer into other implementations. 77 78 Here is the minimal required patch against your draft: 79 80 --- draft-mealling-uuid-urn-02.txt.orig Mon Feb 2 21:50:35 2004 81 +++ draft-mealling-uuid-urn-02.txt Fri Feb 13 15:41:49 2004 82 @@ -751,7 +751,7 @@ 83 [6], and the cost was US$550. 84 85 A better solution is to obtain a 47-bit cryptographic quality random 86 - number, and use it as the low 47 bits of the node ID, with the most 87 + number, and use it as the low 47 bits of the node ID, with the least 88 significant bit of the first octet of the node ID set to one. This 89 bit is the unicast/multicast bit, which will never be set in IEEE 802 90 addresses obtained from network cards; hence, there can never be a 91 @@ -1369,7 +1369,7 @@ 92 } 93 else { 94 get_random_info(seed); 95 - seed[0] |= 0x80; 96 + seed[0] |= 0x01; 97 memcpy(&saved_node, seed, sizeof saved_node); 98 fp = fopen("nodeid", "wb"); 99 if (fp) { 100 101 But I recommend you to perhaps also add one or two sentences which 102 explain what I explained above (the difference between memory and 103 transmission order), just to make sure people are not confused in the 104 other direction and then think there is a bug (in the then fixed and 105 correct) standard, because they know about the transmission order of MAC 106 addresses. 107 108 Yours, 109 Ralf S. Engelschall 110 rse@engelschall.com 111 www.engelschall.com 112 113 Date: Fri, 13 Feb 2004 11:05:51 -0500 114 From: Rich Salz <rsalz@datapower.com> 115 To: rse@engelschall.com 116 Cc: paulle@microsoft.com, michael@neonym.net 117 Message-ID: <402CF5DF.4020601@datapower.com> 118 Subject: Re: [PATCH] draft-mealling-uuid-urn-02.txt 119 References: <20040213150931.GA7656@engelschall.com> 120 Content-Length: 431 121 Lines: 11 122 123 Thanks for writing, Ralf. 124 125 You're correct, and this has been noted by the IESG and will be fixed in 126 the next draft. It's unfortunate we made it this far with the bug. 127 128 /r$ 129 -- 130 Rich Salz, Chief Security Architect 131 DataPower Technology http://www.datapower.com 132 XS40 XML Security Gateway http://www.datapower.com/products/xs40.html 133 XML Security Overview http://www.datapower.com/xmldev/xmlsecurity.html 134 135 Date: Thu, 22 Jan 2004 05:34:11 -0800 (PST) 136 From: "Ralf S. Engelschall" <rse@FreeBSD.org> 137 Message-Id: <200401221334.i0MDYB1K018137@repoman.freebsd.org> 138 To: src-committers@FreeBSD.org, cvs-src@FreeBSD.org, cvs-all@FreeBSD.org 139 Subject: cvs commit: src/sys/kern kern_uuid.c 140 X-FreeBSD-CVS-Branch: HEAD 141 X-Loop: FreeBSD.ORG 142 Content-Length: 1907 143 Lines: 42 144 145 rse 2004/01/22 05:34:11 PST 146 147 FreeBSD src repository 148 149 Modified files: 150 sys/kern kern_uuid.c 151 Log: 152 Fix generation of random multicast MAC address. 153 154 In case no real/physical IEEE 802 address is available, both the expired 155 "draft-leach-uuids-guids-01" (section "4. Node IDs when no IEEE 802 156 network card is available") and RFC 2518 (section "6.4.1 Node Field 157 Generation Without the IEEE 802 Address") recommend (quoted from RFC 158 2518): 159 160 "The ideal solution is to obtain a 47 bit cryptographic quality random 161 number, and use it as the low 47 bits of the node ID, with the _most_ 162 significant bit of the first octet of the node ID set to 1. This bit 163 is the unicast/multicast bit, which will never be set in IEEE 802 164 addresses obtained from network cards; hence, there can never be a 165 conflict between UUIDs generated by machines with and without network 166 cards." 167 168 Unfortunately, this incorrectly explains how to implement this and 169 the FreeBSD UUID generator code inherited this generation bug from 170 the broken reference code in the standards draft. They should instead 171 specify the "_least_ significant bit of the first octet of the node ID" 172 as the multicast bit in a memory and hexadecimal string representation 173 of a 48-bit IEEE 802 MAC address. 174 175 This standards bug arised from a false interpretation, as the multicast 176 bit is actually the _most_ significant bit in IEEE 802.3 (Ethernet) 177 _transmission order_ of an IEEE 802 MAC address. The standards authors 178 forgot that the bitwise order of an _octet_ from a MAC address _memory_ 179 and hexadecimal string representation is still always from left (MSB, 180 bit 7) to right (LSB, bit 0). 181 182 Fortunately, this UUID generation bug could have occurred on systems 183 without any Ethernet NICs only. 184 185 Revision Changes Path 186 1.7 +1 -1 src/sys/kern/kern_uuid.c 187 188 Date: Thu, 22 Jan 2004 15:20:22 -0800 189 From: Marcel Moolenaar <marcel@xcllnt.net> 190 To: "Ralf S. Engelschall" <rse@FreeBSD.org> 191 Cc: src-committers@FreeBSD.org, cvs-src@FreeBSD.org, cvs-all@FreeBSD.org 192 Subject: Re: cvs commit: src/sys/kern kern_uuid.c 193 Message-ID: <20040122232022.GA77798@ns1.xcllnt.net> 194 References: <200401221334.i0MDYB1K018137@repoman.freebsd.org> 195 Content-Length: 380 196 Lines: 14 197 198 On Thu, Jan 22, 2004 at 05:34:11AM -0800, Ralf S. Engelschall wrote: 199 > rse 2004/01/22 05:34:11 PST 200 > 201 > FreeBSD src repository 202 > 203 > Modified files: 204 > sys/kern kern_uuid.c 205 > Log: 206 > Fix generation of random multicast MAC address. 207 208 An excellent catch and an outstanding commit log. Chapeau! 209 210 -- 211 Marcel Moolenaar USPA: A-39004 marcel@xcllnt.net 212 213 ___________________________________________________________________________ 214 215 Index: ChangeLog 216 =================================================================== 217 RCS file: /e/ossp/cvs/ossp-pkg/uuid/ChangeLog,v 218 retrieving revision 1.42 219 diff -u -d -r1.42 ChangeLog 220 --- ChangeLog 13 Feb 2004 16:17:07 -0000 1.42 221 +++ ChangeLog 13 Feb 2004 21:01:07 -0000 222 @@ -13,6 +13,14 @@ 223 224 Changes between 0.9.6 and 0.9.7 (11-Feb-2004 to 13-Feb-2004) 225 226 + o remove --with-rfc2518 option and functionality because 227 + even the IETF/IESG has finally approved our report about the broken 228 + random multicast MAC address generation in the standard (and 229 + will fix it in new versions of the draft-mealling-uuid-urn). So, 230 + finally get rid of this broken-by-design backward compatibility 231 + functionality. 232 + [Ralf S. Engelschall] 233 + 234 o Add support to uuid(1) CLI for decoding from stdin for 235 both binary and string representations. 236 [Ralf S. Engelschall] 237 Index: uuid.ac 238 =================================================================== 239 RCS file: /e/ossp/cvs/ossp-pkg/uuid/uuid.ac,v 240 retrieving revision 1.10 241 diff -u -d -r1.10 uuid.ac 242 --- uuid.ac 11 Feb 2004 14:38:40 -0000 1.10 243 +++ uuid.ac 13 Feb 2004 19:20:32 -0000 244 @@ -71,12 +71,6 @@ 245 AC_CHECK_SIZEOF(unsigned long long, 8) 246 247 dnl # options 248 - AC_ARG_WITH(rfc2518, 249 - AC_HELP_STRING([--with-rfc2518], [use incorrect generation of IEEE 802 multicast addresses according to RFC2518]), 250 - [ac_cv_with_rfc2518=$withval], [ac_cv_with_rfc2518=no]) 251 - if test ".$ac_cv_with_rfc2518" = ".yes"; then 252 - AC_DEFINE(WITH_RFC2518, 1, [whether to use incorrect generation of IEEE 802 multicast addresses according to RFC2518]) 253 - fi 254 AC_ARG_WITH(dce, 255 AC_HELP_STRING([--with-dce], [build DCE 1.1 backward compatibility API]), 256 [ac_cv_with_dce=$withval], [ac_cv_with_dce=no]) 257 Index: uuid.c 258 =================================================================== 259 RCS file: /e/ossp/cvs/ossp-pkg/uuid/uuid.c,v 260 retrieving revision 1.44 261 diff -u -d -r1.44 uuid.c 262 --- uuid.c 19 Jan 2004 14:56:35 -0000 1.44 263 +++ uuid.c 13 Feb 2004 19:22:01 -0000 264 @@ -61,69 +61,9 @@ 265 Unix UTC base time is January 1, 1970) */ 266 #define UUID_TIMEOFFSET "01B21DD213814000" 267 268 -/* IEEE 802 MAC address encoding/decoding bit fields 269 - 270 - ATTENTION: 271 - 272 - In case no real/physical IEEE 802 address is available, both 273 - "draft-leach-uuids-guids-01" (section "4. Node IDs when no IEEE 802 274 - network card is available") and RFC 2518 (section "6.4.1 Node Field 275 - Generation Without the IEEE 802 Address") recommend (quoted from RFC 276 - 2518): 277 - 278 - "The ideal solution is to obtain a 47 bit cryptographic quality 279 - random number, and use it as the low 47 bits of the node ID, with 280 - the most significant bit of the first octet of the node ID set to 281 - 1. This bit is the unicast/multicast bit, which will never be set 282 - in IEEE 802 addresses obtained from network cards; hence, there can 283 - never be a conflict between UUIDs generated by machines with and 284 - without network cards." 285 - 286 - This passage clearly explains the intention to use IEEE 802 multicast 287 - addresses. Unfortunately, it incorrectly explains how to implement 288 - this! It should instead specify the "*LEAST* significant bit of the 289 - first octet of the node ID" as the multicast bit in a memory and 290 - hexadecimal string representation of a 48-bit IEEE 802 MAC address. 291 - 292 - Unfortunately, even the reference implementation included in the 293 - expired IETF "draft-leach-uuids-guids-01" incorrectly set the 294 - multicast bit with an OR bit operation and an incorrect mask of 295 - 0x80. Hence, several other UUID implementations found on the 296 - Internet have inherited this bug. 297 - 298 - Luckily, neither DCE 1.1 nor ISO/IEC 11578:1996 are affected by this 299 - problem. They disregard the topic of missing IEEE 802 addresses 300 - entirely, and thus avoid adopting this bug from the original draft 301 - and code ;-) 302 - 303 - It seems that this standards bug arises from a false interpretation, 304 - as the multicast bit is actually the *MOST* significant bit in IEEE 305 - 802.3 (Ethernet) _transmission order_ of an IEEE 802 MAC address. The 306 - authors were likely not aware that the bitwise order of an octet from 307 - a MAC address memory and hexadecimal string representation is still 308 - always from left (MSB, bit 7) to right (LSB, bit 0). 309 - 310 - For more information, see "Understanding Physical Addresses" in 311 - "Ethernet -- The Definitive Guide", p.43, and the section "ETHERNET 312 - MULTICAST ADDRESSES" in http://www.iana.org/assignments/ethernet-numbers. 313 - 314 - At OSSP, we do it the intended/correct way and generate a real 315 - IEEE 802 multicast address. Those wanting to encode broken IEEE 316 - 802 MAC addresses (as specified) can nevertheless use a brain dead 317 - compile-time option to switch off the correct behavior. When decoding 318 - we always use the correct behavior of course. */ 319 - 320 -/* encoding */ 321 -#ifdef WITH_RFC2518 322 -#define IEEE_MAC_MCBIT_ENC BM_OCTET(1,0,0,0,0,0,0,0) 323 -#else 324 -#define IEEE_MAC_MCBIT_ENC BM_OCTET(0,0,0,0,0,0,0,1) 325 -#endif 326 -#define IEEE_MAC_LOBIT_ENC BM_OCTET(0,0,0,0,0,0,1,0) 327 - 328 -/* decoding */ 329 -#define IEEE_MAC_MCBIT_DEC BM_OCTET(0,0,0,0,0,0,0,1) 330 -#define IEEE_MAC_LOBIT_DEC BM_OCTET(0,0,0,0,0,0,1,0) 331 +/* IEEE 802 MAC address encoding/decoding bit fields */ 332 +#define IEEE_MAC_MCBIT BM_OCTET(0,0,0,0,0,0,0,1) 333 +#define IEEE_MAC_LOBIT BM_OCTET(0,0,0,0,0,0,1,0) 334 335 /* IEEE 802 MAC address octet length */ 336 #define IEEE_MAC_OCTETS 6 337 @@ -622,8 +562,8 @@ 338 (unsigned int)uuid->obj.node[3], 339 (unsigned int)uuid->obj.node[4], 340 (unsigned int)uuid->obj.node[5], 341 - (uuid->obj.node[0] & IEEE_MAC_LOBIT_DEC ? "local" : "global"), 342 - (uuid->obj.node[0] & IEEE_MAC_MCBIT_DEC ? "multicast" : "unicast")); 343 + (uuid->obj.node[0] & IEEE_MAC_LOBIT ? "local" : "global"), 344 + (uuid->obj.node[0] & IEEE_MAC_MCBIT ? "multicast" : "unicast")); 345 } 346 else { 347 /* decode anything else as hexadecimal byte-string only */ 348 @@ -843,8 +783,8 @@ 349 if ((mode & UUID_MAKE_MC) || (uuid->mac[0] & BM_OCTET(1,0,0,0,0,0,0,0))) { 350 /* generate random IEEE 802 local multicast MAC address */ 351 prng_data(uuid->prng, (void *)&(uuid->obj.node), sizeof(uuid->obj.node)); 352 - uuid->obj.node[0] |= IEEE_MAC_MCBIT_ENC; 353 - uuid->obj.node[0] |= IEEE_MAC_LOBIT_ENC; 354 + uuid->obj.node[0] |= IEEE_MAC_MCBIT; 355 + uuid->obj.node[0] |= IEEE_MAC_LOBIT; 356 } 357 else { 358 /* use real regular MAC address */ 359