slightivybridge

ANALYSISOFINTEL'SIVYBRIDGEDIGITALRANDOMNUMBERGENERATORPREPAREDFORINTELBYMikeHamburgPaulKocherMarkE.
MarsonCryptographyResearch,Inc.
575MarketSt.
,11thFloorSanFrancisco,CA94105(415)397-0123March12,2012DISCLAIMER:ThisreportwaspreparedbyCryptographyResearch,Inc.
(CRI)undercontracttoIntelCorporation,andreflectstheopinionsoftheauthors,basedontheirknowledgeatthetimeofauthorship,andmaycontainerrors.
Notwithstandinganythingtothecontrary,inperformingthisevaluation,CRIhasnotengagedinanyevaluationorconsulting,andmakesnorecommendations,ofanykind,relatingtoresistancetosidechannelanalysis(e.
g.
,differentialpoweranalysis)orcountermeasurestherefor,andthemaking,using,selling,offeringforsale,orimportingofsuchcountermeasureswouldrequireaseparatelicenseunderCRI'spatentspertainingthereto.
ANALYSISOFINTEL'SIVYBRIDGEDIGITALRANDOMNUMBERGENERATORMARCH12,2012CRYPTOGRAPHYRESEARCH,INC.
PAGE2OF22Contents1Introduction31.
1Entropy_31.
2Deterministicrandombitgenerators_41.
3Theneedfornondeterministicrandombitgenerators42Architecture52.
1Systemoverview52.
2Entropysource_72.
3Healthand"swellness"tests_82.
4Deterministicrandombitgenerator92.
4.
1Conditioning92.
4.
2Reseeding_102.
4.
3Generation112.
5Built-InSelf-Test(BIST)112.
6Normaloperation123TheoreticalAnalysis133.
1Entropysource_133.
2Systemanalysis143.
2.
1Failuremodes_143.
2.
2Healthchecks_153.
2.
3Swellnesscheck163.
2.
4Conditioningdataforseeding/reseedingtheDRBG163.
2.
5Post-processingthedatawiththeDRBG_173.
2.
6Clockgating_174EmpiricalTests174.
1Basicstatisticaltests174.
2Entropy,bitprediction,andMarkovmodeling194.
3Chargetracking_204.
4Randomnesstests_205Conclusions_206Bibliography_22ANALYSISOFINTEL'SIVYBRIDGEDIGITALRANDOMNUMBERGENERATORMARCH12,2012CRYPTOGRAPHYRESEARCH,INC.
PAGE3OF221IntroductionGoodcryptographyrequiresgoodrandomnumbers.
ThispaperevaluatesIntel'shardware-baseddigitalrandomnumbergenerator(RNG)foruseincryptographicapplications.
Almostallcryptographicprotocolsrequirethegenerationanduseofsecretvaluesthatmustbeunknowntoattackers.
Forexample,randomnumbergeneratorsarerequiredtogeneratepublic/privatekeypairsforasymmetric(publickey)algorithmsincludingRSA,DSA,andDiffie-Hellman.
Keysforsymmetricandhybridcryptosystemsarealsogeneratedrandomly.
RNGsareusedtocreatechallenges,nonces(salts),paddingbytes,andblindingvalues.
Becausesecurityprotocolsrelyontheunpredictabilityofthekeystheyuse,randomnumbergeneratorsforcryptographicapplicationsmustmeetstringentrequirements.
Themostimportantpropertyisthatattackers,includingthosewhoknowtheRNGdesign,mustnotbeabletomakeanyusefulpredictionsabouttheRNGoutputs.
Inparticular,theapparententropyoftheRNGoutputshouldbeascloseaspossibletothebitlength.
1.
1EntropyEntropyisameasurementofhowrandomaparticularprocessis.
Whilethereareseveralwaystomeasureentropy,inthispaperwewillprimarilyuseShannonentropy[1]andmin-entropy[2].
Intheaboveformulas,piistheprobabilityoftheprocessbeingintheithofnpossiblestates,orreturningtheithofnpossibleoutputs.
Byusingabase-2logarithmwearemeasuringtheentropyinbits.
Shannonentropymeasurestheaverageamountofinformationrequiredtodescribethestate,whereasmin-entropymeasurestheprobabilitythatanattackercanguessthestatewithasingleguess.
Themin-entropyofaprocessisalwayslessthanorequaltoitsShannonentropy.
Inthecaseofarandomnumbergeneratorthatproducesak-bitbinaryresult,piistheprobabilitythatanoutputwillequali,where.
Thus,foraperfectrandomnumbergenerator,pi=2-k.
InthiscasetheShannonentropyandmin-entropyoftheoutputarebothequaltokbits,andallpossibleoutcomesareequallylikely.
Theinformationpresentintheoutputcannot,onaverage,berepresentedinasequenceshorterthankbits,andanattackercannotguesstheoutputwithprobabilitygreaterthan2-k.
ANALYSISOFINTEL'SIVYBRIDGEDIGITALRANDOMNUMBERGENERATORMARCH12,2012CRYPTOGRAPHYRESEARCH,INC.
PAGE4OF22AnRNGforcryptographicapplicationsshouldappeartocomputationally-boundedadversariestobecloseaspossibletoaperfectRNG.
Forthisreview,weanalyzewhetherthereisanyfeasiblewaytodistinguishtheIntelRNGfromaperfectRNG.
1.
2DeterministicrandombitgeneratorsMost"random"numbersourcesactuallyutilizeadeterministicrandombitgenerator(DRBG).
DRBGsusedeterministicprocessestogenerateaseriesofoutputsfromaninitialseedstate.
Becausetheoutputispurelyafunctionoftheseeddata,theactualentropyoftheoutputcanneverexceedtheentropyoftheseed.
Itcan,however,becomputationallyinfeasibletodistinguishawell-seededDRBGfromaperfectRNG.
Forexample,consideraDRBGseededwith256bitsofentropythatproducesmorethan256bitsofoutput.
AnattackerwhosuccessfullyguessedtheseeddatacouldpredicttheentireDRBGoutput.
Guessinga256-bitseedvalueiscomputationallyinfeasible,however,sosuchaDRBGcanbeappropriateforcryptographicapplicationseventhoughitsoutputsarenottrulyrandom.
Cryptographicapplicationsoftendemandextremelyhighqualityoutput,necessitatinggreatcareinthedevelopment,testing,andselectionofDRBGalgorithms.
NISThaspublishedSP800-90A[2],whichspecifiesseveralDRBGconstructions.
Thepublicationincludesrecommendationsforinstantiating,using,andreseedingDRBGs.
DRBGsalsorequirerandomseeds.
Adeterministicprocesscannotcreaterandomness,soultimatelyanondeterministic(aka"true")randomnumbergeneratorisstillrequiredforseedingtheseconstructions.
1.
3TheneedfornondeterministicrandombitgeneratorsAnondeterministicrandombitgeneratorusesanondeterministicsourcetoproducerandomness.
Mostoperatebymeasuringunpredictablenaturalprocesses,suchasthermal(resistanceorshot)noise,atmosphericnoise,ornucleardecay.
Theentropy,trustworthiness,andperformancealldependontheunderlyingentropysource.
ADRBGbyitselfwillbeinsecurewithoutanentropysourceforseeding.
Seedingrequiresasourceoftruerandomness,sinceitisimpossibletocreatetruerandomnessfromwithinadeterministicsystem.
Oncomputerswithoutahardwareentropysource,programmerstypicallytrytoobtainentropyforseeddatausingexistingperipherals.
ModernUNIXandWindowsOS'shaveOS-levelRNGsbasedonthetimingofkernelIOevents.
Unfortunately,thequalityoftheentropycollecteddependsuponthesystem'sconfigurationandhardware.
Forexample,theentropyavailablefromembeddeddeviceswithoutharddrivesorkeyboardsmaybeinsufficient.
Similarly,anoperationthatissecureonabusytestnetworkmaybecomeinsecurewhenmovedtoahigh-security,low-trafficenvironment.
Evenwhenitispossibleforapplicationstoproducetheirownsecurerandomdata,manydonot.
ReviewsbyCryptographyResearchfrequentlyidentifyweaknessesinrandomnumbergeneration.
BruceSchneierwrites,"Goodrandom-numbergeneratorsarehardtoANALYSISOFINTEL'SIVYBRIDGEDIGITALRANDOMNUMBERGENERATORMARCH12,2012CRYPTOGRAPHYRESEARCH,INC.
PAGE5OF22design,becausetheirsecurityoftendependsontheparticularsofthehardwareandsoftware.
Manyproductsweexamineusebadones.
"[3]Forexample,LucianoBellodiscoveredaseriousflawintheDRBGthatshippedwiththeOpenSSLcryptographylibraryonDebianandUbuntuLinuxsystemsfromSeptember2006toMay2008[4].
AllOpenSSLkeysgeneratedbytheaffectedsystemswerecompromised,includingservercertificates,SSHloginkeysandemailsigning/encryptionkeys.
Morerecently,in2012astudyshowedthatanunexpectedlylargenumberofRSAmodulisharecommonprimefactors,whichcaneasilybecomputedusingtheGCDalgorithm.
Oneofthemostlikelycausesispoorrandomnumbergenerationprocesses[5].
Theneedforstrongrandomnessisnotlimitedtokeygeneration.
Forexample,thepopularDSAandECDSAdigitalsignaturestandardsrequirearandomvaluewheneachsignatureisproduced.
EvenveryslightbiasesintheRNGusedtoproducethisvaluecanleadtoexploitablecryptographicweaknesses.
BleichenbacherdiscoveredthatthenoncegenerationmethoddefinedinFIPS186wasslightlybiased,andthisbiascouldbeusedtomountacryptanalyticattackagainstDSAandECDSA[6].
AlthoughRNGproblemsarecommon,flawsareoftenmissedbecausethereisnocomputationally-boundedtestthatcananalyzeanRNG'soutputandauthoritativelyconfirmthattheoutputisrandom.
Inaddition,cryptographicsoftwarelibrariesoftenleaveittoapplicationdeveloperstosupplytheirownseedmaterial,butprogrammersmaylacktheexperiencetodothiseffectively.
Inothercases,systemdesignersarefacedwithatrade-offbetweensecurityandconvenience.
Forexample,toavoidhavingtocollectfreshseeddataeachtimetheprogramloads,manysoftwareapplicationsstoretheirseedmaterialontheharddrivewheretherecanbeariskofcompromise.
Thebestsolutiontothesechallengesisforthehardwaretoprovideawell-designed,efficient,andeasy-to-usehardwareentropysource.
2ArchitectureIntelprovidedCRIwithdetaileddocumentationontheRNG,aswellasaccesstoitsprincipaldevelopers.
Thissectiondescribestheoverallarchitectureandthemaincomponentsofthesystem.
2.
1SystemoverviewAblockdiagramofthemajorcomponentsoftheIntelIvyBridgeRNGisshowninFigure1below.
ANALYSISOFINTEL'SIVYBRIDGEDIGITALRANDOMNUMBERGENERATORMARCH12,2012CRYPTOGRAPHYRESEARCH,INC.
PAGE6OF22Figure1:BlockdiagramoftheIntelRNG(adaptedfrom[7])MostmodernRNGs,includingtheIntelIvyBridgedesign,consistofanentropysource(ES)followedbydigitalpost-processinglogic.
Rawoutputfromentropysourcesgenerallycontainsdetectablebiasesandotherartifactsthatdistinguishtheoutputfromrandombinarydata.
Thepurposeofthepost-processinglogicistoconvertthisrawoutputintolower-bitrate,buthigher-quality,randomdata.
TheIntelRNG'spost-processinglogicisrelativelysophisticated.
Likemanysoftware-basedRNGs,thepost-processingusesstrongcryptographytopreventdeficienciesintheentropysourcefromleadingtoexploitableweaknesses.
Inparticular,theRNGmaintainsanentropypoolwhichisseededusingarelativelylargeamountofdatafromtheES.
EveniftheESisseverelydegraded,thefinaloutputwillremainofhighqualityandcryptographicallystrongandshouldappearindistinguishablefromtruerandombycomputationally-boundedadversaries(despitebeingnonrandomfromaninformationtheoreticperspective).
Onedrawbackofusingpost-processingisthatdefectsintheentropysourcebecomemoredifficulttoobserve.
Asaresult,usersoftheRNGhaveamoredifficulttimeassessingthequalityoftheunderlyingentropysource,andsomecatastrophicfailuremodescanactuallybecomedifficulttodetect.
TheIntelIvyBridgedesignershaveemployedseveralstrategiesthathelpmitigatetheseconcerns,includingtheincorporationoflogictomonitorthehealthoftheentropysource.
Inaddition,whilerawaccesstoentropysourceoutputisnotavailableonproductionparts,testpartscanprovidedirectaccesstoentropysourceoutputs.
TheIntelRNGoperatesasfollows:1.
Theentropysource(ES)isaself-clockingcircuitwhichoperatesasynchronouslyandgeneratesrandombitsatahighrate(about3GHz).
ANALYSISOFINTEL'SIVYBRIDGEDIGITALRANDOMNUMBERGENERATORMARCH12,2012CRYPTOGRAPHYRESEARCH,INC.
PAGE7OF222.
RandombitsgeneratedbytheESarecombined,sampledbythesynchronouslogic,andgroupedinto256-bitblocksinashiftregister.
3.
Basicstatisticaltestsareperformedbytheonlinehealthtestlogic(OHT)oneach256-bitblocktocheckforpotentialfailuremodesoftheES.
4.
The256-bitblocksintheonlineself-testedentropy(OSTE)queuearecryptographicallyprocessedintoa256-bitconditionedentropypoolbytheconditioninglogic.
5.
TheconditionedentropypoolisusedtoreseedtheDRBG.
6.
TheDRBGgeneratesthefinalbitsoutputbytheRNG.
Therestofthissectiondescribesindetaileachofthecomponents,andhowtheyoperateandinteract.
2.
2EntropysourceTheentropysource(ES)attheheartoftheIntelRNGisaself-oscillatingdigitalcircuitwithfeedback,showninFigure2below.
Figure2:EntropysourcefortheIntelRNG(from[8])TheESisadualdifferentialjamblatchwithfeedback.
Itisalatchformedbytwocross-coupledinverters(nodesAandB).
Thecircuitisself-clocking(heart_clock),anddesignedsuchthatwhentheclockisrunning,thecircuitentersametastablestate.
Thecircuitthenresolvestooneoftwopossiblestates,determinedrandomlybythermalnoiseinthesystem.
Thesettlingofthecircuitisbiasedbythedifferentialinthechargesonthecapacitors(AcapsandBcaps).
ThestatetowhichthelatchresolvesistherandombitofoutputoftheES.
Thecircuitisalsodesignedwithfeedbacktoseekoutitsmetastableregion.
Basedonhowthelatchresolves,afixedamountofchargeisdrainedfromonecapacitorandaddedANALYSISOFINTEL'SIVYBRIDGEDIGITALRANDOMNUMBERGENERATORMARCH12,2012CRYPTOGRAPHYRESEARCH,INC.
PAGE8OF22totheother.
Thegoalistohavethelatchoscillatearoundthemetastableregion,usingthelastoutputtodeterminethechargechangestothecapacitors.
Atnormalprocess,voltageandtemperature(PVT)conditions,theESrunsatabout3GHz.
See[8]foradetaileddescriptionoftheEScircuit.
IntelhasdevelopedatheoreticalmathematicalmodelfortheES,describedin[8]and[9].
WeanalyzethismodeltheoreticallyandempiricallyinSections3and4,respectively.
TherestoftheRNGisclockedat800MHz.
TheESgeneratesrandombitsatarateofabout3GHz,andtheyneedtobetransferredacrosstothesynchronousregionofthecircuit.
TheRNGprovidesanoptiontoaccumulatesamplesfromtheESwitharunningXORcircuit.
ThisXORsumofallpreviousESbitsisstoredinasingle-bitbuffer.
WhenanESoutputarrives,itisXORedwiththecurrentvalueofthebuffer,andtheresultiswrittenbacktothebuffer.
Thebufferisthensampledbythesynchronouslogicat800MHz.
Alternatively,theRNGcanbeconfiguredtooverwritethebufferwitheachnewESoutput.
Inthiscase,someESoutputswillnotbesampledbeforethebufferisoverwritten,andthuswillnotbeused.
FutureversionsoftheRNGwilluseadifferentsynchronizationlogic.
TheESoutputwillbedeserialized,andthensampledinparallelintothesynchronousregion,therebypreservingalltheESsamplesforpost-processing.
2.
3Healthand"swellness"testsOncethedataissampledintothesynchronousregion,itispassedseriallytotheon-linehealthtestunitinaslidingwindow,andfromthereintothe2-deep,256-bit-wideOnlineSelfTestedEntropy(OSTE)FIFObuffer.
Thehealthcheckunitevaluatesthehealthofeach256-bitsample.
Itcountshowmanytimeseachofsixdifferentbitpatternsappearsinasample.
Thesampleisdeemed"healthy"ifandonlyifthenumberoftimeseachpatternappearsfallswithincertainbounds.
ThebitpatternsandtheboundsforeachareshowninTable1below.
BitpatternAllowablenumberofoccurrencesper256-bitsample11090then:a.
Nextoutputbit=1b.
Reduce(differenceinchargeoncapacitors)by(leftstepsize)+noise4.
Else:a.
Nextoutputbit=0b.
Increase(differenceinchargeoncapacitors)by(rightstepsize)+noise.
Inanidealsystem,wewouldhave:Gaussianthermalnoisewithstandarddeviation1unitStepsineitherdirectionarealways0.
1unit,withnonoiseSerialcoefficient=0Startingstatewithnochargeonthecapacitors.
However,wemodelednon-idealconditionsaswell,including:Non-GaussianthermalnoiseStepsizeslargerorsmallerthan0.
1unitStepswhicharedifferentsizesineachdirectionNoiseonthestepsizePositiveornegativeserialcoefficientStartingwithsomechargeonthecapacitors.
ANALYSISOFINTEL'SIVYBRIDGEDIGITALRANDOMNUMBERGENERATORMARCH12,2012CRYPTOGRAPHYRESEARCH,INC.
PAGE14OF22Byquantizingthechargedifferenceandlimitingittoafewstandarddeviations,weturnedtheabovemodelintoaMarkovprocesssuitableformathematicalanalysis.
Ineachcase,weusedthisprocesstoestimatethelong-termShannonentropy,themin-entropyover32bits,andlocalstatisticssuchasautocorrelationandbias.
WecomparedtheresultstomeasurementsofanInteltoolwhichsimulatestheentropysource,andfoundtheminagreement.
Figure4:Effectofbiasandserialcoefficientonmin-entropy,meanstepsize=0.
2Figure4showsaninterestingresultofthismodeling:iftheserialcoefficientispositiveorzero,thenbiasinthestepsizewilldecreaseentropy.
However,ifitisnegative,thenbiaswillbreakthepatternofoscillation,whichmayincreaseentropy.
Thisgraphshowsextremecases.
Therealpartsweanalyzedhadserialcoefficientsunder0.
1.
3.
2Systemanalysis3.
2.
1FailuremodesTheentropysourceisthemostsensitivepartintheRNG,andalsothemostdifficulttotest.
Hence,wewillfirstconsideritspossiblefailuremodes.
Failuremodesconsideredinclude:TheESalwaysshowssingle-bitbias,serialcorrelationandothersmalldeviationsfromperfectrandomness.
Ifthesebiasesaresevere,theymayreducetheentropyrateoftheESbelowacceptablelevels.
TheESmighttakealongtimetowarmup,andduringthistimecouldoutputmostly0sormostly1suntilitsettlesonthemetastableregion.
TheESmightbecome"stuck",alwaysoutputting0oralwaysoutputting1.
TheESmightoscillatebetween0and1,orinsomeothershortpattern.
0.
00.
10.
20.
30.
40.
50.
60.
70.
80.
91.
011.
11.
21.
31.
41.
51.
61.
71.
81.
92EntropyrateRatioofleft/rightstepsizeSerial-1.
0Serial-0.
5Serial-0.
2Serial-0.
1NoserialSerial+0.
1Serial+0.
2Serial+0.
5Serial+1.
0ANALYSISOFINTEL'SIVYBRIDGEDIGITALRANDOMNUMBERGENERATORMARCH12,2012CRYPTOGRAPHYRESEARCH,INC.
PAGE15OF22TheESmightbemostlystuckinoneoftheprecedingpatterns,butoccasionallydeviatefromit.
TheESmightbeinfluencedbyanexternalcircuit(forexample,anearbybusorthechip'spowersupply)inawaythatispredictableorexploitablebyanattacker.
TheRNGhasageneroussafetymargin,sothesefailureswillonlyimpactsecurityiftheyaresevere.
Ofthepossiblefailuresabove,mostshouldbedetectedreliablybythehealthandswellnesschecks.
Themostcomplexissuesinvolvebriefexternally-inducedtransitorylossesofentropy,butthecombinationover-collectionofentropyandtheRNG'suseofcryptographyshouldmitigateanysuchunexpectedissues.
Also,whilesuchfailurescancausethedesigntobehavebrieflyasacryptographically-strongdeterministicRNG,thisshouldnotresultinanylossofsecurity.
3.
2.
2HealthchecksThegoalofthehealthchecksistorejectESoutputswithlittleactualentropy.
Sinceentropyisimpossibletomeasure,insteadthedesignisintendedtocatchsinglepointsoffailureintheESsuchasthefailuremodeslistedabove.
IftheywererunondirectESoutputs,thehealthcheckswoulddothisquitewell.
Infact,norepeatingpatternwithaperiodshorterthan12bitscanpassthehealthchecks.
However,thehealthchecksareperformedaftertheoptionalXORfilterandsynchronizationlogic.
Theratioofthefrequenciesbetweentheself-clockingESandthesynchronousregionisnotanexactinteger,andwilldriftovertime.
HencethenumberofESsamplesthatareincludedineachsamplecrossingtheclockboundarywillvary.
Forexample,iftheESis"stuckat1",thentheoutputoftheXORfilterwilltogglebetween0and1.
Thesampledoutputwilloscillateinamorecomplicatedpattern,dependingonhowmanyESoutputswereaccumulatedineachsample.
Ifthefrequencyratioisconstantandnear3.
3,thenthesampledoutputfailshealthchecksbyamarginof5samples.
Ifthefrequencyratiovariesslightly,ortheESisonlymostlystuckat1,thenthepartmaypassthehealthchecksdespitehavinglittleentropy.
Inourexperiments,manysamplespassthehealthcheckseveniftheESis96%stuckat1.
Suchafailurewouldgoundetected,andwouldbringthesystemoutsideitsdesignmargins.
SinceproductionpartscannotexaminetheES'srawoutput,softwarewouldnotbeabletodetectthisfailureeither.
Still,aftertheXORfilterandclockdomaincrossing,thesamplesinthisfailuremodehaveaShannonentropyrateofnearly0.
4,withmin-entropyonlyslightlylower.
Whilethisislessthanthedesignmarginof0.
5,thesystem'sconservativeinitializationallowsittocomeupsecurelywithmin-entropyrateof0.
004,twoordersofmagnitudelessthanthisfailureallows.
ThefirstgenerationoftheRNGdoesnotusetheXORfilter.
Inthiscase,ESsampleswillgodirectlythroughtothehealthchecks.
However,theoutputoftheESisstillunder-sampledwhencrossingtheclockboundary.
Thatis,someofitsoutputbitswillbeused,andothersdropped.
ButthehealthchecksaremoreeffectivewithouttheXORfilter.
WithouttheXORfilter,afailuresuchas"mostlystuckat1"willcertainlybecaught.
Instead,theESwouldneedtooscillateataslightlyinconsistentratetohaveanANALYSISOFINTEL'SIVYBRIDGEDIGITALRANDOMNUMBERGENERATORMARCH12,2012CRYPTOGRAPHYRESEARCH,INC.
PAGE16OF22undetectedfailure.
Thisfailuremodeseemslesslikely,thoughitmighthappenifthefeedbackcircuit'sstepsizeweresomehowfartoolarge.
However,withouttheXORfilter,thehealthcheckswillnotbeforgivingofbiasintheentropysource.
Anypartwhichisbiasedbymorethan57%onesto43%zeros(orviceversa)islikelytofailBIST.
TheseconcernscanberesolvedbyhavingthehealthchecksoperateonalltheESoutputbitsdirectly.
InfutureversionsoftheRNG,theESoutputwillbedeserialized,andthensampledinparallelintothesynchronousregion.
ThisnewerlogicwillthereforeprovidemostoralloftherawESoutputtothehealthchecks,andavoidthisissue.
3.
2.
3SwellnesscheckTheswellnesscheckservesthreemainpurposes.
Itcausesthefirst129healthysamplesfromtheES–morethan32kilobits–tobeconditionedintotheDRBG'skeyduringBIST.
Thus,itwillsaturateits128-bitentropypoolevenifthosesampleshaveamin-entropyrateaslowas0.
004.
ItpreventstheRNGfrompassingBISTunlessatleast129ofthefirst256samplesarehealthy.
Itpreventsthesystemfromremainingmostlyunhealthyfortoolong.
Swellnessalsoprotectsthereseedlogic,butonlyinthelongterm.
Reseedshappeneveryfewblocks,butifusersarenotconsumingmuchentropy,thenthetimebetweenreseedsmaybelong.
Duringthistime,theES'scapacitorsmightdischarge,andwhentheESisturnedbackon,itmightgeneratepoordata.
Ifmostofthisdatafailsthehealthchecks,thentheswellnesscheckwilleventuallyfail,sothatmorehealthysamplesarerequired.
Oncethisoccurs,theESwillneedtowarmupenoughtoproducemostlyhealthysamples.
Inthis(entirelyhypothetical)case,somereseedswillbestrongerthanothers.
Intelhastoldusthatworstcasesimulationssuggestthatonlythefirst256bitscouldbeaffected,andthewarm-upeffectcannotbedetectedinrealsilicon.
Reseedingpreservestheoldseed'sentropy.
Therefore,iftheinitialseedisstrong,poorreseedswillnotweakenit.
TheDRBGreseedsmuchmoreoftenthanNISTSP800-90Arequires,andsomeweakreseedsarenotaconcernsolongasstrongoneshappenoccasionally.
3.
2.
4Conditioningdataforseeding/reseedingtheDRBGEntropyconditioningisdoneviatwoindependentAES-CBC-MACchains,oneforthegenerator'skeyandoneforitscounter.
AES-CBC-MACshouldbesuitableasanentropyextractor,andallowsreuseofthemodule'sAEShardware.
Importantly,theconditioneraccumulatesatleast129healthysamples(33,024bits)fortheDRBG'skeyduringBIST,soeveniftheentropyrateislow,thegeneratorwillbeinasecurestatebeforeitreturnsanydata.
Weseenoproblemswiththisconditioner.
Undermoderateload,thegeneratorwillreseedbeforeeach128-bitoutput,sothattheoutputisinformation-theoreticallyrandomiftheentropyrateofhealthysamplesisatleast0.
25.
Underheavyload,iftheDRBG'sstateweresomehowcompromised,theANALYSISOFINTEL'SIVYBRIDGEDIGITALRANDOMNUMBERGENERATORMARCH12,2012CRYPTOGRAPHYRESEARCH,INC.
PAGE17OF22conditioninglogicwouldrestoreittoastrongstateiftheESachievesitsdesignedentropyrateofatleast0.
5.
3.
2.
5Post-processingthedatawiththeDRBGTheDRBGisbasedonAESincountermode,pertheNISTSP800-90Arecommendations.
Itisatheoreticallysound,conservativedesign.
Undermoderateload,itsoutputshouldbeinformation-theoreticallyrandom.
Underheavyload,itshouldprovidesecurityequivalentto128-bitAES,evenagainstanattackerwhocanseesomeofitsoutputsand,afteragoodreseed,forcetheEStooutputnonrandom,knownvalues.
3.
2.
6ClockgatingTheRNGsupportsclockgatingtoreducepowerconsumption.
Ifnoapplicationrequestsentropyforashorttime,theRNGwillfreezeitsclockandstoptheES.
AnareaofconcernwiththisapproachisthatthechargeoncapacitorsmaydissipatewhentheESisnotoperating,whichmightaffectthequalityoftheentropyoutputbytheESwhenrestarted.
AsstatedinSection3.
2.
3,simulationsandtestsbyIntelsuggestthatthisisnotanissue,astheESresumesnormaloperationquickly.
Inaddition,thereshouldbesufficiententropyintheDRBGfromtheinitialseedingduringBIST.
4EmpiricalTestsWedidnothaveaccesstoIvyBridgeparts,soIntelprovideduswithtestingdatafrompre-productionchips.
ThesechipsallowaccesstotherawESoutput,acapabilitywhichisdisabledinproductionchips.
Evenso,innormaloperationsomedataislostcrossingtheclockboundary.
Foreasieranalysis,IntelperformedextensivetestingwiththeESclocksynchronizedtothesystemclock,sothatalltheoutputcouldbecollected.
WealsoreceiveddatafromtestchipswithspecialhardwaretocollecttheentireESoutput,andfromchipsrunninginthenormaloperationalmodewiththeXORfilterandclock-domain-crossinglogicinplace.
WeanalyzedallthedatafilesthatIntelprovided,butinthisreportwewillfocusonthedatacollectedwiththeESclocksynchronized,becausethisdatawascollectedfromawidevarietyofchipsandshowsthemostinterestingfeatures.
4.
1BasicstatisticaltestsWerananumberofstatisticaltestsontheentropysourcedatathatIntelprovidedus.
Forthemostbasictest,wemeasuredthebiasandserialcorrelationsofthedata.
ThesemeasurementsaresummarizedinFigure5.
ANALYSISOFINTEL'SIVYBRIDGEDIGITALRANDOMNUMBERGENERATORMARCH12,2012CRYPTOGRAPHYRESEARCH,INC.
PAGE18OF22Figure5:BiasandautocorrelationinthedataFigure5showsthebiasandserialcorrelationinthedatawereceived.
Eachdiamondrepresentsdatafromasinglechip.
Serialcorrelationsinthisdataarerelativelysmall,atmostafewpercent.
Single-bitbiasisabiggerproblem,with12%typicalandanoutlieratalmost25%.
Thedatahadserialcorrelationsathigheroffsetsaswell.
Asmallanti-correlation(1-2%)isexpectedduetothenegativefeedbackcircuit.
Instead,wesawvaryingpositiveandnegativeautocorrelationsatlongeroffsets,allontheorderof1%.
Theseautocorrelationsaresymptomaticofafaint"ringing"withinthesystem.
Inordertoinvestigatethisringingbehavior,welookedattheFouriertransformsofthedata.
Figure6:Fouriertransformofdatafromonepart,showingringing-7%-6%-5%-4%-3%-2%-1%0%1%2%-30%-25%-20%-15%-10%-5%0%5%10%15%Autocorrelationatoffset1Bias=Pr(1)-Pr(0)0.
0%0.
5%1.
0%1.
5%2.
0%2.
5%01/121/61/41/35/121/2AveragemagnitudeFrequency|DC|=1.
8%frombias|F(1/2)|=2.
2%fromserialcorrelation|F(0.
32)|=1.
1%strongesttoneANALYSISOFINTEL'SIVYBRIDGEDIGITALRANDOMNUMBERGENERATORMARCH12,2012CRYPTOGRAPHYRESEARCH,INC.
PAGE19OF22Figure6showstheFouriertransformofoneparticulardatafile.
Thisfileshowsasmallbias,anoffset-1autocorrelation,andanoticeabletonenear1/3.
Thistoneissymptomaticof"ringing"behaviorwithperiodslightlyover3bits.
Comparedtotheotherparts,thisoneshowsasmallerbiasandastrongertonethanmost.
Itisotherwiserepresentative.
Mostpartsshowaflatspectrumwithafewfainttones,plusasingle-bitbiasandasmallserialcorrelation.
4.
2Entropy,bitprediction,andMarkovmodelingWeconstructedMarkovmodelsofeachsamplefilethatIntelprovided.
Thestateofourmodelcomprisedthelast12bitsofoutput;withalargerstate,errorscreptinduetohavingtoofewsamplesineachstate.
Fromthismodel,weusedtheMarkov-Rényi[11]algorithmtoestimatetheworst-casemin-entropy.
Thisalgorithmismuchmorepessimisticthansamplingthemin-entropydirectly.
Inparticular,itassumesthatanadversarycanwaituntilthesystemisinastatewhichproduceslowentropy,whichisnotactuallypossible.
Figure7:Entropymeasurementson45partsFigure7summarizestheresultsoftheseentropymeasurements.
Thehorizontalaxisisthepartwhichwassampled,sortedbythemeanoftheentropymeasurements.
Theverticalaxisistheentropyperbitaccordingtotheindicatedmetrics.
ThetoplineshowstheShannonentropy,computedoverthebytesoftheentropysource'soutput.
Thismeasurementshowshowmuchentropytheentropysource'soutputshaveonaverage.
Theseresultsareclearlyverygood.
Thesecondlineshowsthesampledmin-entropy,measuredon13-bitsamples(ourMarkovmodel'sstate,plusitsoutput).
Thisisarelativelyaccuratemodelofthedifficultyofguessingtheoutputofthegenerator.
0.
500.
600.
700.
800.
901.
00EstimatedentropyperbitSampledpartShannonSampleMinMarkov-RényiMinWeakestANALYSISOFINTEL'SIVYBRIDGEDIGITALRANDOMNUMBERGENERATORMARCH12,2012CRYPTOGRAPHYRESEARCH,INC.
PAGE20OF22ThethirdlineshowstheMarkov-Rényimin-entropy,modelingthenextbitofoutputusingtheprevious12bits.
Thisisamoreconservativemodelofthedifficultyofguessingtheoutputofthegenerator.
ThelowestlineshowstheentropyoftheweakeststatesoftheMarkovmodel.
ThislineismuchlowerthantheMarkov-Rényilinebecausethegeneratordoesnotstayintheseweakstatesforlong.
Therefore,theydonotposeathreattothesecurityoftheRNG.
Threemajoreffectsarevisibleinthischart.
Someofthepartsgeneratelower-qualityentropyduetocorrelationandbias.
Thishasamuchmoredramaticeffectonthemin-entropythanontheShannonentropy.
Still,eventhemostpessimisticestimatesoftheworstpartsarehigherthanthe50%thresholddiscussedinSection2.
4.
1.
ThedatafortheseCPUswascollectedbyplacingtheminatestingmachine,ratherthanbyissuingdebuggingcommandsfromtheCPUitself.
Asaresult,someruns(inparticular,thespikeneartherightsideoftheplot)showartifactswherethetestingmachinebeganreadingbeforetheESturnedon.
AfterdiscussingtheseartifactswithIntel,webelievethattheycannothappenduringoperation.
Theringingbehaviorofsomepartsmeansthatafteracertain2-or3-bitpatternhasoccurred,itisslightlymorelikelytooccuragain.
Thisringingbehaviorisfaint,butevensoitcanreducetheMarkov-Rényientropyestimatebyupto10%.
4.
3ChargetrackingWeattemptedtotrackthechargeonthecapacitors,inparttopredicttheoutputofthecircuitandinparttoverifythatourmodelwascorrect.
Wedidnotexpectourpredictionstobeveryaccurate,becauseevenifthesystemideallymatchedourmodel,itwouldhavehighentropy.
Butwedidexpecttheestimatedchargeonthecapacitorstocorrelatetotheoutput.
Wesawtheexpectedcorrelation(andlackofpredictability)inthedatacollectedfromarunningIvyBridgeCPU,butnotinthedatacollectedfromanexternaltester.
WesuspectthatthelinkbetweentheCPUandthetesterisnotfastenoughtotransmiteverysample,thwartingourattemptstotrackthecapacitorchargeontheseparts.
4.
4RandomnesstestsWetestedthefinal,post-processedoutputsoftheRNGwiththeNISTSP800-22statisticaltestsuite[12]inordertomakesurethattherearenoglaringflawsinthegenerator.
Asexpected,theoutputseasilypassedtheentiretestsuite.
5ConclusionsOverall,theIvyBridgeRNGisarobustdesignwithalargemarginofsafetythatensuresgoodrandomdataisgeneratedeveniftheESisnotoperatingaswellaspredicted.
ANALYSISOFINTEL'SIVYBRIDGEDIGITALRANDOMNUMBERGENERATORMARCH12,2012CRYPTOGRAPHYRESEARCH,INC.
PAGE21OF22TheESisaninterestingdesignbasedontherandomresolutionofacircuitdesignedtoseekoutitsmetastablestate.
IntelhasmodeledandtestedtheESextensivelyandbelievesthatwithinawiderangeofconditions,includingtypicalPVTvariations,theESgeneratesatleast0.
5bitsofentropypersample.
Ourmodelingandtestingagreewiththisassessment.
Thehealthandswellnesstestsaregenerallywelldesignedandshouldidentifybadlybrokenentropysources.
TheyaremosteffectivewhenperformeddirectlyonESoutput,andtheoptionalXORfilteringandclockboundarycrossinglogicweakensthem.
However,thelargenumberofESsamplesmixedintotheDRBGAESkeyduringBISTandreseedingshouldcompensateforanESwhichisgeneratingdatawithevenverylowentropy.
TheDRBGconstructionissound.
Wefoundnoissueswiththeentropyconditioning,reseeding,andrandomdatagenerationlogic.
BecausetheIvyBridgeRNGisimplementedasaninstructionintheCPU,itismuchsimplertousethanotherhardware-basedRNGsandavoidstheneedforadditionalsoftwarelayersthatcouldintroducebugs.
Applicationsdoneedtoperformsomesimplechecks,however,notablytestingthecarryflagtodetectfailuresandtestingtoensuresafeoperationifrunonaCPUwithoutanintegratedRNG.
Inaddition,developersshouldbeawarethattheRNGinstructioncanbevirtualized,andcouldbeinterceptedtodelivernonrandomdatatoapplications.
Ofcourse,amalicioushypervisorcanruinapplications'securityinnumerousother,simplerways.
Inconclusion,webelievetheIvyBridgeRNGiswelldesigned,withawidemarginofsafety,andtheoutputisappropriatetousedirectlyforcryptographickeys,secretnonces,andothersensitivevalues.
However,themostprudentapproachisalwaystocombineanyotheravailableentropysourcestoavoidhavingasinglepointoffailure.
ForOSimplementationsthatmaintainanentropypool,werecommendthefrequentincorporationofRNGoutputsasanadditionalinputintotheOSentropypool.
TheexceptionalperformanceoftheInteldesignalsoenablesdirectmixingofdatafromtheIvyBridgeRNGoutputswithoutputdeliveredfromotherRNGs.
Inallcases,usersshouldcheckthecarryflagaftereachcalltotheRNGtoverifythatitisworkingproperlyandtherandomdatareceivedisvalid.
ANALYSISOFINTEL'SIVYBRIDGEDIGITALRANDOMNUMBERGENERATORMARCH12,2012CRYPTOGRAPHYRESEARCH,INC.
PAGE22OF226Bibliography[1]C.
E.
Shannon,"AMathematicalTheoryofCommunication,"BellSystemTechnicalJournal,vol.
27,pp.
379–423,623-656,1948.
[2]E.
BarkerandJ.
Kelsey,RecommendationforRandomNumberGenerationUsingDeterministicRandomBitGenerators,NISTSpecialPublication800-90A,January2012.
[3]B.
Schneier,SecurityPitfallsinCryptography,CounterpaneSystems,1998.
[4]"DSA-1571-1-openssl--predictablerandomnumbergenerator,"Debian,13May2008.
[Online].
Available:http://www.
debian.
org/security/2008/dsa-1571.
[Accessed1February2012].
[5]A.
K.
Lenstra,J.
P.
Hughes,M.
Augier,J.
W.
Bos,T.
KleinjungandC.
Wachter,"Ronwaswrong,Whitisright,"IACReprintarchive,vol.
064,2012.
[6]D.
Bleichenbacher,Onthegenerationofone-timekeysinDLsignatureschemes,IEEEP1363WorkingGroupMeeting,November2000.
[7]D.
J.
Johnston,"MircoarchitectureSpecification(MAS)forPP-DRNG,"IntelCorporation(unpublished),V1.
4,2009.
[8]C.
E.
Dike,"3GbpsBinaryRNGEntropySource,"IntelCorporation(unpublished),2011.
[9]C.
E.
DikeandS.
Gueron,"DigitalSymmetricRandomNumberGeneratorMathematics,"IntelCorporation(unpublished),2009.
[10]M.
Dworkin,"RecommendationforBlockCipherModesofOperation:TheCCMModeforAuthenticationandConfidentiality,"NISTSpecialPublication800-38C,May2004.
[11]Z.
Rached,F.
AlajajiandL.
Campbell,"Rényi'sEntropyRateForDiscreteMarkovSources,"1999.
[12]NIST,"NISTSpecialPublication800-22rev1a,"11August2010.
[Online].
Available:http://csrc.
nist.
gov/groups/ST/toolkit/rng/documentation_software.
html.
[Accessed2February2012].