Reverse Fuzzy Extractors: Enabling Lightweight Mutual Authentication for PUF-Enabled RFIDs

RFID-based tokens are increasingly used in electronic payment and ticketing systems for mutual authentication of tickets and terminals. These systems typically use cost-effective tokens without expensive hardware protection mechanisms and are exposed to hardware attacks that copy and maliciously modify tokens. Physically Unclonable Functions (PUFs) are a promising technology to protect against such attacks by binding security critical data to the physical characteristics of the underlying hardware. However, existing PUF-based authentication schemes for RFID do not support mutual authentication, are often vulnerable to emulation and denial-of service attacks, and allow only for a limited number of authentications. In this paper, we present a new PUF-based authentication scheme that overcomes these drawbacks: it supports PUF-based mutual authentication between tokens and readers, is resistant to emulation attacks, and supports an unlimited number of authentications without requiring the reader to store a large number of PUF challenge/response pairs. In this context, we introduce reverse fuzzy extractors, a new approach to correct noise in PUF responses that allows for extremely lightweight implementations on the token. Our proof-of-concept implementation shows that our scheme is suitable for resource-constrained devices.