Jul 17, 2012 - ... we design a new type of ring oscillator PUF in which the different inverters .... new RO-PUF characterized by smaller design, highe...

0 downloads 2 Views 763KB Size

arXiv:1207.4017v1 [cs.CR] 17 Jul 2012

Department of Electronic Systems, School of ICT, KTH - Royal Institute of Technology, Stockholm Email:{shsm,dubrova}@kth.se

Abstract—One of the most common types of Physical Unclonable Functions (PUFs) is the ring oscillator PUF (RO-PUF), in which the output bits are obtained by comparing the oscillation frequencies of different ring oscillators. In this paper we design a new type of ring oscillator PUF in which the different inverters composing the ring oscillators can be supplied by different voltages. The new RO-PUF can be used to (1) increase the maximum number of possible challenge/response pairs produced by the PUF; (2) generate a high number of bits while consuming a low area; (3) improve the reliability of the PUF in case of temperature variations. We present the basic idea of the new RO-PUF and then discuss its applications.

I. I NTRODUCTION Most secure cryptographic algorithms use a private secret value, defined as key, to encrypt and decrypt data. The key is normally stored in a RAM or a non-volatile memory. Being dependent to a unique value stored in memory makes algorithms vulnerable to various attacks such as invasive and semi-invasive attacks like physical tampering [1]–[3], whose goal is to obtain access to the key. Protecting the stored key against these attacks is vital for guaranteeing the security of the cryptographic devices. As suggested in [2], possible techniques used during manufacturing, such as using fuse memory arrays and planarising each predecessor layer before applying the next layer, can partially protect the storage elements against these attacks. However, the attackers are constantly looking for new attack methods. There is a non-stop ongoing battle between the designers who are trying to improve the security of their products and the attackers who are constantly trying to break them [2]. Physical Unclonable Functions (PUFs) were introduced in 2002 [4] by B. Gassend and co-workers. PUFs use the physical structure of each device to generate a set of unique data which resembles the chip fingerprint. Even if identical PUFs are implemented in different chips using the same manufacturing process, small device-to-device variations result in each PUF generating a different set of data, which is in principle unique and impossible to duplicate for all chips. PUFs are sensitive to device variations; any invasive or semi-invasive attack will, with a high probability, cause a permanent alteration of the device physical properties and thus alter permanently the behaviour of the PUF, rendering the device unusable. Therefore, it is believed that Physical Unclonable Functions provide high security for hardware devices. Two main usages of PUFs in

crypto-systems are embodying a single cryptographic key and implementing a challenge-response authentication method. Ring Oscillator PUFs (RO-PUF) were introduced in 2007 [5] and exploit the differences between the delay characteristics of wires and transistors. The output bits of a ROPUF are determined by comparing the oscillation frequencies of ring oscillators. RO-PUFs have a high reliability and are easier to implement compared to previously proposed designs such as butterfly PUFs [6]. Since 2007, many researches were conducted on RO-PUFs. In [7] and [8], a possible implementation of a RO-PUF on an FPGA was suggested. [9] and [10] introduced methods to increase the reliability in case of temperature variations; other works aimed at making the hardware more secure [11]. In this work we suggest a new design for RO-PUFs, which is based on the idea to use independent supply voltages for the different inverters composing all ring oscillators. Our method can be used for: • Improving authentication by increasing the maximum number of possible challenge/response pairs produced by a RO-PUF. • Designing low-area RO-PUFs for applications with strong area limitations • Improving the RO-PUF reliability by decreasing its sensitivity to temperature variations All three applications are analysed in detail, comparing the results we obtain with state-of-art solutions that can be found in literature. The remainder of the paper is organized as follows: in Section II, an overview of RO-PUFs is given; in Section III we discuss the dependency of ring oscillator frequencies to supply voltage variations; in Section IV we introduce the basic idea of our new RO-PUF; in Section V we calculate the uniqueness of our RO-PUF; in Section VI we study how our RO-PUF can be used to implement an efficient challengeresponse authentication method; in Section VII we estimate the area savings that can be obtained using our RO-PUF; in Section VIII we suggest how our RO-PUF can be used to increase reliability in presence of temperature variations; in Section IX we conclude the paper and discuss future works. II. R ING O SCILLATOR PUF S Ring Oscillator PUFs (RO-PUFs), as designed in [5], have a simple architecture made of two n-bit multiplexer, 2 counters, 1 comparator and n ring oscillators (ROs) (see Figure 1).

