1
$\begingroup$

Wikipedia article claims that physical unclonable functions are superior to ROM because they require less hardware:

Unlike a ROM containing a table of responses to all possible challenges, which would require hardware exponential in the number of challenge bits, a PUF can be constructed in hardware proportional to the number of challenge and response bits.

Then, examples of PUFs are given, such as reading a device-specific signature present in DRAM upon startup, which indeed requires exponential hardware. Other kinds of PUFs are based on different physical principles (optical, mechanical, magnetic) which encode the device-specific differences, but I fail to see how using a different physical principle could lead to linear (rather than exponential) hardware requirements.

Could someone provide an example of such hardware or explain how such low hardware requirements are possible in PUFs?

Improve this question
$\endgroup$
7
  • $\begingroup$ ROMs are very inefficient at implementing some functions, e.g. AES encryption with a fixed secret key would require $2^{128}$ bits if implemented as a big ROM. So it is in no way surprising that the efficiency of ROM can be beaten. $\endgroup$
    – fgrieu ♦
    Aug 9, 2017 at 11:50
  • $\begingroup$ @fgrieu Wouldn't implementing AES with a fixed key require 256 bit of ROM to store the key plus some logic to realize the algorithm? $\endgroup$
    – Dmitry Grigoryev
    Aug 9, 2017 at 12:07
  • $\begingroup$ Indeed, AES can be implemented with relatively little logic (strictly speaking, the 256-bit ROM is not even necessary and can be moved into the logic). That's however not the "implementation as a big ROM" with 128 address bits (the plaintext input) and 128 data bits (the ciphertext output) that I and (I guess) the question's citation are considering. $\endgroup$
    – fgrieu ♦
    Aug 9, 2017 at 12:17
  • 1
    $\begingroup$ @fgrieu Then it sounds like the main advantage of PUFs over e.g. an AES with a fixed key is the "unclonable" part, since a logic implementation of AES would likely beat PUFs as well. $\endgroup$
    – Dmitry Grigoryev
    Aug 9, 2017 at 15:56
  • 1
    $\begingroup$ Not clear to me why the Wikipedia article mentions this! Obviously you could have an AES-256 circuit and a 256-bit ROM for a key, and that would work just as well as an AES-256 PUF, security aside. The important property is that an AES-256 PUF's key can't be extracted and used on another machine. $\endgroup$
    – Squeamish Ossifrage
    Aug 9, 2017 at 16:37

1 Answer 1

Reset to default
2
$\begingroup$

To implement challenge-response in ROM only (no computations), you basically need a lookup table, a mapping from challenges to responses. So for a $k$ bit challenge, you would need $2^k$ entries in your lookup table.

How would this work on a PUF?

Consider the following PUF example (taken from Improved Ring Oscillator PUF: An FPGA-friendly Secure Primitive, Journal of Cryptology, 2011):

enter image description here

The portion on the right shows the ring oscillator (RO), whose value is going to be entirely dependent on the fabrication process and therefore is "unclonable". You put a bunch of these ROs together, feeding into two MUXs, with the challenge determining which RO value to select. Finally, the outputs of the two MUXs are used to increment two counters, which are (after some short period of time) used to determine a single bit by doing a comparison. Your $k$ bit challenge may be divided up into smaller challenges to get a larger response from the PUF than a single bit. This would be a deterministic process so that given the same $k$ bit challenge, you would get the same response (in practice there is some probability of bits being flipped in the response, so typically some error correcting is done).

To get a secure $k$ bit response, you will need some number of ROs, but you won't need an exponential number of ROs. If you have $N$ ROs, there are $N(N-1)/2$ distinct pairs of ROs. Each pairing can be used to generate a single bit using the setup shown above. However, as noted in Physical Unclonable Functions for Device Authentication and Secret Key Generation, the entropy of the circuit will not be as high as that. In that paper, the authors derive the maximum entropy of the circuit as $\log_2(N!)$. So for a desired $k$, you could compute $N$. As an alternative method, the authors note that for simplicity, you could design the system such that each oscillator is used only once for any challenge value. If you did this, you would need $2k$ oscillators to generate a $k$ bit response. I would note that due to error correcting, you may need additional bits, but this should only increase the number of oscillators by a constant factor.

Now, how would this be used in a challenge/response protocol. Well, first there must be a trusted setup. The challenger, in a clean environment, sends a bunch of challenges to the PUF and records the responses. So, the challenger may have to store a lot of challenge/response pairs depending on the application. The point is, the hardware does not have to store all that information.

Then, when the system is fielded, the challenger sends a challenge to the device. The device runs it through the PUF and returns the response. Someone without access to the PUF could not compute the correct response. Further, someone trying to clone the PUF would not succeed because of the manufacturing variations in the ROs. Those manufacturing variations, even when very subtle, would be enough that the responses would not be the same.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thanks, that clears things up a lot. An estimation of the number of ROs needed for a k-bit challenge would be nice to see though, because without it the schematic seems to imply that I do need $2^k$ ROs in order to process a k-bit challenge. $\endgroup$
    – Dmitry Grigoryev
    Aug 9, 2017 at 14:42
  • 1
    $\begingroup$ @DmitryGrigoryev, the PUFKY paper from CHES 2012 implements a key generation application on a PUF (instead of challenge/response). They generate a 128-bit key using 848 ROs. $\endgroup$
    – mikeazo
    Aug 9, 2017 at 15:04
  • 1
    $\begingroup$ @DmitryGrigoryev, I updated my answer with the results from the paper I was thinking of. See the 2nd paragraph after the figure. $\endgroup$
    – mikeazo
    Aug 9, 2017 at 15:19
  • $\begingroup$ Actually, to get a k-bit response from a ROM, one doesn't need $2^k$ 1-bit ROMs either, but only k of them. So the hardware requirements are linear regarding the size of response in both cases. Am I wrong? $\endgroup$
    – Dmitry Grigoryev
    Aug 9, 2017 at 16:11
  • $\begingroup$ @DmitryGrigoryev, that would be for a single (fixed) k bit response, right? So the challenge would not affect the output. $\endgroup$
    – mikeazo
    Aug 9, 2017 at 16:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.