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.
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.
generation using pattern matching, HOST 2011, Proceedings of the 2011
IEEE International Symposium on Hardware-Oriented Security and
Trust (HOST), 5-6 June 2011.
No comments:
Post a Comment