# Correlations in ring oscillator PUFs

A bunch of silicon Physical Unclonable Functions (PUFs) designs rely on variations of the propagation delay (due to process variation) of signals in different path. In many cases, a challenge selects the paths (e.g. using a muxer) to be compared and the response bit(s) compare the two paths (e.g. which signal arrived first or the number of oscillations in ring oscillators).

For example, here is a conventional design using ring oscillators [1]:

Given $$N$$ oscillators, there are $$N(N-1)/2$$ distinct pairs of oscillators. The paper explains:

However, the entropy of this circuit, which corresponds to the number of independent bits that can begenerated from the circuit, is clearly less than $$N(N−1)/2$$ because the bits obtained from pair-wise comparisons are correlated. For example, if oscillator A is faster than oscillator B, the comparison will yield a 1. If B is in turn faster than C, the comparison will yield a 1. It is clear that when A is compared with C that the comparison will yield a 1—these bits are correlated. [1]

Since correlated answers are unwanted, the paper goes on:

Fortunately, it is possible to derive the maximum entropy of this circuit assuming pair-wise comparisons [...] There are $$N!$$ different orderings of ring oscillators based on their frequencies. If the orderings are equally likely, the entropy will be $$log_2(N!)$$ bits. For example, 35 oscillators can produce 133 bits.

However, some other designs use a different approach that splits oscillators into two sets/blocks/groups [2,3]:

[3] says this about the impact on correlations:

One very important goal of this system is separating the Transcient Effect Ring Oscillatoires (TERO) cells into two blocks because of security. Indeed, without this separation, first order dependencies appear inside generated signatures depending on which cells contribute to the response.

I understand that having two sets prevents direct correlations such as if $$A_{freq} > B_{freq}$$ and $$B_{freq} > C_{freq}$$ then $$A_{freq} > C_{freq}$$ (two elements of $${A, B, C}$$ needs to be on the same set and thus cannot be compared). However, it looks like a bad solution as it does not prevent indirect correlations and it reduces the max entropy for $$N$$ oscillators.

What is the impact of using two sets on the correlations? Can we quantify it? I think it boils down to computing the entropy of the circuit with two sets of $$N/2$$ elements—which I don't know how to do.

• Tangential: How is this function physically uncloneable, anyway? We can just measure the ordering of the frequencies of all the oscillators and put that in a ROM table – user253751 Jul 14 at 9:56
• @user253751 Because it's not the frequencies that do it. It's the relative jitter between them, measured in nano and pico seconds. Or sometime PUFs depend on meta-stable circuits to have unique semi-oscillating behavioural characteristics when operating within such small time frames. And that's not easily copied. – Paul Uszak Jul 14 at 11:46
• @user253751 See this related question. – DurandA Jul 14 at 15:08
• @PaulUszak any output bits from this circuit can be copied because they are just bits. Even if the bits vary over time we can take a measurement over time. But DurandA has linked to some reasons why someone might want this kind of circuit. – user253751 Jul 14 at 15:35
• @user253751 That's a really good point, and I'm struggling to contradict you. However, there is a huge body of research and commercial products that claim to be PUFs. What's going on? – Paul Uszak Jul 22 at 2:59