IACR News item: 22 March 2016
Marten van Dijk, Ulrich Rührmair
ePrint Report
We continue investigations on the use of so-called Strong PUFs as a cryptographic primitive in realistic attack models. We focus on two scenarios: Firstly, the {\it PUF re-use model}, where PUFs are being used in more than one protocol run, implying that adversaries may gain {\it retrospective access} to PUFs after the completion of an earlier protocol. Such re-use appears indispensible in economically and practically viable PUF-applications, but can lead to unexpected attacks. Secondly, the {\it bad} (or {\it malicious}) {\it PUF model}, in which the employed PUFs have been manipulated to possess additional, hidden properties, which enable adversaries to cheat. For the first time, we consider adversaries who build new, malicious PUFs by using old, possibly benign PUFs as subparts of the new PUF, naming this scenario the {\it PUFs-inside-PUFs model}. In these three models, we obtain and/or formally prove the following results:
\begin{itemize}
\item {\sc PUF re-use, part I:} Any PUF that is {\it ``ideal''} and retrospectively accessible can be replaced by a standard random oracle. By applying the famous Impagliazzo-Rudich result \cite{IR}, this means that the power of plain Strong PUFs under retrospective access is severely limited; for example, it does not suffice to implement key exchange (KE) or oblivious transfer (OT).
\item {\sc PUF re-use, part II:} Any PUF that is both bad/malicious and retrospectively accessible can be completely eliminated from the protocol. The protocol can be compiled into an information-theoretically equivalent one without this PUF.
\item {\sc Bad PUFs and Simplification:} As a minor contribution, we simplify a recent OT-protocol for malicious PUFs by Dachman-Soled et al.~\cite{Dachman-Soled} from CRYPTO 2014. We can achieve the same security properties under the same assumptions, but use only one PUF instead of two.
\item {\sc PUFs-inside-PUFs, part I:} We propose the new adversarial model of {\it ``PUFs-inside-PUF attacks''}, and show that the earlier protocol of Dachman-Soled et al.\ \cite{Dachman-Soled} is vulnerable in this model (which lies outside the original framework of \cite{Dachman-Soled}).
\item {\sc PUFs-inside-PUFs, part II:} We construct a new PUF-based OT-protocol, which is secure against PUFs-inside-PUFs attacks if the used bad PUFs are stateless. Our protocol introduces the technique of interleaved challenges. We illustrate why the use of interactive hashing in the protocol is necessary, and why a first protocol attempt without interactive hashing fails.
\end{itemize}
Our findings are not restricted to the UC-framework or its peculiarities, but also apply in stand-alone settings. They have immediate relevance for PUF hardware design: The secure re-use of PUFs in protocols like KE or OT requires properties beyond unpredictability and unclonability. These include {\it reconfigurability} or {\it erasability} as well as {\it certifiability}. Their effective implementation is posed as a central new design goal by our work. Finally, we stress that the secure use of Strong PUFs in standard PUF-based identification protocols remains mostly unaffected by our results, and by attacks in the bad PUF model and the PUF re-use model alike.
\begin{itemize}
\item {\sc PUF re-use, part I:} Any PUF that is {\it ``ideal''} and retrospectively accessible can be replaced by a standard random oracle. By applying the famous Impagliazzo-Rudich result \cite{IR}, this means that the power of plain Strong PUFs under retrospective access is severely limited; for example, it does not suffice to implement key exchange (KE) or oblivious transfer (OT).
\item {\sc PUF re-use, part II:} Any PUF that is both bad/malicious and retrospectively accessible can be completely eliminated from the protocol. The protocol can be compiled into an information-theoretically equivalent one without this PUF.
\item {\sc Bad PUFs and Simplification:} As a minor contribution, we simplify a recent OT-protocol for malicious PUFs by Dachman-Soled et al.~\cite{Dachman-Soled} from CRYPTO 2014. We can achieve the same security properties under the same assumptions, but use only one PUF instead of two.
\item {\sc PUFs-inside-PUFs, part I:} We propose the new adversarial model of {\it ``PUFs-inside-PUF attacks''}, and show that the earlier protocol of Dachman-Soled et al.\ \cite{Dachman-Soled} is vulnerable in this model (which lies outside the original framework of \cite{Dachman-Soled}).
\item {\sc PUFs-inside-PUFs, part II:} We construct a new PUF-based OT-protocol, which is secure against PUFs-inside-PUFs attacks if the used bad PUFs are stateless. Our protocol introduces the technique of interleaved challenges. We illustrate why the use of interactive hashing in the protocol is necessary, and why a first protocol attempt without interactive hashing fails.
\end{itemize}
Our findings are not restricted to the UC-framework or its peculiarities, but also apply in stand-alone settings. They have immediate relevance for PUF hardware design: The secure re-use of PUFs in protocols like KE or OT requires properties beyond unpredictability and unclonability. These include {\it reconfigurability} or {\it erasability} as well as {\it certifiability}. Their effective implementation is posed as a central new design goal by our work. Finally, we stress that the secure use of Strong PUFs in standard PUF-based identification protocols remains mostly unaffected by our results, and by attacks in the bad PUF model and the PUF re-use model alike.
Additional news items may be found on the IACR news page.