Helper data authentication in PUFs

As I understand, PUFs work by using two procedures: generation and reproduction. Generation reads a value $w$ from a fuzzy source and generates a key $R$ and helper data $P$. Then, in the reproduction procedure, it reads $w'$ from the fuzzy source and, using $P$, is able to recover $R$.

My question is: this seems to assume that $P$ can be stored safely and can be authenticated, since if a attacker changes the value $P$ that is stored then he can force the system to use a different key. How can this be done, if you don't have a key in the first place? Or am I missing something?

(I have followed the notation from this paper)

-

2 Answers

It is very similar to how we authenticate ourselves to a website. During registration, the website must store enough information to, at some time in the future, convince itself that the person trying to authenticate now is the same person who registered at some time in the past. For online services, this typically involves storing some function of the password. The online service also wants to make sure that the stored information is stored safely (i.e., unauthorized entities cannot get it) and authenticated (i.e., no unauthorized parties can change it). Otherwise authentication would fail.

With a PUF, it is almost the same. You register the PUF with the system by extracting $R$ and $P$ from $w$. $R$ and $P$ would then be stored in, for example, a database. When the PUF is used again to authenticate, the service would read $w'$, pull $P$ from the database and run the reproduction procedure to get $R'$. It could then pull $R$ from the database and see if $R==R'$. If so, authentication is successful and access is granted.

How you protect $R$ and $P$ from the generation phase is up to you. It also depends on how paranoid you are, how valuable the service is, your threat model, etc. For some, simply storing them in a database that (hopefully) only they have read access to is fine. Others might want to encrypt and sign the values.

It should be noted that $P$ is a public value. It does not need to be kept secret for the system to be secure. As you noted, however, if someone tampers with $P$, they could trick the system into authenticating the wrong party. Equivalently, if I change the hash stored in a database with login credentials, I can now become that user.

Active Attacker Update

Things become tricky when you allow your adversary to modify $P$. AFAIK, there are no guarantees that the attacker cannot modify $P$ in a devistating way (e.g., to publically reveal $R$). And I am not aware of any PUF research to mitigate the problem.

Fortunately PUFs and biometrics are very similar.

1. Both are a noisy source
2. Both require fuzzy extraction to be used to handle the noise

Given that, hopefully the following will at least help to solve the problem.

In "Robust and Reusable Fuzzy Extractors" by Boyen in the book "Security with Noisy Data", Boyen tackles a similar problem. From the chapter:

Unfortunately, ordinary fuzzy extractors do not address the issue of an active adversary that can modify $P$ maliciously, either on the storage server or while in transit to the user.

I don't fully understand the details of the work yet, so I don't feel it wise to try and describe the algorithms and protocols.

NOTE: It looks like much of that chapter was taken from a paper by Boyen and some of his colleagues titled "Secure Remote Authentication using Biometric Data". I have not read the paper to confirm that all the detail you might be looking for is there, however.

-
I see, it makes sense if the PUF is used for authentication. But what if the PUF is used to generate a key for a device? – Conrado PLG Jan 24 '12 at 15:27
@ConradoPLG, for key generation, you use R from the generation stage (or some function of it) to encrypt the data. Then you can store P and throw away R. Upon regeneration, if someone has modified P, they won't be able to decrypt. You shouldn't even need to store R for key generation. And, P gives an attacker negligible information, so it can remain public. Protect it against modification if necessary using standard methods. – mikeazo♦ Jan 24 '12 at 17:15
Thanks for the clarification, but I still don't understand something: how can I protect it against modification? For that I would need a key, but I'm using the PUF to get a key in the first place. Is there any kind of guarantee that an attacker can't change $P$ in such a way to force the system to derive a key $R'$ of his choice? – Conrado PLG Jan 24 '12 at 17:49
@ConradoPLG, I know of no such guarantee. Why can't you use a different key to make sure $P$ isn't changed? Generate a GPG public/private key pair. Sign the value $P$ with the private key, then anyone with the public key can verify that $P$ has not been modified. Or, use an HMAC with a password of some sort. The key to protect $P$ is completely different from $R$. – mikeazo♦ Jan 24 '12 at 19:23

1
I guess my question wasn't clear enough, sorry for that! Suppose that the PUF is used by some device to derive a key that is used to encrypt and authenticate its hard drive, for example. There is no user interaction. If the device generates and stores a key to sign $P$, then an attacker can change both the key and $P$ (that is, assume that there is no secure storage) and the security would be compromised. If you assume there is a safe place to store the second key and $P$, then why use a PUF in the first place if you can generate a key and store it there? – Conrado PLG Jan 26 '12 at 10:42
show 1 more comment

You can also think about PUFs in terms of challenges/responses. If I want to authenticate you with a PUF, I need to be in possession of it first. I make a list of challenges and determine, for each, the reading from the PUF for that challenge. The reading won't necessarily be a compact, high entropy string. So to distil the reading down to a high entropy value, I use an extractor.

Extractors are fine if the readings are consistent. However with most PUFs, the readings will be noisy and moderately inconsistent. The $P$ value is sometimes called a secure sketch ($P$). All it does is help do error correction. The sketch is not specific to using PUFs; it is part of a "fuzzy extraction" process that can be done after getting a noisy reading from any source.

For each challenge, I record the value extracted from the reading as the correct response. I then send you the PUF. When you want to authenticate, I send a challenge that I haven't used before, you get a reading off the PUF, use the profile to extract the response, and send the response. If it matches, I scratch the challenge & response pair off the list and authenticate you for that session.

The sketches can be made public. They leak no useful information to an adversary trying to guess the correct response. The adversary will have just as much luck guessing the response with or without the sketch.

There is no threat of the adversary changes the sketch server-side: I've already used the sketch to generate the responses and I'm done with it.

An adversary might change the sketch client-side. This would cause a denial-of-service: a legitimate user will no longer be able to authenticate. That is an accepted limitation of the threat model.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 38, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9418573975563049, "perplexity_flag": "middle"}