Random Recipes

Secure Programming Cookbook Unix & Windows Secure Programming Cookbook for C and C++ Secure Programming Cookbook for C and C++ John Viega and Matt Messier Copyright � 2003 O�Reilly & Associates, Inc. All rights reserved. 568 Chapter11 Security-criticalapplicationsoftenrequirewell-chosenrandomnumbers,forpur- posesrangingfromcryptographickeygenerationtoshufflingavirtualdeckofcards. Eventhoughproblemswithrandomnumbersseemasiftheyshouldbefewandfar Copyright � 2003 O�Reilly & Associates, Inc. All rights reserved. Solution Moreproperly,thesearenoncryptographicpseudo-randomnumbergenerators. Youshouldgenerallyassumethatanattackercouldpredicttheoutputofsucha Thesetakeasinglesecureseedandproduceasmanyunguessablerandomnum- bersfromthatseedasnecessary.Suchasolutionshouldbesecureformostuses Chapter11:Random Numbers Notethatcryptographicpseudo-randomnumbergeneratorsalwaysproduceaniden- ticalstreamofoutputwhenidenticallyseeded.Ifyouwishtorepeatastreamof numbers,youshouldavoidreseedingthegenerator(oryouneedtodotheexact Mostcommon�randomnumbergenerators,�whichwewillcall pseudo-randomnumbergenerators ,arenotsecure.Theystartwithaseed(which needstoberandominandofitselftohaveanychanceofsecurity)andusethatseed toproduceastreamofnumbersthatlookrandomfromthepointofviewofastatisti- Fromthepointofviewofagoodcryptographer,though,thenumbersproducedby suchageneratorarenotsecure.Generally,noncryptographicgeneratorsleakinfor- mationabouttheirinternalstatewitheachoutput,meaningthatagoodcryptogra- phercanstartpredictingoutputswithhighaccuracyafterseeingafewrandom numbers.Inarealsystem,yougenerallydonotevenneedtoseetheoutputsdirectly, insteadinferringinformationabouttheoutputsfromthebehavioroftheprogram (whichisgenerallymadeeveneasierwithabitofreverseengineeringofthepro- Traditionalnoncryptographicpseudo-randomnumbergeneratorsincludethe rand() random() functionsyou�dexpecttoseeinmostlibraries(so-calledlinearcongru- entialgenerators).Othernoncryptographicgeneratorsincludethe�Mersenne Twister�andlinearfeedbackshiftregisters.Ifarandomnumbergeneratorisnot advertisedasacryptographicrandomnumbergenerator,anditdoesnotoutput Copyright � 2003 O�Reilly & Associates, Inc. All rights reserved. thebyteiseven,hereducesthenumberofguessesnecessaryto2 (128),inwhich Wecanhavefractionalbitsofentropy.Ifwehaveonebit,andithasa25%chanceof Inpublickeycryptography, -bitkeyscontainfarfewerthan bitsof entropy.Thatisbecausetherearenot2 possiblekeys.Forexample, inRSA,wearemoreorlesslimitedbythenumberofprimesthatare Chapter11:Random Numbers Finally,youneedtorealizethatevenproperlyusedcryptographicpseudo-random numbergeneratorsareonlygoodforacertainnumberofbytesofoutput,though IfabreakintheunderlyingPRNGalgorithmweretobefound,itmightbepossible Therefore,ifyouaregeneratingveryimportantdata,suchaslong-termcrypto- graphickeys,generatethosekeysbytakingdatadirectlyfromanentropysourceif Tips on Collecting Entropy �Makesurethatanydatacomingfromanentropy-producingsourceispostpro- cessedwithcryptographytoremoveanylingeringstatisticalbiasandtohelp ensurethatyourdatahasatleastasmanybitsofentropyinputasbitsyouwant �Makesureyouuseenoughentropytoseedanypseudo-randomnumbergenera- �Whenchoosingapseudo-randomnumbergenerator,makesuretopickonethat explicitlyadvertisesthatitiscryptographicallystrong.Ifyoudonotseetheword �cryptographic�anywhereinassociationwiththealgorithm,itisprobablynot �WhenselectingaPRNG,prefersolutionswitharefereedproofofsecurity bounds.Countermode,inparticular,comeswithsuchaproof,sayingthatif youuseablockcipherbitwith128-bitkeysand128-bitblocksseededwith128 bitsofpureentropy,andifthecipherisapseudo-randompermutation,thegen- �Usepostprocessedentropyforseedingpseudo-randomnumbergeneratorsor,if available,forpickinghighlyimportantcryptographickeys.Foreverythingelse, Copyright � 2003 O�Reilly & Associates, Inc. All rights reserved. Using a Generic API for Randomness and Entropy | 573 See Also 11.2Using a Generic API for Randomness and Entropy Problem Chapter11:Random Numbers Thefunctions spc_keygen() spc_entropy() shouldcryptographi- callypostprocess(whiten)anyentropytheyusebeforeoutputtingit,if that�snotalreadydonebytheunderlyingentropysources.Often,it willbedoneforyou,butitwillnothurttodoitagainifyouarenot See Also Copyright � 2003 O�Reilly & Associates, Inc. All rights reserved. Using the Standard Unix Randomness Infrastructure | 575 11.3Using the Standard Unix Randomness Infrastructure Problem Solution OnmostmodernUnixsystems,therearetwodevicesfromwhichyoucanread: ,whichisexpectedtoproduceentropy,and ,whichisexpected toprovidecryptographicallysecurepseudo-randomvalues.Inreality,theseexpecta- Ifyouneedacryptographicallystrongrandomnumbersourcethatis Chapter11:Random Numbers don�tthinkyoushouldworryaboutthisissueinpractice.(Therearealmostalways Second,dependingontheoperatingsystem,theentropyproducedby maybereusedby .Whilefew(ifany)Unixplatformstrytoguaranteea Copyright � 2003 O�Reilly & Associates, Inc. All rights reserved. Using the Standard Unix Randomness Infrastructure | 577 Chapter11:Random Numbers spc_rand() byreadingfrom .Finally,wewillimplement spc_keygen() byreadingasmuchdataaspossiblefrom inanonblockingfashion,then Notethatweneedtoopen ontwofiledescriptors,oneblockingand onenot,sothatwemayavoidraceconditionswhere spc_keygen() expectsafunc- tiontobenonblockingbut spc_entropy() Copyright � 2003 O�Reilly & Associates, Inc. All rights reserved. Using the Standard Unix Randomness Infrastructure | 579 if (errno == EINTR) continue; Chapter11:Random Numbers 11.4Using the Standard Windows Randomness Infrastructure Problem Solution CryptGenRandom() unlessyouabsolutelyneedentropy,inwhichcaseseeRecipe CryptAcquireContext() Numberofbytesofrandomdatarequired.Theoutputbuffermustbeatleast Copyright � 2003 O�Reilly & Associates, Inc. All rights reserved. Using an Application-Level Generator | 581 if (!hProvider) spc_rand_init(); Solution Forgeneral-purposeuse,werecommendapseudo-randomnumbergeneratorbased ontheAESencryptionalgorithmrunincounter(CTR)mode(seeRecipe5.9).This Chapter11:Random Numbers Streamciphersareactuallycryptographicpseudo-randomnumbergenerators.One Copyright � 2003 O�Reilly & Associates, Inc. All rights reserved. Using an Application-Level Generator | 583 attacksarearealisticthreat,youwillusuallyhavefarbiggerthreats,andmitigating Thereisalotthatcangowrongwhenusingapseudo-randomnumbergenerator. Comingupwithagoodconstructturnsouttobetheeasypart.Herearesomethings �Pseudo-randomnumbergeneratorsneedtobeseededwithanadequateamount ofentropy;otherwise,theyarestillpotentiallypredictable.Werecommendat least80bits.Seethevariousrecipeselsewhereinthischapterforinformationon �Becarefultopayattentiontothemaximumnumberofoutputsageneratorcan producebeforeitwillneedtobereseededwithnewentropy.Atsomepoint,gen- eratorsstarttoleakinformationandwillgenerallyfallintoacycle.Note, though,thatfortheconfigurationswepresent,youwillprobablyneverneedto worryaboutthelimitinpractice.Forexample,thegeneratorbasedonAES-128 leaksabitofinformationafter2 16-byteblocksofoutput,andcyclesafter2 �Whenaddingentropytoasystem,itisbesttocollectalotofentropyandseed allatonce,insteadofseedingalittlebitatatime.Wewillillustratewhyby example.Supposethatyouseedageneratorwithonebitofentropy.Anattacker hasonlyonebittoguess,whichcanbedoneaccuratelyaftertwooutputs.Ifthe Chapter11:Random Numbers Theseedshouldbeatleastaslargeasthekeysizeofthecipher,becauseitwillbe usedtokeyablockcipher.Inaddition,itisusefultohaveadditionalseeddatathat Copyright � 2003 O�Reilly & Associates, Inc. All rights reserved. Using an Application-Level Generator | 585 Chapter11:Random Numbers prng-ix = 0; prng-kl = kl; SPC_BCPRNG_UNLOCK(); SPC_BCPRNG_LOCK(); prng-ix %= SPC_BLOCK_SZ; } while (l = SPC_BLOCK_SZ) { SPC_DO_ENCRYPT(&(prng-ks), prng-ctr, p); spc_increment_counter(prng); p += SPC_BLOCK_SZ; l -= SPC_BLOCK_SZ; } if (l) { SPC_DO_ENCRYPT(&(prng-ks), prng-ctr, prng-lo); spc_increment_counter(prng); prng-ix = l; while (l--) p[l] = prng-lo[l]; } SPC_BCPRNG_UNLOCK(); Copyright � 2003 O�Reilly & Associates, Inc. All rights reserved. Using an Application-Level Generator | 587 Using a stream cipher as a generator Aswementioned,streamciphersarethemselvespseudo-randomnumbergenera- tors,wherethekey(andtheinitializationvector,ifappropriate)constitutestheseed. Ifyouareplanningtousesuchacipher,westronglyrecommendtheSNOW2.0 BecauseofthepopularityoftheRC4cipher,weexpectthatpeoplewillprefertouse RC4,eventhoughitdoesnotlookasgoodasSNOW.TheRC4streamcipherdoes makeanacceptablepseudo-randomnumbergenerator,anditisincrediblyfastifyou donotrekeyfrequently(thatisparticularlyusefulifyouexpecttoneedaheckofa lotofnumbers).Ifyoudorekeyfrequentlytoavoidbacktrackingattacks,ablock RC4requiresalittlebitofworktouseproperly,givenastandardAPI.First,most APIswantyoutopassindatatoencrypt.Becauseyouwantonlytherawkeystream, youmustalwayspassinzeros.Second,besuretouseRC4inasecuremanner,as IfyourRC4implementationhastheAPIdiscussedinRecipe5.23,seedingitasa pseudo-randomnumbergeneratoristhesameaskeyingthealgorithm.RC4can BecauseoflimitationsinRC4,youshouldthrowawaythefirst256 Afterencrypting256bytesandthrowingtheresultsaway,youcanthen,givenan Chapter11:Random Numbers #define SPC_RC4RNG_UNLOCK() ReleaseMutex(hSpcRC4RNGMutex) unsigned char *p = buf;#ifdef WIN32 if (!hSpcRC4RNGMutex) hSpcRC4RNGMutex = CreateMutex(0, FALSE, 0);#endif SPC_RC4RNG_LOCK(); SPC_RC4RNG_UNLOCK(); RC4isonlybelievedtobeastrongsourceofrandomnumbersfor about2 outputs.Afterthat,westronglyrecommendthatyoureseed itwithnewentropy.Ifyourapplicationwouldnotconceivablyuse thatmanyoutputs,itshouldgenerallybeokaynottocheckthatcon- Using a generator based on a cryptographic hash function Themostcommonmistakemadewhentryingtouseahashfunctionasacrypto- graphicpseudo-randomnumbergeneratoristocontinuallyhashapieceofdata. Suchanapproachgivesawaythegenerator�sinternalstatewitheveryoutput.For example,supposethatyourinternalstateissomevalueX,andyougenerateandout- putYbyhashingX.Thenexttimeyouneedrandomdata,rehashingXwillgivethe sameresults,andanyattackerwhoknowsthelastoutputsfromthegeneratorcan Copyright � 2003 O�Reilly & Associates, Inc. All rights reserved. Using an Application-Level Generator | 589 Oneverysafewaytouseacryptographichashfunctioninacryptographicpseudo- randomnumbergeneratoristouseHMACincountermode,asdiscussedinRecipe 6.10.HereweimplementageneratorbasedontheHMAC-SHA1implementation fromRecipe6.10.YoushouldbeabletoadaptthiscodeeasilytoanyHMACimple- unsigned char lo[MAC_OUT_SZ]; /* Leftover block of output */ int ix; /* index into lo. */} SPC_MPRNG_CTX;#ifndef WIN32static pthread_mutex_t spc_mprng_mutex = PTHREAD_MUTEX_INITIALIZER;#define SPC_MPRNG_LOCK() pthread_mutex_lock(&spc_mprng_mutex) #define SPC_MPRNG_UNLOCK() pthread_mutex_unlock(&spc_mprng_mutex) #define SPC_MPRNG_LOCK() WaitForSingleObject(hSpcMPRNGMutex, INFINITE) #define SPC_MPRNG_UNLOCK() ReleaseMutex(hSpcMPRNGMutex) Chapter11:Random Numbers SPC_MPRNG_UNLOCK(); SPC_MPRNG_LOCK(); Copyright � 2003 O�Reilly & Associates, Inc. All rights reserved. Reseeding a Pseudo-Random Number Generator | 591 Ifyourhashfunctionproduces -bitoutputsandhasnopracticalweaknesses,donot usethegeneratorafteryouruntheMACmorethan2 times.Forexample,with SHA1,thisgeneratorshouldbenotbeaproblemforatleast2 20bytes.Inprac- Tobindthiscryptographicpseudo-randomnumbergeneratortotheAPIinRec- ipe11.2,youcanuseasingleglobalgeneratorcontextthatyouseedin init() Chapter11:Random Numbers TherearetwocommonreasonswhyyoumaywanttoreseedaPRNG.First,your threatmodelmayincludethepossibilityoftheinternalstateofyourPRNGbeing compromised,andyouwanttopreventagainstanattacker�sbeingabletofigureout numbersthatwereoutputbeforethestatecompromise.Reseeding,ifdoneright, essentiallytransformstheinternalstateinawaythatpreservesentropywhilemak- ingitessentiallyimpossibletobacktrack.Protectingagainstbacktrackingattackscan Second,youmaywanttoaddentropyintothestate.Thiscouldserveanumberof purposes.Forexample,youmightwanttoaddentropytothesystem.Remember, however,thatcryptographicgeneratorshaveamaximumamountofentropythey Whenavailable,however,reseedingwithentropyisagoodconservativemeasure,for severalreasons.Foronereason,ifyouhaveunderestimatedtheamountofentropy thatageneratorhas,addingentropyisagoodthing.Foranother,ifthegeneratorhas lostanyentropy,newentropycanhelpreplenishit.Suchentropylossisnatural Whenaddingentropytoasystem,itisbesttocollectalotofentropy andseedallatonce,insteadofseedingalittlebitatatime.Wewill illustratewhybyexample.Supposeyouseedageneratorwithonebit ofentropy.Anattackerhasonlyonebittoguess,whichcanbedone Copyright � 2003 O�Reilly & Associates, Inc. All rights reserved. Reseeding a Pseudo-Random Number Generator | 593 1.Figureouthowbigaseedyouneed.Attheveryleast,youneedaseedthatisas manybitsinlengthasbitsofentropyyouthinkareinthegenerator.Generally, thiswillbeatleastaslargeasthekeysizeoftheunderlyingprimitive(ortheout- 2.Ifyouneedtointroducenewentropy,properlycompressthedatacontaining entropy.Inparticular,youmusttransformthedataintoaseedoftheproper size,withminimallossofentropy.Oneeasywaytodothatistoprocessthe stringwithacryptographichashfunction(truncatingthehashoutputtothe desiredlength,ifnecessary).ThenXORthecompressedentropywiththeseed 3.Takethevalueanduseittoreseedthegenerator.Ifyouareusingacounter- Chapter11:Random Numbers 11.7Using an Entropy Gathering Daemon�Compatible Solution Problem Yourapplicationneedsrandomness,andyouwantittobeabletorunonUnix-based platformsthatlackthe devicesdiscussedinRecipe Solution Useathird-partysoftwarepackagethatgathersandoutputsentropy,suchasthe EntropyGatheringandDistributionSystem(EGADS).ThenusetheEntropyGather- ingDaemon(EGD)interfacetoreadentropy.EGDisatoolforentropyharvesting WhenimplementingourrandomnessAPIfromRecipe11.2,useentropygathered overtheEGDinterfaceinplaceswhereentropyisneeded;then,toimplementthe restoftheAPI,usedatafromthatinterfacetoseedanapplication-levelcrypto- Afewentropycollectionsystemsexistasprocessesoutsidethekernelanddistribute Copyright � 2003 O�Reilly & Associates, Inc. All rights reserved. Using an Entropy Gathering Daemon�Compatible Solution | 595 Querytheamountofentropybelievedtobeavailable.Thisinformationisnotat alluseful,particularlybecauseyoucannotuseitinanydecisiontoreaddata Readdataifavailable.Thiscommandtakesasingle-byteargumentspecifying howmanybytesofdatashouldberead,ifthatmuchdataisavailable.Ifnot Chapter11:Random Numbers process.WhileEGADSimplementstheEGDinterface,itignorestheentropyesti- matesuppliedbytheuser.Itdoesmixtheentropyintoitsstate,butitassumesthatit Thefollowingcodeimplementsthe spc_entropy() spc_keygen() fromRecipe11.2usingtheEGDinterface.Weomit spc_rand() butassumethatit exists(itiscalledby spc_keygen() whenappropriate).Toimplement spc_rand() Whenimplementing spc_entropy() spc_keygen() ,wedonotcryptographically postprocesstheentropytothwartstatisticalanalysisifwedonothaveasmuch entropyasestimated,asyoucangenerallyexpectserversimplementingtheEGD interfacetodothis(EGADScertainlydoes).Ifyouwanttobeabsolutelysure,you Notethatthefollowingcoderequiresyoutoknowinadvancethefileonthefilesys- temthatimplementstheEGDinterface.ThereisnostandardplacetolookforEGD Copyright � 2003 O�Reilly & Associates, Inc. All rights reserved. Using an Entropy Gathering Daemon�Compatible Solution | 597 Chapter11:Random Numbers Copyright � 2003 O�Reilly & Associates, Inc. All rights reserved. } while (nb == -1); See Also �EGADS by Secure Software, Inc.: �Recipes 2.4, 11.2, 11.3, 11.5, 11.16, 11.19 Chapter11:Random Numbers onthestrengthoftheAEScryptographicalgorithm.EGADSdoesagoodjobofpro- tectingagainstcompromisedentropysources,whichotherPRNGstendnottodo.It alsoprovidesagoodamountofprotectionagainstbacktrackingattacks,meaning rentlyavailabletosatisfytherequest,thisfunctionwillblockuntilthereis.Itssigna- spc_entropy() Copyright � 2003 O�Reilly & Associates, Inc. All rights reserved. Numberofbytesofentropythatshouldbewrittenintotheoutputbuffer.You mustbesurethattheoutputbufferissufficientlylargetoholdtherequested Ifanyerroroccurs,anerrorcodewillbestoredinthisargument.Avalueof0 indicatesthatnoerroroccurred;otherwise,oneofthe constantsdefined Chapter11:Random Numbers egads_randlong() Copyright � 2003 O�Reilly & Associates, Inc. All rights reserved. Using the OpenSSL Random Number API | 603 See Also �EGADS by Secure Software, Inc.: �Recipe 11.2 11.9Using the OpenSSL Random Number API Problem ManyfunctionsintheOpenSSLlibraryrequiretheuseoftheOpenSSLpseudo-ran- Chapter11:Random Numbers anyway.Youcanuseanyofthesourceswehavediscussedelsewhereinthischapter forseedingtheOpenSSLPRNG.MultipleAPIfunctionsareavailablethatallowseed Onesuchfunctionis RAND_seed() ,whichallowsyoutopassinarbitrarydatathat RAND_bytes() Copyright � 2003 O�Reilly & Associates, Inc. All rights reserved. Ifthegeneratorisnotseededwithenoughentropy,thisfunctioncouldproduceout- Donot,underanycircumstances,usetheAPIfunction, bytes() .ItisnotacryptographicallystrongPRNGandthereforeis notworthusingforanythingthathasevenaremotepossibilityof Youcanimplement spc_rand() ,thecryptographicpseudo-randomnessfunction fromRecipe11.2,bysimplycalling RAND_bytes() andabortingifthatfunction Chapter11:Random Numbers Copyright � 2003 O�Reilly & Associates, Inc. All rights reserved. Inallcases,youwillstartwithafunctionthatgivesyouarandomunsignednumber thatcanbeanyvalue,suchas spc_rand_uint() fromRecipe11.10.Youwillmold Someprogrammersmayexpectthisfunctiontoexcludetheupper limitasapossiblevalue;however,weimplementthisfunctioninsuch if (max min) abort(); /* Do your own error handling if appropriate.*/ rado = spc_rand_uint(); Chapter11:Random Numbers Youmightworryaboutasituationwhereperformancesuffersbecausethiscodehas Copyright � 2003 O�Reilly & Associates, Inc. All rights reserved. Solution Becauseofthewaythatfloating-pointnumbersarestored,simplycastingbitstoa Chapter11:Random Numbers Inallcases,westartwithanumberwithuniformdistributionusingtheAPIfrom Notethatthesefunctionsusemathoperationsdefinedinthestandardmathlibrary. Onmanyplatforms,youwillhavetolinkagainsttheappropriatelibrary(usuallyby myr1 = spc_rand_real(); myr2 = spc_rand_real(); Copyright � 2003 O�Reilly & Associates, Inc. All rights reserved. Chapter11:Random Numbers while (--len) *p++ = (char)spc_rand_range(33, 126); Copyright � 2003 O�Reilly & Associates, Inc. All rights reserved. Compressing Data with Entropy into a Fixed-Size Seed | 613 See Also 11.16Compressing Data with Entropy into a Fixed-Size Seed Problem Youarecollectingdatathatmaycontainentropy,andyouwillneedtooutputa fixed-sizeseedthatissmallerthantheinput.Thatis,youhavealotofdatathathasa Itisagoodideatouseacryptographicalgorithmtocompressthedatafromthe entropysourceintoaseedoftherightsize.Thishelpspreserveentropyinthedata, uptotheoutputsizeofthemessagedigestfunction.Ifyouneedfewerbytesfora seedthanthedigestfunctionproduces,youcanalwaystruncatetheoutput.Inaddi- tion,cryptographicprocessingeffectivelyremovesanypatternsinthedata(assum- ingthatthehashfunctionisapseudo-randomfunction).Patternsinthedatacan helpfacilitatebreakinganentropysource(inpartorinfull),particularlywhenthat Chapter11:Random Numbers Copyright � 2003 O�Reilly & Associates, Inc. All rights reserved. Statistically Testing Random Numbers | 615 Itwouldbeniceifyoudidnothavetocollectentropyeverytimeaprogramstartsup Chapter11:Random Numbers FIPS140testsareusefulforprovingthatastreamofrandomnumbers areweak,butthetestsdon�tdemonstrateatallwhenthenumbersare Copyright � 2003 O�Reilly & Associates, Inc. All rights reserved. Statistically Testing Random Numbers | 617 Forthisreason,wethinkthefullsuiteofFIPS140-1testsisthewaytogoanytime Chapter11:Random Numbers int spc_fips_poker(unsigned char data[FIPS_NUMBYTES]) { int i; for (i = 0; i FIPS_NUMBYTES; i++) { counts[data[i] & 0xf]++; Copyright � 2003 O�Reilly & Associates, Inc. All rights reserved. Statistically Testing Random Numbers | 619 unsigned char curr; for (cur_val = i = runsz = 0; i FIPS_NUMBYTES; i++) { curr = data[i]; Chapter11:Random Numbers Thesecondoutputisalsosavedandisthencomparedtothethirdblock.Thispro- Thefollowing(non-thread-safe)codeaddsaFIPS-compliantwrappertothe entropy() functionfromRecipe11.2(notethatthisassumesthat spc_entropy() doesnotcryptographicallypostprocessitsdata,becauseotherwisethetestisallbut static char *last = b1, *next = b2; char *p = outbuf; if (bufsz == -1) { while (n = RNG_BLOCK_SZ) { /* Old next becomes last here */ *next ^= *last; *last ^= *next; *next ^= *last; spc_entropy(next, RNG_BLOCK_SZ); for (i = 0; i RNG_BLOCK_SZ; i++) if (next[i] != last[i]) goto okay; abort(); ) goto okay2; abort(); Copyright � 2003 O�Reilly & Associates, Inc. All rights reserved. Performing Entropy Estimation and Management | 621 See Also �NISTCryptographicModuleValidationProgramhomepage: �Recipe 11.2 11.19Performing Entropy Estimation and Problem Chapter11:Random Numbers example,supposethatyouwanttocollecta128-bitseed,andyoureadkeyboard inputandalsoreadseparatelyfromafasthardwarerandomnumbergenerator.With Copyright � 2003 O�Reilly & Associates, Inc. All rights reserved. Performing Entropy Estimation and Management | 623 Onethingyoushoulddotoavoidintroducingsecurityproblemsby underestimatingentropyisaggregateeachentropysourceindepen- Chapter11:Random Numbers Particularlywhenanattackermayhavelocalaccesstoamachine,itcanbeahope- lesstasktofigureoutwhatallthepossiblechannelsare.Makingthingsdifficultis Copyright � 2003 O�Reilly & Associates, Inc. All rights reserved. Performing Entropy Estimation and Management | 625 youuseaseedfile,youcanjustcollectentropyatinstalltime,atwhichpointinter- Entropy in timestamps Chapter11:Random Numbers However,inpractice,eventhatnumberistoohighbyabit,becausewealwaysknow thatthemostsignificantbitwecountisa1.Onlytherestofthedataisreallylikely Inpractice,tocalculatethemaximumamountofentropywebelievewemayhavein thedelta,wefindthemostsignificant1bitinthevalueandcountthenumberofbits fromthatpointforward.Forexample,therearefivebitsfollowingthemostsignifi- cant1bitin ,sowewouldcountsix.Thisisthesameastakingthefloorofthe Copyright � 2003 O�Reilly & Associates, Inc. All rights reserved. Performing Entropy Estimation and Management | 627 Chapter11:Random Numbers However,ifyouhaveamoreliberalthreatmodel,theremaybesomeentropyinthe positionofthemouse.Unfortunately,mostmousemovementsfollowsimpletrajec- torieswithverylittleentropy.Themostentropyoccurswhenthepointerreachesthe Copyright � 2003 O�Reilly & Associates, Inc. All rights reserved. Performing Entropy Estimation and Management | 629 withahigh-resolutionclock(i.e.,onerunningintheGHzrange).Ifyourclockhas Chapter11:Random Numbers 11.20Gathering Entropy from the Keyboard Problem Youneedentropyinalow-entropyenvironmentandcanprompttheusertotypein Solution OnUnix,readdirectlyfromthecontrollingterminal( ).OnWindows,pro- cessallkeyboardevents.Mixintoanentropypoolthekeypressed,alongwiththe timestampatwhicheachonewasprocessed.Estimateentropybaseduponyour Therecanbeareasonableamountofentropyinkeypresses.Theentropycomesnot simplyfromwhichkeyispressed,butfromwheneachkeyispressed.Infact,mea- suringwhichkeyispressedcanhaveverylittleentropyinit,particularlyinan embeddedenvironmentwherethereareonlyafewkeys.Mostoftheentropywill Copyright � 2003 O�Reilly & Associates, Inc. All rights reserved. Gathering Entropy from the Keyboard | 631 Collecting entropy from the keyboard on Unix Chapter11:Random Numbers &#xstdi;&#xo.h0;#include stdio.h #define HASH_OUT_SZ 20 #define OVERHEAD_CHARS 7 void spc_raw(int fd, struct termios *saved_opts) { struct termios new_opts; Copyright � 2003 O�Reilly & Associates, Inc. All rights reserved. Gathering Entropy from the Keyboard | 633 } else Chapter11:Random Numbers Collecting entropy from the keyboard on Windows TocollectentropyfromthekeyboardonWindows,wewillstartbybuildingadia- logthatdisplaysabriefmessageadvisingtheusertotyperandomcharactersonthe keyboarduntilenoughentropyhasbeencollected.Thedialogwillalsocontaina progressbarandanOKbuttonthatisinitiallydisabled.Asentropyiscollected,the progressbarwillbeupdatedtoreporttheprogressofthecollection.Whenenough entropyhasbeencollected,theOKbuttonwillbeenabled.ClickingtheOKbutton Callthefunction SpcGatherKeyboardEntropy() tobegintheprocessofcollecting entropy.ItrequirestwoadditionalargumentstoitsUnixcounterpart, keyboard_entropy() Applicationinstancehandlenormallyobtainedfromthefirstargumentto WinMain() Handletothedialog�sparentwindow.Itmaybespecifiedas ,inwhichcase Numberofbytesofentropytoplaceintotheoutputbuffer.Theoutputbuffer mustbesufficientlylargetoholdtherequestedamountofentropy.Thenumber ofbytesofentropyrequestedshouldnotexceedthesizeofthehashfunction used,whichisSHA1inthecodeprovided.SHA1producesa160-bitor20-byte hash.Iftherequestedentropyissmallerthanthehashfunction�soutput,the Copyright � 2003 O�Reilly & Associates, Inc. All rights reserved. Gathering Entropy from the Keyboard | 635 SpcGatherKeyboardEntropy() usestheCryptoAPItohashthedatacollectedfromthe keyboard.Itfirstacquiresacontextobject,thencreatesahashobject.Aftertheargu- mentsarevalidated,thedialogresourceisloadedbycalling CreateDialog() ,which createsamodelessdialog.Thedialogiscreatedmodelesssothatkeyboardmessages canbecaptured.Ifamodaldialogiscreatedusing DialogBox() oroneofitssiblings, Oncethedialogissuccessfullycreated,themessage-handlingloopperformsnormal messagedispatching,calling IsDialogMessage() tododialogmessageprocessing. Keyboardmessagesarecapturedinthelooppriortocalling IsDialogMessage() ,how- ever.That�sbecause IsDialogMessage() causesthemessagestobetranslatedanddis- Whenakeyispressed,a messagewillbereceived,whichcontainsinfor- mationaboutwhichkeywaspressed.Whenakeyisreleased,a willbereceived,whichcontainsthesameinformationaboutwhichkeywasreleased containsaboutakeypress.Thekeyboardscancodeisextractedfrom themessage,combinedwithatimestamp,andfedintothehashobject.Ifthecur- rentscancodeisthesameasthepreviousscancode,itisnotcountedasentropybut isaddedintothehashanyway.Asotherkeystrokesarecollected,theprogressbaris updated,andwhentherequestedamountofentropyhasbeenobtained,theOKbut- WhentheOKbuttonisclicked,thedialogisdestroyed,terminatingthemessage loop.Theoutputfromthehashfunctioniscopiedintotheoutputbufferfromthe Chapter11:Random Numbers Copyright � 2003 O�Reilly & Associates, Inc. All rights reserved. Gathering Entropy from the Keyboard | 637 } if (dEntropy = cbOutput * 8) { Chapter11:Random Numbers 11.21Gathering Entropy from Mouse Events on Windows Problem Youneedentropyinalow-entropyenvironmentandcanprompttheusertomove Solution OnWindows,processallmouseevents.Mixintoanentropypoolthecurrentposi- tionofthemousepointeronthescreen,alongwiththetimestampatwhicheach eventwasprocessed.Estimateentropybaseduponyouroperatingenvironment;see Therecanbeareasonableamountofentropyinmousemovement.Theentropy comesnotjustfromwherethemousepointerisonthescreen,butfromwheneach movementwasmade.Infact,themousepointer�spositiononthescreencanhave verylittleentropyinit,particularlyinanenvironmentwheretheremaybeverylittle interactionfromalocaluser.Mostoftheentropywillcomefromtheexacttimingof Copyright � 2003 O�Reilly & Associates, Inc. All rights reserved. Gathering Entropy from Mouse Events on Windows | 639 numberofbitsofentropyhasbeencollected.Aprogressbarisalsodisplayedthat Callthefunction SpcGatherMouseEntropy() tobegintheprocessofcollectingentropy. Ithasthesamesignatureas SpcGatherKeyboardEntropy() fromRecipe11.20.This Applicationinstancehandlenormallyobtainedfromthefirstargumentto WinMain() Handletothedialog�sparentwindow.Itmaybespecifiedas ,inwhichcase Numberofbytesofentropytoplaceintotheoutputbuffer.Theoutputbuffer mustbesufficientlylargetoholdtherequestedamountofentropy.Thenumber ofbytesofentropyrequestedshouldnotexceedthesizeofthehashfunction used,whichisSHA1inthecodeprovided.SHA1producesa160-bitor20-byte hash.Iftherequestedentropyissmallerthanthehashfunction�soutput,the SpcGatherMouseEntropy() usestheCryptoAPItohashthedatacollectedfromthe mouse.Itfirstacquiresacontextobject,thencreatesahashobject.Aftertheargu- mentsarevalidated,thedialogresourceisloadedbycalling DialogBoxParam() ,which Chapter11:Random Numbers createsamodaldialog.Amodaldialogcanbeusedforcapturingmousemessages insteadofthemodelessdialogthatwasrequiredforgatheringkeyboardentropyin Recipe11.20,becausenormaldialogprocessingdoesn�teatmousemessagestheway Oncethedialogissuccessfullycreated,themessagehandlingprocedurehandles messages,whichwillbereceivedwheneverthemousepointermovesover thedialogoritscontrols.Thepositionofthemousepointerisextractedfromthe message,convertedtoscreencoordinates,combinedwithatimestamp,andfedinto thehashobject.Ifthecurrentpointerpositionisthesameasthepreviouspointer position,itisnotcountedasentropybutisaddedintothehashanyway.Asmouse movementsarecollected,theprogressbarisupdated,andwhentherequested WhentheOKbuttonisclicked,thedialogisdestroyed,terminatingthemessage loop.Theoutputfromthehashfunctioniscopiedintotheoutputbufferfromthe Copyright � 2003 O�Reilly & Associates, Inc. All rights reserved. Gathering Entropy from Mouse Events on Windows | 641 Chapter11:Random Numbers if (!(pbHashData = (BYTE *)LocalAlloc(LMEM_FIXED, cbHashData))) goto done; DialogData.dEntropy = 0.0; DialogData.cbRequested = cbOutput * 8; Copyright � 2003 O�Reilly & Associates, Inc. All rights reserved. Gathering Entropy from Thread Timings | 643 See Also 11.22Gathering Entropy from Thread Timings Problem Youwanttocollectsomeentropywithoutuserintervention,hopingthatthereis Solution Inpractice,timinghowlongittakestostartupandstopaparticularnumberof threadscanprovideabitofentropy.Forexample,manyJavavirtualmachinesexclu- Becausethethreadtimingdataisonlyindirectlyrelatedtoactualuserinput,itis goodtobeextremelyconservativeaboutthequalityofthisentropysource.Werec- Chapter11:Random Numbers OnWindows,theideaisthesame,andthestructureofthecodeissimilar.Hereis Copyright � 2003 O�Reilly & Associates, Inc. All rights reserved. Gathering Entropy from System State | 645 Westronglyrecommendthatyoudonotincreaseyourentropyesti- matesbasedonanykernelstatecollected,particularlyonasystemthat ismostlyidle.Muchofthetime,kernelstatechangesmoreslowly thanpeoplethink.Inaddition,attackersmaybeabletoquerythe Chapter11:Random Numbers Often,thesecommandswillneedtorunwithsuperuserprivileges(forexample, ).Dependingonyourthreatmodel,suchcommandscanpossiblybemore