α

Each ring oscillator contains an odd number of inverters connected in a loop; each ring oscillates with a unique frequency depending on the characteristics of each of its inverters, which variate unpredictably from cell to cell due to manufacturing variations, even within the same chip, and are impossible to imitate. If the frequencies at which the ring oscillators oscillate are too high, the counters may not be able to count oscillations; therefore, there is a minimal number of inverters in every ring oscillator necessary to ensure a suitable oscillating frequency. This value depends on the technology but is typically in the order of 10 - 20 inverters. The two multiplexers select two ROs which are compared together (pair). The two counter blocks count the number of oscillations of each of the two ROs in a fixed time interval (comparison time). At the end of the interval, the outputs of the two counters are compared together. Depending on which of the two counters has the highest value, the output of the PUF is set to 0 or 1. The output of the PUF is set to 0 if the first ring oscillator in the pair is faster than the second (the value of the first counter is higher than that of the second), and to 1 if it is slower (the value of the first counter is lower than that of the second). If the two frequencies are very close to each other, the output of the PUF may variate unpredictably from run to run. It is however possible to improve the accuracy of the PUF by using larger counters and longer comparison time intervals. Originally, a RO-PUF produces 1-bit output for each comparison time interval. In each comparison time interval, the multiplexer selector is changed, the pair is changed and the RO-PUF produces another bit. A RO-PUF can be modified to produce multiple bits of data per comparison interval by increasing the number of multiplexers, counters and comparators, and comparing several pairs of ring oscillators at the same time. 11 00

RO1 RO2

11 00

n bit mux

counter >?

n bit mux 11 00

ROn

Fig. 1.

out

counter

A RO-PUF circuit implemented as in [5]

III. VOLTAGE S UPPLY D EPENDENCY All electronic components are sensitive to variations of their operating conditions. Supply voltage variations in CMOS systems affect the delay d of a combinational path of digital cells: if the supply voltage raises, the delay decreases and viceversa. The relation between the delay d and the supply voltage V of the path is a complex relation which can be measured experimentally or estimated at SPICE level. A simplified, approximate model for this relation is given by the Alpha law [12]: d=K

V dM (V − Vth )α

(1)

