Cryptology ePrint Archive: Report 2017/551

A Fourier Analysis Based Attack against Physically Unclonable Functions

Fatemeh Ganji and Shahin Tajik and Jean-Pierre Seifert

Abstract: Electronic payment systems have leveraged the advantages offered by the RFID technology, whose security is promised to be improved by applying the notion of Physically Unclonable Functions (PUFs). Along with the evolution of PUFs, numerous successful attacks against PUFs have been proposed in the literature. Among these are machine learning (ML) attacks, ranging from heuristic approaches to provable algorithms, that have attracted great attention. Our paper pursues this line of research by introducing a Fourier analysis based attack against PUFs. More specifically, this paper focuses on two main aspects of ML attacks, namely being provable and noise tolerant. In this regard, we prove that our attack is naturally integrated into a provable Probably Approximately Correct (PAC) model. Moreover, we show that our attacks against known PUF families are effective and applicable even in the presence of noise. Our proof relies heavily on the intrinsic properties of these PUF families, namely arbiter, Ring Oscillator (RO), and Bistable Ring (BR) PUF families. We believe that our new style of ML algorithms, which take advantage of the Fourier analysis principle, can offer better measures of PUF security.

Category / Keywords: Physically Unclonable Functions, Boolean Analysis, Noise Sensitivity, Low Degree Algorithm, Machine Learning, PAC Learning.

Original Publication (with minor differences): Financial Cryptography and Data Security 2018

Date: received 6 Jun 2017, last revised 30 Nov 2017

Contact author: fganji at sec t-labs tu-berlin de

Available format(s): PDF | BibTeX Citation

Version: 20171130:134315 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]