idnits 2.17.1 draft-leach-uuids-guids-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Cannot find the required boilerplate sections (Copyright, IPR, etc.) in this document. Expected boilerplate is as follows today (2024-03-29) according to https://trustee.ietf.org/license-info : IETF Trust Legal Provisions of 28-dec-2009, Section 6.a: This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 2: Copyright (c) 2024 IETF Trust and the persons identified as the document authors. All rights reserved. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 3: This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** Missing expiration date. The document expiration date should appear on the first and last page. ** The document seems to lack a 1id_guidelines paragraph about Internet-Drafts being working documents. ** The document seems to lack a 1id_guidelines paragraph about the list of current Internet-Drafts. ** The document seems to lack a 1id_guidelines paragraph about the list of Shadow Directories. == The page length should not exceed 58 lines per page, but there was 16 longer pages, the longest (page 12) being 68 lines Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** There are 2 instances of too long lines in the document, the longest one being 36 characters in excess of 72. ** The abstract seems to contain references ([2], [1]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. ** The document seems to lack a both a reference to RFC 2119 and the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. RFC 2119 keyword, line 274: '...he initial value MUST NOT be correlate...' RFC 2119 keyword, line 440: '...wever, it is strongly RECOMMENDED that...' RFC 2119 keyword, line 443: '...ntation protocol MUST be large enough ...' Miscellaneous warnings: ---------------------------------------------------------------------------- == Line 162 has weird spacing: '...eserved unsig...' == Line 268 has weird spacing: '...ence is incre...' == Line 497 has weird spacing: '...size of user ...' == Line 656 has weird spacing: '...ed long unsi...' == Line 657 has weird spacing: '...d short unsig...' == (2 more instances...) -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (February 24, 1997) is 9895 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Informational ---------------------------------------------------------------------------- == Missing Reference: '6' is mentioned on line 852, but not defined -- Looks like a reference, but probably isn't: 'HASHLEN' on line 557 == Missing Reference: '0' is mentioned on line 569, but not defined Summary: 10 errors (**), 0 flaws (~~), 9 warnings (==), 4 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group Paul J. Leach, Microsoft 3 INTERNET-DRAFT Rich Salz, Open Group 4 5 Category: Informational 6 Expires August 24, 1997 February 24, 1997 8 UUIDs and GUIDs 10 STATUS OF THIS MEMO 12 This document is an Internet-Draft. Internet-Drafts are working 13 documents of the Internet Engineering Task Force (IETF), its areas, 14 and its working groups. Note that other groups may also distribute 15 working documents as Internet-Drafts. 17 Internet-Drafts are draft documents valid for a maximum of six months 18 and may be updated, replaced, or obsoleted by other documents at any 19 time. It is inappropriate to use Internet-Drafts as reference 20 material or to cite them other than as "work in progress". 22 To learn the current status of any Internet-Draft, please check the 23 "1id-abstracts.txt" listing contained in the Internet-Drafts Shadow 24 Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe), 25 munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or 26 ftp.isi.edu (US West Coast). 28 Distribution of this document is unlimited. Please send comments to 29 the authors or the CIFS mailing list at . 30 Discussions of the mailing list are archived at 31 . 33 ABSTRACT 35 This specification defines the format of UUIDs (Universally Unique 36 IDentifier), also known as GUIDs (Globally Unique IDentifier). A UUID 37 is 128 bits long, and if generated according to the one of the 38 mechanisms in this document, is either guaranteed to be different 39 from all other UUIDs/GUIDs generated until 3400 A.D. or extremely 40 likely to be different (depending on the mechanism chosen). UUIDs 41 were originally used in the Network Computing System (NCS) [1] and 42 later in the Open Software Foundation's (OSF) Distributed Computing 43 Environment [2]. 45 This specification is derived from the latter specification with the 46 kind permission of the OSF. 48 Table of Contents 50 1. Introduction......................................................2 51 Internet-Draft UUIDs and GUIDs (DRAFT) 02/24/97 53 2. Motivation........................................................2 55 3. Specification.....................................................3 57 3.1 Format ..........................................................3 59 3.2 Algorithms for Creating a UUID ..................................5 61 3.2.1 Clock Sequence...............................................5 63 3.2.2 System Reboot................................................6 65 3.2.3 Clock Adjustment.............................................7 67 3.2.4 Clock Overrun................................................7 69 3.2.5 UUID Generation..............................................7 71 3.3 String Representation of UUIDs ..................................8 73 3.4 Comparing UUIDs .................................................9 75 3.5 Byte order of UUIDs .............................................9 77 4. Node IDs when no IEEE 802 network card is available...............9 79 5. Obtaining IEEE 802 addresses.....................................11 81 6. Security Considerations..........................................12 83 7. Acknowledgements.................................................12 85 8. References.......................................................12 87 9. Authors' addresses...............................................12 89 1. Introduction 91 This specification defines the format of UUIDs (Universally Unique 92 IDentifiers), also known as GUIDs (Globally Unique IDentifiers). A 93 UUID is 128 bits long, and if generated according to the one of the 94 mechanisms in this document, is either guaranteed to be different 95 from all other UUIDs/GUIDs generated until 3400 A.D. or extremely 96 likely to be different (depending on the mechanism chosen). 98 2. Motivation 100 One of the main reasons for using UUIDs is that no centralized 101 authority is required to administer them (beyond the one that 102 allocates IEEE 802.1 node identifiers). As a result, generation on 103 Internet-Draft UUIDs and GUIDs (DRAFT) 02/24/97 105 demand can be completely automated, and they can be used for a wide 106 variety of purposes. The UUID generation algorithm described here 107 supports very high allocation rates: 10 million per second per 108 machine if you need it, so that they could even be used as 109 transaction IDs. 111 UUIDs are fixed-size (128-bits) which is reasonably small relative to 112 other alternatives. This fixed, relatively small size lends itself 113 well to sorting, ordering, and hashing of all sorts, storing in 114 databases, simple allocation, and ease of programming in general. 116 3. Specification 118 A UUID is an identifier that is unique across both space and time, 119 with respect to the space of all UUIDs. To be precise, the UUID 120 consists of a finite bit space. Thus the time value used for 121 constructing a UUID is limited and will roll over in the future 122 (approximately at A.D. 3400, based on the specified algorithm). A 123 UUID can be used for multiple purposes, from tagging objects with an 124 extremely short lifetime, to reliably identifying very persistent 125 objects across a network. 127 The generation of UUIDs does not require that a registration 128 authority be contacted for each identifier. Instead, it requires a 129 unique value over space for each UUID generator. This spatially 130 unique value is specified as an IEEE 802 address, which is usually 131 already available to network-connected systems. This 48-bit address 132 can be assigned based on an address block obtained through the IEEE 133 registration authority. This section of the UUID specification 134 assumes the availability of an IEEE 802 address to a system desiring 135 to generate a UUID, but if one is not available section 4 specifies a 136 way to generate a probabilistically unique one that can not conflict 137 with any properly assigned IEEE 802 address. 139 3.1 Format 141 The following table gives the format of a UUID. The UUID consists of 142 a record of 16 octets. The fields are in order of significance for 143 comparison purposes, with "time_low" the most significant, and "node" 144 the least significant. 146 Field Data Octet Note 147 Type # 149 time_low unsigned 0-3 The low field of the 150 32 bit timestamp. 151 integer 153 time_mid unsigned 4-5 The middle field of the 154 16 bit timestamp. 155 integer 156 Internet-Draft UUIDs and GUIDs (DRAFT) 02/24/97 158 time_hi_and_version unsigned 6-7 The high field of the 159 16 bit timestamp multiplexed 160 integer with the version number. 162 clock_seq_hi_and_reserved unsigned The high field of the 163 8 bit clock sequence 8 164 integer multiplexed with the 165 variant. 167 clock_seq_low unsigned 9 The low field of the 168 8 bit clock sequence. 169 integer 171 node unsigned The spatially unique 172 48 bit node identifier. 10-15 173 integer 175 To minimize confusion about bit assignments within octets, the UUID 176 record definition is defined only in terms of fields that are 177 integral numbers of octets. The version number is in the most 178 significant 4 bits of the time stamp (time_hi), and the variant field 179 is in the most significant 3 bits of the clock sequence 180 (clock_seq_high). 182 The timestamp is a 60 bit value. For UUID version 1, this is 183 represented by Coordinated Universal Time (UTC) as a count of 100- 184 nanosecond intervals since 00:00:00.00, 15 October 1582 (the date of 185 Gregorian reform to the Christian calendar). 187 The following table lists currently defined versions of the UUID. 189 Msb0 Msb1 Msb2 Msb3 Version Description 191 0 0 0 1 1 The version specified 192 in this document. 194 0 0 1 0 2 Reserved for DCE 195 Security version, with 196 embedded POSIX UIDs. 198 The variant field determines the layout of the UUID. The structure of 199 UUIDs is fixed across different versions within a variant, but not 200 across variants; hence, other UUID variants may not interoperate with 201 the UUID variant specified in this document. Interoperability of 202 UUIDs is defined as the applicability of operations such as string 203 conversion, comparison, and lexical ordering across different 204 systems. The variant field consists of a variable number of the msbs 205 of the clock_seq_hi_and_reserved field. 207 The following table lists the contents of the variant field. 209 Internet-Draft UUIDs and GUIDs (DRAFT) 02/24/97 211 Msb0 Msb1 Msb2 Description 213 0 - - Reserved, NCS backward compatibility. 215 1 0 - The variant specified in this document. 217 1 1 0 Reserved, Microsoft Corporation GUID. 219 1 1 1 Reserved for future definition. 221 The clock sequence is required to detect potential losses of 222 monotonicity of the clock. Thus, this value marks discontinuities and 223 prevents duplicates. An algorithm for generating this value is 224 outlined in the _Clock Sequence_ section below. 226 The clock sequence is encoded in the 6 least significant bits of the 227 clock_seq_hi_and_reserved field and in the clock_seq_low field. 229 The node field consists of the IEEE address, usually the host 230 address. For systems with multiple IEEE 802 nodes, any available node 231 address can be used. The lowest addressed octet (octet number 10) 232 contains the global/local bit and the unicast/multicast bit, and is 233 the first octet of the address transmitted on an 802.3 LAN. 235 Depending on the network data representation, the multi-octet 236 unsigned integer fields are subject to byte swapping when 237 communicated between different endian machines. 239 The nil UUID is special form of UUID that is specified to have all 240 128 bits set to 0 (zero). 242 3.2 Algorithms for Creating a UUID 244 Various aspects of the algorithm for creating a UUID are discussed in 245 the following sections. UUID generation requires a guarantee of 246 uniqueness within the node ID for a given variant and version. 247 Interoperability is provided by complying with the specified data 248 structure. To prevent possible UUID collisions, which could be caused 249 by different implementations on the same node, compliance with the 250 algorithm specified here is required. 252 3.2.1 Clock Sequence 253 The clock sequence value must be changed whenever: 255 - the UUID generator detects that the local value of UTC has gone 256 backward. 258 - the UUID generator has lost its state of the last value of UTC 259 used, indicating that time may have gone backward; this is typically 260 the case on reboot. 262 Internet-Draft UUIDs and GUIDs (DRAFT) 02/24/97 264 While a node is operational, the UUID service always saves the last 265 UTC used to create a UUID. Each time a new UUID is created, the 266 current UTC is compared to the saved value and if either the current 267 value is less (the non-monotonic clock case) or the saved value was 268 lost, then the clock sequence is incremented modulo 16,384, thus 269 avoiding production of duplicate UUIDs. 271 The clock sequence must be initialized to a random number to minimize 272 the correlation across systems. This provides maximum protection 273 against node identifiers that may move or switch from system to 274 system rapidly. The initial value MUST NOT be correlated to the node 275 identifier. 277 The rule of initializing the clock sequence to a random value is 278 waived if, and only if all of the following are true: 280 - The clock sequence value is stored in non-volatile storage. 282 - The system is manufactured such that the IEEE address ROM is 283 designed to be inseparable from the system by either the user or 284 field service, so that it cannot be moved to another system. 286 - The manufacturing process guarantees that only new IEEE address 287 ROMs are used. 289 - Any field service, remanufacturing or rebuilding process that could 290 change the value of the clock sequence must reinitialise it to a 291 random value. 293 In other words, the system constraints prevent duplicates caused by 294 possible migration of the IEEE address, while the operational system 295 itself can protect against non-monotonic clocks, except in the case 296 of field service intervention. At manufacturing time, such a system 297 may initialise the clock sequence to any convenient value. 299 3.2.2 System Reboot 300 There are two possibilities when rebooting a system: 302 - the UUID generator state - the last UTC, adjustment, and clock 303 sequence - of the UUID service has been restored from non-volatile 304 store 306 - the state of the last UTC or adjustment has been lost. 308 If the state variables have been restored, the UUID generator just 309 continues as normal. Alternatively, if the state variables cannot be 310 restored, they are reinitialised, and the clock sequence is changed. 312 If the clock sequence is stored in non-volatile store, it is 313 incremented; otherwise, it is reinitialised to a new random value. 315 Internet-Draft UUIDs and GUIDs (DRAFT) 02/24/97 317 3.2.3 Clock Adjustment 318 UUIDs may be created at a rate greater than the system clock 319 resolution. Therefore, the system must also maintain an adjustment 320 value to be added to the lower-order bits of the time. Logically, 321 each time the system clock ticks, the adjustment value is cleared. 322 Every time a UUID is generated, the current adjustment value is read 323 and incremented atomically, then added to the UTC time field of the 324 UUID. 326 3.2.4 Clock Overrun 327 The 100 nanosecond granularity of time should prove sufficient even 328 for bursts of UUID creation in high-performance multiprocessors. If a 329 system overruns the clock adjustment by requesting too many UUIDs 330 within a single system clock tick, the UUID service may raise an 331 exception, handled in a system or process-dependent manner either by: 333 - terminating the requester 335 - reissuing the request until it succeeds 337 - stalling the UUID generator until the system clock catches up. 339 If the processors overrun the UUID generation frequently, additional 340 node identifiers and clocks may need to be added. 342 3.2.5 UUID Generation 343 UUIDs are generated according to the following algorithm: 345 - Determine the values for the UTC-based timestamp and clock sequence 346 to be used in the UUID, as described above. 348 - For the purposes of this algorithm, consider the timestamp to be a 349 60-bit unsigned integer and the clock sequence to be a 14-bit 350 unsigned integer. Sequentially number the bits in a field, starting 351 from 0 (zero) for the least significant bit. 353 - Set the time_low field equal to the least significant 32-bits (bits 354 numbered 0 to 31 inclusive) of the time stamp in the same order of 355 significance. 357 - Set the time_mid field equal to the bits numbered 32 to 47 358 inclusive of the time stamp in the same order of significance. 360 - Set the 12 least significant bits (bits numbered 0 to 11 inclusive) 361 of the time_hi_and_version field equal to the bits numbered 48 to 59 362 inclusive of the time stamp in the same order of significance. 364 - Set the 4 most significant bits (bits numbered 12 to 15 inclusive) 365 of the time_hi_and_version field to the 4-bit version number 366 corresponding to the UUID version being created, as shown in the 367 table above. 369 Internet-Draft UUIDs and GUIDs (DRAFT) 02/24/97 371 - Set the clock_seq_low field to the 8 least significant bits (bits 372 numbered 0 to 7 inclusive) of the clock sequence in the same order of 373 significance. 375 - Set the 6 least significant bits (bits numbered 0 to 5 inclusive) 376 of the clock_seq_hi_and_reserved field to the 6 most significant bits 377 (bits numbered 8 to 13 inclusive) of the clock sequence in the same 378 order of significance. 380 - Set the 2 most significant bits (bits numbered 6 and 7) of the 381 clock_seq_hi_and_reserved to 0 and 1, respectively. 383 - Set the node field to the 48-bit IEEE address in the same order of 384 significance as the address. 386 3.3 String Representation of UUIDs 388 For use in human readable text, a UUID string representation is 389 specified as a sequence of fields, some of which are separated by 390 single dashes. 392 Each field is treated as an integer and has its value printed as a 393 zero-filled hexadecimal digit string with the most significant digit 394 first. The hexadecimal values a to f inclusive are output as lower 395 case characters, and are case insensitive on input. The sequence is 396 the same as the UUID constructed type. 398 The formal definition of the UUID string representation is provided 399 by the following extended BNF: 401 UUID = "-" "-" 402 "-" 403 404 "-" 405 time_low = 4* 406 time_mid = 2* 407 time_high_and_version = 2* 408 clock_seq_and_reserved = 409 clock_seq_low = 410 node = 6* 412 hexDigit = 413 "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" 414 | "a" | "b" | "c" | "d" | "e" | "f" 415 | "A" | "B" | "C" | "D" | "E" | "F" 417 The following is an example of the string representation of a UUID: 419 f81d4fae-7dec-11d0-a765-00a0c91e6bf6 420 Internet-Draft UUIDs and GUIDs (DRAFT) 02/24/97 422 3.4 Comparing UUIDs 424 Consider each field of the UUID to be an unsigned integer as shown in 425 the table in section 3.1. Then, to compare a pair of UUIDs, 426 arithmetically compare the corresponding fields from each UUID in 427 order of significance and according to their data type. Two UUIDs are 428 equal if and only if all the corresponding fields are equal. The 429 first of two UUIDs follows the second if the most significant field 430 in which the UUIDs differ is greater for the first UUID. The first of 431 a pair of UUIDs precedes the second if the most significant field in 432 which the UUIDs differ is greater for the second UUID. 434 3.5 Byte order of UUIDs 436 UUIDs may be transmitted in many different forms, some of which may 437 be dependent on the presentation or application protocol where the 438 UUID may be used. In such cases, the order, sizes and byte orders of 439 the UUIDs fields on the wire will depend on the relevant presentation 440 or application protocol. However, it is strongly RECOMMENDED that 441 the order of the fields conform with ordering set out in section 3.1 442 above. Furthermore, the payload size of each field in the application 443 or presentation protocol MUST be large enough that no information 444 lost in the process of encoding them for transmission. 446 In the absence of explicit application or presentation protocol 447 specification to the contrary, a UUID is encoded as a 128-bit object, 448 as follows: the fields are encoded as 16 octets, with the sizes and 449 order of the fields defined in section 3.1, and with each field 450 encoded with the Most Significant Byte first (also known as network 451 byte order). 453 0 1 2 3 454 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 455 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 456 | time_high | 457 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 458 | time_mid | time_hi_and_version | 459 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 460 |clk_seq_hi_res | clk_seq_low | node (0-1) | 461 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 462 | node (2-5) | 463 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 465 4. Node IDs when no IEEE 802 network card is available 467 If a system wants to generate UUIDs but has no IEE 802 compliant 468 network card or other source of IEEE 802 addresses, then this section 469 describes how to generate one. 471 The ideal solution is to obtain a 47 bit cryptographic quality random 472 number, and use it as the low 47 bits of the node ID, with the most 473 Internet-Draft UUIDs and GUIDs (DRAFT) 02/24/97 475 significant bit of the first octet of the node ID set to 1. This bit 476 is the unicast/multicast bit, which will never be set in IEEE 802 477 addresses obtained from network cards; hence, there can never be a 478 conflict between UUIDs generated by machines with and without network 479 cards. 481 If a system does not have a primitive to generate cryptographic 482 quality random numbers, then in most systems there are usually a 483 fairly large number of sources of randomness available from which one 484 can be generated. Such sources are system specific, but often 485 include: 487 - the percent of memory in use 489 - the size of main memory in bytes 491 - the amount of free main memory in bytes 493 - the size of the paging or swap file in bytes 495 - free bytes of paging or swap file 497 - the total size of user virtual address space in bytes 499 - the total available user address space bytes 501 - the size of boot disk drive in bytes 503 - the free disk space on boot drive in bytes 505 - the current time 507 - the amount of time since the system booted 509 - the individual sizes of files in various system directories 511 - the creation, last read, and modification times of files in various 512 system directories 514 - the utilization factors of various system resources (heap, etc.) 516 - current mouse cursor position 518 - current caret position 520 - current number of running processes, threads 522 - handles or IDs of the desktop window and the active window 524 - the value of stack pointer of the caller 526 - the process and thread ID of caller 527 Internet-Draft UUIDs and GUIDs (DRAFT) 02/24/97 529 - various processor architecture specific performance counters 530 (instructions executed, cache misses, TLB misses) 532 (Note that it precisely the above kinds of sources of randomness that 533 are used to seed cryptographic quality random number generators on 534 systems without special hardware for their construction.) 536 In addition, items such as the computer's name and the name of the 537 operating system, while not strictly speaking random, will help 538 differentiate the results from those obtained by other systems. 540 The exact algorithm to generate a node ID using these data is system 541 specific, because both the data available and the functions to obtain 542 them are often very system specific. However, assuming that one can 543 concatenate all the values from the randomness sources into a buffer, 544 and that a cryptographic hash function such as MD5 [3] is available, 545 the following code will compute a node ID: 547 #include 548 #define HASHLEN 16 550 void GenNodeID( 551 unsigned char * pDataBuf, // concatenated "randomness values" 552 long cData, // size of randomness values 553 unsigned char NodeID[6] // node ID 554 ) 555 { 556 int i, j, k; 557 unsigned char Hash[HASHLEN]; 558 MD_CTX context; 560 MDInit (&context); 561 MDUpdate (&context, pDataBuf, cData); 562 MDFinal (Hash, &context); 564 for (j = 0; j<6; j++) NodeId[j]=0; 565 for (i = 0,j = 0; i < HASHLEN; i++) { 566 NodeID[j++] ^= Hash[i]; 567 if (j == 6) j = 0; 568 }; 569 NodeID[0] |= 0x80; // set the multicast bit 570 }; 572 Other hash functions, such as SHA-1 [4], can also be used (in which 573 case HASHLEN will be 20). The only requirement is that the result be 574 suitably random _ in the sense that the outputs from a set uniformly 575 distributed inputs are themselves uniformly distributed, and that a 576 single bit change in the input can be expected to cause half of the 577 output bits to change. 579 5. Obtaining IEEE 802 addresses 581 The following URL 582 Internet-Draft UUIDs and GUIDs (DRAFT) 02/24/97 584 http://stdsbbs.ieee.org/products/oui/forms/index.html 586 contains information on how to obtain an IEEE 802 address block. Cost 587 is $1000 US. 589 6. Security Considerations 591 It should not be assumed that UUIDs are hard to guess; they should 592 not be used as capabilities. 594 7. Acknowledgements 596 This document draws heavily on the OSF DCE specification for UUIDs. 597 Ted Ts'o provided helpful comments, especially on the byte ordering 598 section which we mostly plagiarized from a proposed wording he 599 supplied (all errors in that section are our responsibility, 600 however). 602 8. References 604 [1] Lisa Zahn, et. al., Network Computing Architecture, Prentice 605 Hall, Englewood Cliffs, NJ, 1990 607 [2] DCE: Remote Procedure Call, Open Group CAE Specification C309 608 ISBN 1-85912-041-5 28cm. 674p. pbk. 1,655g. 8/94 610 [3] R. Rivest, RFC 1321, "The MD5 Message-Digest Algorithm", 611 04/16/1992. 613 [4] SHA Spec - TBD 615 9. Authors' addresses 617 Paul J. Leach 618 Microsoft 619 1 Microsoft Way 620 Redmond, WA, 98052, U.S.A. 621 Email: 623 paulle@microsoft.com 625 Rich Salz 626 The Open Group 627 11 Cambridge Center 628 Cambridge, MA 02142, U.S.A. 629 Email r.salz@opengroup.org 631 Appendix A _ UUID Reference Implementation 633 /* 634 ** Copyright (c) 1990- 1993, 1996 Open Software Foundation, Inc. 636 Internet-Draft UUIDs and GUIDs (DRAFT) 02/24/97 638 ** Copyright (c) 1989 by Hewlett-Packard Company, Palo Alto, Ca. & 639 ** Digital Equipment Corporation, Maynard, Mass. 640 ** To anyone who acknowledges that this file is provided "AS IS" 641 ** without any express or implied warranty: permission to use, copy, 642 ** modify, and distribute this file for any purpose is hereby 643 ** granted without fee, provided that the above copyright notices and 644 ** this notice appears in all source code copies, and that none of 645 ** the names of Open Software Foundation, Inc., Hewlett-Packard 646 ** Company, or Digital Equipment Corporation be used in advertising 647 ** or publicity pertaining to distribution of the software without 648 ** specific, written prior permission. Neither Open Software 649 ** Foundation, Inc., Hewlett-Packard Company, nor Digital Equipment 650 ** Corporation makes any representations about the suitability of 651 ** this software for any purpose. 652 */ 653 #include 654 #include 656 typedef unsigned long unsigned32; 657 typedef unsigned short unsigned16; 658 typedef unsigned char unsigned8; 659 typedef unsigned char byte; 661 #define CLOCK_SEQ_LAST 0x3FFF 662 #define RAND_MASK CLOCK_SEQ_LAST 664 typedef struct _uuid_t { 665 unsigned32 time_low; 666 unsigned16 time_mid; 667 unsigned16 time_hi_and_version; 668 unsigned8 clock_seq_hi_and_reserved; 669 unsigned8 clock_seq_low; 670 byte node[6]; 671 } uuid_t; 673 typedef struct _unsigned64_t { 674 unsigned32 lo; 675 unsigned32 hi; 676 } unsigned64_t; 678 /* 679 ** Add two unsigned 64-bit long integers. 680 */ 681 #define ADD_64b_2_64b(A, B, sum) \ 682 { \ 683 if (!(((A)->lo & 0x80000000UL) ^ ((B)->lo & 0x80000000UL))) { 684 \ 685 if (((A)->lo&0x80000000UL)) { \ 686 (sum)->lo = (A)->lo + (B)->lo; \ 687 (sum)->hi = (A)->hi + (B)->hi + 1; \ 688 } \ 689 else { \ 690 (sum)->lo = (A)->lo + (B)->lo; \ 691 (sum)->hi = (A)->hi + (B)->hi; \ 692 Internet-Draft UUIDs and GUIDs (DRAFT) 02/24/97 694 } \ 695 } \ 696 else { \ 697 (sum)->lo = (A)->lo + (B)->lo; \ 698 (sum)->hi = (A)->hi + (B)->hi; \ 699 if (!((sum)->lo&0x80000000UL)) (sum)->hi++; \ 700 } \ 701 } 703 /* 704 ** Add a 16-bit unsigned integer to a 64-bit unsigned integer. 705 */ 706 #define ADD_16b_2_64b(A, B, sum) \ 707 { \ 708 (sum)->hi = (B)->hi; \ 709 if ((B)->lo & 0x80000000UL) { \ 710 (sum)->lo = (*A) + (B)->lo; \ 711 if (!((sum)->lo & 0x80000000UL)) (sum)->hi++; \ 712 } \ 713 else \ 714 (sum)->lo = (*A) + (B)->lo; \ 715 } 717 /* 718 ** Global variables. 719 */ 720 static unsigned64_t time_last; 721 static unsigned16 clock_seq; 723 static void 724 mult32(unsigned32 u, unsigned32 v, unsigned64_t *result) 725 { 726 /* Following the notation in Knuth, Vol. 2. */ 727 unsigned32 uuid1, uuid2, v1, v2, temp; 729 uuid1 = u >> 16; 730 uuid2 = u & 0xFFFF; 731 v1 = v >> 16; 732 v2 = v & 0xFFFF; 733 temp = uuid2 * v2; 734 result->lo = temp & 0xFFFF; 735 temp = uuid1 * v2 + (temp >> 16); 736 result->hi = temp >> 16; 737 temp = uuid2 * v1 + (temp & 0xFFFF); 738 result->lo += (temp & 0xFFFF) << 16; 739 result->hi += uuid1 * v1 + (temp >> 16); 740 } 742 static void 743 get_system_time(unsigned64_t *uuid_time) 744 { 745 struct timeval tp; 746 unsigned64_t utc, usecs, os_basetime_diff; 747 Internet-Draft UUIDs and GUIDs (DRAFT) 02/24/97 749 gettimeofday(&tp, (struct timezone *)0); 750 mult32((long)tp.tv_sec, 10000000, &utc); 751 mult32((long)tp.tv_usec, 10, &usecs); 752 ADD_64b_2_64b(&usecs, &utc, &utc); 754 /* Offset between UUID formatted times and Unix formatted times. 755 * UUID UTC base time is October 15, 1582. 756 * Unix base time is January 1, 1970. */ 757 os_basetime_diff.lo = 0x13814000; 758 os_basetime_diff.hi = 0x01B21DD2; 759 ADD_64b_2_64b(&utc, &os_basetime_diff, uuid_time); 760 } 762 /* 763 ** See "The Multiple Prime Random Number Generator" by Alexander 764 ** Hass pp. 368-381, ACM Transactions on Mathematical Software, 765 ** 12/87. 766 */ 767 static unsigned32 rand_m; 768 static unsigned32 rand_ia; 769 static unsigned32 rand_ib; 770 static unsigned32 rand_irand; 772 static void 773 true_random_init(void) 774 { 775 unsigned64_t t; 776 unsigned16 seed; 778 /* Generating our 'seed' value Start with the current time, but, 779 * since the resolution of clocks is system hardware dependent and 780 * most likely coarser than our resolution (10 usec) we 'mixup' the 781 * bits by xor'ing all the bits together. This will have the effect 782 * of involving all of the bits in the determination of the seed 783 * value while remaining system independent. Then for good measure 784 * to ensure a unique seed when there are multiple processes 785 * creating UUIDs on a system, we add in the PID. 786 */ 787 rand_m = 971; 788 rand_ia = 11113; 789 rand_ib = 104322; 790 rand_irand = 4181; 791 get_system_time(&t); 792 seed = t.lo & 0xFFFF; 793 seed ^= (t.lo >> 16) & 0xFFFF; 794 seed ^= t.hi & 0xFFFF; 795 seed ^= (t.hi >> 16) & 0xFFFF; 796 rand_irand += seed + getpid(); 797 } 799 static unsigned16 800 true_random(void) 801 { 802 if ((rand_m += 7) >= 9973) 803 Internet-Draft UUIDs and GUIDs (DRAFT) 02/24/97 805 rand_m -= 9871; 806 if ((rand_ia += 1907) >= 99991) 807 rand_ia -= 89989; 808 if ((rand_ib += 73939) >= 224729) 809 rand_ib -= 96233; 810 rand_irand = (rand_irand * rand_m) + rand_ia + rand_ib; 811 return (rand_irand >> 16) ^ (rand_irand & RAND_MASK); 812 } 814 /* 815 ** Startup initialization routine for the UUID module. 816 */ 817 void 818 uuid_init(void) 819 { 820 true_random_init(); 821 get_system_time(&time_last); 822 #ifdef NONVOLATILE_CLOCK 823 clock_seq = read_clock(); 824 #else 825 clock_seq = true_random(); 826 #endif 827 } 829 static int 830 time_cmp(unsigned64_t *time1, unsigned64_t *time2) 831 { 832 if (time1->hi < time2->hi) return -1; 833 if (time1->hi > time2->hi) return 1; 834 if (time1->lo < time2->lo) return -1; 835 if (time1->lo > time2->lo) return 1; 836 return 0; 837 } 839 static void new_clock_seq(void) 840 { 841 clock_seq = (clock_seq + 1) % (CLOCK_SEQ_LAST + 1); 842 if (clock_seq == 0) clock_seq = 1; 843 #ifdef NONVOLATILE_CLOCK 844 write_clock(clock_seq); 845 #endif 846 } 848 void uuid_create(uuid_t *uuid) 849 { 850 static unsigned64_t time_now; 851 static unsigned16 time_adjust; 852 byte eaddr[6]; 853 int got_no_time = 0; 855 get_ieee_node_identifier(&eaddr); /* TO BE PROVIDED */ 857 do { 858 get_system_time(&time_now); 859 Internet-Draft UUIDs and GUIDs (DRAFT) 02/24/97 861 switch (time_cmp(&time_now, &time_last)) { 862 case -1: 863 /* Time went backwards. */ 864 new_clock_seq(); 865 time_adjust = 0; 866 break; 867 case 1: 868 time_adjust = 0; 869 break; 870 default: 871 if (time_adjust == 0x7FFF) 872 /* We're going too fast for our clock; spin. */ 873 got_no_time = 1; 874 else 875 time_adjust++; 876 break; 877 } 878 } while (got_no_time); 880 time_last.lo = time_now.lo; 881 time_last.hi = time_now.hi; 883 if (time_adjust != 0) { 884 ADD_16b_2_64b(&time_adjust, &time_now, &time_now); 885 } 887 /* Construct a uuid with the information we've gathered 888 * plus a few constants. */ 889 uuid->time_low = time_now.lo; 890 uuid->time_mid = time_now.hi & 0x0000FFFF; 891 uuid->time_hi_and_version = (time_now.hi & 0x0FFF0000) >> 16; 892 uuid->time_hi_and_version |= (1 << 12); 893 uuid->clock_seq_low = clock_seq & 0xFF; 894 uuid->clock_seq_hi_and_reserved = (clock_seq & 0x3F00) >> 8; 895 uuid->clock_seq_hi_and_reserved |= 0x80; 896 memcpy(uuid->node, &eaddr, sizeof uuid->node); 897 }