System-of-PUFs: multilevel security for embedded systems

Embedded systems continue to provide the core for a wide range of applications, from smart-cards for mobile payment to smart-meters for power-grids. The resource and power dependency of embedded systems continues to be a challenge for state-of-the-art security practices. Moreover, even theoretically secure algorithms are often vulnerable in their implementation. With decreasing cost and complexity, physical attacks are an increasingly important threat. This threat led to the development of Physically Unclonable Functions (PUFs) which are disordered physical systems with various applications in hardware security. However, consistent security oriented design of embedded systems remains a challenge, as most formalizations and security models are concerned with isolated physical components or high-level concept. We provide four unique contributions: (i) We propose a system-level security model to overcome the chasm between secure components and requirements of high-level protocols; this enables synergy between component-oriented security formalizations and theoretically proven protocols. (ii) An analysis of current practices in PUF protocols using the proposed system-level security model; we identify significant issues and expose assumptions that require costly security techniques. (iii) A System-of-PUF (SoP) that utilizes the large PUF design-space to achieve security requirements with minimal resource utilization; SoP requires 64% less gate-equivalent units than recently published schemes. (iv) A multilevel authentication protocol based on SoP which is validated using our system-level security model and which overcomes current vulnerabilities. Furthermore, this protocol offers breach recognition and recovery.