Ring oscillator based PUF

I am unable to understand why - using a counter comparison based ring oscillator PUF - the output bit is either 0 or 1.

Since the output is one bit I don't see how multi bit responses are obtained. Using this information how can I calculate intra- and inter-Hamming distance? Can you provide some provide example to explain it?

Using ring oscillator based PUF proposed by Devadas and Suh it compares counter values and then produces 1 bit of output. So from this one bit of output, how is it possible to get a multiple bit response to calculate intra- or inner-Hamming distance?

If I apply input of 1001010 it is input to two sets of ring oscillator each having 128 ring oscillator out of two set one from each a ring oscillator is selected and feed to counter and comparator produces output 0 or 1.

So a single bit response is obtained But in the paper of Devadas and Suh : https://people.csail.mit.edu/devadas/pubs/puf-dac07.pdf in figure 4 for challenge 1001010 the response is 010101. How is this possible?

• provide more details so this is actually a readable question. Jul 26 '19 at 7:49
• I've made an extensive edit trying to make your question more readable. Please check if nothing has changed significantly. There is still quite a bit of redundancy in your post, please try and remove any duplicate information in it (by editing it). Jul 28 '19 at 14:30

note: I am unsure that you can get an answer for your question as there's not enough technical information in the paper to reproduce (for me anyway) the results. However, you could work through it in the following method for any ring oscillator.

A ring oscillator is comprised of a ring built of an odd number of inverters. The simplest model of this oscillator can be represented with a single inverting transfer function $$f(\cdot)$$, a delay of $$\tau$$ and a feedback loop that meet the Barkhausen criteria. The $$f(\cdot)$$ function can be approximated with a hyperbolic tangent. However, an electrical model must involve additional lumped components (low pass filter) namely the input capacitance $$C$$ and the output resistance R that represent inverter's active region behavior. The $$RC$$ is particularly pertinent due to the FPGA architecture in this case. The noise processes of the circuit are represented in the model by $$N(t)$$. The purpose of the "PUF" in this case is to have unique delay, which is the $$N(t)$$. The momentary $$N(t)$$) value results from the sum of Gaussian noise and two-way shot noise sources (it's not thermal noise, which is actually shot noise in a semiconductor and every textbook that says otherwise is incorrect. You can derive it from 1st principles) with a zero mean value and $${\sigma^2_N}$$ variance.

The ring oscillator manifests oscillations due to the propagation delay $$\tau$$ in delay in the feedback loop. In the image, $$\Sigma$$ is the contributions of $$N(t)$$ You then look at this behavior as non-linear delay such that

$$\widetilde{\dot{\mathbf{U}}}_i = \frac{f(\widetilde{U},t-\tau)-\widetilde{{\mathbf{U}}}_i+N(t)}{RC},$$

where $$f(\cdot)$$ is the transfer function. The transfer function in this case is the PUF behavior, which the authors did not model. Also, it would be dependent on not only the semiconductor fab mismatch, but the router. The question is "does the RC of the routing contribute more than the PUF circuit variance". There's no way to know.

What they should have done is the following: Let's assume that randomness is a function of the nondeterministic contribution of N(t) and a derivative of the random variable $$\widetilde{{\mathbf{U}}}_i$$. The behavior of the circuit can be explained when the random part in the above equation is omitted and a we can linearize it with a small signal model. In this case, the linearized $$f(\cdot)$$ function brings an amplification coefficient g, therefore, the circuit can be described with a linear differential equation as

$$\frac{d u_i}{dt} = \frac{-g u_i(t-\tau)-u_i}{RC}$$

You can then take the above and put it through a Laplace transform and find the zeros resulting in

$$s+ \frac{1+g e^{-\tau s}}{RC}=0$$

The solution can then represented as a Fourier series with periodic responses from the time domain. You can then use these modeled for each oscillator in the chain to understand the contribution of each oscillator. For this reason, I do not believe that their analysis is adequate enough to make assumptions about the hamming distance in any method that is qualitative. It is a quantitate measurement, and I am not convinced by that paper that the authors know how their system works.

