Physical Unclonable Functions (PUFs) and Applications

LPN-Based PUFs

This project presents a fuzzy extractor whose security can be reduced to the hardness of Learning Parity with Noise (LPN) and can efficiently correct a constant fraction of errors in a biometric source with a “noise-avoiding trapdoor.” Using this computational fuzzy extractor, a stateless construction of a cryptographically-secure Physical Unclonable Function is presented. The new construct requires no non-volatile (permanent) storage, secure or otherwise, and its computational security can be reduced to the hardness of an LPN variant under the random oracle model. The construction is “stateless,” because there is no information stored between subsequent queries, which mitigates attacks against the PUF via tampering. Moreover, our stateless construction corresponds to a PUF whose outputs are free of noise because of internal error-correcting capability, which enables a host of applications beyond authentication. Experimental evidence shows that the construction is practical and reliable under a wide environmental range (up to 20% errors can be corrected while still being able to generate secure bits under appropriate LPN assumptions).

As a consequence of the internal error-correcting capability the idea of Controlled PUFs can now be realized in practice; “control” is realized by a PUF interface and is specific to the security application, e.g., providing a “proof of execution” or “backward security” (see below). Without sufficient error-correcting capability, responses can only be compared which limits PUF technology to identification and authentication applications.

The above is ongoing collaborative work with C. Herder, L. Ren, M. van Dijk, M. Yu, and S. Devadas.

Reference

• C. Herder, L. Ren, M. Yu, M. van Dijk, and S. Devadas, "Trapdoor Computational Fuzzy Extractors and Stateless Cryptographically-Secure Physical Unclonable Functions", IEEE Transactions on Dependable and Secure Systems, March 2016. [Eprint]

Backward Security

Recent years have shown the fallacy of Certificate Authorities (CAs); insiders are able to steal master signing keys and impersonate certificates, exploitation of system vulnerabilities and other means of infiltration allow attackers to gain access to CAs and copy their keys, etc. At stake is the mere survival of public key infrastructures as trust in them is bootstrapped from trust in certificates that bind public keys to known identities. The current attack surface exposed by CAs makes trust in their issued certificates questionable. Cryptography has found a partial solution with its introduction of forward security meaning that even if a current key is stolen, a forward secure key management scheme guarantees that the stolen current key does not leak non-negligible information about past keys. The main problem, however, is what the current stolen key tells about to be used future keys for signing future certificates.

A secure solution to this central problem cannot be based on a key management scheme which uses pseudo randomness (in the form of a PRNG) instead of unclonable true randomness and which captures all its state in digital form (including PRNG seeds); once an attacker takes a snapshot of all digital state, the attacker is able to successfully clone the key management scheme in its current state from which the attacker can fast forward its execution and recover future keys. Therefore a secure solution must be based on unclonable true randomness, which is not a straightforward exercise since newly generated secret keys need certain algebraic properties in order to offer forward security and newly reconfigured secret keys through tampering of digital state by an attacker should be revoked before the attacker is even able to sign valid certificates. Our proposed solution is based on a physical unclonable function with a trusted logical interface having constant sized tamper resistant storage which an adversary can take snapshots of (as in the explained attack model) but cannot modify.

The project (1) introduces a new notion of backward security which allows the legitimate owner of a reconstructed secret key to detect whether this key is known to another party before the owner will start using the key. In order to realize a backward (and forward) secure key management scheme the proposed work (2) introduces Programmable Logically Erasable PUFs, a new hardware security primitive based on a Physical Unclonable Function (PUF) which, given a PUF challenge, allows one to program the max number of times the PUF is allowed to measure the response corresponding to the challenge (after which the challenge response pair can be viewed as being erased). The above leads to (3) efficient self-recovering certificate authorities; these are CAs which in the presence of an adversary, who can take a snapshot of all digital (non-volatile) state, who can even see (volatile) internal PUF interface computations (i.e., the internal workings of the PUF itself cannot be observed, in particular, the PUF is assumed to resist side channel attacks), and who can modify all digital storage except for a small constant sized state (in the PUF interface), is able to recover from any impersonation attack by (a) revoking signing keys known to the adversary before the CA is going to use them and by (b) using a non-compromised signing key sequence (which exists with overwhelming probability) to replace the revoked ones. Backward security and programmable logically erasable PUFs are useful concepts in themselves with application to (4) forward and backward secure public key encryption, the corner stone to offerering strong privacy guarantees of encrypted cloud storage with outsourced key management.

The above is ongoing collaborative work with C. Jin, C. Herder, X. Yu, W. Burleson, U. Ruhrmaier, and M. van Dijk. A preliminary first version explaining the notions of PLayPUF and backward security can be found

Reference

• C. Jin, X. Xu, W. Burleson, U. Ruhrmair and M. van Dijk. "PLayPUF: Programmable Logically Erasable PUFs for Forward and Backward Secure Key Management".IACR Cryptology ePrint Archive 2015, 1052 (2015). [Eprint]