Virgil D. Gligor (Carnegie Mellon University), Maverick S. L. Woo (Carnegie Mellon University)

Root-of-Trust (RoT) establishment ensures either that the state of an untrusted system contains all and only content chosen by a trusted local verifier and the system code begins execution in that state, or that the verifier discovers the existence of unaccounted for content. This ensures program booting into system states that are free of persistent malware. An adversary can no longer retain undetected control of one's local system.

We establish RoT {em unconditionally}; i.e., without secrets, trusted hardware modules and instructions, or bounds on the adversary's computational power. The specification of a system's chipset and device controllers, and an external source of true random numbers, such as a commercially available quantum RNG, is all that is needed. Our system specifications are those of a concrete Word Random Access Machine (cWRAM) model -- the closest computation model to a real system with a large instruction set.

We define the requirements for RoT establishment and explain their differences from past attestation protocols. Then we introduce a RoT establishment protocol based on a new computation primitive with concrete (non-asymptotic) optimal space-time bounds in adversarial evaluation on the cWRAM. The new primitive is a randomized polynomial, which has $k$-independent uniform coefficients in a prime order field. Its collision properties are stronger than those of a $k$-independent (almost) universal hash function in cWRAM evaluations, and are sufficient to prove existence of malware-free states before RoT is established. Preliminary measurements show that randomized-polynomial performance is practical on commodity hardware even for very large $k$.

To prove the concrete optimality of randomized polynomials, we present a result of independent complexity interest: a Horner-rule program is uniquely optimal whenever the cWRAM execution space and time are simultaneously minimized.

View More Papers

Cracking the Wall of Confinement: Understanding and Analyzing Malicious...

Eihal Alowaisheq (Indiana University, King Saud University), Peng Wang (Indiana University), Sumayah Alrwais (King Saud University), Xiaojing Liao (Indiana University), XiaoFeng Wang (Indiana University), Tasneem Alowaisheq (Indiana University, King Saud University), Xianghang Mi (Indiana University), Siyuan Tang (Indiana University), Baojun Liu (Tsinghua University)

Read More

TIMBER-V: Tag-Isolated Memory Bringing Fine-grained Enclaves to RISC-V

Samuel Weiser (Graz University of Technology), Mario Werner (Graz University of Technology), Ferdinand Brasser (Technische Universität Darmstadt), Maja Malenko (Graz University of Technology), Stefan Mangard (Graz University of Technology), Ahmad-Reza Sadeghi (Technische Universität Darmstadt)

Read More

MBeacon: Privacy-Preserving Beacons for DNA Methylation Data

Inken Hagestedt (CISPA Helmholtz Center for Information Security), Yang Zhang (CISPA Helmholtz Center for Information Security), Mathias Humbert (Swiss Data Science Center, ETH Zurich/EPFL), Pascal Berrang (CISPA Helmholtz Center for Information Security), Haixu Tang (Indiana University Bloomington), XiaoFeng Wang (Indiana University Bloomington), Michael Backes (CISPA Helmholtz Center for Information Security)

Read More

Private Continual Release of Real-Valued Data Streams

Victor Perrier (Data61, CSIRO and ISAE-SUPAERO), Hassan Jameel Asghar (Macquarie University and Data61, CSIRO), Dali Kaafar (Macquarie University and Data61, CSIRO)

Read More