Attacking PUF-Based pattern Matching Key Generators via Helper Data Manipulation

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, Reliable and efficient PUF-based key 
     generation using  pattern matching, HOST 2011, Proceedings of the 2011
     IEEE International Symposium on Hardware-Oriented Security and
     Trust (HOST), 5-6 June 2011.