Marcin led the last study group
on ``Attacking PUF-Based pattern Matching Key Generators via Helper Data
Manipulation'' (Jeroen Delvaux and Ingrid Verbauwhede) presented at CT-RSA 2014
(link ).

Physically Unclonable Functions
(PUFs) can be roughly thought as `random' functions accepting a

**challenge**(typically a sequence of bits) as input, and generating a**response**(a different sequence of bits) that is unique for each PUF and for each physical instance. More precisely, it is a*physical*device that produces*unclonable*challenge-response pairs (CRPs); this means that the input/output behavior of any physical copy of one PUF will differ from that of the original one due to some uncontrollable randomness in the copying process.
PUFs are emerging hardware
primitives which can be used for example in key generation applications,
replacing the more conventional non-volatile memory (NVM); thus, instead of
storing the secret key in digital memory, PUFs permit to derive it from the
physical characteristics of the integrated circuits (ICs), reducing consequently the risks of
physical and invasive attacks.

Unfortunately, there are two main issues concerning PUFs, namely the lack
of robustness and unpredictability: in some applications we would like to
obtain the same response every time the corresponding challenge is queried (for
example to enable repeatable key-generations), but often, due to the noise, the
responses are not perfectly reproducible, causing CRPs of type (c,r), (c, r');
moreover, quite likely the response bits are non-uniformly distributed,
especially when the number of CRPs is very large. While fixing the latter
problem is relatively easy, for example using hash functions, obtaining
robustness is more involved.

To overcome both these issues it
is necessary to implement additional post-processing logic. There are
essentially two different solutions: Fuzzy extractors [1], that perform both error correction (using for
example BCH codes) and privacy amplification (applying hash functions), and Pattern Matching Key
Generators (PMKGs) [2].

Delvaux and Verbauwhede in their work describe an attack
to PMGK and also propose a countermeasure to it.

**Pattern Matching Key Generators – Description**

At a high level we can say that
this approach reverses the standard challenge-response format of a PUF.

To describe a PMKG we distinguish
an Enrollment phase and a Reconstruction
phase.

*Enrollment.*Consider a stream (

**Resp**) of PUF response bits, corresponding to a certain number of challenges, and refer as a pattern any subset of W consecutive bits of

**Resp.**If

**Resp**consists of L+W – 1 bits, then we have L possible patterns.

a. Select one of these patterns
at random (using an external interface) and store the index

*j*corresponding to it. The actual corresponding response bits (**Patt**) are published publicly and form the Public Helper Data (**Pub**).
Note here that is the index

*j*that is kept secret, and hence used to derive the secret key, and not the response bits; any index provides log_2(L) bits, assuming L=2^k, for some positive integer k.
b. Repeat the previous step H times (

*Rounds*).
c. Concatenate the indices (j_1
|| j_2 || ... || j_H) to obtain the full secret key.

*Reconstruction*. To recover the key, the PUF is iterated through a deterministic set of challenges, obtaining

**Resp'_i**, i=1, ..., H, (

**Resp'_i**can be seen as

**Resp_i+Noise_i).**Then perform a patter matching procedure for every round. Note that

**Resp'_i**contains some noise, so the pattern

**Patt'_i**corresponding to the public

**Patt_i**will be the the (only) one which satisfies d(

**Patt_i,Patt'_i**) =t <= T, where T is a fixed and well-chosen threshold value, and d denotes the Hamming distance.

**Pattern Matching Key Generators – Attack**

To describe the attack the
authors first model the failures of PMKG. It is very easy to see that there are
two possible failures for key reconstruction: pattern misses and pattern
collisions. The first occur when t > T, and the second occur if t =< T for some index

*j' not*corresponding to the secret sequence of indices. If we denote by P_MISS and P_COLL the probability of a pattern miss and collision, respectively, it is possible to prove that:
P_FAIL= 1-
(1-P_MISS)^H(1-P_COLL)^H,

where P_FAIL indicates the
overall failure probability. Intuitively it is clear that pattern misses occur
when T is small, whereas pattern collisions are more probable when T is large.

In a nutshell, the attack
presented in the paper, and named SNAKE due to the similarities with the
well-known video game, exploits malicious modifications of the public helper
string

**Pub**as follows. The idea is to replace the last (to the right) bit of**Pub**introducing a random bit in the first position (to the left). In this way the first unexposed bit immediately to the left of**Pub**is retrieved via statistical properties of the overall failure probability P_FAIL. Then it is possible repeating the same procedure moving along the PUF response string like a snake. When a consistent change in failure rate occurs, then the secret index*j*is revealed.**References**

[1] Dodis,
Yevgeniy and Ostrovsky, Rafail and Reyzin, Leonid and Smith, Adam,

*Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other*

*Noisy Data,*SIAM J. Comput. , 2008.

[2] Zdenek Sid
Paral and Srinivas Devadas,

IEEE International Symposium on Hardware-Oriented Security and

Trust (HOST), 5-6 June 2011.

*Reliable and efficient PUF-based key**generation using**pattern matching*, HOST 2011, Proceedings of the 2011IEEE International Symposium on Hardware-Oriented Security and

Trust (HOST), 5-6 June 2011.

## No comments:

## Post a Comment