th ) Where K = (VM V−V is a scaling factor; Vth is the M threshold voltage of the transistors, α is the velocity saturation index of the technology and dM is the delay of the path when supplied with the typical supply voltage VM of the technology. In UMC 90 nm ASIC technology, Vth = 0.6V , α = 1.54 and K = 0.379 were estimated by simulating at SPICE level a chain of 10 inverters under different supply voltages. In principle the Alpha law is valid for all combinational paths in a given technology and the only parameter that changes from path to path is the scaling factor dM .

IV. M ULTI -VOLTAGE RO-PUF Our idea is to exploit the delay-to-supply voltage dependency from formula 1 to transform an original RO-PUF into a new RO-PUF characterized by smaller design, higher number of bits and higher resistance to temperature variations. column(1) column(2)

column(c) 11 00 00 11 00 11 00 11

r bit counter mux

11 00 11 00

>? out

n bit counter

00 11 11mux 00 11 00

vc1

vc2

vdd1 vdd2 vdd3 vdd1 vdd2 vdd3

Fig. 2.

vc3 buffer vdd1 vdd2 vdd3

Multi-voltage RO-PUF

The basic scheme of our RO-PUF is shown in Figure 2. In all ring oscillators, the inverters are grouped in C different columns with roughly the same number of inverters. Inverters belonging to the same column always share the same supply voltage. The supply voltage of each column of inverters can be selected among L different values (In Figure 2 L = 3) indicated as V dd1 , V dd2 , ..., V ddL and can be selected independently from the supply voltage of the other columns using PMOS switches. The columns can contain a single inverter per ring or multiple inverters grouped together. The supply voltages V dd1 , ..., V ddL are selected within the technology range allowing direct communication between gates without requiring level shifters, so that inverters can communicate with each other safely. The multiplexers, the counters and the comparators operate always on typical supply voltage. Buffers (two inverters in series operating under typical voltage supply) are introduced at the output of every ring oscillator to guarantee fast signal transitions at the input of the multiplexers. The oscillation frequency of each RO depends on the delay of all the inverters composing it. As an example, let us consider the UMC 90 nm PUF in Figure 3, where two ring oscillators indicated as ROA and ROB are being compared. Both ring oscillators are composed of 3 inverters, with C = 3 and L = 3 (small ring oscillators are chosen to keep the presentation simple, but note that these ring oscillators are too fast to be used in a real PUF). For the case in which all column supply voltages are equal to the typical supply voltage of the technology V dd2 = 1.2V , the relation between the delays of

the inverters di and the total delay dRO of the ROs (the inverse of their oscillating frequency) can be defined as: di1A + di2A + di3A = dROA di1B + di2B + di3B = dROB

(2)

In general, di1 , di2 and di3 are not equal and depend on unpredictable and uncontrollable device variations between the different inverters composing each ring oscillator. As an example, we suppose to have:

typical manufacturing intra-chip tolerances of the technology. We then set the supply voltages of every column to all possible LC = 27 configurations. The relation between the delays of ROA and ROB (dROA − dROB ) for all these configurations is shown in Figure 4. Among all the configurations, 12 result in the first RO being faster than the second, and the other 15 result in the second RO being faster than the first.

3di1A = 2di2A = 6di3A

i.A2 vdd

i.A3 vdd

i.B1 vdd

i.B2 vdd

i.B3 RO2 vdd

vdd1 vdd2 vdd3 vdd1 vdd2 vdd3 vdd1 vdd2 vdd3

(3)

Combining relations 2 and 3, the components of dRO are given by: 3 1 2 dROA + dROA + dROA = dROA 6 6 6 1 4 1 dROB + dROB + dROB = dROB 6 6 6 As discussed in Section III, the supply voltage variation of each electronic component directly affects its delay based on relation 1. If the supply voltage of the first inverter in both ring oscillators is raised from 1.2V to 1.32V , the relation predicts that its delay will decrease by a factor ∼ 0.83. Based on formula 1, the delays of the ring oscillators d∗RO under the new configuration convert to: 2 3 1 d∗ROA = 0.83 dROA + dROA + dROA = 0.94dROA 6 6 6 1 1 4 ∗ dROB = 0.83 dROB + dROB + dROB = 0.97dROB 6 6 6 Due to the increase in the speed of the first inverter in ∗ = d∗ 1 both ROs, the new oscillating frequencies fROA ROA ∗ = d∗ 1 are higher than the nominal frequencies and fROB ROB 1 1 ∗ = fROA = dROA and fROB = dROB . However, since fROA fROA f ∗ ROB 0.94 and fROB = 0.97 , there is no guarantee that these frequencies hold the same relation as they did under nominal supply voltage. In other words, if ROA was slower than ROB under nominal supply voltages, there is a possibility that ROA is faster than ROB with the new supply voltage configuration. In our RO-PUF, instead of a single bit output, by changing the supply voltages of the different columns, each pair of ring oscillators can produce a set of different output bits. For each pair, the maximum number of bits which can be produced with C columns and L supply voltages is equal to LC . As an example, for a RO-PUF with L = 3 and C = 3, the number of bits that can be generated by one pair of ring oscillators is 33 = 27. We generated using SPICE two random 3-inverter ring oscillators in UMC 90 nm technology with C = 3 and L = 3 (V dd1 = 1.08V ; V dd2 = 1.2V ; V dd3 = 1.32V ), setting the characteristics of each device randomly depending on the

A pair of three-inverter ring oscillators with C = 3 and L = 3.

Fig. 3.

dRO1−dRO2 (ns)

4di1B = 4di2B = di3B

RO1

i.A1 vdd

1.2 0.8 0.4 0 −0.4 −0.8 −1.2 0

1

2

3

4

5

6

7

8

9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 #LC (L=3, C=3)

Fig. 4. Values of dROA − dROB for all 27 voltage configurations for the RO pair in Figure 3. dROA and dROB indicate respectively the delays of ROA and ROB . If ROA is faster than ROB , dROA − dROB is negative, else it is positive.

This increase in output bits cannot be obtained by controlling the supply voltage of the entire PUF instead of controlling independently the supply voltage of each inverter column. In fact, if the supply voltage of a whole PUF is changed, then both ring oscillators composing any pair will work at a higher or lower supply voltage. Based on the Alpha law no variation in the output bit of the PUF should occur, because both ring oscillators in the pair operate faster or slower with ideally matched variations. Continuing with the same example RO-PUF from Figure 3 and defined by equations 2 and 3, if all gates work with the highest supply voltage V dd3 = 1.32V , the delays of the ring oscillators d+ RO under the new configuration convert to: 2 3 1 d+ ROA = 0.83 dROA + 0.83 dROA + 0.83 dROA = 0.83dROA 6 6 6 1 1 4 + dROB = 0.83 dROB + 0.83 dROB + 0.83 dROB = 0.83dROB 6 6 6 Since the variations have the same effect on all six inverters, they have the same effect on the delays on the ring oscillators and the RO-PUF output bit does not change. Experimental results reported in [5] are consistent with this analysis and show that by changing the supply voltage of a RO-PUF by 10% from the typical voltage, only 0.48% of the bits flip their value. The bits that flip are explained by higher order effects which are not considered in the Alpha law and which affect mainly pairs of ring oscillators that run at closely matched frequencies. Our solution constrains all inverters in the same column to always be supplied by the same supply voltage. The idea of a

RO-PUF is to compare the oscillating frequencies of ring oscillators that are nominally identical, and without this constraint this would not be the case. An attacker having gained access to the supply voltage configuration of a chip through an invasive or semi-invasive attack can gain knowledge on the structure of the PUF and thus guess the most probable output bit values. Also, the attacker could modify the supply voltages so that one of the output bits is changed in a predictable fashion. Compared to the original RO-PUF, we support multiple supply voltages in our design. Our design should be reliable in case of voltage variations in all the supply levels. To guarantee that the system operates reliably, is that the voltage distance between each two supply levels should satisfy the relation:

M AX(|V ddi − V ddj |) >

M AX(V ARi + V ARj ) 2 (1 < i, j ≤ L)

(4)

where V ARi and V ARj are defined respectively as the maximum variations of V ddi and V ddj (see Figure 5). var1 11111 00000 00000 11111 00000 11111 00000 11111 vdd1

vdd2−vdd1

variation

var2 11111 00000 00000 11111 00000 11111 00000 11111 vdd2

vdd3−vdd2

variation

Fig. 5.

var3 11111 00000 00000 11111 00000 11111 00000 11111 vdd3

variation

Voltage levels contraints

V. U NIQUENESS Inter-chip uniqueness is a parameter typically used to evaluate PUFs. The inter-chip uniqueness of a PUF is calculated by checking how different and random are the output bits of two identical PUFs implemented in different chips. As discussed in [13], the uniqueness U for an original ROPUF can be calculated by considering a set of k identical PUFs implemented in different chips. The uniqueness is defined as the average Hamming Distance between n bit outputs obtained from any possible pair of two PUFs i and j, expressed in percentage: −1 i=k−1 j=k X X k HD (Oi (n), Oj (n)) × 100% U= 2 n i=1 j=i+1 =

j=k i=k−1 X X 2 HD (Oi (n), Oj (n)) × 100% k × (k − 1) i=1 j=i+1 n

where HD (Oi (n), Oj (n)) is the Hamming Distance between two series of n-bit outputs (Oi (n) and Oj (n)) obtained by setting the multiplexers of the two PUFs to n different values (identical for PUFs i and j) during n different comparison intervals. With our RO-PUF, the output bits of a PUF depend not only on which ring oscillators are selected by the multiplexers but also on the supply voltage configuration. The uniqueness is estimated with the same formula as for the original RO-PUF,

but each of the n output bits is obtained by setting the multiplexers and the voltage supplies to n different configurations (identical for PUFs i and j) during n different comparison intervals. We designed k = 20 RO-PUFs in UMC 90 nm technology, each containing only two ring oscillators composed of 13 inverters, with C = 3 and L = 2. The RO-PUFs are all nominally identical, but all devices where generated with random characteristic mismatches based on the typical manufacturing tolerances of the technology. Through SPICE simulation, with n = LC = 8 we found U = 51.35%, which is close to the ideal result 50%. VI. AUTHENTICATION As discussed in [5], RO-PUFs can be used to implement challenge-response authentication protocols. In the original RO-PUF, such as the one shown in Figure 2, the multiplexer selector bits that define which ring oscillators should be paired together are used as challenge bits, i.e. they are set by the system with which the PUF-enabled device communicates, which knows what output it should expect from the cryptographic device. The response to the challenge is defined by the device based on the frequency comparison of the two selected ROs, and checked against tables of expected responses. For a traditional RO-PUF composed of R ring oscillators, , which the maximum number of challenges is given by R(R−1) 2 corresponds to the number of possible ring oscillator pairs. With our RO-PUF, shown in Figure 2, the challenge bits can be set not only by changing the selectors of the multiplexers, but also by setting the voltage configuration of the PUF, i.e. the supply voltage of every column of inverters. The maximum number of challenge/response pairs is increased to R(R − 1) × LC 2 where R is number of ring oscillators, C is the number of columns and L is the number of supply voltages. As pointed out in [5], for the original RO-PUF not all challenges are valid: if, for example, ROA is faster than ROB and ROB is faster than ROC , then ROA is necessarily faster than ROC . The result from the challenge selecting ring oscillators ROA and ROC is predictable if the responses to the other two challenges are known and does not constitute a valid challenge. Also, as discussed in [5], RO-PUF circuits are sensitive to temperature variations: under certain challenges, the output bit of the PUF may flip depending on the temperature. Only challenges that do not exhibit this behaviour are valid. Similarly, in our RO-PUF not all challenges will be valid. Two voltage configurations which are very near to each other (with only a very limited number of supply voltages changing between the two) have a high probability to result in the same output bit. We leave a precise determination of the number of valid challenge-response pairs to future works. In this paper, we compare our RO-PUF with the original RO-PUF only in terms of total number of challenge-response pairs, without considering the impact of the invalid pairs.

Many systems using cryptographic algorithms such as hardware authentication devices (RFID tags, etc.), smartcards, and wireless networks (Bluetooth, NFC, tags, etc.) are characterized by very tight power and area budgets. One of the main advantages of our RO-PUF is its ability to produce the same number of bits than the original RO-PUF [5] using a smaller hardware. In the original RO-PUF, the maximum number of bits produced by the PUF can be increased only by adding more ring oscillators to the PUF (see Figure 6-B). Since the structure of a RO-PUF is simple, the ring oscillators make up most of the RO-PUF area, and increasing the number of ring oscillators easily increases its total area. With our RO-PUF, the maximum number of bits depends not only to number of ring oscillators but also on the number of columns and supply voltages. Increasing each of these three elements increases the number of bits produced by the PUF. From Figure 6, it is obvious that increasing the number of columns instead of the number of ring oscillators is a more effective way to increase the output bits of the PUF. By increasing the number of columns in each PUF without adding to the number of ring oscillators, we achieve the same improvement in the number of bits that can be generated by a traditional RO-PUF, but with a smaller hardware.

vc(1) L vdds

vdd1 vdd2

counter

vc(n) n columns

vc(n) L vdds

vdd1 vdd2

vddL

Fig. 8.

>? out

counter vddL

A low-area RO-PUF circuit.

The area overhead of the PMOS power switches is the only overhead which is added to the original RO-PUF. The percentage of this overhead on the original RO-PUF is shown in Figure 9. The highest overhead (42%) is for a PUF with only 1 pair of ring oscillators, 19 inverters per RO and C = 19. However, this RO-PUF has a much lower area compared to the original RO-PUF which produces the same number of bits (see Figure 7). 40

20

0 0

10 #RO

20

30

20

15

10

5

0

#C

#Max bits/GE

10

GE

400

200

VIII. T EMPERATURE -R ESISTANT RO-PUF

5

20

20 0 30

vc(1)

Fig. 9. Area overheads of the supply voltage switches. Each PMOS switch is assumed to consume 0.5GEs.

8

x 10 600

160M Hz clock frequency. The areas of the power switches are not considered in Table I.

overhead(%)

VII. A REA C ONSIDERATIONS

20

10 #RO

0 0

10 #C

0 30

10 20

10 #RO

0 0

#C

Fig. 7. Area (left) and maximum number of output bits per unit of area (right) for a series of our RO-PUFs with L = 3, 2 ≤ R ≤ 30, number of inverters per RO between 3 and 19 (odd values only) and C equal to the number of inverters per RO.

Figure 7-left shows the area in terms of gate count for a set of UMC 90 nm RO-PUFs with different number of ROs and columns. Brought to the extreme, this leads to what is to our best knowledge the most compact RO-PUF suggested in literature: as shown in Figure 8 the RO-PUF is made of only two ring oscillators which act as a pair, and there are no multiplexers. Table I reports implementation details of the ROPUF in Figure 8 implemented in UMC 90 nm technology. Different values of L and C are considered. The number of inverters is kept equal to C (one inverter per column per ring oscillator). Three values of L and C are chosen to have LC > 222 , LC > 280 and LC > 2160 . Frequency results represent the oscillating frequency of the ring oscillators under typical supply voltage conditions obtained from Cadence RTL Compiler; power results are estimated as a combination of dynamic and leakage power with a typical supply voltage, at

All electronic components are sensitive to variations of their operating conditions. For a RO-PUF, this sensitivity can cause uncertainty in the output bits (low reliability). All PUF circuits should be modelled and tested extensively before a PUF is commercially deployed, to guarantee high reliability, i.e. that the cryptographic key or the unique identifier derived from them is exactly the same under all circumstances. Temperature is one of the main operating conditions that can impact reliability [14]: increasing or decreasing the temperature of a RO-PUF can make some of its output bits flip due to the unequal effect of temperature variations on the two ring oscillators that are being compared. Recently, several temperature-aware RO-PUFs have been suggested in literature. In [9], the authors suggest to introduce a temperature sensor in every chip. After a chip containing the PUF has been manufactured, it is tested to determine in which temperature range every pair of ring oscillators is reliable. All ring oscillator pairs are used only in the intervals in which they are reliable; an output bit is generated using different pairs depending on the temperature of the PUF: if the temperature changes, the pair of ring oscillators generating a bit is changed. A table coupling temperature ranges with reliable pairs is stored in a memory. Even if an attacker can gain access to the contents of this memory, no information about the PUF structure is revealed. The number of output bits is lower than the total number of

7

#Max Bits

#Max Bits

400 A−Original RO−PUF 300 200

6 B−Our RO−PUF 4

190.5 C−Original RO−PUF 190

14 20 #RO

26

30

2

8

14 20 #RO

26 30

x 10

6 D−Our RO−PUF 4 2

189.5 189

8

8

191

2

100 0 2

11

x 10

#Max Bits

8

#Max Bits

500

0 5

10

15

20

5

10

15

20

#C

#C

Fig. 6. Comparison between the maximum number of output bits produced by our PUF (B, D) and the original RO-PUF (A, C). A: original RO-PUF with 11 inverters per RO and 2 ≤ R ≤ 30; B: our RO-PUF with 11 inverters per RO, C = 11, L = 3 and 2 ≤ R ≤ 30; C: original RO-PUF with R = 20 and number of inverters per RO between 3 and 19 (odd values only); D: our RO-PUF with R = 20, L = 3, number of inverters per RO between 3 and 19 (odd values only) and C equal to the number of inverters per RO. #Max bits L C Area (µm2 ) Freq ( MHz) Power (µW )

2 23 289 1141 81.1

222 3 15 241 1712 60.1

4 11 223 2107 52.3

2 81 625 344.8 233.1

280 3 51 463 516.9 157.2

4 41 397 652.3 128.4

2 161 1117 169.2 451.1

2160 3 101 763 266.0 288.4

4 81 637 344.8 233.3

TABLE I A REA , FREQUENCY AND POWER FIGURES OF THE PUF IN F IGURE 8 FOR DIFFERENT VALUES OF C AND L ( ONE INVERTER PER COLUMN PER RING OSCILLATOR ).

ring oscillator pairs; a hardware utilization of in average 80% can be achieved by this design compared to the original PUF. The work in [10] is based on the idea that the effects of temperature changes on ring oscillator frequencies can be partially compensated by changing the supply voltage of a PUF. The authors define and store in memory a table which matches each temperature to a corresponding supply voltage. During operation, the temperature is estimated by an on-chip temperature sensor and the supply voltage of the PUF is changed accordingly. The information related to the operational temperatures and the corresponding supply voltages are saved on an on-chip memory. Attacking this memory does not reveal any useful information to the attacker. This work increases reliability but does not guarantee that all pairs of ring oscillators will result in a reliable output bit: some pairs of ring oscillators will still need to be eliminated for the sake of reliability. With some changes, our multi-level RO-PUF can be transformed into a temperature-aware RO-PUF that can cope with temperature variations. The main idea is that when a pair of ring oscillators is selected, the voltage configuration of the ring oscillators is chosen so that the pair of ROs is guaranteed to work reliably across the whole temperature range. The hardware architecture of our temperature-resistant PUF is shown in Figure 10. Just as for the original RO-PUF, our temperature-aware RO-PUF provides a maximal number of challenge/response pairs equal to R(R−1) , i.e. the challenge 2 consists in selecting a pair of ring oscillators and the response is determined by comparing their oscillating frequencies. In our design, when a pair is selected, a voltage configuration is read from a memory and used to supply the inverters composing the selected ring oscillators. each pair is associated to a voltage configuration that guarantees reliable operation

of the pair across the whole temperature range. Reliable configurations for each pair are pre-computed during the postmanufacturing testing of the PUF and stored in the memory. As shown in Table II, for a UMC 90 nm PUF with L = 2, C = 3, each pair of ring oscillators can operate with LC = 8 different voltage configurations. While some them are unreliable, some of these configurations will guarantee reliable operation across the whole temperature range from −25◦ to 125◦ . It is most probable to find for each pair at least one voltage configuration out of LC cases that is resistant to temperature variations across the whole temperature range. For example, as shown in Table II, for a given pair ... configurations among 8 are resistant to temperature variations. We tested this assumption for 100 pairs of ring oscillators; for each pair, we were able to find at least one case showing resistance to temperature variations. A memory should put in correspondence each ring oscillator pair with a voltage configuration (see Table III). With a basic implementation, the size of the memory in terms of bits can be estimated by: l m R × (R − 1) M EMbits = logL 2 ×C × 2 where L is the number of supply voltages, C is the number of columns and R is number of ring oscillators. As an example, for a PUF with C = 5, L = 2 and R = 4, the size of this memory will be 30 bits. It would be possible to introduce a controller and obtain memory savings exploiting the fact that the majority of the ring oscillator pairs is normally not temperature-sensitive and can operate reliably using the typical voltage configuration, but this requires further investigation and is outside the scope of this paper. Since the entries are saved in a memory, they are potentially vulnerable to invasive and semi-invasive attacks. However,

v1 v2 v3 temp. PUF

000 t2 t3 0 0

t1 0

t1 0

001 t2 t3 0 0

t1 0

010 t2 t3 0 1

t1 0

011 t2 t3 1 1

t1 1

100 t2 t3 1 1

t1 1

101 t2 t3 0 0

t1 1

110 t2 t3 1 0

t1 1

111 t2 t3 1 1

TABLE II O NE PAIR OF RING OSCILLATORS WITH L = 2 AND C = 3 CAN OPERATE UNDER LC = 8 VOLTAGE CONFIGURATIONS . T HE EFFECT OF TEMPERATURE VARIATIONS FROM −25◦ TO 125◦ FOR ALL THESE 8 CONFIGURATIONS ARE SHOWN .

pairs conf.

1,2 01001

1,3 01100

1,4 10010

2,3 01110

2,4 11000

3,4 00110

TABLE III S AMPLE MEMORY USED IN A TEMPERATURE - AWARE IMPLEMENTATION OF A RO-PUF WITH L = 2, C = 5 AND R = 4. 1,2 MEANS THE PAIR BETWEEN RO1 AND RO2.

revealing the information in the memory does not give any extra information regarding the frequency of the two ROs in a pair and the RO-PUF has the same security as the solutions presented in [9] and [10]. Compared to [9], the memory is smaller in our design and a 100% hardware utilization is obtained (each RO pair generates one output bit). Moreover, compared to both [9] and [10], our solution does not require the presence of any temperature sensor. vdd1 vdd2

3 bit

11 00 11 00 11 00 00 11 11 00 11 00

c1

c2

Fig. 10.

c3

Challenge 4 bit

MEM

11 00

2 bit 2 bit

counter >? 1 bit counter Response

Temperature-aware RO-PUF.

IX. C ONCLUSION AND F UTURE W ORKS In conclusion, our RO-PUF can support a high number of challenge/response pairs without impacting excessively the area of the PUF. It can also be used to implement a temperature-aware RO-PUF with a 100% hardware utilization. Issues that remain open and left to future work are a calculation of the number of valid challenge/response pairs and an efficient implementation of the temperature-aware ROPUF. Also, the impact of supply voltage variations should investigated further. R EFERENCES [1] G. E. Suh, D. Clarke, B. Gassend, M. van Dijk, and S. Devadas, “Aegis: architecture for tamper-evident and tamper-resistant processing,” in Proceedings of the 17th annual international conference on Supercomputing, ser. ICS ’03. New York, NY, USA: ACM, 2003, pp. 160–171. [Online]. Available: http://doi.acm.org/10.1145/782814. 782838 [2] S. P. Skorobogatov, “Semi-invasive attacks – a new approach to hardware security analysis,” University of Cambridge, Computer Laboratory, Tech. Rep. UCAM-CL-TR-630, Apr. 2005.

[3] S. Mangard, E. Oswald, and T. Popp, Power Analysis Attacks: Revealing the Secrets of Smart Cards. Springer-Verlag New York, Inc., 2007. [4] B. Gassend, D. Clarke, M. van Dijk, and S. Devadas, “Silicon physical random functions,” in ACM Conference on Computer and Communications Security. ACM Press, 2002, pp. 148–160. [5] G. E. Suh and S. Devadas, “Physical unclonable functions for device authentication and secret key generation,” in Proceedings of the 44th annual Design Automation Conference, ser. DAC ’07. New York, NY, USA: ACM, 2007, pp. 9–14. [Online]. Available: http://doi.acm.org/10.1145/1278480.1278484 [6] J. Lee, D. Lim, B. Gassend, G. Suh, M. van Dijk, and S. Devadas, “A technique to build a secret key in integrated circuits for identification and authentication applications,” in VLSI Circuits, 2004. Digest of Technical Papers. 2004 Symposium on, june 2004, pp. 176 – 179. [7] A. Maiti and P. Schaumont, “Improved ring oscillator puf: An fpgafriendly secure primitive,” J. Cryptology, vol. 24, no. 2, pp. 375–397, 2011. [8] D. Merli, F. Stumpf, and C. Eckert, “Improving the quality of ring oscillator pufs on fpgas,” in WESS’2010. ACM. [9] G. Qu and C.-E. Yin, “Temperature-aware cooperative ring oscillator puf,” in Hardware-Oriented Security and Trust, 2009. HOST ’09. IEEE International Workshop on, july 2009, pp. 36 –42. [10] V. Vivekraja and L. Nazhandali, “Feedback based supply voltage control for temperature variation tolerant pufs,” in VLSI Design (VLSI Design), 2011 24th International Conference on, jan. 2011, pp. 214 –219. [11] Q. Chen, G. Csaba, P. Lugli, and et Al., “The bistable ring puf: A new architecture for strong physical unclonable functions,” in HOST, june 2011, pp. 134 –141. [12] T. Sakurai and A. R. Newton, “Alpha power law mosfet model and its applications to cmos inverter delay and other formulas,” Solid-State Circuits, IEEE Journal on, vol. SC-25, no. 2, pp. 584–594, April 1990. [13] A. Maiti and P. Schaumont, “Improving the quality of a physical unclonable function using configurable ring oscillators,” in FPL, 2009, pp. 703–707. [14] A.-R. Sadeghi and D. Naccache, Towards Hardware-Intrinsic Security: Foundations and Practice, 1st ed. Springer-Verlag New York, Inc., 2010.