idnits 2.17.00 (12 Aug 2021) /tmp/idnits3428/draft-eastlake-selection-04.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** 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? == 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 318 has weird spacing: '... div selec...' == Line 390 has weird spacing: '...ed char unch...' == Line 391 has weird spacing: '...ong int tem...' == Line 504 has weird spacing: '... div selec...' == Line 540 has weird spacing: '... char tin...' -- 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 (March 2000) is 8095 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 1750' on line 188 looks like a reference -- Missing reference section? 'RFC 1321' on line 357 looks like a reference -- Missing reference section? '16' on line 561 looks like a reference -- Missing reference section? '257' on line 540 looks like a reference -- Missing reference section? '800' on line 393 looks like a reference -- Missing reference section? '256' on line 393 looks like a reference -- Missing reference section? '0' on line 549 looks like a reference -- Missing reference section? '1' on line 523 looks like a reference -- Missing reference section? '2' on line 523 looks like a reference -- Missing reference section? '3' on line 523 looks like a reference -- Missing reference section? '4' on line 523 looks like a reference -- Missing reference section? '5' on line 523 looks like a reference -- Missing reference section? '6' on line 523 looks like a reference -- Missing reference section? '7' on line 524 looks like a reference -- Missing reference section? '8' on line 524 looks like a reference -- Missing reference section? '9' on line 524 looks like a reference -- Missing reference section? '10' on line 524 looks like a reference -- Missing reference section? '11' on line 524 looks like a reference -- Missing reference section? '12' on line 524 looks like a reference -- Missing reference section? '13' on line 524 looks like a reference -- Missing reference section? '14' on line 524 looks like a reference -- Missing reference section? '15' on line 525 looks like a reference Summary: 5 errors (**), 0 flaws (~~), 6 warnings (==), 25 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 September 1999 4 Expires March 2000 5 draft-eastlake-selection-04.txt 7 Publicly Verifiable Nomcom Random Selection 8 -------- ---------- ------ ------ --------- 10 Status of this Memo 12 This draft, file name draft-eastlake-selection-04.txt, is intended to 13 become an Informational RFC. Distribution of this document is 14 unlimited. Comments should be sent to the author. 16 This document is an Internet-Draft and is in full conformance with 17 all provisions of Section 10 of RFC2026. Internet-Drafts are working 18 documents of the Internet Engineering Task Force (IETF), its areas, 19 and its working groups. Note that other groups may also distribute 20 working documents as Internet-Drafts. 22 Internet-Drafts are draft documents valid for a maximum of six 23 months. Internet-Drafts may be updated, replaced, or obsoleted by 24 other documents at any time. It is not appropriate to use Internet- 25 Drafts as reference material or to cite them other than as a 26 ``working draft'' or ``work in progress.'' 28 The list of current Internet-Drafts can be accessed at 29 http://www.ietf.org/ietf/1id-abstracts.txt 31 The list of Internet-Draft Shadow Directories can be accessed at 32 http://www.ietf.org/shadow.html. 34 Abstract 36 This document describes a method for making random selections in such 37 a way that the unbiased nature of the choice is publicly verifiable. 38 As an example, the selection of the voting members of the IETF 39 Nominations Committee from the pool of eligible volunteers is used. 40 Similar techniques would be applicable to other cases. 42 Acknowledgement 44 Matt Crawford made major contributions to this document. 46 Table of Contents 48 Status of this Memo........................................1 49 Abstract...................................................1 51 Acknowledgement............................................2 52 Table of Contents..........................................2 54 1. Introduction............................................3 55 2. General Flow of a Publicly Verifiable Process...........3 56 2.1 Determination of the Pool..............................3 57 2.2 Publication of the Algorithm...........................3 58 2.3 Publication of Selection...............................4 59 3. Randomness..............................................4 60 3.1 Sources of Randomness..................................4 61 3.2 Skew...................................................5 62 3.3 Entropy Needed.........................................5 63 4. A Suggested Precise Algorithm...........................6 64 5. Fully Worked Example....................................7 65 6. Security Considerations.................................8 66 7. Reference Code.........................................9 68 Appendix: History of NomCom Member Selection..............15 69 References................................................15 71 Author's Address..........................................16 72 File name and Expiration..................................16 74 1. Introduction 76 Under the IETF rules, each year 10 persons are randomly selected from 77 among the eligible persons who volunteer to be the voting members of 78 the nominations committee (NomCom) to nominate members of the 79 Internet Engineering Steering Group (IESG) and the Internet 80 Architecture Board (IAB) [draft-ietf-poisson-nomcom-v2-*.txt]. The 81 number of eligible volunteers in recent years has varied in the 82 approximate range of 40 to 60. 84 It is highly desireable that the random selection of the voting 85 NomCom be done in a unimpeachable fashion so that no reasonable 86 charges of bias or favoritism can be brought. This is for the 87 protection of the IETF from bias and protection of the administrator 88 of the selection (currently, the appointed non-voting NomCom chair) 89 from suspicion of bias. 91 A method such that public information will enable any person to 92 verify the randomness of the selection meets this criterion. This 93 document gives an example of such a method. 95 2. General Flow of a Publicly Verifiable Process 97 In general, a selection of NomCom members publicly verifiable as 98 unbiased or similar selection could follow the three steps given 99 below. 101 2.1 Determination of the Pool 103 First, you need to determine the pool from which the selection is to 104 be made. 106 Volunteers are solicited by the appointed (non-voting) NomCom chair. 107 Their names are then passed through the IETF Secretariat to check 108 eligibility. (Current eligibility criteria relate to IETF meeting 109 attendance, records of which are maintained by the Secretariat.) The 110 full list of eligible volunteers is made public early enough that 111 there is a reasonable time to resolve any disputes as to who should 112 be in the pool, probably a week to ten days before the selection. 114 2.2 Publication of the Algorithm 116 The exact algorithm to be used, including the public future sources 117 of randomness, is made public. For example, the members of the final 118 list of eligible volunteers are ordered by publicly numbering them, 119 several public future sources of randomness such as government run 120 lotteries are specified, and an exact algorithm is specified whereby 121 eligible volunteers are selected based on a strong hash function [RFC 122 1750] of these future sources of randomness. 124 2.3 Publication of Selection 126 When the prespecified sources of randomness produce their output, 127 those values plus a summary of the execution of the algorithm for 128 selection should be announced so that anyone can verify that the 129 correct randomness source values were used and the algorithm properly 130 executed. A cut off time for any complaint that the algorithm was 131 run with the wrong inputs or not faithfully executed should be 132 specified to finalize the output and provide a stable NomCom. 134 3. Randomness 136 The crux of the unbiased nature of the selection is that it is based 137 exactly on random information which will be revealed in the future 138 and thus can not be known to the person specifying the algorithm by 139 which that random information will be used to select the NomCom 140 members. The random information must be such that it will be 141 publicly revealed in a timely fashion. 143 The random sources should not include anything that any reasonable 144 person would believe to be under the control or influence of the IETF 145 or its components, such as IETF meeting attendance statistics, 146 numbers of documents issued, or the like. 148 3.1 Sources of Randomness 150 Examples of good information to use are lottery winning numbers for 151 specified runnings of specified lotteries. Particularly for 152 government run lotteries, great care is usually taken to see that 153 they produce random quantities. Even in the unlikely case one were 154 to have been rigged, it would almost certainly be in connection with 155 winning money in the lottery, not in connection with IETF use. 157 Other possibilities are such things as the closing price of a stock 158 on a particular day, daily balance in the US Treasury on a specified 159 day, the volume of trading on the New York Stock exchange on a 160 specified day, etc. (However, the reference code given below will not 161 handle integers that are too large.) Sporting events can be used but 162 only with care to specify exactly what quantities are being presumed 163 random and what will be done if they are cancelled or delayed. 165 It is important that the last source of randomness, chronologically, 166 produce a substantial amount of the entropy needed. If most of the 167 randomness has come from the earlier of the specified sources, and 168 someone has even limited influence on the final source, they might do 169 an exhaustive analysis and exert such influence so as to bias the 170 selection in the direction they wanted. Thus it is best for the last 171 source to be an especially strong and unbiased source of a large 172 amount of randomness such as a government run lottery. 174 It is best not to use too many different sources. Every additional 175 source increases the probability that it might be delayed or 176 cancelled calling into play contingency plans or, worst of all, 177 possibly creating a situation that was not anticipated. This would 178 either require arbitrary judgement by the Nomcom chair, defeating the 179 randomness of the selection, or a re-run of with a new set of 180 sources, causing much delay. Probably a good number of sources is 181 three. 183 3.2 Skew 185 Many of the sources of randomness suggested above produce data which 186 is not uniformly distributed. This is certainly true of stock prices 187 and horse race results, for example. However, use of a strong mixing 188 function [RFC 1750] will extract the available entropy and produce a 189 hash value whose bits, remainder modulo a small divisor, etc., are 190 uniformly distributed. 192 3.3 Entropy Needed 194 What we are doing is selection N items without replacement from a 195 population of P items. The number of different ways to do this is as 196 follows, where "!" represents the factorial function: 198 P! 199 ------------- 200 N! * (P - N)! 202 To do this in a completely random fashion requires as many random 203 bits as the logarithm base 2 of that quantity. Some sample 204 calculated approximate number of random bits for the selection of 10 205 nomcom members from various pool sizes is given below: 207 Random Selection of Ten Items From Pool 209 Pool size 20 25 30 35 40 50 60 75 100 210 Bits needed 18 22 25 28 30 34 37 40 44 212 Using an inadequate number of bits means that not all of the possible 213 selections would be available. For a substantially inadequate amount 214 of entropy, there would be substantial correlations between the 215 selection of two members of the pool, for example. However, as a 216 practical matter, for pool sizes likely to be encountered in IETF 217 nomcom membership selection, 40 bits of entropy should always be 218 adequate. Even if there is a large pool and theoretically more bits 219 are needed for complete randomness, 40 bits of entropy will assure 220 that the probability of selection of each pool member differs from 221 that of other pool members, the correlation between the selection of 222 any pair of pool members, etc., differs only insignificantly from 223 that for completely random selection. 225 An MD5 [RFC 1321] hash has 128 bits and therefore can produce no more 226 than that number of bits of entropy. However, this is three times 227 what is likely to ever been needed for IETF nomcom membership 228 selection. 230 4. A Suggested Precise Algorithm 232 It is important that a precise algorithm be given for mixing the 233 random sources specified and making the selection based thereon. 234 Sources suggested above each produce either a single positive number 235 (i.e., closing price for a stock) or a small set of positive numbers 236 (many lotteries provide 6 numbers in the range of 1 through 40 or the 237 like, a sporting event could produce the scores of two teams, etc.). 238 A sample precise algorithm is as follows: 240 For each source producing multiple numeric values, represent each as 241 a decimal number terminated by a period (or with a period separating 242 the whole from the fractional part) and without leading zeroes 243 (except for a single leading zero if the integer part is zero) or 244 trailing zeroes after the period. Order them from smallest to the 245 largest and concatenate them and follow the results by a "/". For 246 each source producing a single number, simply represent it as above 247 with a trailing "/". At this point you have a string for each 248 source, say s1/, s2/, ... Concatenate these strings in a pre- 249 specified order and represent each character as its ASCII code 250 producing s1/s2/.../. 252 You can then produce a sequence of random values derived from a 253 strong mixing of these sources by calculating the MD5 hash [RFC 1321] 254 of this string prefixed and suffixed with a zero byte for the first 255 value, the string prefixed and suffixed by a 0x01 byte for the second 256 value, etc. Treat each of these derived random values as a positive 257 multiprecision integer. If there are P eligible volunteers, select 258 the first voting member by dividing the first derived random value by 259 P and using the remainder plus one as the position of the selectee in 260 the ordered list or volunteers. Select the second voting member by 261 dividing the second derived random value by P-1 and using the 262 remainder plus one as the position of the selectee in the list with 263 the first selectee eliminated. Etc. 265 It is recommended that alphanumeric random sources be avoided due to 266 the greater difficulty in canonicalizing them in an independently 267 repeatable fashion; however, if any are used, all white space, 268 punctuation, and special characters should be removed and all letters 269 set to upper case. This will leave only an unbroken sequence of 270 letters A-Z and digits 0-9 which can be treated as a canonicalized 271 number above and suffixed with a "/". 273 5. Fully Worked Example 275 Assume the following ordered list of 25 eligible volunteers is 276 published in advance of selection: 278 1. John 11. Pollyanna 21. Pride 279 2. Mary 12. Pendragon 22. Sloth 280 3. Bashful 13. Pandora 23. Envy 281 4. Dopey 14. Faith 24. Anger 282 5. Sleepy 15. Hope 25. Kasczynski 283 6. Grouchy 16. Charity 284 7. Doc 17. Love 285 8. Sneazy 18. Longsuffering 286 9. Handsome 19. Chastity 287 10. Cassandra 20. Smith 289 Assume the following (fake example) ordered list of randomness 290 sources: 291 1. The People's Democracy of Betastani State Lottery six winning 292 numbers (ignoring the seventh "extra" number) for 1 October 1998. 293 2. Numbers of the winning horses at Hialeia for all races for the 294 first day on or after x September 1998 on which at least two races 295 are run. 296 3. The Republic of Alphaland State Lottery daily number for 1 297 October 1998 treated as a single four digit integer. 298 4. Closing price of Example Corporation stock on the Lunar Stock 299 Exchange for the first business day after x September 1998 when it 300 trades. 302 Randomness publicly produced: 303 Source 1: 9, 18, 26, 34, 41, 45 304 Source 2: 2, 5, 12, 8, 10 305 Source 3: 9319 306 Source 4: 13 11/16 308 Resulting key string: 310 9.18.26.34.41.45./2.5.8.10.12./9319./13.6875/ 312 The table below gives the hex of the MD5 of the above key string 313 bracketed with a byte whose value is successively 0x00, 0x01, 0x02, 314 through 0x09. The divisor for the number size of the remaining pool 315 at each stage is given and the index of the selectee as per the 316 original number of those in the pool. 318 index hex value of MD5 div selected 319 1 746612D0A75D2A2A39C0A957CF825F8D 25 -> 12 <- 320 2 95E31A4429ED5AAF7377A15A8E10CD9D 24 -> 6 <- 321 3 AFB2B3FD30E82AD6DC35B4D2F1CFC77A 23 -> 8 <- 322 4 06821016C2A2EA14A6452F4A769ED1CC 22 -> 3 <- 323 5 94DA30E11CA7F9D05C66D0FD3C75D6F7 21 -> 2 <- 324 6 2FAE3964D5B1DEDD33FDA80F4B8EF45E 20 -> 24 <- 325 7 F1E7AB6753A773EFE46393515FDA8AF8 19 -> 11 <- 326 8 700B81738E07DECB4470879BEC6E0286 18 -> 19 <- 327 9 1F23F8F8F8E5638A29D332BC418E0689 17 -> 15 <- 328 10 61A789BA86BF412B550A5A05E821E0ED 16 -> 22 <- 330 Resulting selection, in order selected: 332 1. Pendragon (12) 6. Anger (24) 333 2. Grouchy (6) 7. Pollyanna (11) 334 3. Sneazy (8) 8. Chastity (19) 335 4. Bashful (3) 9. Hope (15) 336 5. Mary (2) 10. Sloth (22) 338 6. Security Considerations 340 Careful choice of should be made of randomness inputs so that there 341 is no reasonable suspicion that they are under the control of the 342 administrator. Guidelines given above to use a small number of 343 inputs with a substantial amout of entropy from the last shoud be 344 followed. And equal care needs to be given that the algorithm 345 selected is faithfully executed with the designated inputs values. 346 Publication of the results and a week or so window for the community 347 of interest to duplicate the calculations should give a reasonable 348 assurance against implementation tampering. 350 To maintain the unpredicatable character of selections, should a 351 member of the nomcom need to be replaced due to death, resignation, 352 expulsion, etc., new publicly announced future random sources should 353 be used for the selection of their replacement. 355 7. Reference Code 357 This code makes use of the MD5 reference code from [RFC 1321] ("RSA 358 Data Security, Inc. MD5 Message-Digest Algorithm"). The portion of 359 the code dealing with multiple floating point numbers was written by 360 Matt Crawford. 362 /**************************************************************** 363 * 364 * Reference code for 365 * "Publicly Verifiable Nomcom Random Selection" 366 * Donald E. Eastlake 3rd 367 * 368 ****************************************************************/ 369 #include 370 #include 371 #include 372 #include 373 #include 375 #include "global.h" 376 #include "MD5.h" 378 /* local prototypes */ 379 int longremainder ( unsigned char divisor, 380 unsigned char dividend[16] ); 381 int getinteger ( char *string ); 382 double NPentropy ( int N, int P ); 384 /* limited to 16 inputs of up to sixteen integers each */ 385 /****************************************************************/ 387 main () 388 { 389 int i, j, k, k2, err, keysize, pool, selection; 390 unsigned char unch, uc16[16], remaining, *selected; 391 long int temp, array[16]; 392 MD5_CTX ctx; 393 char buffer[257], key [800], sarray[16][256]; 395 pool = getinteger ( "Type size of pool:\n" ); 396 if ( pool > 255 ) 397 { 398 printf ( "Pool too big.\n" ); 399 exit ( 1 ); 400 } 401 selected = (unsigned char *) malloc ( pool ); 402 if ( !selected ) 403 { 404 printf ( "Out of memory.\n" ); 405 exit ( 1 ); 406 } 407 selection = getinteger ( "Type number of items to be selected:\n" ); 408 if ( selection > pool ) 409 { 410 printf ( "Pool too small.\n" ); 411 exit ( 1 ); 412 } 413 if ( selection == pool ) 414 { 415 printf ( "All of the pool is selected.\n" ); 416 exit ( 0 ); 417 } 418 err = printf ( "Approximately %.1f bits of entropy needed.\n", 419 NPentropy ( selection, pool ) + 0.1 ); 420 if ( err <= 0 ) exit ( 1 ); 421 for ( i = 0, keysize = 0; i < 16; ++i ) 422 { 423 if ( keysize > 500 ) 424 { 425 printf ( "Too much input.\n" ); 426 exit ( 1 ); 427 } 428 /* get the "random" inputs. echo back to user so the user may 429 be able to tell if truncation or other glitches occur. */ 430 err = printf ( 431 "\nType #%d randomness or 'end' followed by new line.\n" 432 "Up to 16 integers or the word 'float' followed by up\n" 433 "to 16 x.y format reals.\n", i+1 ); 434 if ( err <= 0 ) exit ( 1 ); 435 gets ( buffer ); 436 j = sscanf ( buffer, 437 "%ld%ld%ld%ld%ld%ld%ld%ld%ld%ld%ld%ld%ld%ld%ld%ld", 438 &array[0], &array[1], &array[2], &array[3], 439 &array[4], &array[5], &array[6], &array[7], 440 &array[8], &array[9], &array[10], &array[11], 441 &array[12], &array[13], &array[14], &array[15] ); 442 if ( j == EOF ) 443 exit ( j ); 444 if ( !j ) 445 if ( buffer[0] == 'e' ) 446 break; 448 else 449 { /* floating point code by Matt Crawford */ 450 j = sscanf ( buffer, 451 "float %ld.%[0-9]%ld.%[0-9]%ld.%[0-9]%ld.%[0-9]" 452 "%ld.%[0-9]%ld.%[0-9]%ld.%[0-9]%ld.%[0-9]" 453 "%ld.%[0-9]%ld.%[0-9]%ld.%[0-9]%ld.%[0-9]" 454 "%ld.%[0-9]%ld.%[0-9]%ld.%[0-9]%ld.%[0-9]", 455 &array[0], sarray[0], &array[1], sarray[1], 456 &array[2], sarray[2], &array[3], sarray[3], 457 &array[4], sarray[4], &array[5], sarray[5], 458 &array[6], sarray[6], &array[7], sarray[7], 459 &array[8], sarray[8], &array[9], sarray[9], 460 &array[10], sarray[10], &array[11], sarray[11], 461 &array[12], sarray[12], &array[13], sarray[13], 462 &array[14], sarray[14], &array[15], sarray[15] ); 463 if ( j == 0 || j & 1 ) 464 printf ( "Bad format." ); 465 else { 466 for ( k = 0, j /= 2; k < j; k++ ) 467 { 468 /* strip trailing zeros */ 469 for ( k2=strlen(sarray[k]); sarray[k][--k2]=='0';) 470 sarray[k][k2] = '\0'; 471 err = printf ( "%ld.%s\n", array[k], sarray[k] ); 472 if ( err <= 0 ) exit ( 1 ); 473 keysize += sprintf ( &key[keysize], "%ld.%s", 474 array[k], sarray[k] ); 475 } 476 keysize += sprintf ( &key[keysize], "/" ); 477 } 478 } 479 else 480 { /* sort values, not a very efficient algorithm */ 481 for ( k2 = 0; k2 < j - 1; ++k2 ) 482 for ( k = 0; k < j - 1; ++k ) 483 if ( array[k] > array[k+1] ) 484 { 485 temp = array[k]; 486 array[k] = array[k+1]; 487 array[k+1] = temp; 488 } 489 for ( k = 0; k < j; ++k ) 490 { /* print for user check */ 491 err = printf ( "%ld ", array[k] ); 492 if ( err <= 0 ) exit ( 1 ); 493 keysize += sprintf ( &key[keysize], "%ld.", array[k] ); 494 } 495 keysize += sprintf ( &key[keysize], "/" ); 496 } 497 } /* end for i */ 499 /* have obtained all the input, now produce the output */ 500 err = printf ( "Key is:\n %s\n", key ); 501 if ( err <= 0 ) exit ( 1 ); 502 for ( i = 0; i < pool; ++i ) 503 selected [i] = i + 1; 504 printf ( "index hex value of MD5 div selected\n" ); 505 for ( unch = 0, remaining = pool; 506 unch < selection; 507 ++unch, --remaining ) 508 { 509 MD5Init ( &ctx ); 510 MD5Update ( &ctx, &unch, 1 ); 511 MD5Update ( &ctx, (unsigned char *)key, keysize ); 512 MD5Update ( &ctx, &unch, 1 ); 513 MD5Final ( uc16, &ctx ); 514 k = longremainder ( remaining, uc16 ); 515 /* printf ( "Remaining = %d, remainder = %d.\n", remaining, k ); */ 516 for ( j = 0; j < pool; ++j ) 517 if ( selected[j] ) 518 if ( --k < 0 ) 519 { 520 printf ( "%2d " 521 "%02X%02X%02X%02X%02X%02X%02X%02X%02X%02X%02X%02X%02X%02X%02X%02X " 522 "%2d -> %2d <-\n", 523 unch+1, uc16[0],uc16[1],uc16[2],uc16[3],uc16[4],uc16[5],uc16[6], 524 uc16[7],uc16[8],uc16[9],uc16[10],uc16[11],uc16[12],uc16[13],uc16[14], 525 uc16[15], remaining, selected[j] ); 526 selected[j] = 0; 527 break; 528 } 529 } 530 printf ( "\nDone, type any character to exit.\n" ); 531 getchar (); 532 return 0; 533 } 535 /* prompt for an integer input */ 536 /****************************************************************/ 537 int getinteger ( char *string ) 538 { 539 int i, j; 540 char tin[257]; 542 while ( 1 ) 543 { 544 printf ( string ); 545 printf ( "(or 'exit' to exit) " ); 546 gets ( tin ); 547 j = sscanf ( tin, "%d", &i ); 548 if ( ( j == EOF ) 549 || ( !j && ( ( tin[0] == 'e' ) || ( tin[0] == 'E' ) ) ) 550 ) 551 exit ( j ); 552 if ( j == 1 ) 553 return i; 554 } /* end while */ 555 } 557 /* get remainder of dividing a 16 byte unsigned int 558 by a small positive number */ 559 /****************************************************************/ 560 int longremainder ( unsigned char divisor, 561 unsigned char dividend[16] ) 562 { 563 int i; 564 long int kruft; 566 if ( !divisor ) 567 return -1; 568 for ( i = 0, kruft = 0; i < 16; ++i ) 569 { 570 kruft = ( kruft << 8 ) + dividend[i]; 571 kruft %= divisor; 572 } 573 return kruft; 574 } /* end longremainder */ 576 /* calculate how many bits of entropy it takes to select N from P */ 577 /****************************************************************/ 578 /* P! 579 log ( ----------------- ) 580 2 N! * ( P - N )! 581 */ 583 double NPentropy ( int N, int P ) 584 { 585 int i; 586 double result = 0.0; 588 if ( ( N < 1 ) /* not selecting anything? */ 589 || ( N >= P ) /* selecting all of pool or more? */ 590 ) 591 return 1.0; /* degenerate case */ 593 for ( i = P; i > ( P - N ); --i ) 594 result += log ( i ); 595 for ( i = N; i > 1; --i ) 596 result -= log ( i ); 597 /* divide by [ log (base e) of 2 ] to convert to bits */ 598 result /= 0.69315; 599 return result; 600 } /* end NPentropy */ 602 Appendix: History of NomCom Member Selection 604 For reference purposes, here is a list of the IETF Nominations 605 Committee member selection techniques and chairs so far: 607 YEAR CHAIR SELECTION METHOD 609 1993/1994 Jeff Case Clergy 610 1994/1995 Fred Baker Clergy 611 1995/1996 Guy Almes Clergy 612 1996/1997 Geoff Huston Spouse 613 1997/1998 Mike St.Johns Algorithm 614 1998/1999 Donald Eastlake 3rd This Algorithm 615 1999/2000 Avri Doria This Alogrithm 617 Clergy = Names were written on pieces of paper, placed in a 618 receptacle, and a member of the clergy picked the Nomcom members. 620 Spouse = Same as Clergy except chair's spouse made the selection. 622 Algorithm = Algorithmic selection based on the same concepts as 623 documented herein. 625 This Algorithm = Algorithmic selection using the algorithm and 626 reference code (but not the fake example sources of randomness) 627 described herein. 629 References 631 RFC 1321 - "The MD5 Message-Digest Algorithm", R. Rivest. April 1992. 633 RFC 1750 - "Randomness Recommendations for Security", D. Eastlake, 634 3rd, S. Crocker & J. Schiller. December 1994. 636 [draft-ietf-poisson-nomcom-v2-*.txt] - "IAB and IESG Selection, 637 Confirmation, and Recall Process: Operation of the Nominating and 638 Recall Committees", J. Galvin. 640 Author's Address 642 Donald E. Eastlake, 3rd 643 IBM 644 65 Shindegan Hill Road, RR #1 645 Carmel, NY 10512 USA 647 tel: +1-914-276-2668 (h) 648 +1-914-784-7913 (w) 649 fax: +1-914-784-3833 (w) 650 email: dee3@us.ibm.com 652 File name and Expiration 654 This file is draft-eastlake-selection-04.txt. It expires March 2000.