I have no idea why this paper is so highly cited. I would not pass muster in a circuits journal, and honestly, it just complicates things. You can already consider an inverter to have a unique transfer function due to surface roughness and manufacturing defects. I do not know either of the original authors, but I would love to know why this was thought to be a good idea.

• Re. very last sentence. What was thought to be a good idea? Jul 29 '19 at 20:46
• @PaulUszak The FPGA fabric will have a hysteresis due to the basic architecture, so I am unclear how the PUF approach would be any better than just using the fabric as a ring oscillator. Also, the PUFs in parallel will still be correlated, so using the setup for more than one challenge would be risky. Mainly, it's just that I would conject that the PUF is less random then just using a series of ring oscillators. They did not do a complete analysis of the PUF from the circuits side for me to believe that this improves randomness. Marginal increase in $N(t)$ contributions at best. Jul 30 '19 at 1:07

All you need is in that paper. I'm just going to paraphrase from the paper:-

how multi bit response is obtained?

Because of the multiplexer (MUX) input. One output bit is returned for each and every input. That's the challenge-response pairing. There are $$N(N−1)/2$$ distinct pairs given $$N$$ ring oscillators. And you simply select which two oscillators you wish to compare. If you avoid reuse of any oscillator because you're worried about correlated behaviour, 128 pairs of oscillators (256 oscillators total) can be used to generate 128 independent bits. And the target oscillators are selected via the MUX input. We would say that there are 128 challenge-response pairs in this PUF.

how to calculate inter and intra hamming distance

• Inter-chip variation: How many PUF output bits are different between PUF A and PUF B? This is a measure of uniqueness. If the PUF produces uniformly distributed independent random bits, the inter-chip variation should be 50% on average.

• Intra-chip (environmental) variation: How many PUF output bits change when re- generated again from a single PUF with or without environmental changes? This indicates the reproducibility of the PUF outputs. Ideally, the intra-chip variation should be 0%

So the thing here is that you can't simulate this. That's the "P" in PUF. You have to build physical devices and test them for inter and intra hamming distances. Figure 6 shows these normalised metrics for 128 bit output sequences. Standard Hamming distance algorithms can be found in the Wiki article.

• I agree to your statement that 128 challenge response pair is obtained, but I was asking if I apply input of 1001010 it is input to two sets of ring oscillator eash having 128 ring oscillator out of two set one from each a ring oscillator is selected and feed to counter and comparator produces output 1/0. So a single bit response is obtained But in that paper in figure 4 for challenge 1001010 response is 010101 . How it happens?
– user70750
Jul 26 '19 at 13:28
• @Mohit Ah! It doesn't happen. Again quoting, "We present PUF designs", and please focus on section 3.3. $1001010 \to 010101$ is a theoretical extended example. It is not from the multiplexed ring oscillator architecture of Fig.2. Some would call the paper somewhat wishy-washy. It's more of a literature review with scant new ideas. The hollow conclusion demonstrates this. Jul 27 '19 at 2:43
• Can you explain the construction of ring oscillator based puf which prodces a response of say 6bit/8bit with a schematic.
– user70750
Jul 27 '19 at 6:03
• @Mohit I can't actually. If you look at their RO architecture and consider the most conservative pairwise MUX arrangement, you still only get a challenge/response bit ratio of $\approx 16:1$. They've themselves identified that this " can only generate a relatively small number of bits. ". The addition of a binary counter to Figure 2 and a read input would work, but that would only generate a fixed crypto key, and not generic challenge/response pairings. I think that you're looking at an expansion of Figure 1, which they've said too. Jul 27 '19 at 13:05
• With hindsight, their paper is entirely lacking in enrolment/training components or error correction. Direct PUF output from the raw entropy units is not entirely deterministic, hence the stochastic hamming analyses. Fuzzy entropy extraction is often needed. Poor paper. Jul 27 '19 at 13:12