berdardini14theoretical

Introduction

• Weak PUFs have a limited domain size that, in the extreme case, can reduce to the empty set, making
  the PUF a constant function. We propose for the latter case (the only one considered in this paper) the term Physically Unclonable Constant (PUC).

• The typical usage of a PUC is to provide the chip with a unique secret ID that can be used, for example, to generate private cryptographic keys.

• The problem of instability of PUFs, when used for authentication, is sometimes solved by accepting the response even if the match is not perfect.

• PUCs used for private key creation are even more delicate.

• Two drawbacks of helper-based stabilizers are the fact that:

  • the helper could leak information or be used for attacking the system (e.g, with a side-channel attack)

  • helper NVM are often expensive since they require special processes (different from the usual CMOS) for their production.

• Given the drawbacks of helper-based stabilizers, there is some interest in developing helper-less stabilizers, that is, stabilizers that do not require auxiliary data.

• The direct usage of error correction codes does not work since there is no guarantee that the nominal output of the PUC will be a codeword.

• In order to understand if helper-less stabilization is feasible and which kind of performance we can expect, in this paper we determine some theoretical limits of helperless stabilizers and show that the helper-less approach has the potential of providing good performance with limited complexity.

STATE OF THE ART

Most of the stabilizers developed so far make use of helpers. Among the most common proposed stabilizers one can cite fuzzy extractors, usually based on error correction codes [21], [22], stabilizer based on pattern matching [7], and Index Based Syndrome stabilizers [27].

The only helperless stabilizer we are aware of is a brute-force exhaustive search for the error pattern proposed in [28].   

OUR CONTRIBUTION

This paper has three main results.

1. First, we prove that global stability is not achievable, that is, it is not possible to construct an helper-less stabilizer that stabilizes every possible device (see Theorem 1).

2. The second result softens the first negative result showing that, although global stability cannot be achieved, one can achieve stability as good as desired over a proper subset, large as desired, of the possible devices (see Theorem 2).

3. Finally, the third result shows that it is possible to recognize (and discard) at construction time the devices belonging to the ``bad'' subset (see Theorem 3), achieving quasi-global stability.

Nomenclature

• Raw PUC (RPUC)

• Stabilized PUC (SPUC)

THE MODEL

THE RPUC

An SRAM cell with a strong asymmetry will have a marked preference for one of the two values, actually acting as a random constant; if the cell is almost symmetric it will have no preference and every query will be almost as a coin toss.

Q is the probability of getting ``1'' as outcome: the best cells have Q 0 or Q 1

Open

THE STABILIZER

In this paper we are interested, however, in helper-less stabilizers, that is, stabilizers that do not require any auxiliary value.

More precisely, we are interested in finding out the theoretical limits to the stability of a SPUC that employs a helper-less stabilizer.

WHAT ARE GOOD SPUCs MADE OF?

The two most important characteristics that a SPUC should have: stability (or noiseless) and uniformity (or maximum entropy).

MEASURING THE STABILITY OF A SPUC

Open

NON-REDUNDANT STABILIZERS AND BALANCED STABILIZERS

The unbalance depends on the employed RPUC scheme via the distribution of Q and that the unbalance of a good stabilizer will be small and almost independent on the details of the distribution of Q. It is clear that we prefer balanced stabilizers since the output will have maximum entropy.

LOCAL AND GLOBAL STABILITY

FIRST RESULT: PERFECT RELIABILITY IS UNACHIEVABLE

SECOND RESULT: (\nu, \sigma)-STABILITY IS ACHIEVABLE

Although Algorithm 1 can be used in practice, no claim is done about its optimality. Actually, the problem of constructing the optimal helper-less stabilizer for a given RPUC is still open.

Note that if the distribution of Q changes because of aging or environmental variations, the right hand side of (23) will be likely to change too. If (23) is going to be used in a real design, a possible approach is to consider the worst case and take for K the maximum of (23), taken over all the environment
conditions.

Note that the right hand side of (23) is likely to be a ``pessimistic'' bound, since it is derived from Chebyshev's inequality. A less pessimistic bound can be derived by approximating mq (mean of q) with a Gaussian variable.

THIRD RESULT: FROM (\nu, \sigma)-STABILITY TO QUASI-GLOBAL STABILITY

We will call any procedure designed to check if a device is reliable or not a verifier.

EXAMPLES OF STABILIZER DESIGNS

(I think they referred to the Dark Bit approach defined in [32])

THE QUASI-GLOBAL STABILITY APPROACH

An alternative approach that requires a smaller number of queries is the approach described in Section VII, that is, testing the cells at the first turn-on and disabling those that are not reliable enough. This approach has the drawback that it requires a surplus of cells in order to get a working device even with some cells disabled.