ZEKRA: Zero-Knowledge Control-Flow Attestation
Authors: 
Heini Bergsson Debes, Edlira Dushku, Thanassis Giannetsos, Ali MarandiAuthors Info & Claims
Pages 357 - 371
Abstract
To detect runtime attacks against programs running on a remote computing platform, Control-Flow Attestation (CFA) lets a (trusted) verifier determine the legality of the program’s execution path, as recorded and reported by the remote platform (prover). However, besides complicating scalability due to verifier complexity, this assumption regarding the verifier’s trustworthiness renders existing CFA schemes prone to privacy breaches and implementation disclosure attacks under “honest-but-curious” adversaries. Thus, to suppress sensitive details from the verifier, we propose to have the prover outsource the verification of the attested execution path to an intermediate worker of which the verifier only learns the result. However, since a worker might be dishonest about the outcome of the verification, we propose a purely cryptographical solution of transforming the verification of the attested execution path into a verifiable computational task that can be reliably outsourced to a worker without relying on any trusted execution environment. Specifically, we propose to express a program-agnostic execution path verification task inside an arithmetic circuit whose correct execution can be verified by untrusted verifiers in zero knowledge.
References
[1]
Martín Abadi 2009. Control-flow integrity principles, implementations, and applications. ACM TISSEC 13, 1 (2009), 1–40.
[2]
Tigist Abera 2016. C-FLAT: control-flow attestation for embedded systems software. In Proceedings of the 2016 ACM SIGSAC Conference. 743–754.
[3]
Tigist Abera 2019. DIAT: Data Integrity Attestation for Resilient Collaboration of Autonomous Systems. In NDSS.
[4]
Alcardo Alex Barakabitze, Arslan Ahmad, Rashid Mijumbi, and Andrew Hines. 2020. 5G network slicing using SDN and NFV: A survey of taxonomy, architectures and future challenges. Computer Networks 167 (2020).
[5]
Eli Ben-Sasson 2013. SNARKs for C: Verifying program executions succinctly and in zero knowledge. In Annual cryptology conference. Springer, 90–108.
[6]
Eli Ben-Sasson 2014. Succinct non-interactive zero knowledge for a von Neumann architecture. In 23rd { USENIX} Security Symposium. 781–796.
[7]
Eli Ben-Sasson 2018. Scalable, transparent, and post-quantum secure computational integrity. Cryptology ePrint Archive (2018).
[8]
Daniel Benarroch 2021. Zero-Knowledge Proofs for Set Membership: Efficient, Succinct, Modular. In International Conference on Financial Cryptography and Data Security. Springer, 393–414.
[9]
Tyler Bletsch 2011. Jump-oriented programming: a new class of code-reuse attack. In Proceedings of the 6th ACM AsiaCCS. 30–40.
[10]
Sean Bowe, Ariel Gabizon, and Matthew D Green. 2018. A multi-party protocol for constructing the public parameters of the Pinocchio zk-SNARK. In International Conference on Financial Cryptography and Data Security. Springer, 64–77.
[11]
Benjamin Braun 2013. Verifying computations with state. In Proceedings of the twenty-fourth ACM Symposium on Operating Systems Principles. 341–357.
[12]
Xavier Carpent 2018. Reconciling Remote Attestation and Safety-Critical Operation on Simple IoT Devices. In DAC ’18.
[13]
Liqun Chen 2008. Property-based attestation without a trusted third party. In International Conference on Information Security. Springer, 31–46.
[14]
Heini Debes. 2022. Code for ZEKRA. https://github.com/HeiniDebes/ZEKRA
[15]
Ghada Dessouky 2017. Lo-fat: Low-overhead control flow attestation in hardware. In Proceedings of the 54th Design Automation Conference 2017. 1–6.
[16]
Ghada Dessouky 2018. Litehax: lightweight hardware-assisted attestation of program execution. In 2018 IEEE/ACM ICCAD. IEEE, 1–8.
[17]
Jacob Eberhardt and Stefan Tai. 2018. Zokrates-scalable privacy-preserving off-chain computations. In IEEE International Conference on Internet of Things.
[18]
Embench. 2022. Modern Embedded Benchmark Suite. https://www.embench.org/
[19]
Aurélien et. al. Francillon. 2014. A minimalist approach to Remote Attestation. In Design, Automation & Test in Europe Conference & Exhibition (DATE).
[20]
Rosario Gennaro 2013. Quadratic span programs and succinct NIZKs without PCPs. In EUROCRYPT. Springer, 626–645.
[21]
Shafi Goldwasser 1989. The knowledge complexity of interactive proof systems. SIAM Journal on computing 18, 1 (1989), 186–208.
[22]
Lorenzo Grassi 2021. Poseidon: A new hash function for zero-knowledge proof systems. In 30th { USENIX} Security Symposium ({ USENIX} Security 21).
[23]
Jens Groth. 2010. Short pairing-based non-interactive zero-knowledge arguments. In Asiacrypt. Springer, 321–340.
[24]
Jens Groth. 2016. On the size of pairing-based non-interactive arguments. In EUROCRYPT. Springer, 305–326.
[25]
Aric Hagberg 2008. Exploring network structure, dynamics, and function using NetworkX. Technical Report. Los Alamos National Lab., Los Alamos, NM.
[26]
Caleb Helbling. 2020. Directed Graph Hashing. preprint arXiv:2002.06653 (2020).
[27]
Hong Hu 2016. Data-Oriented Programming: On the Expressiveness of Non-control Data Attacks. In IEEE Symposium on Security and Privacy (SP).
[28]
Jianxing Hu 2019. A probability prediction based mutable control-flow attestation scheme on embedded platforms. In 18th TrustCom/BigDataSE. IEEE.
[29]
iden3. 2022. zkSNARK implementation. https://github.com/iden3/snarkjs
[30]
Joe Kilian. 1992. A note on efficient zero-knowledge proofs and arguments. In Proceedings of the twenty-fourth annual ACM symposium on Theory of computing.
[31]
Tommy Koens, Coen Ramaekers, and Cees Van Wijk. 2018. Efficient zero-knowledge range proofs in ethereum. ING. blockchain@ ing. com (2018).
[32]
Ahmed Kosba. 2021. Java zkSNARK library. https://github.com/akosba/jsnark
[33]
Ahmed Kosba 2018. xJsnark: A framework for efficient verifiable computation. In 2018 IEEE Symposium on Security and Privacy (SP). IEEE, 944–961.
[34]
Boyu Kuang 2020. DO-RA: data-oriented runtime attestation for IoT devices. Computers & Security 97 (2020), 101945.
[35]
SCIPR Lab. 2020. C++ zkSNARK library. https://github.com/scipr-lab/libsnark
[36]
Panagiotis Liakos 2017. Realizing memory-optimized distributed graph processing. IEEE Transactions on Knowledge and Data Engineering 30, 4 (2017).
[37]
Jingbin Liu 2019. Log-Based Control Flow Attestation for Embedded Devices. In International Symposium on Cyberspace Safety and Security. Springer, 117–132.
[38]
Silvio Micali. 1994. CS proofs. In Proceedings 35th Annual Symposium on Foundations of Computer Science. IEEE, 436–453.
[39]
Assa Naveh and Eran Tromer. 2016. Photoproof: Cryptographic image authentication for any set of permissible transformations. In 2016 IEEE S&P. IEEE, 255–271.
[40]
Ivan De Oliveira Nunes 2020. { APEX} : A Verified Architecture for Proofs of Execution on Remote Devices under Full Software Compromise. In 29th { USENIX} Security Symposium ({ USENIX} Security 20). 771–788.
[41]
Ivan De Oliveira Nunes 2020. Tiny-CFA: A minimalistic approach for CFA using verified proofs of execution. arXiv:2011.07400 (2020).
[42]
Bryan Parno 2013. Pinocchio: Nearly practical verifiable computation. In 2013 IEEE Symposium on Security and Privacy. IEEE, 238–252.
[43]
Eli Ben Sasson 2014. Zerocash: Decentralized anonymous payments from bitcoin. In 2014 IEEE Symposium on Security and Privacy. IEEE, 459–474.
[44]
Berry Schoenmakers 2016. Trinocchio: privacy-preserving outsourcing by distributed verifiable computation. In ACNS. Springer, 346–366.
[45]
Srinath Setty. 2020. Spartan: Efficient and general-purpose zkSNARKs without trusted setup. In Annual International Cryptology Conference. Springer, 704–737.
[46]
Srinath Setty 2012. Taking proof-based verified computation a few steps closer to practicality. In 21st { USENIX} Security Symposium. 253–268.
[47]
Hovav Shacham. 2007. The geometry of innocent flesh on the bone: Return-into-libc without function calls (on the x86). In 14th ACM CCS.
[48]
Yan Shoshitaishvili 2016. SoK: (State of) The Art of War: Offensive Techniques in Binary Analysis. (2016).
[49]
Zhichuang Sun 2020. OAT: Attesting operation integrity of embedded devices. In 2020 IEEE Symposium on Security and Privacy (SP). IEEE, 1433–1449.
[50]
Flavio Toffalini 2019. ScaRR: Scalable Runtime Remote Attestation for Complex Systems. In 22nd International Symposium on { RAID}. 121–134.
[51]
Riad S Wahby 2014. Efficient RAM and control flow in verifiable outsourced computation. Cryptology ePrint Archive (2014).
[52]
Howard Wu 2018. { DIZK} : A distributed zero knowledge proof system. In 27th { USENIX} Security Symposium ({ USENIX} Security 18). 675–692.
[53]
Shaza Zeitouni 2017. Atrium: Runtime attestation resilient under memory attacks. In 2017 IEEE/ACM ICCAD. IEEE, 384–391.
[54]
Yumei Zhang 2021. ReCFA: Resilient Control-Flow Attestation. In Annual Computer Security Applications Conference(ACSAC ’21).
Index Terms
- ZEKRA: Zero-Knowledge Control-Flow Attestation
Recommendations
Whole-Program Control-Flow Path Attestation
CCS '23: Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications SecurityPath attestation is an approach to remotely attest the execution of a program ℘. In path attestation, a prover platform, which executes ℘, convinces a remote verifier V of the integrity of ℘ by recording the path that ℘ takes as it executes a particular ...
Practical and Efficient Attribute-Based Encryption with Constant-Size Ciphertexts in Outsourced Verifiable Computation
ASIA CCS '16: Proceedings of the 11th ACM on Asia Conference on Computer and Communications SecurityIn cloud computing, computationally weak users are always willing to outsource costly computations to a cloud, and at the same time they need to check the correctness of the result provided by the cloud. Such activities motivate the occurrence of ...
Attribute-based versions of Schnorr and ElGamal
We design in this paper the first attribute-based cryptosystems that work in the classical discrete logarithm, pairing-free, setting. The attribute-based signature scheme can be seen as an extension of Schnorr signatures, with adaptive security relying ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2023
1066 pages
Copyright © 2023 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 10 July 2023
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed limited
Conference
ASIA CCS '23
Sponsor:
ASIA CCS '23: ACM Asia Conference on Computer and Communications Security
July 10 - 14, 2023
VIC, Melbourne, Australia
Acceptance Rates
Overall Acceptance Rate 418 of 2,322 submissions, 18%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 337Total Downloads
- Downloads (Last 12 months)190
- Downloads (Last 6 weeks)12
Reflects downloads up to 09 Nov 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign inFull Access
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML Format