Abstract
Root-of-Trust (RoT) establishment assures that either a state of an untrusted system contains all and only content chosen by an external verifier and the verifier’s code begins execution in that state, or the verifier discovers the existence of unaccounted content. RoT establishment is sufficient to assure program booting in malware-free system states, and necessary for establishing secure initial states for any software system. In particular, it is necessary for software deployed in access control and cryptographic applications despite the presence of an adversary (e.g., persistent malware) that controls that system. In this paper, we define requirements for RoT establishment and their relationships. These requirements differ from those for software-based and cryptographic attestation protocols. We point out these differences and explain why these protocols cannot be expected to satisfy the defined RoT requirements. Then we argue that jointly satisfying all these requirements yields a secure solution for establishing malware-free states – a strictly weaker requirement than RoT establishment. However, to establish RoT, it is sufficient to load a family of almost universal hash functions in a malware-fee state and then verify their outputs when applied to state components.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Different constants of asymptotic lower and upper bounds of \(C_{m,t}\) cause these bounds to differ for concrete values of m and t.
- 2.
This is the opposite of perfect universal hash functions, which seek a constant t independent of the scalable m.
- 3.
Input synchronization delays for \(nonce_{j+1}\) within a \(checksum_j\) computation on a network interface card (Netgear GA 620) that takes time t can be as high as 0.4t with a standard deviation of about 0.0029t; see [3], Sects. 5.4.2-5.4.4.
References
Parno, B., McCune, J.M., Perrig, A.: Bootstrapping Trust in Modern Computers. Springer Briefs in Computer Science, vol. 10. Springer, New York (2011). https://doi.org/10.1007/978-1-4614-1460-5
Li, Y., McCune, J.M., Perrig, A.: SBAP: software-based attestation for peripherals. In: Acquisti, A., Smith, S.W., Sadeghi, A.-R. (eds.) Trust 2010. LNCS, vol. 6101, pp. 16–29. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13869-0_2
Li, Y., McCune, J.M., Perrig, A.: VIPER: verifying the integrity of PERipherals’ firmware. In: Proceedings of the 18th ACM Conference on Computer and Communications Security, pp. 3–16. ACM Press (2011)
Cui, A., Costello, M., Stolfo, S.: When firmware modifications attack: a case study of embedded exploitation. In: Proceedings of the 2013 Network and Distributed Systems Security Symposium, ISOC (2013)
Stewin, P.: Detecting Peripheral-based Attacks on the Host Memory. T-Lab Series in Telecommunication Services. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-319-13515-1
Delugre, G.: Closer to metal: reverse engineering the broadcom NetExtreme’s firmware. In: Sogeti ESEC Lab. (2010)
Duflot, L., Perez, Y.-A., Morin, B.: What if you can’t trust your network card? In: Sommer, R., Balzarotti, D., Maier, G. (eds.) RAID 2011. LNCS, vol. 6961, pp. 378–397. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-23644-0_20
Zaddach, J., et al.: Implementation and implications of a stealth hard-drive backdoor. In: Proceedings of the 29th Annual Computer Security Applications Conference (ACSAC). ACM (2013)
Mearian, L.: There’s no way of knowing if the NSA’s spyware is on your hard drive. Computerworld 2 (2015)
Raiu, C.: Equation: The Death Star of the Malware Galaxy, February 2015
Applebaum, J., Horchert, J., Stocker, C.: Catalog reveals NSA has back doors for numerous devices, vol. 29 (2013)
Greenberg, A.: Why the security of USB is fundamentally broken. In: Wired Magazine, Number July (2014)
Parno, B.: Bootstrapping trust in a trusted platform. In: Proceedings of the 3rd Conference on Hot Topics in security, pp. 1–6. USENIX Association (2008)
Lone-Sang, F., Nicomette, V., Deswarte, Y.: I/O attacks in intel-pc architectures and countermeasures. In: Proceedings of the Symposium for the Security of Information and Communication Technologies SSTIC (2011)
Lone-Sang, F., Nicomette, V., Deswarte, Y.: A tool to analyze potential I/O attacks against PCs. In: IEEE Security and Privacy, pp. 60–66 (2014)
Kaspersky Lab: The Duqu 2.0 - Technical Details (version 2.1). Technical report (2015)
Eldefrawy, K., Perito, D., Tsudik, G.: SMART: Secure and minimal architecture for (establishing a dynamic) root of trust, February 2012
Koeberl, P., Schulz, S., Sadeghi, A.-R., Varadharajan, V.: TrustLite: a security architecture for tiny embedded devices. In: Proceedings of the Ninth European Conference on Computer Systems, EuroSys 2014 (2014)
Asokan, N., et al.: SEDA: scalable embedded device attestation. In: Proceedings of the 2015 ACM Conference on Computer and Communications Security. ACM (2015)
Ibrahim, A., Sadeghi, A.R., Tsudik, G., Zeitouni, S.: DARPA: device attestation resilient to physical attacks. In: Proceedings of the 9th ACM Conference on Security & Privacy in Wireless and Mobile Networks. WiSec 2016, pp. 171–182. ACM (2016)
Ibrahim, A., Sadeghi, A.R., Zeitouni, S.: SeED: secure non-interactive attestation for embedded devices. In: Proceedings of the 10th ACM Conference on Security and Privacy in Wireless and Mobile Networks. WiSec 2017, pp. 64–74 (2017)
Lipton, R., Ostrovsky, R., Zikas, b.: Provable virus detection: using the uncertainty principle to protect against malware. Cryptology ePrint Archive, Report 2015/728 (2015). http://eprint.iacr.org/2015/728
Lipton, R., Ostrovsky, R., Zikas, V.: Provably secure virus detection: using the observer effect against malware. In: 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, 11–15 July 2016, Rome, Italy, pp. 32:1–32:14 (2016)
Thorup, M.: High speed hashing for integers and strings. CoRR arXiv:1504.06804, September 2015
Spinellis, D.: Reflection as a mechanism for software integrity verification. ACM Trans. Inf. Syst. Secur. 3(1), 51–62 (2000)
Seshadri, A., Luk, M., Shi, E., Perrig, A., van Doorn, L., Khosla, P.: Pioneer: verifying code integrity and enforcing untampered code execution on legacy systems. In: Proceedings of the 20th ACM Symposium on Operating Systems Principles, pp. 1–16. ACM (2005)
Seshadri, A., Luk, M., Perrig, A., van Doorn, L., Khosla, P.: SCUBA: secure code update by attestation in sensor networks. In: Proceedings of the 5th ACM Workshop on Wireless Security, pp. 85–94. ACM (2006)
Seshadri, A., Luk, M., Qu, N., Perrig, A.: SecVisor: a tiny hypervisor to provide lifetime kernel code integrity for commodity OSes. In: Proceedings of 21st ACM Symposium on Operating Systems Principles, pp. 335–350. ACM (2007)
Kovah, X., Kallenberg, C., Weathers, C., Herzog, A., Albin, M., Butterworth, J.: New results for timing-based attestation. In: Proceedings of the 2012 IEEE Symposium on Security and Privacy, pp. 239–253. IEEE (2012)
Jakobsson, M., Johansson, K.A.: Retroactive detection of malware with applications to mobile platforms. In: Proceedings of the 5th USENIX Workshop on Hot Topics in Security, USENIX (2010)
Li, Y., Cheng, Y., Gligor, V., Perrig, A.: Establishing software-only root of trust on embedded systems: facts and fiction. In: Christianson, B., Švenda, P., Matyáš, V., Malcolm, J., Stajano, F., Anderson, J. (eds.) Security Protocols 2015. LNCS, vol. 9379, pp. 50–68. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-26096-9_7
Aldaz, M., Heintz, J., Matera, G., Montaa, J., Pardo, L.: Time-space tradeoffs in algebraic complexity theory. J. Complex. 16(1), 2–49 (2000)
Miltersen, P.B.: Lower bounds for static dictionaries on RAMs with bit operations but no multiplication. In: Meyer, F., Monien, B. (eds.) ICALP 1996. LNCS, vol. 1099, pp. 442–453. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-61440-0_149
Andersson, A., Miltersen, P.B., Riis, S., Thorup, M.: Static dictionaries on \(AC^0\) RAMs: query time \({\varTheta } (\sqrt{(}log~n/log~log~n))\) is necessary and sufficient. In: Proceedings of 37th FOCS, pp. 441–450 (1996)
Seshadri, A., Perrig, A., van Doorn, L., Khosla, P.: SWATT: software-based attestation for embedded devices. In: Proceedings of the IEEE Symposium on Security and Privacy, pp. 272–282. IEEE (2004)
Castelluccia, C., Francillon, A., Perito, D., Soriente, C.: On the difficulty of software-based attestation of embedded devices. In: Proceedings of the 16th ACM Conference on Computer and Communications Security, pp. 400–409. ACM (2009)
Perrig, A., van Doorn, L.: Refutation of “on the difficulty of software-based attestation of embedded devices” (2010)
Armknecht, F., Sadeghi, A.R., Schulz, S., Wachsmann, C.: A security framework for the analysis and design of software attestation. In: Proceedings of the 2013 ACM Conference on Computer and Communications Security, pp. 1–12. ACM (2013)
Francillon, A., Nguyen, Q., Rasmussen, K.B., Tsudik, G.: A minimalist approach to remote attestation. In: Proceedings of the Conference on Design, Automation & Test in Europe. DATE 2014, 3001 Leuven, Belgium, Belgium, pp. 244:1–244:6. European Design and Automation Association (2014)
Yao, A.C.-C.: Should tables be sorted? J. ACM 28(3), 615–628 (1981)
Zhao, J., Gligor, V., Perrig, A., Newsome, J.: ReDABLS: revisiting device attestation with bounded leakage of secrets. In: Christianson, B., Malcolm, J., Stajano, F., Anderson, J., Bonneau, J. (eds.) Security Protocols 2013. LNCS, vol. 8263, pp. 94–114. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-41717-7_12
Acknowledgment
Comments received from Gene Tsudik and Adrian Perrig helped clarify the differences between RoT establishment and past attestation protocols.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer Nature Switzerland AG
About this paper
Cite this paper
Gligor, V., Woo, M. (2018). Requirements for Root of Trust Establishment. In: Matyáš, V., Švenda, P., Stajano, F., Christianson, B., Anderson, J. (eds) Security Protocols XXVI. Security Protocols 2018. Lecture Notes in Computer Science(), vol 11286. Springer, Cham. https://doi.org/10.1007/978-3-030-03251-7_23
Download citation
DOI: https://doi.org/10.1007/978-3-030-03251-7_23
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-03250-0
Online ISBN: 978-3-030-03251-7
eBook Packages: Computer ScienceComputer Science (R0)