Paper 2017/932

Why Attackers Lose: Design and Security Analysis of Arbitrarily Large XOR Arbiter PUFs

Nils Wisiol, Christoph Graebnitz, Marian Margraf, Manuel Oswald, Tudor A. A. Soroceanu, and Benjamin Zengin

Abstract

In a novel analysis, we formally prove that arbitrarily many Arbiter PUFs can be combined into a stable XOR Arbiter PUF. To the best of our knowledge, this design cannot be modeled by any known oracle access attack in polynomial time. Using majority vote of arbiter chain responses, our analysis shows that with a polynomial number of votes, the XOR Arbiter PUF stability of almost all challenges can be boosted exponentially close to 1; that is, the stability gain through majority voting can exceed the stability loss introduced by large XORs for a feasible number of votes. Considering state-of-the-art modeling attacks by Becker and Rührmair et al., our proposal enables the designer to increase the attacker's effort exponentially while still maintaining polynomial design effort. This is the first result that relates PUF design to this traditional cryptographic design principle.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. PROOFS 2017
Contact author(s)
nils wisiol @ fu-berlin de
History
2017-09-25: received
Short URL
https://ia.cr/2017/932
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/932,
      author = {Nils Wisiol and Christoph Graebnitz and Marian Margraf and Manuel Oswald and Tudor A.  A.  Soroceanu and Benjamin Zengin},
      title = {Why Attackers Lose: Design and Security Analysis of Arbitrarily Large XOR Arbiter PUFs},
      howpublished = {Cryptology ePrint Archive, Paper 2017/932},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/932}},
      url = {https://eprint.iacr.org/2017/932}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.