  Physically unclonable functions (PUFs) can be employed for device
identification, authentication, secret key storage, and other security tasks.
However, PUFs are susceptible to modeling attacks if a number of PUFs'
challenge-response pairs (CRPs) are exposed to the adversary. Furthermore, many
of the embedded devices requiring authentication have stringent resource
constraints and thus require a lightweight authentication mechanism. We propose
PUF-RLA, a PUF-based lightweight, highly reliable authentication scheme
employing binary string shuffling. The proposed scheme enhances the reliability
of PUF as well as alleviates the resource constraints by employing error
correction in the server instead of the device without compromising the
security. The proposed PUF-RLA is robust against brute force, replay, and
modeling attacks. In PUF-RLA, we introduce an inexpensive yet secure stream
authentication scheme inside the device which authenticates the server before
the underlying PUF can be invoked. This prevents an adversary from brute
forcing the device's PUF to acquire CRPs essentially locking out the device
from unauthorized model generation. Additionally, we also introduce a
lightweight CRP obfuscation mechanism involving XOR and shuffle operations.
Results and security analysis verify that the PUF-RLA is secure against brute
force, replay, and modeling attacks, and provides ~99% reliable authentication.
In addition, PUF-RLA provides a reduction of 63% and 74% for look-up tables
(LUTs) and register count, respectively, in FPGA compared to a recently
proposed approach while providing additional authentication advantages.
