Modeling attacks on strong physical unclonable functions strengthened by random number and weak PUF

Physical Unclonable Function (PUF) is a promising hardware security primitive. One important category of PUFs is the strong PUF with numerous Challenge-Response Pairs (CRPs). Since the typical strong PUFs, the arbiter PUF and several its variants, were broken by modeling attacks, many new designs for resisting modeling attacks have been proposed. Do they really achieve their promise, or are they only another pipe dream? This paper targets two PUF designs: the randomized PUF and the obfuscation PUF, which strengthen the arbiter PUF by leveraging the random number and the weak PUF, respectively. A heuristic algorithm is proposed for attacking these PUFs. The algorithm is implemented in CUDA. Some PUFs that cannot be broken in several months by CPU show their vulnerabilities in days by leveraging the GPU acceleration. The experimental results show that, for certain scales of objective PUFs, the prediction accuracy is beyond the reliability of CRPs, indicating successful attacks.