PUF-derived IoT identities in a zero-knowledge protocol for blockchain

Depósi o de in es igación de la Uni e sidad de Se illa h ps://idus.us.es/ “This is an Accep ed Manusc ip o an a icle published by Else ie in In e ne o Things (The Ne he lands) on Ma ch 2020, a ailable a : h ps://doi.o g/10.1016/j.io .2019.100057 ” PUF-de i ed IoT iden i ies in a ze o-knowledge p o ocol o blockchain Miguel ´ Angel P ada-Delgado, Iluminada Ba u one Ins i u o de Mic oelec ´onica de Se illa, IMSE, CNM (Uni e sidad de Se illa, CSIC) Se ille, Spain Ge o Di mann, Jens Jeli o, And eas Kind IBM Resea ch – Zu ich, Swi ze land Abs ac As he in e ne o hings mo es in o inc easingly sensi i e domains, connec ed de ices need o be secu ed agains da a manipula ion and coun e ei ing. Whe e he unde lying business p ocesses in ol e mul iple independen pa ies, a block- chain pla o m can p o ide a common sou ce o u h. I changes o he common s a e depend on IoT de ices, he au hen ici y and in eg i y o he IoT inpu mus be ensu ed. Employing a blockchain pla o m o au hen ica ing de ices makes he p ocess independen o he de ice manu ac u e . This pape shows how c yp og aphic keys de i ed om a de ice’s physical inge p in can be employed in a ze o-knowledge p o ocol o au hen ica e a de ice. As he keys a e egene a ed a boo ime a he han s o ed, he app oach does no need an expensi e secu e elemen . An e icien implemen a ion enables e en ligh weigh de ices o p o e hei iden i y and sign messages. Expe imen al esul s demons a e he obus ness o he app oach. Keywo ds: PUF, IoT, blockchain, ze o-knowledge p oo , au hen ica ion, mic ocon olle , SRAM 1. In oduc ion The numbe o objec s wi h embedded mic ocon olle s (MCUs) connec ed o he in e ne o hings (IoT) is inc easing apidly [1]—also in he sa e y- P ep in submi ed o In e ne o Things May 12, 2019 and secu i y-c i ical medical, ene gy and au omo i e indus ies. The use o dis- ibu ed ledge echnology in combina ion wi h IoT de ices has gained a lo o 5 a en ion no only in he inancial sec o bu in many indus ies as a means o inc ease us and isibili y, e.g. along complex supply chains o mo e accu- a e goods acing, coun e ei de ec ion [2, 3] and in o ma ion e i ica ion [4]. Complex manu ac u ing lines and dis ibu ion sys ems can be secu ely moni- o ed and documen ed such ha downs eam business p ocesses can alida e10 he p o enance o p oduc s. This back- o-bi h aceabili y is c i ical and o en e en manda o y, e.g. in he ai line indus y o li e-limi ed pa s [5] o in he pha ma sec o o p esc ip ion medicine [6]. Likewise, ups eam business p o- cesses can de e mine he ecipien s o goods, o ins ance in case o a p oduc ecall.15 Blockchains le e age c yp og aphy, dis ibu ed p o ocols, and p i acy-enabling echniques (e.g. ze o-knowledge p o ocols, h eshold-signa u e schemes) o en- able us and o con ol isibili y o he in o ma ion in mul i-pa y en i on- men s [7]. In his ega d, i is o c ucial impo ance he p i acy p o ec ion in blockchain-based IoT sys ems om issues caused due o in o ma ion leakage20 [8]. A blockchain alone, howe e , is o en insu icien o p o e p oduc o iginal- i y o p o ide an unin e up ed and indispu able chain o cus ody h oughou he p oduc li e-cycle because i canno gua an ee he uniqueness o a physical en i y. In addi ion, an IoT connec ion is commonly used o moni o o con ol an25 objec connec ed o he blockchain. This connec ion wi h physical de ices is necessa y, bu i opens he doo o new a ack ec o s such as he injec ion o ha dwa e ulne abili ies by a malicious i mwa e upda e [9]. Fo secu i y, c yp- og aphic p o ocols au hen ica e he objec s wi h keys o passwo ds con igu ed by he manu ac u e 1. Au hen ica ion also add esses coun e ei p oduc s and30 ake eplacemen pa s which a e becoming mo e sophis ica ed and p esen a majo p oblem o many indus ies [10]. 1By manu ac u e we e e o he in eg a o a he han he p oduce o he MCU chip. 2 Hence, an IoT-enabled home appliance such as a washing machine whose con olle boa d ea u es a ne wo k connec ion mus be secu e, no only o p o- ec i sel om a acks bu o p o ec also he ne wo k o which i is connec ed.35 In he p oduc ion p ocess, he manu ac u e con igu es he con olle wi h a c yp og aphic key and s o e he coun e pa key in a da abase.2Once sold and deployed in he ield, he machine may equi e se ices o e ed by he manu- ac u e . To au hen ica e he machine, he manu ac u e sends a challenge ha he machine mus answe employing i s sec e key. The manu ac u e e i ies40 he esponse using he coun e pa key. Beyond au hen ica ion, he sec e key may also be used o signing da a sen by he machine, e.g., senso eadings, a es ing om which machine hey o igina e. In MCUs, he sec e key mus be s o ed in a way ha is no accessible om he ou side o make hem impossible o copy in o a coun e ei . The se-45 cu e elemen s ha p o ide such s o age [11], howe e , add signi ican cos and, consequen ly, ew con olle s ha e hem. In his pape , an al e na i e au hen ica ion app oach in which an MCU gen- e a es a sec e key in e nally is in oduced, exploi ing manu ac u ing a iabili y as a physical unclonable unc ion (PUF). As he key is gene a ed by he de-50 ice i sel , manu ac u e s sa e he expense o a secu e en i onmen o ex e nal key gene a ion. In p oduc ion, once chips a e loaded wi h a i mwa e, i is only necessa y o un an in e nal cha ac e iza ion and pass on he esul ing public key, mask and helpe da a o be s o ed o au hen ica ion and eco e y. Fu he ex e nal memo y access is p e en ed, e.g., by blowing he JTAG secu i y use.55 As he sec e key is egene a ed (wi h he same esul each ime) a he han s o ed in non- ola ile memo y, i is e y ha d o clone and he cos o a secu e elemen can be sa ed. The case o such IoT de ices is s eng hened u he in combina ion wi h a dis ibu ed ledge , o blockchain. Fi s o all, he immu abili y and dis ibu ed60 2In asymme ic c yp og aphy, he de ice is con igu ed wi h a p i a e key and he manu- ac u e s o es he public key; in symme ic c yp og aphy, bo h hold he same sec e key. 3 us p o ided by a blockchain can make he de ice au hen ica ion independen o he manu ac u e . Secondly, a business p ocess implemen ed in chaincode ha elies on IoT inpu s can alida e de ice signa u es o ensu e he au hen ici y and in eg i y o hose inpu s. Replacing he cen al da abase ope a ed by a manu ac u e wi h a blockchain65 makes he sys em independen o he manu ac u e . The chaincode will s ill al- low only he manu ac u e o c ea e new machine en ies on he dis ibu ed ledge bu as he ledge con en is dis ibu ed o all pa icipan s (mul iple man- u ac u e s, e aile s, owne s, e c.) he manu ac u e is elie ed o adminis e ing he sys em and gua an eeing i s a ailabili y. A cen al da abase would go o line70 when he manu ac u e goes ou o business whe eas a blockchain can su i e. Gi en he secu i y disad an ages o symme ic au hen ica ion schemes (keep- ing a da abase o keys o au hen ica e wi h he isk o being hacked o los , he isk o cloning, and ba ie s o hi d-pa y au hen ica ion, among o he s) ou app oach ins ead uses public-key c yp og aphy based on lea ning pa i y wi h75 noise (LPN) p oblems, and in pa icula ze o-knowledge (ZK) p o ocols o u - he simpli y he managemen o de ice public keys. The blockchain may make he public keys gene a ed by each de ice a ailable o anyone o use in hei own au hen ica ion sys em. As o he second aspec , e en a low-cos de ice can p e en manipula ion80 o i s communica ion wi h a blockchain by signing i s messages wi h ou PUF- de i ed keys, making he p oposal sui able o any esou ces-limi ed de ice con- nec ed o he blockchain [9]. The chain code, in u n, can also alida e he de ice signa u es o ensu e da a in eg i y and au hen ici y, ex ending he us he blockchain p o ides in o he IoT de ice.85 This pape p oposes using an SRAM-based PUF o gene a e c yp og aphic keys ha a e employed in a ze o-knowledge p oo o au hen ica e an IoT de ice. We p esen an e icien implemen a ion in an MCU and show ha e en low-cos de ices can pe o m he equi ed compu a ional asks su icien ly as . Expe - imen al esul s demons a e ha ou app oach is obus agains empe a u e90 a ia ions and ha collisions o de ice iden i ies a e unlikely. 4 This pape is s uc u ed as ollows. Sec ion 2 e iews ela ed wo k in digi al and physical us on he blockchain as well as PUFs using LPN p oblems o unde s and PUFs, ZK p oo s o knowledge, and exac LPN (xLPN) p oblems. Sec ion 3 desc ibes ou p oposal o use PUFs in c yp osys ems based on xLPN95 p oblems. An e icien implemen a ion o he p oposal on an MCU is desc ibed in Sec ion 4. Expe imen al esul s o he implemen a ion a e p esen ed in Sec ion 5. Finally, conclusions and u u e wo k a e gi en in Sec ion 6. 2. P elimina ies 2.1. Ex ension o us in o physical p oduc s100 An ex ension o he blockchain-p o ided us beyond he digi al in o he physical domain is equi ed o eliably de e mine p oduc o iginali y o o accu- a ely ace he mo emen o goods. The physical objec s mus be unequi ocally ied o hei associa ed digi al eco ds. Typically, a unique iden i ie (UID) is used o link a physical objec o a digi al eco d. The iden i ie can be unique in105 he sense ha i ep esen s an indi idual objec , o i can mo e b oadly iden i y a class o objec s by model, ba ch, p oduc ion si e, manu ac u e o simila [12]. A UID is ypically a ached as a ag, p in ed o embossed on he objec o i s packaging. Such iden i ie s, howe e , can o en easily be cloned o ans e ed o a ake objec . Hence, an iden i ie alone canno uniquely and secu ely iden i y,110 i.e., au hen ica e an objec . A b oad a ie y o concep s and solu ions has been s udied and in oduced o iden i y objec s secu ely and uniquely. The concep s include ha d- o-clone elec- onic ags [13], embedded secu i y ea u es such as hose ound in bankno es, all he way o physical inge p in s o he objec s hemsel es. Such inge p in s115 ypically esul om uncon ollable ma e ial o manu ac u ing a iabili ies and a e well s udied in he con ex o PUFs [14, 15]. Examples include he s uc u e o lea he , he imp in o p oduc ion-line ools, o he doping in semiconduc o s. The a iabili y may be a common p oduc ion side-e ec (in insic) o speci i- cally in oduced (ex insic), o ins ance by adding special pa icles [16] o colo 120 5 codes [17] o medical p oduc s. 2.2. PUFs and compu a ionally ha d p oblems The e m PUF was used o he i s ime o cha ac e ize he physical mi- c os uc u e in oduced by andom a ia ions o a manu ac u ing p ocess, pa - icula ly o he CMOS ab ica ion p ocess [18, 19]. The unique a ia ions be-125 ween CMOS componen s a e exploi ed by a ha dwa e PUF o gene a e unique, componen -speci ic esponses o iden ical challenges. Howe e , since PUF e- sponses change sligh ly om one measu emen o ano he , he use o a uzzy ex ac o was p oposed o help econs uc ing a cons an and unique esponse linked o he physical cha ac e is ics o a PUF [20].130 Recen ly, he use o lea ning wi h e o (LWE) p oblems was p oposed [21] in a LWE-based lossless compu a ional uzzy ex ac o as a way o p o ec sec e in o ma ion in a compu a ionally secu e manne . In a e y simila way, [22, 23] used lea ning pa i y wi h noise (LPN) o c ea e a compu a ional uzzy ex ac o and c yp og aphically-secu e PUF. Tha p oposal uses an LPN-based135 challenge- esponse p o ocol oge he wi h a symme ic key (ob usca ed by he compu a ional uzzy ex ac o ) o au hen ica e he PUF. Despi e he in e es ing ad an ages o compu a ional uzzy ex ac o s, hei use is ou side he scope o his wo k, and we will use only adi ional uzzy ex ac o s o simplici y. 2.3. Physical unclonable unc ions p ope ies and me ics140 The e is always una oidable a iabili y du ing he manu ac u ing p ocess o any de ice. In his con ex , a PUF is a physically e alua ed unc ion ha exploi s he andom a iabili y unin en ionally in oduced in he de ice p oduc ion. Be- cause o he uncon ollable na u e o hese a ia ions, hey a e impossible o clone and he esponses o a challenge can iden i y di e en de ices uniquely,145 like inge p in s. To be conside ed as a PUF, he ollowing p ope ies mus be sa is ied [15]: •Rep oducibili y: The esponse o a PUF o a gi en challenge mus be he same o e ime. 6 •Uniqueness: The esponses o di e en PUFs o a gi en challenge mus be150 e y di e en . •Unp edic abili y: I di e en challenges a e p o ided o a PUF, i s e- sponses mus be comple ely di e en and unp edic able. As PUF esponses a e ypically digi al hese p ope ies a e commonly e al- ua ed using he Hamming dis ance (HD) [24] which ep esen s he pe cen age o di e en bi s be ween PUF esponses as ollows: HD( i, gj) = 1 L L−1 X b=0 i[b]⊕gj[b] (1) whe e iand gj ep esen he esponse o a PUF o he challenge iand g o he challenge j, espec i ely; Lis he leng h o he esponse ec o in bi s and155 bis a bi posi ion in he esponse ec o , and ’⊕’ deno es bi wise XOR. I is he esponse o a PUF a a ime = 1 o a gi en challenge i, and g is he esponse o his PUF a ime = 2 o he same challenge (i=j) hen Equa ion 1 yields he in a-de ice Hamming dis ance (in a-HD), e alua ing he ep oducibili y o he PUF esponses by i s e o , which ideally should be 0. I ,160 in con as , gis he esponse o his PUF a = 1 o a di e en challenge (i6=j) hen Equa ion 1 e alua es he unp edic abili y o he PUF esponses by hei simila i y, wi h an ideal alue o 50%. Finally, i gis he esponse o ano he PUF a any ime o he same challenge, hen Equa ion 1 gi es he in e -de ice Hamming dis ance (in e -HD) and e alua es he uniqueness o he PUFs by he165 simila i y o hei esponses, whose ideal alue is 50%. Ano he me ic ha can be used o e alua e he PUF p ope ies is he min- imum en opy [24]. I gi es he pe cen age o andomness in a se o sequences wi h he ollowing equa ion: Hmin (pmax) = 1 L L−1 X b=0 −log2(pmax [b]) (2) whe e pmax [b] ep esen s he maximum p obabili y o aking logic alue 0 o 1 obse ed a he b h bi o he PUF esponse. 7 I pmax [b] is calcula ed in a single PUF using esponses o e ime o he same challenge, hen Equa ion 2 e alua es he ep oducibili y and he minimum170 en opy should ideally be 0. I he esponses a e gene a ed using di e en chal- lenges, hen i e alua es he unp edic abili y and he minimum en opy should ideally be 100%. Finally, i he esponses a e ob ained om di e en PUFs, hen he p ope y e alua ed is he uniqueness, and he minimum en opy should ide- ally be 100%.175 2.4. Fuzzy ex ac o s PUF esponses will be e y simila bu no exac ly he same o successi e gene a ions. The e o e, an e o -co ec ing code (ECC) has o be implemen ed o econs uc a s able esponse. Fuzzy ex ac o s [25] ha e been widely used in PUFs oge he wi h a so -decision helpe -da a algo i hm [20]. The PUF quali y180 can be u he imp o ed by condi ioning esponses o elimina e uns able bi s and bias. To do his, he algo i hm desc ibed in [26, 27] i s akes mul iple esponses om a PUF and compa es hem o de ec which bi s o he esponse a e s able and which bi s a e uns able. This esul is exp essed as masks o s able and185 uns able bi s. Conside ing only he s able bi s inc eases he ep oducibili y o he PUF esponses. The masks a e used o c ea e unique iden i ie s o keys om s able bi s, and andom seeds om uns able bi s. The s able bi s selec ed om he PUF esponse may be biased owa ds ei he 1 o 0 and he e o e mus be condi ioned be o e being used in a c yp og aphic190 algo i hm. In [26], he pai -ou pu on Neumann algo i hm (2O-VN) is in o- duced o debiasing. I c ea es ano he mask ha , combined wi h he mask o s able bi s, esul s in a selec ion mask. The bi sequence ob ained a e ap- plying he selec ion mask is a PUF esponse wi h highe ep oducibili y and unp edic abili y, hus sui able o c yp og aphy.195 The ope a ion o uzzy ex ac o s can be di ided in o wo phases: egis a ion and gene a ion. The egis a ion phase akes he debiased s ing o he PUF, D, and combines i wi h an n- imes epe i ion o a sec e key s,C=REPEAT(s, n), 8 Subsec ion 2.6, he de ice needs he sec e e o , e, o calcula e C2. Since he de ice s o es i s public key (o i is p o ided om he ou side a e i is powe ed up), i can compu e e=A·s⊕y. Besides, his e o can be e i ied as easily as coun ing he numbe o bi s wi h alue ’1’ o he ec o ob ained, i.e., calcula ing350 i s Hamming weigh . As explained in [29], i he e we e a single w ong bi in s, he ec o eob ained would look like a uni o m andom a iable, and he p obabili y ha i s weigh we e equal o wwould be negligible hanks o he ha dness o he xLPN p oblem. This allows he de ice no only o e i y he co ec ness o he e o bu also o de ec i be o e exchanging any message in355 he ZK p o ocol. 4. E icien implemen a ion on a mic ocon olle 4.1. Ha dwa e pla o m One o he main challenges o many c yp og aphic algo i hms is he an- si ion om heo e ical desc ip ion o implemen a ion, especially when i comes360 o making e icien use o ha dwa e esou ces. We used SRAM PUFs o com- me cial mic ocon olle s [26] o ob ain he in insic iden i y o elec onic de ices and es i s sui abili y as sec e s o he ZK p oo s de ailed in Sec ion 3. The in e ac i e ze o-knowledge p oo s make i impossible o ans e he us , and so he iden i y canno be coun e ei ed.365 While he p o ocol is gene ic and simple enough o wo k in any mic ocon- olle , he ideal de ice should ha e enough pe sis en memo y o s o e cha ac- e iza ion da a (such as ma ix A) o a oid ecalcula ing i o e e y i e a ion o ecei ing i om he e i ie . I is also ecommended o ha e c yp og aphic accele a o s a ailable in low powe mic ocon olle s o simpli y he design, all370 wi hou ha ing o d aw upon mo e expensi e high- equency p ocesso s o DSPs. We ha e implemen ed ou app oach on a Texas Ins umen s (TI) Launch- PadTM de elopmen ki wi h a 16-bi RISC MSP430FR5994 mic ocon olle a 16 MHz. In addi ion, we designed a command-line in e ace (CLI) in MAT- LABTM o in e ac wi h he mic ocon olle ia a se ial po . In his se up,375 15 he mic ocon olle ac s as p o e while he CLI ac s as a e i ie and sends challenges in o de o e i y he ZK p oo s. The mic ocon olle has 8 KB o SRAM, 256 KB o e oelec ic andom- access memo y (FRAM) and uses a lib a y ha implemen s he NIST s anda d o he coun e -mode de e minis ic andom bi gene a o (CTR-DRBG) [35] us-380 ing i s AES ha dwa e accele a o . I also has a low-ene gy accele a o o signal p ocessing, se e al ul a-low-powe modes, and up o ou eUSCI po s (TI’s enhanced uni e sal se ial communica ion in e ace). We used all hese cha ac- e is ics o simpli y he de elopmen o ou p oo o concep . Rega ding he use o PUFs, he de ice sel -cha ac e iza ion is mo e esou ce-385 demanding han he e i ica ion s ep. Howe e , his p ocess is ca ied ou only a he egis a ion phase o he uzzy ex ac o and can be ully au oma ed wi hin he de ice. Wi h espec o he ZK p o ocol, he asks ha equi e he highes compu a ional powe a e he mul iplica ion o ma ices and he gene a ion o andom numbe s. The implemen a ion o all hese algo i hms and he pa icula 390 solu ions p oposed a e p esen ed in he ollowing. 4.2. Sel -cha ac e iza ion While many TI mic ocon olle s a e low powe , hose o he FRAM amily ea u e ul a-low-powe modes. They can shu down pa s o he sys em on a chip (SoC) in a con olled way, powe ing down anscei e s and pe iphe als,395 clocks and he SRAM. We use he ul a-low-powe mode LPM 3.5 and he eal- ime clock o powe cycle he p ocesso a e a p ede ined ime o e ase he in o ma ion s o ed in SRAM and all egis e s. A e each powe cycle, he SRAM s a -up alues ep esen he PUF esponses used in he uzzy ex ac o , as de ailed in Subsec-400 ion 2.4. The FRAM, which is non- ola ile, is employed o s o e he mul iple measu emen s o PUF esponses needed o gene a e he bi -selec ion mask. 4.3. Ma ix and ec o ope a ions in xLPN Ma ix and ec o mul iplica ions a e compu a ionally cos ly ope a ions. In he p o ocol employed, hey a e equi ed o gene a e he public key in he o m405 16 y=A·s⊕e, o calcula e he pe ec ly binding commi men (as de ailed in Subsec ion 2.6), and o gene a e he commi men messages o he p oo s (as de ailed in Subsec ion 2.7). As discussed in [29], xLPN ope a ions ha e a simila complexi y o decoding andom linea codes. Thanks o wo king wi h bina y ec o p oduc s and XOR410 sums, he ope a ions a e equi alen o pe o ming linea combina ions o ec o s. The bina y ec o sin he ope a ion y=A·s⊕eindica es which columns o A should pa icipa e in he calcula ion o he pa i y sum along wi h he ec o e. Only he columns ha a e mul iplied by a non-ze o alue a ec he esul . One way o combine he ec o p oduc s is employing XOR sums, educing he xLPN415 p oduc o linea combina ions o he columns o A ha a e mul iplied by non- ze o elemen s o s. Figu e 2 shows an example in which he non-ze o elemen s o s a e {0,2,3}, and he e o e ycan be calcula ed as y=A(:,0)⊕A(:,2)⊕A(:,3)⊕e. 𝒚 = 𝑨 ∙ 𝒔 ⨁ 𝒆 𝑘 𝑘 ℓ + 𝑛 𝑘 ℓ+ 𝑛 10101 10001 10110 10011 00100 11010 10001 00101 11001 01100 1 0 1 1 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 1 0 1 1 1 0 Figu e 2: Linea combina ions o Acolumns wi h noise e. When his ope a ion is used o calcula e he commi men s, he claimed in- 17 o ma ion mus be compac ed o he size o s, which is analogous o gene a ing420 mul iple p oduc s o ma ix Awi h pieces o he claim, and hen add an e o e. In o he wo ds, when used o calcula ing Com(m) = A·( ||m)⊕ewi h m∈ In, i o example he claim mhad size k=O(n) = β·nins ead o size n, and i could be desc ibed as m= [m1, m2, ..., mβ], hen: Com(m) = β M i=1 [A·( i||mi)] ⊕e=A· || β M i=1 [mi]!⊕e o eR ← Ik w, i R ← I`, and Lβ i=1 i= . In his equa ion, he message o 425 leng h βn is compac ed using XOR ope a ions in o a message o leng h n, and only a single xLPN ope a ion is equi ed o calcula e he commi men o his claim. This comp ession is e y use ul especially o he commi men o he andom pe mu a ion which helps o educe he size om k·log2(k) o n. 4.4. Va ian s o he de e minis ic andom bi gene a o 430 The p o ocol equi es andom ec o s om a uni o m dis ibu ion in mul iple s eps. We gene a e hem using he mic ocon olle ’s AES ha dwa e accele a o in he NIST app o ed CTR-DRBG mode4. O he pa s o he algo i hm, such as he weigh ed e o s o he andom ec o pe mu a ions, equi e andom se- quences o a di e en na u e. The algo i hms used o adap he andom numbe 435 gene a o o ul ill hese p o ocol equi emen s a e desc ibed in he ollowing. 4.4.1. Weigh ed uni o m andom bi gene a o The CTR-DRBG unc ions a e used o gene a e a weigh ed uni o m dis i- bu ion. The sequences needed by he xLPN p oblem should ha e a Hamming weigh no o won a e age bu exac ly equal o w. To achie e his, he imple-440 men ed algo i hm s a s om an all-ze os ec o o kelemen s deno ed as 0k. Since he esul ing ec o mus ha e a cons an weigh , i means ha w=bτke ones a e inse ed in he sequence o ze os. The posi ions in which he wones a e 4Al e na i ely, a C implemen a ion o he AES algo i hm can be used o a p ocesso wi hou such an accele a o . 18 in oduced ollow a uni o m dis ibu ion o andom alues in he ange [0, k −1] p o ided by he CTR-DRBG. I a andom posi ion is epea ed, i is disca ded,445 and a new posi ion is gene a ed un il wones a e inse ed. Figu e 3 shows he diag am ha desc ibes he algo i hm. 2 Fo ha eason, ou modi ica ion o e he Knu h Shu le algo i hm pe o ms a modulo ope a ion, bu only using powe s o 2 𝑤 [0,𝑘 − 1] 0𝑘→ 1𝑤 Figu e 3: Weigh ed andom numbe gene a o using CTR-DRBG. 4.4.2. Random pe mu a ion gene a ion Ins ead o gene a ing andom posi ions by ial and e o o all elemen s o a ec o , we de eloped and implemen ed a a ian o he Knu h shu le algo i hm.450 The o iginal algo i hm s a s wi h any pe mu a ion ( o example, he iden i y pe mu a ion) w i en o a s ing π[ ] o size k. Then, i poin s o posi ions 0 h ough k−2 using an index a iable i(assuming he ec o elemen s a e indexed 0 o k−1). Fo each posi ion o i, he algo i hm swaps he elemen in ha posi ion wi h a andomly chosen elemen be ween and including posi ions455 iand k−1 ( he end o he ec o ). The e a e some issues ega ding he andom numbe gene a ion in he ange i o k–1. The CTR-DRBG o he chosen mic ocon olle always p oduces a 128-bi ou pu , so he ou pu is pos -p ocessed o ma ch he in e al [i, k–1]. 19 Applying echniques such as modulo ope a o o he ou pu o he RNG will no 460 gene a e he uni o m ou pu in he desi ed ange bu a biased s ing in which he lowe pa o he ange has a highe p obabili y o occu ence. [𝑘 − 𝑥,𝑘 − 1] M andom numbe s (posi ions) 0 𝑘 ze os bi s ing 𝑘 bi s wi h exac ly ⌊𝑘 × 𝜏⌉ weigh 1 ⌊𝑘 × 𝜏⌉ one bi s 𝑚𝑜𝑑(𝑥)+𝑘 − 𝑥 [0,2128 − 1] Figu e 4: Random pe mu a ion gene a o based on he Knu h shu le. To add ess his p oblem, ou modi ica ion o he Knu h shu le algo i hm, shown in Figu e 4, pe o ms a modulo ope a ion using only powe s o 2 (which is equi alen o elimina ing he leas signi ican bi s). Wi h his change i gen-465 e a es andom numbe s in he ange [0, x −1] o x= 2n, making he Knu h shu le algo i hm mo e e icien while main aining a p obabili y o occu ence ha ollows he uni o m dis ibu ion. Besides, kmus be a powe o wo so ha he absence o bias is also sa is ied when educing he ange o andom numbe s om [0,2128 −1] o [0, k−1]. I is wo h no ing ha modulo 2nope a ions can be470 implemen ed by shi ing a egis e by nbi s. This g ea ly simpli ies compu ing on any de ice wi h limi ed esou ces. 20 The modi ied Knu h shu le algo i hm o andom pe mu a ions is summa- ized in algo i hm 1. The p obabili y o epea ing a andom posi ion will be always in he ange (0,0.5) wi h his modi ica ion. Wi h he o iginal imple-475 men a ion (wi hou applying modulo) he p obabili y o epea ing a andom posi ion ends o (1 −1/k) when i ends o k. Gi en ha each i e a ion o he ZK p o ocol equi es pe mu a ions, his imp o emen subs an ially inc eases he pe o mance o ou implemen a ion. Algo i hm 1 Random pe mu a ion gene a o based on he Knu h shu le p ocedu e Gene a e a andom pe mu a ion, π∈ Sk Ini ialize a iables: π←[0,1,2,3, ..., k −2, k −1] i←0 while i < k: x←2dlog2(k−i)e p←CTR-DRBG[0,2128 −1] mod (x)+k−x i p≥i hen swap(π[i], π[p]) i←i+ 1 5. Expe imen al esul s480 This sec ion de ails he expe imen al esul s as well as he p o ocol imple- men a ion. P o ec ion o he de ice agains side-channel a acks is beyond he scope o his wo k. To p e en some o hese a acks, such as di e en ial powe analysis (DPA), he sys em should be buil in such a way ha i is impossible o ex ac any in o ma ion om he ou side, e.g., by measu ing elec omagne ic485 adia ion. Conside ing a acks ia he JTAG po , he secu i y uses should be blown once he de ice is pu in o p oduc ion. These coun e measu es a e conside ed s anda d in he indus y when dealing wi h secu e sys ems. We an he expe imen s on 10 TI LaunchPadsTM wi h MSP430FR5994 mi- 21 c ocon olle s. In o al we ook 120 eadings o he comple e SRAM (8 KB)490 o each mic ocon olle a 3 di e en empe a u es, wi h he de ice powe ed o be ween measu emen s o wo seconds by LPM 3.5.5This numbe o mea- su emen s and ope a ing condi ions ha e p o en o be su icien o cha ac e ize SRAMs co ec ly and ob ain hei mask in an e icien way [24]. F om each se o 120 measu emen s, we used 20 measu emen s o compu e he selec ion495 mask o he de ices. Wi h he emaining 100 measu emen s we e alua ed he p ope ies o he mic ocon olle SRAM PUFs ( ep oducibili y, uniqueness, and unp edic abili y). As shown in [24], empe a u e a ia ions al e he beha io o SRAM PUFs signi ican ly. The empe a u es suppo ed by he mic ocon olle ange om500 −40 ◦C o +85 ◦C, acco ding o he manu ac u e . We conduc ed expe imen s a a±5◦C ma gin om hese bounda ies, a −35 ◦C and 80 ◦C, and a a con olled nominal empe a u e o 25 ◦C. We calcula ed he in a-de ice Hamming dis ance (in a-HD) and in e - de ice Hamming dis ance (in e -HD) acco ding o Equa ion 1. Figu e 5(a) shows505 in a-HD in one de ice a −35 ◦C wi h and wi hou selec ion mask, and Fig- u e 5(b) he in e -HD conside ing all he 10 de ices a −35 ◦C. Figu es 6 and 7 show he same in a-HD and in e -HD ep esen a ions a 25 ◦C and 80 ◦C, espec i ely. I can be seen how he selec ion mask d as ically educes he in a-HD by510 mo e han 50% a ex eme empe a u es, and app oxima ely 90% in nominal condi ions, app oaching he op imal in a-HD alue o 0%. The in e -HD dis i- bu ions, on he o he hand, a e p ac ically una ec ed by he mask wi h a e ages a ound he ideal uniqueness alue o 50%. Ano he c i ical pa o he ze o-knowledge p oo p o ocol is he gene a ion515 o andom numbe s. I is impo an o e alua e he quali y, i.e., unp edic abili y 5The ime be ween measu emen s has been de e mined by cha ac e izing he mic ocon- olle s o his pa icula p o o ype. I mus be adjus ed o each indi idual ype o mic ocon- olle o in eg a ed ci cui . 22 (a) (b) Figu e 5: In a- and in e -de ice Hamming dis ance (exp essed in %) wi h and wi hou selec- ion mask a −35 ◦C. o he seeds ha a e used o eed he pseudo andom numbe gene a o . Since hese seeds come om he uns able cells o he SRAM, we mus e alua e hei minimum en opy as de ailed in Equa ion 2. The expe imen al esul s o his me ic can be seen in Figu e 8, wi h and wi hou selec ion mask, a −35 ◦C,520 25 ◦C and 80 ◦C. 10 20 30 40 50 60 70 80 90 100 Numbe o measu emen s 0 5 10 15 20 25 30 35 Pe cen age o Hmin Masked a -35ºC Unmasked a -35ºC Masked a 25ºC Unmasked a 25ºC Masked a 80ºC Unmasked a 80ºC Figu e 8: Minimum en opy a −35 ◦C, 25 ◦C and 80 ◦C, wi h and wi hou selec ion mask. 23 (a) (b) Figu e 6: In a- and in e -de ice Hamming dis ance (exp essed in %) wi h and wi hou selec- ion mask a 25 ◦C. Tables 1 and 2 show he indi idual measu emen s o a e age in a-HD and minimum en opy in he en de ices, cha ac e ized a −35 ◦C, 25 ◦C and 80 ◦C, bo h wi h and wi hou he mask. We obse e ha he ela i e beha io o all de ices is simila , jus showing sligh ly di e en absolu e alues owing o hei 525 di e en manu ac u ing a ia ions. De ice 1 2 3 4 5 6 7 8 9 10 Unmasked a −35 ◦C 5.18 5.31 5.02 4.24 3.98 4.94 4.23 5.14 4.91 4.86 Masked a −35 ◦C 1.99 3.86 3.79 3.86 2.31 2.35 1.96 3.96 1.95 2.65 Unmasked a 25 ◦C 4.98 5.02 4.90 5.03 4.27 4.89 4.58 4.58 5.02 4.59 Masked a 25 ◦C 0.44 0.45 0.42 0.45 0.36 0.43 0.40 0.38 0.42 0.33 Unmasked a 80 ◦C 4.85 4.71 4.67 4.40 4.80 4.71 4.90 3.57 4.41 4.11 Masked a 80 ◦C 2.45 2.70 2.48 3.50 3.51 2.41 3.36 1.58 2.01 1.98 Table 1: A e age in a-HD pe cen age o en de ices a −35 ◦C, 20 ◦C and 80 ◦C wi h and wi hou mask. 24 Re e ences [1] A. No d um, Popula In e ne o Things Fo ecas o 50 Billion De ices by 2020 Is Ou da ed, IEEE Spec um (2016) 0–2.635 URL h ps://spec um.ieee.o g/ ech- alk/ elecom/in e ne / popula -in e ne -o - hings- o ecas -o -50-billion-de ices-by-2020-is-ou da ed [2] N. Kshe i, Blockchain’s oles in mee ing key supply chain managemen objec i es, In e na ional Jou nal o In o ma ion Managemen 39 (2018) 80–89. doi:10.1016/J.IJINFOMGT.2017.12.005.640 URL h ps://www.sciencedi ec .com/science/a icle/pii/ S0268401217305248 [3] K. W¨us , A. Ge ais, Do you need a Blockchain?, ep in .iac .o g. URL h ps://ep in .iac .o g/2017/375.pd [4] Q. Xu, C. Jin, M. F. B. M. Rasid, B. Vee a alli, K. M. M. Aung,645 Blockchain-based decen alized con en us o docke images, Mul ime- dia Tools and Applica ions 77 (14) (2018) 18223–18248. doi:10.1007/ s11042-017-5224-6. URL h p://link.sp inge .com/10.1007/s11042-017-5224-6 [5] P ese ing ai c a alue: echnical eco ds in comme cial leases.650 URL h ps://ae o ime.ae o/zi ile.zalagenai e/ 20740-p ese ing-ai c a - alue- echnical- eco ds-in-comme cial-leases [6] Pha maceu ical T aceabili y. URL h ps://www.hda.o g/issues/pha maceu ical- aceabili y [7] E. And oulaki, A. Ba ge , V. Bo niko , C. Cachin, K. Ch is idis, A. De655 Ca o, D. Enyea , C. Fe is, G. La en man, Y. Mane ich, S. Mu alidha- an, C. Mu hy, B. Nguyen, M. Se hi, G. Singh, K. Smi h, A. So nio i, C. S a hakopoulou, M. Vukoli´c, S. W. Cocco, J. Yellick, Hype ledge Fab- ic: A Dis ibu ed Ope a ing Sys em o Pe missioned Blockchains, in: P oceedings o he Thi een h Eu oSys Con e ence, ACM, 2018. doi:660 31 10.1145/3190508.3190538. URL h p://a xi .o g/abs/1801.10228 [8] M. U. Hassan, M. H. Rehmani, J. Chen, P i acy p ese a ion in blockchain based IoT sys ems: In eg a ion issues, p ospec s, challenges, and u u e esea ch di ec ions, Fu u e Gene a ion Compu e Sys ems 97 (2019)665 512–529. doi:10.1016/J.FUTURE.2019.02.060. URL h ps://www.sciencedi ec .com/science/a icle/pii/ S0167739X18326542 [9] M. A. Khan, K. Salah, IoT secu i y: Re iew, blockchain solu ions, and open challenges, Fu u e Gene a ion Compu e Sys ems 82 (2018) 395–411.670 doi:10.1016/j. u u e.2017.11.022. URL h ps://linkinghub.else ie .com/ e ie e/pii/ S0167739X17315765 [10] M. M. Teh anipoo , U. Guin, S. Bhunia, In asion o he ha dwa e sna che s, IEEE Spec um 54 (5) (2017) 36–41. doi:10.1109/MSPEC.2017.7906898.675 URL h p://ieeexplo e.ieee.o g/documen /7906898/ [11] C. Shephe d, G. A aoui, I. Gu ulian, R. P. Lee, K. Ma kan onakis, R. N. Ak am, D. Sau e on, E. Conchon, Secu e and T us ed Execu- ion: Pas , P esen , and Fu u e - A C i ical Re iew in he Con ex o he In e ne o Things and Cybe -Physical Sys ems, in: 2016 IEEE680 T us com/BigDa aSE/ISPA, IEEE, 2016, pp. 168–177. doi:10.1109/ T us Com.2016.0060. URL h p://ieeexplo e.ieee.o g/documen /7846943/ [12] GS1 UniqueID — GS1. URL h ps://www.gs1.o g/gs1-uniqueid685 [13] C yp oSeal (CSS100) – Ch onicled. URL h ps://s o e.ch onicled.com/p oduc s/c yp o-seal-s ip 32 [14] R. Maes, Physically unclonable unc ions : cons uc ions, p ope ies and applica ions, Sp inge , 2013. [15] C. B¨ohm, M. Ho e , C. Bohm, M. Ho e , Physical Unclonable Func ions in690 Theo y and P ac ice., Sp inge , 2012. doi:10.1007/978-1-4614-5040-5. [16] G. M. Miyake, R. A. Wei ekamp, V. A. Piuno a, R. H. G ubbs, Syn hesis o Isocyana e-Based B ush Block Copolyme s and Thei Rapid Sel -Assembly o In a ed-Re lec ing Pho onic C ys als, Jou nal o he Ame ican Chemical Socie y 134 (34) (2012) 14249–14254. doi:10.1021/ja306430k.695 URL h p://pubs.acs.o g/doi/10.1021/ja306430k [17] O. G¨ok¸ce, C. Me cande i, E. Delama che, High-Con en Op ical Codes o P o ec ing Rapid Diagnos ic Tes s om Coun e ei ing, Analy ical Chem- is y 90 (12) (2018) 7383–7390. doi:10.1021/acs.analchem.8b00826. URL h p://pubs.acs.o g/doi/10.1021/acs.analchem.8b00826700 [18] R. Pappu, B. Rech , J. Taylo , N. Ge shen eld, Physical One-Way Func- ions, Science 297 (5589). [19] B. Gassend, D. Cla ke, M. an Dijk, S. De adas, Silicon physical andom unc ions, in: P oceedings o he 9 h ACM con e ence on Compu e and communica ions secu i y - CCS ’02, ACM P ess, New Yo k, New Yo k,705 USA, 2002, p. 148. doi:10.1145/586110.586132. URL h p://po al.acm.o g/ci a ion.c m?doid=586110.586132 [20] R. Maes, P. Tuyls, I. Ve bauwhede, Low-O e head Implemen a ion o a So Decision Helpe Da a Algo i hm o SRAM PUFs, Sp inge , Be lin, Heidelbe g, 2009, pp. 332–347. doi:10.1007/978-3-642-04138-9_24.710 URL h p://link.sp inge .com/10.1007/978-3-642-04138-9{_}24 [21] C. Hu h, D. Becke , J. G. Me chan, P. Duplys, T. Guneysu, Secu ing Sys ems Wi h Indispensable En opy: LWE-Based Lossless Compu a ional Fuzzy Ex ac o o he In e ne o Things, IEEE Access 5 (2017) 11909– 33 11926. doi:10.1109/ACCESS.2017.2713835.715 URL h p://ieeexplo e.ieee.o g/documen /7944563/ [22] C. He de , L. Ren, M. an Dijk, M.-D. Yu, S. De adas, T apdoo com- pu a ional uzzy ex ac o s and s a eless c yp og aphically-secu e physical unclonable unc ions, IEEE T ansac ions on Dependable and Secu e Com- pu ing 14 (1) (2017) 65–82. doi:10.1109/TDSC.2016.2536609.720 URL h p://ieeexplo e.ieee.o g/documen /7422776/ [23] C. Jin, C. He de , L. Ren, P. Nguyen, B. Fulle , S. De adas, M. an Dijk, FPGA Implemen a ion o a C yp og aphically-Secu e PUF Based on Lea ning Pa i y wi h Noise, C yp og aphy 1 (3) (2017) 23. doi: 10.3390/c yp og aphy1030023.725 URL h p://www.mdpi.com/2410-387X/1/3/23 [24] I. Ba u one, M. A. P ada-Delgado, S. Ei oa, Imp o ed Gene a ion o Iden- i ie s, Sec e Keys, and Random Numbe s F om SRAMs, IEEE T ans- ac ions on In o ma ion Fo ensics and Secu i y 10 (12) (2015) 2653–2668. doi:10.1109/TIFS.2015.2471279.730 URL h p://ieeexplo e.ieee.o g/documen /7217837/ [25] Y. Dodis, R. Os o sky, L. Reyzin, A. Smi h, Fuzzy Ex ac o s: How o Gene a e S ong Keys om Biome ics and O he Noisy Da a, SIAM Jou - nal on Compu ing 38 (1) (2008) 97–139. doi:10.1137/060651380. URL h p://epubs.siam.o g/doi/10.1137/060651380735 [26] M. A. P ada-Delgado, A. Vazquez-Reyes, I. Ba u one, Physical unclonable keys o sma lock sys ems using Blue oo h Low Ene gy, in: IECON 2016 - 42nd Annual Con e ence o he IEEE Indus ial Elec onics Socie y, IEEE, 2016, pp. 4808–4813. doi:10.1109/IECON.2016.7792955. URL h p://ieeexplo e.ieee.o g/documen /7792955/740 [27] R. A jona, M. A. P ada-Delgado, J. A cenegui, I. Ba u one, A PUF- and Biome ic-Based Ligh weigh Ha dwa e Solu ion o Inc ease Secu i y a 34 Senso Nodes, Senso s 18 (8) (2018) 2429. doi:10.3390/s18082429. URL h p://www.mdpi.com/1424-8220/18/8/2429 [28] S. Goldwasse , S. Micali, C. Racko , The knowledge complexi y o in e -745 ac i e p oo -sys ems, in: P oceedings o he se en een h annual ACM sym- posium on Theo y o compu ing - STOC ’85, ACM P ess, New Yo k, New Yo k, USA, 1985, pp. 291–304. doi:10.1145/22145.22178. URL h p://po al.acm.o g/ci a ion.c m?doid=22145.22178 [29] A. Jain, S. K enn, K. Pie zak, A. Ten es, Commi men s and E icien 750 Ze o-Knowledge P oo s om Lea ning Pa i y wi h Noise, Sp inge , Be lin, Heidelbe g, 2012, pp. 663–680. doi:10.1007/978-3-642-34961-4_40. URL h p://link.sp inge .com/10.1007/978-3-642-34961-4{_}40 [30] N. M. D¨o ling, C yp og aphy based on he Ha dness o Decoding, Ph.D. hesis (2014).755 [31] K. Pie zak, C yp og aphy om Lea ning Pa i y wi h Noise, Sp inge , Be lin, Heidelbe g, 2012, pp. 99–114. doi:10.1007/978-3-642-27660-6_ 9. URL h p://link.sp inge .com/10.1007/978-3-642-27660-6{_}9 [32] N. Yao, Y. Yu, X. Li, D. Gu, On he Robus ness o Lea ning Pa -760 i y wi h Noise, Sp inge , Cham, 2016, pp. 99–106. doi:10.1007/ 978-3-319-50011-9_8. URL h p://link.sp inge .com/10.1007/978-3-319-50011-9{_}8 [33] E. Ba ke , A. Roginsky, Recommenda ion o C yp og aphic Key Gen- e a ion, Tech. ep., Na ional Ins i u e o S anda ds and Technology,765 Gai he sbu g, MD (dec 2012). doi:10.6028/NIST.SP.800-133. URL h ps://n lpubs.nis .go /nis pubs/SpecialPublica ions/ NIST.SP.800-133.pd [34] L. Chen, Recommenda ion o key de i a ion using pseudo andom unc- ions ( e ised), Tech. ep., Na ional Ins i u e o S anda ds and Technology,770 35 Gai he sbu g, MD (2009). doi:10.6028/NIST.SP.800-108. URL h ps://n lpubs.nis .go /nis pubs/Legacy/SP/ nis specialpublica ion800-108.pd [35] E. B. Ba ke , J. M. Kelsey, Recommenda ion o Random Numbe Gene - a ion Using De e minis ic Random Bi Gene a o s, Tech. ep., Na ional775 Ins i u e o S anda ds and Technology, Gai he sbu g, MD (jun 2015). doi:10.6028/NIST.SP.800-90A 1. URL h ps://n lpubs.nis .go /nis pubs/SpecialPublica ions/ NIST.SP.800-90A 1.pd [36] A. Esse , R. K¨uble , A. May, LPN Decoded, Sp inge , Cham, 2017, pp.780 486–514. doi:10.1007/978-3-319-63715-0_17. URL h p://link.sp inge .com/10.1007/978-3-319-63715-0{_}17 36