2010 Reports :  Cryptology ePrint Archive Forum
Discussion forum for Cryptology ePrint Archive reports posted in 2010. Please put the report number in the subject.
2010/251 PUF exaggeration
Posted by: djb (IP Logged)
Date: 05 May 2010 08:10

The authors of 2010/251 are wildly exaggerating the impact of their results when they claim that they can clone many types of PUFs and thus break "essentially all" PUF applications and protocols.

The easiest way to understand this is to consider the classic _linear_ PUFs (the original optical PUFs using speckle patterns). For these PUFs, the type of "break" carried out in 2010/251 is trivial by design: anyone with access to the PUF can easily see the PUF behavior and build a _large_ device (camera + laptop + projector) that simulates the PUF. The PUF is nevertheless unbroken: the attacker is unable to manufacture a _small_ device that simulates the PUF. The PUF user verifies the PUF size, of course.

---D. J. Bernstein
Research Professor, Computer Science, University of Illinois at Chicago

Re: 2010/251 PUF exaggeration
Posted by: boskom (IP Logged)
Date: 17 May 2011 18:29

luzagodom Wrote:
-------------------------------------------------------
> 2010/251 PUF exaggeration. Posted by: djb (IP
> Logged). Date: 05 May 2010 08:10. The authors of
> 2010/251 are wildly exaggerating the impact of
> their results

I must say that I desagree, but that is my opinion.

Re: 2010/251 PUF exaggeration
Posted by: GeorgeBest (IP Logged)
Date: 22 July 2013 15:15

I must admit that I do not find D.J. Bernstein’s assessment appropriate, for a number of reasons.

First of all, the optical example he gives does not really apply to the work of Rührmair et al. They only discuss modeling attacks on electrical PUFs with digital, one-bit outputs. Such outputs can easily be imitated if an efficient algorithm that predicts the electrical PUF is known. The simulation algorithms which Rührmair et al. derive are, in fact, extremely simple. They often merely require the addition of small integers, followed by a comparison operation. If implemented, their form factor would be quite close to a “real PUF”. In particular, they could be easily implemented in smart cards and the like, which are one of the standard application examples for PUFs. In order to notice the difference, honest users would have to physically open the PUF/smart card and inspect it with utmost thoroughness, which is in an impractical task for the average user. This makes the simulation algorithms of Rührmair et al an extremely effective way to cheat.

Furthermore, even if the outputs of a PUF are analog and complex (as in the case of optical PUFs), a simulation algorithm can be used to break certain protocols. For example, an exchanged key can be derived already from mere numeric simulations of the PUF. The exact analog imitation of the complex optical signal is not necessary to this end.

I also cannot share D.J. Bernstein’s claim that the authors would exaggerate their results. They give intensive and, in my opinion, well-balanced discussions on the reach, but at the same time on the limitations of their techniques in the introduction section (and partly also in the summary section). For example, they make clear that their attacks apply to so-called “Weak PUFs” only under very rare circumstances, and that they do not apply at all to Coating PUFs, SRAM PUFs, or Butterfly PUFs. Any readers who had a short glimpse at the introduction cannot miss this discussion, and could hardly make claims on a “PUF-exaggeration”, as the ones we have seen.

Finally, it may be interesting to add that following its publication on the ePrint archive, the paper has been accepted to CCS in 2010. It has been quoted multiple times in the meantime (please see Google scholar). It is clear that such acceptance and citation numbers cannot always prove the quality of scientific work. But in this case, they show at least that the paper has been received rather well in the PUF community, which is somewhat at odds with D.J. Bernstein’s (perhaps too harsh) criticism of the paper.

GeorgeBest