True Random Number Generator based on ROPUF circuit
4.4 RP4 - True random number generator based on ring oscillator PUF circuit
The paper RP4 extends the work performed in the RP3. Additional testing is performed to ensure stability of generated bitstream in changing environment. The set of test ruling out crosstalk and parasitic frequencies was performed. Two experimental setups were verified – one with multiple RO pairs active simultaneously and switching regulator is used as power supply, while another one with setup when single RO pair is active at a given moment and linear regulator is used as power supply. The paper was published inMicroprocessors and Microsystems [A.5].
Microprocessors and Microsystems 53 (2017) 33–41
ContentslistsavailableatScienceDirect
Microprocessors and Microsystems
journalhomepage:www.elsevier.com/locate/micpro
True random number generator based on ring oscillator PUF circuit
SimonaBuchovecká∗,Róbert Lórencz, FilipKodýtek,Jiˇrí Buˇcek
Department of Computer Systems, Faculty of Information Technology, Czech Technical University, Thakurova 9, 160 00 Prague, Czech Republic
art icl e info
Article history:
Received 9 January 2017 Revised 28 June 2017 Accepted 29 June 2017 Available online 4 July 2017 Keywords:
Inthispaperweproposethemethodofgeneratingtruerandomnumbersutilizingthecircuitprimarily designedasPhysicallyUnclonableFunction(PUF)basedonringoscillators.Thegoalistoshowthatitis possibletodesigntheuniversalcryptosystem,thatcanbeusedforvariousapplications– thePUFcanbe utilizedforasymmetriccryptographyandgeneratingasymmetrickeys,TrueRandomNumberGenerator (TRNG)forsymmetriccryptography(generatingsessionandephemeralkeys),noncesandsalts.Inthe papertheresultsofevaluationofsuchacircuitutilizedforTRNGpurposearepresented.
© 2017ElsevierB.V.Allrightsreserved.
1.Introduction
Asstatedin[5],thesecurityofcryptographicsystemsismainly linkedtotheprotectionofconfidentialkeys.Inhighend informa-tionsecuritysystems,whenusedinanuncontrolledenvironment, cryptographickeysshouldneverbegeneratedoutsidethesystem andtheyshouldneverleavethesysteminclear.Forthesame rea-son,ifthesecuritysystemisimplementedinasinglechip (crypto-graphicsystem-on-chip),thekeysshouldbegeneratedinsidethe samechip.
Implementationofpropermethodsforcryptographickey gen-erationand their securestorage inlogic devices (including con-figurablelogic devices) isofsignificant importance.Moreover, it isnecessary touse thecryptography and corresponding keysin propermanner.Guidelinesonhowtoproperlydealwiththis mat-tercanbefounde.g.inNISTSpecialPublication800-133[1].
Nowadays, TRNGs are mostly usedfor keygeneration. There-fore,thequalityoftherandomnumbergeneratorhasasignificant influenceonthesecurityofthewholecryptosystem.
In[7],aradicallynewapproachtosecurekeystorageisdefined.
Withregardstodrawbacksofnon-volatilestorage,authorsdefine thecriteriafornewapproach– authorsstatethatkeyshouldnot be permanently storedin digital formon the device, it should beuniquelylinkedtothedevice,shouldnotbereproducible,and shouldbeonlyusedwhenrequired.Thus,thekeysshouldbe ex-tractedfromtheintrinsicpropertiesofthedevice,andtheauthors furtherbuildtheirconcept forsecurekeystorageonPUFsrather thanstoringkeysinnon-volatilememory.
∗Corresponding author.
E-mail address: buchosim@fit.cvut.cz (S. Buchovecká).
The concept ofPUF was originally introducedin [13,14] and the authors showed that instead of relying on number theory, themesoscopicphysicsofcoherenttransportthroughadisordered medium can beused toallocate and authenticate unique iden-tifiers by physically reducing the medium’s microstructure to a fixed-lengthstringofbinarydigits.Thesephysicalone-way func-tions areinexpensive tofabricate,prohibitively difficultto dupli-cate, admitnocompactmathematicalrepresentation,andare in-trinsicallytamper-resistant.ThismakesPUFanidealcandidatefor providingtamperresistantdesignforcryptographickeygeneration andstorage.
1.1. SuitabilityofTRNGsandPUFsforkeygeneration
Strictrequirementsare laidon thequalityofgenerated cryp-tographic keyfor sensitiveapplications,aswell asmeeting vari-ousmathematicalpropertiesofaparticularcryptosystem.Thekey shouldbeunpredictable, andthusistoday mostoften generated using TRNG.Moreover, TRNGsare ofgreatadvantagewhen gen-eratingothershort-term orpublic values.TRNGs aresuitablefor followingtasks:
•Key generation for symmetric cryptography – session keys, ephemeralkeys,
•Publiclytransmittedoropenvaluessuchasnonces,challenges, salts,initializationvectors,
•Generation ofephemeral keys and otherone-time values for asymmetricschemes.
Apart from TRNGs that are traditionally used for generating cryptographickeys,PUFsarebeingpresentedasanovelapproach increasing physical security. As discussed in[19], safely manag-ing and storing secrets (including cryptographic keys) in mem-http://dx.doi.org/10.1016/j.micpro.2017.06.021
0141-9331/© 2017 Elsevier B.V. All rights reserved.
34 S. Buchovecká et al. / Microprocessors and Microsystems 53 (2017) 33–41
ory isdifficultandexpensive.UsingPUF,thekeysarenot physi-callystored,rathertheyaregeneratedwhentheyareneeded.The factthatthekeywasgenerateddirectlyonthedeviceandcannot becopiednorcloned,isadvantageousespeciallyinthefollowing cases:
•Identificationanddeviceauthentication,
•Keygenerationandkeystorageforsymmetriccryptography(for on-chipencryption),
•Key generation and key storage forasymmetric cryptography (privatekeys).
Assuch,itisadvantageousforproperimplementationof var-ious cryptographicprotocolstohavethe abilitytogenerateboth randomnumber(e.g.forsymmetrickeys),aswellasPUF(for se-curegenerationandstorageofasymmetrickeys).
1.2.Truerandomnumbergeneratorsbasedonringoscillators
Random numberscanbe generatedeither algorithmically(so called deterministic RNG or pseudo-RNG), or using an entropy sourcerealizedinhardware(physicalortrueRNG– TRNG).There are variousapproaches,how togetentropyfromhardware. Ana-logcomponentsareoftenusedassourceofentropy,examples in-cludedesigns basedon sinusoidalvoltage source[18],avalanche diode[15]orthermalnoiseofresistor[24].Otherapproachesuse physicalphenomenonsuchasquantumeffectsorradioactivedecay [8,23].
The TRNG we propose inthis paper utilizes Ring Oscillators (RO)astheentropysource.Theideatouseringoscillatorsasthe source ofanentropy isnot new.Theprinciple ofTRNG genera-tionbased on ROsisdiscussed in[21]– the delay instabilityof logic gates (inverters) connected into the ringis seen as a fre-quency/phaseinstability(ajitter)ofthegeneratedclock.Thejitter isextractedinasamplingunitusingflip-flopsorlatches.
Variety of TRNG designs based on ROs were proposed. In [20]twoROsareusedasclocksforalinearfeedbackshiftregister andacellularautomatashiftregisterandoutputissampledwhen a new random numberis requested.Design based on Fibonacci and GaloisRing Oscillators is presented in[6]. The randomness as well as robustness can be further increasedby XOR-ing the outputsoftwooscillators,onebeingintheGaloisandtheotherin the Fibonacciconfiguration.Thedesignproposedin[11]consists of two independent and identically configured ROs, a sampling circuit, and a control circuit. The sampling unit uses one clock signal to sample the other clock signal. The stream of samples consists ofa run ofonesanda gap ofzeros. Thelength ofthis run and gap iscounted modulo2 and output as a random bit.
OscillatorbasedRNGdesignisevensuitabletobeintegratedina SmartCardmicrocontroller[2].
1.3.Ourapproach
Asdiscussedinprevioussections,fromkeygeneration perspec-tive itis advantageoustohavethe capabilitytohaveboth PUFs andTRNGsimplementedinasingledevice.Therefore,wepropose themethodofgeneratingtruerandomnumbersutilizingthe cir-cuitprimarilydesignedasaPUFbasedonROs.Weutilizethe ex-istingROPUFcircuit[9,10]alsoforTRNGgeneration,basedonthe factthatROcircuitsarewidelyusedasentropysourcesforTRNGs.
Inthispaper,weverifythatitispossibletodesigntheuniversal cryptosystembasedonROs,thatcanbeusedforvarious applica-tions – thePUFcanbeutilizedforasymmetriccryptographyand generatingasymmetrickeys,andtheTRNGforsymmetric cryptog-raphy.
Thepaperisorganizedasfollows–Section2presentsthe pro-posalofTRNGbasedonROPUFcircuit.Section3providesthe
re-sultsofexperimentaltesting.Twoexperimentswerecarriedout -duringfirstexperimentalsetupmultipleROpairsareactive simul-taneouslyandswitchingregulatorisusedaspowersupply,while duringsecondoneonlysingleROpairisactiveatagivenmoment andlinearregulatorisusedaspowersupplytoruleoutcrosstalk andparasiticfrequencies.Section4concludesthepaper.
2. Theproposedtruerandomnumbergeneratorbasedon ROPUFcircuit
As discussed in previous section, various implementation of cryptographicsystemscantakeanadvantagefromuniversalcircuit forgeneratingPUFandTRNGatthesametime.
Inpreviouswork [9,10],the ROPUFcircuitwasproposed. The principleisdepictedinFig.1– thebasicbuildingelementofthe proposedROPUFdesignisafivestageRO(1NAND, 4inverters).
InsteadofmeasuringfrequencyofeachROusingreferenceclock, wechoosetwoROs(aROpair),andcounttheiroscillations simul-taneously using two counters.Assoon as oneofthese counters overflows,themeasurementisstopped.Theresultingvalueinthe counterthatdidnotoverflowisused forfurtherprocessing. Ob-tainedmeasuredcountervaluesareusedasoutputand theyare notmodifiedinanyway.
Theworkin[9,10]showsthatthesevaluesarerepresentedin binarycode,theappropriatelyselectedpartofeachbinarynumber forPUFoutput.Further,the[9,10]assumesthatifwemake mul-tiplemeasurementsofoneROpair,bitsthatareclosetotheleast significantbit(LSB) willvary alot(forexample,dueto environ-mentalchanges).Onthecontrary,bitsclosetothemostsignificant bit(MSB)willbestableandtheenvironmentalchangeswillhave almost noinfluence on them.The morewewillbe closetothe MSB,themorestablethesebitswillbe.
GiventhefactthattheentropyofleastsignificantbitsofROPUF circuitishighandbitsvaryalot,aswellastheRO-basedcircuits are proventobesecuretobeusedasTRNGgeneration,we pre-sentedandvalidatedthe ideathatsingleROcircuitcan beused both forPUFand TRNGgeneration in[3]– principleisdepicted inFig.2. Themiddlebitsofgeneratedvalues(9–7)are usedfor PUF,whilethelowestbits(3–0)withhighestentropyareusedfor TRNG.
3. Experimentalresults
In following sections, the results of testing of the proposed TRNGarepresented.TheDigilentBasys2prototypingboard con-taining a XilinxSpartan3E-100 FPGAwas used for twoseparate sets of measurement. Forthe first measurements (presented in this section), weimplementeda circuit containing150ROpairs.
AllROpairswereactivesimultaneouslyduringthemeasurement.
An on-board switchingregulatorwas usedas thepower supply.
The scheme ofthe measurement setupis depicted in Fig.3. In Section3.5,we willmodifythesetuptolimittheinherentnoise andcrosstalkpresentinthefirstmeasurementsetup.
Themeasuredvaluesweresubjecttofurthertests.Toevaluate randomness,weusedNISTtestsuite[16]thatwascrafted specif-icallywith cryptographicoperationsinmind. Theversion ofthe usedNISTsoftwareisSTS2.1.2.Thetestsuiteconsistsof15tests, such as frequency test, runs test, cumulative sumstest, various variations on templates test, entropy test, serialtest or discrete Fouriertransformtest.
3.1. IndividualROpairstests
Firstofall,weexaminedsinglebitsfromeveryROpair,aswe considereveryROpairasa uniquesourceofentropy.Asthe in-putsequencesforthesetests,weusedtheraw,nonpost-processed
4.4. True random number generator based on ring oscillator PUF circuit
S. Buchovecká et al. / Microprocessors and Microsystems 53 (2017) 33–41 35
Fig. 1. ROPUF circuit [9,10] used for TRNG generation.
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
Increasing entropy Increasing stability
MSB LSB
Bits user for PUF Bits for TRNG?
Fig. 2. Behavior of bits in a 16-bit counter – The lower bits, the increasing entropy.
Fig. 3. First experimental setup – all RO pairs active simultaneously, a switching regulator used as power supply.
outputsfrom1,100,000measurements.Weselectedsinglebitfrom everyROpair output. Thus, we got 150×16 bitstreams, as de-pictedinFig.4.
Only someofthetestsfromNIST testsuite wererun inthis setup, as for the tests that require long input bit stream (106 bits×100sequencesatleast),wedidnothaveenoughdata gener-ated.Theteststhatwewereabletorunforsinglebitsforeachpair ofROwere Frequency test(for blocklength 8),Block frequency test,CumulativeSums,Runstest,LongestrunandApproximate en-tropytest(forblocklength7).
Theresultsofthetestsweresimilarforallofthepairs.Bit0 failsinsomeofthetests,bits1and 2showexcellent character-istics,bit 3failsinsome ofthe tests,and bits4and higherfail allofthe tests. Therefore, the bits0 – 3 canbe consideredfor
furthertesting.However,thereweresomeROpairs,thatdidnot showsatisfactoryresults– onlyfewuniquevaluesweregenerated during multipleruns,resulting theteststofail,thereforewe ex-cludedthesepairsfromfurtherprocessing.Theresultsofthetests aresummarizedinTable1.Thetableshowstheresultingmedian valuesfromindividualtestsofallROpairs(exceptexcludedones).
Thepassrateforthetestsis96/100andhigher.
3.2.ConcatenatedROpairsoutputstests
Theinitialtestshaveshown,thateachROpaircanbeusedas a sourceofentropy.Singlebits0to3forminguniquebitstream foreveryROpair havesatisfactorycharacteristics.However,such setupisnotpracticalforreal worlduse. Itmakesmoresenseto concatenatethebitsfromalloftheROpairs,(asshowninFig.5) toreachhigherrateofgeneratedbits.
Theconcatenatedbitstreamwassubjecttofurthertests.After concatenationtherewasenoughdatatorunalltestsfromtheNIST testsuite.Table2summarizestheresultsoftestingbits0to3.If thetestfailed forthedistributionofp-valuesthecellsare high-lightedinbold.Thepassrateis96/100,exceptforRandom Excur-sionsandRandomExcursionsVariants.Further,wealsotested con-catenatedbits0to3and1to3intosinglebitstream.Asthebit streamconsistingof0bitsfailsnotonlyinfrequencyand cumula-tivesumstests,butalsoinrunstest,weexamineditsinfluenceon combinedbitstream.Thetestsshowthatthestatisticalproperties ofgeneratedbitstreamsaresatisfactory,exceptforfrequencyand cumulativesumstests,thatarefocusedonuniformdistributionof 0sand1sinthetestedbitstream.However,thisoftenhappens whendealingwithtrulyrandomnumbergenerators.Thereare var-iouswaysofpostprocessingtodealwiththisproblem,ifwe as-sumethatthebiasistheonlyproblem,andthegeneratedbitsare statisticallyindependent[4]. Toenhancetheproperties of
gener-36 S. Buchovecká et al. / Microprocessors and Microsystems 53 (2017) 33–41 Fig. 4. Initial test - Single bits from every RO pair examined.
Table 1
Individual RO test–results of NIST STS tests. Each test was run for 150 generated bit streams and median and average values from 150 test output values is presented. Minimum allowed pass rate is 96/100.
Bit 0 1 2 3 4
Median Average Median Average Median Average Median Average Median Average Frequency 97/100 96 ,7/100 99/100 98 ,6/100 99/100 98 ,8/100 98/100 89 ,9/100 7/100 8 ,1/100 Fig. 5. Concatenating bits across RO pairs into single stream to get higher rate of generated bits.
ated bit stream,we involvedpostprocessingmethodsinfurther testing.
3.3.Post-processingthegeneratedbitstreamusingVonNeumann corrector
One of possible methods for de-biasing truly random bit streamswasintroducedbyVonNeumannandisdiscussedin de-tailin[12].TheprincipleofVonNeumanncorrectionisasfollows, iftheinputis“00” or“11”,theinputisdiscarded,iftheinputis
“10”,outputa“1”,iftheinputis“01”,outputa“0”.
TheresultsoftestsafterapplyingtheVon Neumanncorrector aresummarizedinTable3.Thebitstreamsconsistingofbits1–3 showsexcellentcharacteristicsaftercorrection.However,itshows, thatworsebit0characteristics,revealedinprevioustests(by fail-inginrunstest)influencetheoverallbitstream,andthusthebits 1to3canbeconsideredforfurtheruse.Asthe8pairsof oscil-latorswere excluded, we are ableto get142×3random bitsat onerun,shortenedbyapprox.75%duetopostprocessusingVon Neumanncorrector.
3.4.Post-processingthegeneratedbitstreamusingXORcorrector
TheresultsafterapplyingVonNeumanncorrectorare satisfac-tory, however the corrector shortens theoutput stream by75%.
Therefore,welookedatanotherwidelyusedmethod– simpleXOR correction, which shortensthe outputstream only by50%, asit takestwosubsequentbitsfrominputstream,XORsthemandputs theresultingbitintotheoutputstream.
TheresultsoftestsafterapplyingtheXORcorrectorare sum-marizedinTable3.Theresultsaresimilartothoseafterapplying VonNeumanncorrector– again,bitstreamsconsistingofbits1–3 showsexcellentcharacteristicsaftercorrection.Worsebit 0 char-acteristics,revealedinprevioustests(byfailinginrunstest) influ-encetheoverallbitstreamandXORcorrectiondoesnotsolvethis issue,andthusthebits1to3canbeconsideredforfurtheruse.As the8pairsofoscillatorswereexcluded,atonerunofthecircuit we areabletoget142×3randombitsshortenedby50%dueto postprocess.
4.4. True random number generator based on ring oscillator PUF circuit
S. Buchovecká et al. / Microprocessors and Microsystems 53 (2017) 33–41 37 Table 2
Concatenated RO test–The bit streams from n th bit from all RO pairs were concatenated and tested using NIST STS test suite. Furthermore, to achieve higher rate of generated bit stream, also bits 0–3 and 1–3 were concatenated. Minimum allowed pass rate is 96/100. The bold values indicate that the test failed for the distribution of p -values.
3.5.Rulingoutcrosstalkandparasiticfrequencies
ToruleoutpotentialcrosstalkbetweenindividualROpairsand parasitic frequencies from switching regulators influencing ran-domnessofgeneratedbitstreamandthustoverifythateachRO paircanbeconsideredasself-containedentropysource,wetested individualpairsseparately,usingasetoflinearregulatorsaspower supply.Forthispurpose,acircuitcontaining130ROpairswas im-plemented.ThelowernumberofROpairsiscausedbyadditional logicneededtoalloweachROpairtoberunandmeasured sep-arately (as opposed tonormal operation, whenallthe RO pairs runand are measured together). TheDigilent Basys2 prototyp-ingboardwasmodifiedsothattheoriginalpowersupplycircuit isdisconnectedandthe newpower supplyconsistsofa battery
ToruleoutpotentialcrosstalkbetweenindividualROpairsand parasitic frequencies from switching regulators influencing ran-domnessofgeneratedbitstreamandthustoverifythateachRO paircanbeconsideredasself-containedentropysource,wetested individualpairsseparately,usingasetoflinearregulatorsaspower supply.Forthispurpose,acircuitcontaining130ROpairswas im-plemented.ThelowernumberofROpairsiscausedbyadditional logicneededtoalloweachROpairtoberunandmeasured sep-arately (as opposed tonormal operation, whenallthe RO pairs runand are measured together). TheDigilent Basys2 prototyp-ingboardwasmodifiedsothattheoriginalpowersupplycircuit isdisconnectedandthe newpower supplyconsistsofa battery