idnits 2.17.1 draft-eastlake-selection-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-04-25) 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 6 months document validity -- however, there's a paragraph with a matching beginning. Boilerplate error? ** 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. ** Bad filename characters: the document name given in the document, 'draft-eastlake-selection-00.txt,', contains other characters than digits, lowercase letters and dash. ** Missing revision: the document name given in the document, 'draft-eastlake-selection-00.txt,', does not give the document revision number ~~ Missing draftname component: the document name given in the document, 'draft-eastlake-selection-00.txt,', does not seem to contain all the document name components required ('draft' prefix, document source, document name, and revision) -- see https://www.ietf.org/id-info/guidelines#naming for more information. == Mismatching filename: the document gives the document name as 'draft-eastlake-selection-00.txt,', but the file name used is 'draft-eastlake-selection-00' == No 'Intended status' indicated for this document; assuming Proposed Standard 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. Miscellaneous warnings: ---------------------------------------------------------------------------- == Line 239 has weird spacing: '... div selec...' == Line 291 has weird spacing: '...ed char unc...' == Line 382 has weird spacing: '... div selec...' == Line 417 has weird spacing: '... char tin...' == Couldn't figure out when the document was first submitted -- there may comments or warnings related to the use of a disclaimer for pre-RFC5378 work that could not be issued because of this. Please check the Legal Provisions document at https://trustee.ietf.org/license-info to determine if you need the pre-RFC5378 disclaimer. -- The document date (April 1999) is 9142 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: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Missing reference section? 'RFC 2282' on line 70 looks like a reference -- Missing reference section? 'RFC1750' on line 111 looks like a reference -- Missing reference section? 'RFC1321' on line 177 looks like a reference -- Missing reference section? '16' on line 437 looks like a reference -- Missing reference section? '257' on line 417 looks like a reference -- Missing reference section? '525' on line 295 looks like a reference -- Missing reference section? '0' on line 425 looks like a reference -- Missing reference section? '1' on line 401 looks like a reference -- Missing reference section? '2' on line 401 looks like a reference -- Missing reference section? '3' on line 401 looks like a reference -- Missing reference section? '4' on line 401 looks like a reference -- Missing reference section? '5' on line 401 looks like a reference -- Missing reference section? '6' on line 401 looks like a reference -- Missing reference section? '7' on line 402 looks like a reference -- Missing reference section? '8' on line 402 looks like a reference -- Missing reference section? '9' on line 402 looks like a reference -- Missing reference section? '10' on line 402 looks like a reference -- Missing reference section? '11' on line 402 looks like a reference -- Missing reference section? '12' on line 402 looks like a reference -- Missing reference section? '13' on line 402 looks like a reference -- Missing reference section? '14' on line 402 looks like a reference -- Missing reference section? '15' on line 403 looks like a reference Summary: 10 errors (**), 1 flaw (~~), 7 warnings (==), 24 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Network Working Group Donald E. Eastlake 3rd 2 IBM 3 INTERNET-DRAFT October 1998 4 Expires April 1999 6 Publicly Verifiable Random Selection 7 -------- ---------- ------ --------- 9 Status of this Memo 11 This draft, file name draft-eastlake-selection-00.txt, is intended to 12 become an Informational RFC. Distribution of this document is 13 unlimited. Comments should be sent to the author. 15 This document is an Internet-Draft. Internet-Drafts are working 16 documents of the Internet Engineering Task Force (IETF), its areas, 17 and its working groups. Note that other groups may also distribute 18 working documents as Internet-Drafts. 20 Internet-Drafts are draft documents valid for a maximum of six 21 months. Internet-Drafts may be updated, replaced, or obsoleted by 22 other documents at any time. It is not appropriate to use Internet- 23 Drafts as reference material or to cite them other than as a 24 ``working draft'' or ``work in progress.'' 26 To view the entire list of current Internet-Drafts, please check the 27 "1id-abstracts.txt" listing contained in the Internet-Drafts Shadow 28 Directories on ftp.is.co.za (Africa), ftp.nordu.net (Northern 29 Europe), ftp.nis.garr.it (Southern Europe), munnari.oz.au (Pacific 30 Rim), ftp.ietf.org (US East Coast), or ftp.isi.edu (US West Coast). 32 Abstract 34 This document describes a method for making random selections in such 35 a way that the unbiased nature of the choice is publicly verifiable. 36 As an example, the selection of the voting members of the IETF 37 Nominations Committee from the pool of eligible volunteers is used. 38 Similar techniques would be applicable to other cases. 40 Table of Contents 42 Status of this Memo........................................1 43 Abstract...................................................1 45 Table of Contents..........................................2 47 1. Introduction............................................3 49 2. General Flow of Publicly Verifiable Process.............4 50 2.1 Determination of the Pool..............................4 51 2.2 Publication of the Algorithm...........................4 52 2.3 Publication of Selection...............................4 53 3. Sources of Randomness...................................5 54 4. A Sample Precise Algorithm..............................5 55 5. Fully Worked Example....................................6 56 6. Security Considerations.................................8 58 7. Reference Code.........................................9 60 References................................................13 61 Author's Address..........................................13 62 File name and Expiration..................................13 64 1. Introduction 66 Under the current IETF rules, each year 10 persons are randomly 67 selected from among the eligible persons who volunteer to be the 68 voting members of the nominations committee (NomCom) to nominate 69 members of the Internet Engineering Steering Group (IESG) and the 70 Internet Architecture Board (IAB) [RFC 2282]. The number of eligible 71 volunteers in recent years has varied in the approximate range of 40 72 to 60. 74 It is highly desireable that the random selection of the voting 75 NomCom be done in a unimpeachable fashion so that no charges of bias 76 or favoratism can be brought. This is for the protection of the IETF 77 from bias and protection of the adminstrator of the selection 78 (currently, the appointed non-voting NomCom chair) from suspicion of 79 bias. 81 A method such that public information will enable any person to 82 verify the randomness of the selection meets this criterion. This 83 document gives an examaple of such a method. 85 2. General Flow of Publicly Verifiable Process 87 In general, a selection of NomCom members publicly verifiable as 88 unbiased or similar selection could follow the three steps given 89 below. 91 2.1 Determination of the Pool 93 First, you need to determine the pool from which the selection is to 94 be made. 96 Volunteers are solicited by the appointed (non-voting) NomCom chair. 97 Their names are then passed through the IETF Secretariat to check 98 eligibility. (Current eligibility criteria relate to IETF meeting 99 attendence, records of which are maintained by the Secretariat.) The 100 full list of eligible volunteers is made public early enough that 101 there is a reasonable time to resolve any disputes as to who should 102 be in the pool, probably a week to ten days before the selection. 104 2.2 Publication of the Algorithm 106 The exact algorithm to be used, including the public sources of 107 randomness, is made public. For example, the members of the final 108 list of eligible volunteers are ordered by numbering them, several 109 public future sources of randmoness such as government run lotteries 110 are specified, and an exact algorithm is specified whereby elegible 111 volunteers are selected based on a strong hash function [RFC1750] of 112 these future sources of randmoness. 114 2.3 Publication of Selection 116 When the prespecified sources of randomness produce their output, 117 those values plus a summary of the execution of the algorithm for 118 selection should be announced so that anyone can verify that the 119 correct randomness source values were used and the algorithm properly 120 executed. To finalize the output and provide a stable NomCom, a cut 121 off time should be specified such that any complaint that the 122 algorithm was run with the wrong inputs or not faithfully executed 123 must be made before that cut off. 125 3. Sources of Randomness 127 The crux of the unbiased nature of the selection is that it is based 128 exactly on random information which will be revealed in the future 129 and thus can not be known to the person specifying the algorithm by 130 which that random information will be used to select the NomCom 131 members. The random information must be such that it will be 132 publicly revealed in a timely fashion. 134 Examples of such information are lottery winning numbers for 135 specified runnings of specified lotteries. Particularly for 136 government run lotteries, great care is usually taken to see that 137 they produce random quantities. Even in the unlikely case one were 138 to have been rigged, it would almost certainly be in connection with 139 winning money in the lottery, not in connection with IETF use. 141 Other possibilities are such things as the closing price of a stock 142 on a particular day, daily balance in the US Treasury on a specified 143 day, the volume of trading on the New York Stock exchange on a 144 specified day, etc. (However, the reference code given below will not 145 handle integers that are too large.) Sporting events can be used but 146 only with care to specify exactly what quantities are being presumed 147 random and what will be done if they are cancelled or delayed. 149 The random sources should not include anything that any reasonable 150 person would believe to be under the control or influence of the IETF 151 or its components, such as IETF meeting attendance statistics, 152 numbers of documents issued, or the like. 154 4. A Sample Precise Algorithm 156 It is important that a precise algorithm be given for mixing the 157 random sources specified and making the selection based thereon. 158 Suggested sources above each produce either a single positive number 159 (i.e., US Treasury balance) or a small set of positive numbers (many 160 lotteries provide 6 numbers in the range of 1 through 40 or the like, 161 a sporting event could produce the scores of two teams, etc.). 162 A sample precise algorithm is as follows: 164 For each source producing multiple numeric values, represent each as 165 a decimal number terminated by a period (or with a period separating 166 the whole from the fractional part) and without leading zeroes 167 (except for a single leading zero if the integer is zero) or trailing 168 zeroes after the period, order then from smallest to the largest and 169 concantenate them followed by a "/". For each source producing a 170 single number, simply represent it as above with a trailing "/".. At 171 this point you have a string for each source, say s1, s2, ... 173 Concatente these strings in a pre-specified order and represent each 174 character as its ASCII code producing s1/s2/.../. 176 You can then produce a sequence of random values derived from a 177 strong mixing of these sources by calculating the MD5 hash [RFC1321] 178 of this string prefixed and suffixed with a zero byte for the first 179 value, the string prefixed and suffixed by a 0x01 byte for the second 180 value, etc. Treat each of these derived random values as a positive 181 multiprecision integer. If there are N eligible volunteers, select 182 the first voting member by dividing the first derived random value by 183 N and using the remainder plus one as the position of the selectee in 184 the ordered list. Select the second voting member by dividing the 185 second derived random value by N-1 and using the remainder plus one 186 as the position of the selectee in the list with the first selectee 187 eliminated. Etc. 189 It is recommended that alphanumeric random sources be avoided due to 190 the greater difficulty in canonicalizing them in an independently 191 repeatable fashion; however, if any are used, all white space, 192 punctuation, and special characters should be removed and all letters 193 set to upper case. This will leave only an unbroken sequence of 194 letters A-Z and digits 0-9 which can be treated as a canonicalized 195 number above and suffixed with a "/". 197 5. Fully Worked Example 199 Ordered list of 25 eligible volunteers: 201 1. John 11. Pollyanna 21. Pride 202 2. Mary 12. Pendragon 22. Sloth 203 3. Bashful 13. Pandora 23. Envy 204 4. Dopey 14. Faith 24. Anger 205 5. Sleepy 15. Hope 25. Kasczynski 206 6. Grouchy 16. Charity 207 7. Doc 17. Love 208 8. Sneazy 18. Longsuffering 209 9. Handsome 19. Chastity 210 10. Cassandra 20. Smith 212 Ordered list of randomness sources: 213 1. Massachusetts Mass Millions lottery six winning numbers 214 (ignoring the seventh "extra" number) for 1 October 1998. 215 2. Numbers of the winning horses at Hialeia for all races for the 216 first day on or after x October 1998 on which at least two races are 217 run. 218 3. The Massachusetts State Lottery daily number for 1 October 219 1998 treated as a single four digit integer. 220 4. Closing price of Example Company stock for the first business 221 day after x October 1998 when it trades. 223 Randomness publicly produced: 224 Source 1: 9, 18, 26, 34, 41, 45 225 Source 2: 2, 5, 12, 8, 10 226 Source 3: 9319 227 Source 4: 13 11/16 229 Resulting key string: 231 9.18.26.34.41.45./2.5.8.10.12./9319./13.6875/ 233 The table below gives the hex of the MD5 of the above key string 234 bracketed with a byte whose value is successively 0x00, 0x01, 0x02, 235 through 0x09. The divisor for the number size of the remaining pool 236 at each stage is given and the index of the selectee as per the 237 original number of those in the pool. 239 index hex value of MD5 div selected 240 1 746612D0A75D2A2A39C0A957CF825F8D 25 -> 12 <- 241 2 95E31A4429ED5AAF7377A15A8E10CD9D 24 -> 6 <- 242 3 AFB2B3FD30E82AD6DC35B4D2F1CFC77A 23 -> 8 <- 243 4 06821016C2A2EA14A6452F4A769ED1CC 22 -> 3 <- 244 5 94DA30E11CA7F9D05C66D0FD3C75D6F7 21 -> 2 <- 245 6 2FAE3964D5B1DEDD33FDA80F4B8EF45E 20 -> 24 <- 246 7 F1E7AB6753A773EFE46393515FDA8AF8 19 -> 11 <- 247 8 700B81738E07DECB4470879BEC6E0286 18 -> 19 <- 248 9 1F23F8F8F8E5638A29D332BC418E0689 17 -> 15 <- 249 10 61A789BA86BF412B550A5A05E821E0ED 16 -> 22 <- 251 Resulting selection, in order selected: 253 1. Pendragon (12) 6. Anger (24) 254 2. Grouchy (6) 7. Pollyanna (11) 255 3. Sneazy (8) 8. Chastity (19) 256 4. Bashful (3) 9. Hope (15) 257 5. Mary (2) 10. Sloth (22) 259 6. Security Considerations 261 Careful choice of should be made of randomness inputs so that there 262 is no reasonable suspicion that they are under the control of the 263 administrator. And equal care needs to be given that the algorithm 264 selected is faithfully executed with the designated inputs values. 265 Publication of the results and a week or so window for the community 266 of interest to duplicate the calculations should give a reasonable 267 assurance against implementation tampering. 269 7. Reference Code 271 This code makes use of MD5 reference code from RFC 1321. 273 #include 274 #include 275 #include 276 #include 278 #include "global.h" 279 #include "MD5.h" 281 /* local prototypes */ 282 int longremainder ( unsigned char divisor, 283 unsigned char dividend[16] ); 284 int getinteger ( char *string ); 286 /* limited to 16 inputs of up to sixteen integers each */ 287 /****************************************************************/ 288 main () 289 { 290 int i, j, k, k2, err, keysize, pool, selection; 291 unsigned char unch, uc16[16], remaining; 292 char *selected; 293 long int temp, array[16]; 294 MD5_CTX ctx; 295 char buffer[257], key [525]; 297 pool = getinteger ( "Type size of pool:\n" ); 298 if ( pool > 255 ) 299 { 300 printf ( "Pool too big.\n" ); 301 exit ( 1 ); 302 } 303 selected = (char *) malloc ( pool ); 304 if ( !selected ) 305 { 306 printf ( "Out of memory.\n" ); 307 exit ( 1 ); 308 } 309 selection = getinteger ( "Type number of items to be selected:\n" ); 310 if ( selection > pool ) 311 { 312 printf ( "Pool too small.\n" ); 313 exit ( 1 ); 314 } 315 if ( selection == pool ) 316 { 317 printf ( "All of pool is selected.\n" ); 318 exit ( 0 ); 319 } 320 for ( i = 0, keysize = 0; i < 16; ++i ) 321 { 322 if ( keysize > 500 ) 323 { 324 printf ( "Too much input.\n" ); 325 exit ( 1 ); 326 } 327 /* get the "random" inputs. echo back to user so the user may 328 be able to tell if truncation or other glitches occur. */ 329 printf ( "Type #%d randomness or 'end' followed by new line.\n" 330 "Up to 16 integers or the word 'float' followed by the\n" 331 "before and after decimal point parts.\n", i+1 ); 332 gets ( buffer ); 333 j = sscanf ( buffer, 334 "%ld%ld%ld%ld%ld%ld%ld%ld%ld%ld%ld%ld%ld%ld%ld%ld", 335 &array[0], &array[1], &array[2], &array[3], 336 &array[4], &array[5], &array[6], &array[7], 337 &array[8], &array[9], &array[10], &array[11], 338 &array[12], &array[13], &array[14], &array[15] ); 339 if ( j == EOF ) 340 exit ( j ); 341 if ( !j ) 342 if ( buffer[0] == 'e' ) 343 break; 344 else 345 { 346 j = sscanf ( buffer, "float %ld %ld", 347 &array[0], &array[1] ); 348 if ( j != 2 ) 349 printf ( "Bad format.\n" ); 350 else 351 { /* print for user check */ 352 err = printf ( "%ld.%ld\n", array[0], array[1] ); 353 if ( err <= 0 ) exit ( 1 ); 354 keysize += sprintf ( &key[keysize], "%ld.%ld/", 355 array[0], array[1] ); 356 } 357 } 358 else 359 { /* sort values, not very efficient */ 360 for ( k2 = 0; k2 < j - 1; ++k2 ) 361 for ( k = 0; k < j - 1; ++k ) 362 if ( array[k] > array[k+1] ) 363 { 364 temp = array[k]; 365 array[k] = array[k+1]; 366 array[k+1] = temp; 367 } 368 for ( k = 0; k < j; ++k ) 369 { /* print for user check */ 370 err = printf ( "%ld ", array[k] ); 371 if ( err <= 0 ) exit ( 1 ); 372 keysize += sprintf ( &key[keysize], "%ld.", array[k] ); 373 } 374 err = printf ( "\n" ); 375 if ( err <= 0 ) exit ( 1 ); 376 keysize += sprintf ( &key[keysize], "/" ); 377 } 378 } 379 printf ( "key is:\n %s\n\n", key ); 380 for ( i = 0; i < pool; ++i ) 381 selected [i] = i + 1; 382 printf ( "index hex value of MD5 div selected\n" ); 383 for ( unch = 0, remaining = pool; 384 unch < selection; 385 ++unch, --remaining ) 386 { 387 MD5Init ( &ctx ); 388 MD5Update ( &ctx, &unch, 1 ); 389 MD5Update ( &ctx, (unsigned char *)key, keysize ); 390 MD5Update ( &ctx, &unch, 1 ); 391 MD5Final ( uc16, &ctx ); 392 k = longremainder ( remaining, uc16 ); 393 /* printf ( "Remaining = %d, remainder = %d.\n", remaining, k ); */ 394 for ( j = 0; j < pool; ++j ) 395 if ( selected[j] ) 396 if ( --k < 0 ) 397 { 398 printf ( "%2d " 399 "%02X%02X%02X%02X%02X%02X%02X%02X%02X%02X%02X%02X%02X%02X%02X%02X " 400 "%2d -> %2d <-\n", 401 unch+1, uc16[0],uc16[1],uc16[2],uc16[3],uc16[4],uc16[5],uc16[6], 402 uc16[7],uc16[8],uc16[9],uc16[10],uc16[11],uc16[12],uc16[13],uc16[14], 403 uc16[15], remaining, selected[j] ); 404 selected[j] = 0; 405 break; 406 } 407 } 408 printf ( "\nDone, type any character to exit.\n" ); 409 getchar (); 410 } 412 /* prompt for an integer input */ 413 /****************************************************************/ 414 int getinteger ( char *string ) 415 { 416 int i, j; 417 char tin[257]; 418 while ( 1 ) 419 { 420 printf ( string ); 421 printf ( "(or 'exit' to exit) " ); 422 gets ( tin ); 423 j = sscanf ( tin, "%d", &i ); 424 if ( ( j == EOF ) 425 || ( !j && ( ( tin[0] == 'e' ) || ( tin[0] == 'E' ) ) ) 426 ) 427 exit ( j ); 428 if ( j == 1 ) 429 return i; 430 } /* end while */ 431 } 433 /* get remainder of dividing a 16 byte unsigned int 434 by a small positive number */ 435 /****************************************************************/ 436 int longremainder ( unsigned char divisor, 437 unsigned char dividend[16] ) 438 { 439 int i; 440 long int kruft; 442 if ( !divisor ) 443 return -1; 444 for ( i = 0, kruft = 0; i < 16; ++i ) 445 { 446 kruft = ( kruft << 8 ) + dividend[i]; 447 kruft %= divisor; 448 } 449 return kruft; 450 } 452 References 454 RFC 1321 - "The MD5 Message-Digest Algorithm", R. Rivest. April 1992. 456 RFC 1750 - "Randomness Recommendations for Security", D. Eastlake, 457 3rd, S. Crocker & J. Schiller. December 1994. 459 RFC 2282 - "IAB and IESG Selection, Confirmation, and Recall Process: 460 Operation of the Nominating and Recall Committees", J. Galvin. 461 February 1998. 463 Author's Address 465 Donald E. Eastlake, 3rd 466 IBM 467 318 Acton Street 468 Carlisle, MA 01741 470 tel: +1-978-287-4877 471 +1-914-784-7913 472 fax: +1-978-371-7148 473 email: dee3@us.ibm.com 475 File name and Expiration 477 This file is draft-eastlake-selection-00.txt. 479 It expires April 1999.