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