Keeping Secrets in Resource Aware Components

Tom Chothia, Jun Pang, Muhammad Torabi DashtiQAPL 2007 · DOI

TL;DR

This paper introduces a novel framework for automatically verifying the secrecy of values within software components, even when an attacker can monitor resource usage. They achieve this by extending automata models to incorporate resource costs and developing a "secrecy degree" metric to quantify information leakage, which can be automatically calculated using the µCRL toolset.

What Problem Does This Paper Address?

In component-based software development, components are often reused and interchanged. A critical concern is ensuring that sensitive data within these components remains secret from other components or potential attackers on the same system. This is particularly challenging because attackers can not only observe external communication but also monitor resource usage (like CPU time, memory, or bandwidth), which can inadvertently leak information. Existing methods often struggle to account for this resource-based leakage, leaving a gap in comprehensive security analysis.

Methods

The authors propose a framework based on Q-automata, which are automata augmented with a Q-algebra to label transitions with resource usage costs. This allows for a compositional model of component behavior and resource consumption. They extend these Q-automata to handle value passing, enabling them to model components that process and manipulate data.

The core of their approach lies in defining and automatically checking secrecy degrees. A component is considered to have perfect secrecy if its observable behavior is identical regardless of the secret values it processes. When perfect secrecy isn't achieved, they quantify the leakage using:

  • Component Secrecy Degree (csd): Measures the size of the smallest equivalence class of component instantiations that are indistinguishable to an attacker.
  • Variable Secrecy Degree (vsd): Quantifies the secrecy of individual variables within the component.

To automate this, they leverage the µCRL toolset for state space reduction modulo strong bisimulation. This involves generating a large automaton that represents all possible input values for the component and then reducing it using bisimulation to identify equivalence classes. The size of these classes directly informs the secrecy degrees.

Datasets

Not discussed in the paper. The paper focuses on a theoretical framework and a method for analyzing user-defined automata models.

Key Insights and Ideas

  • Resource Usage as a Leakage Channel: The paper highlights that resource consumption (CPU, memory, bandwidth) can be a significant channel for information leakage, a factor often overlooked in traditional secrecy analysis.
  • Secrecy Degree as a Quantifiable Metric: Moving beyond a binary "secret" or "not secret", the concept of secrecy degree provides a nuanced measure of how much information an attacker can deduce, allowing for a more practical assessment of security.
  • Bisimulation for Secrecy: Using strong bisimulation as the equivalence relation for checking secrecy is a conservative choice. It ensures that even subtle differences in observable behavior (including resource usage) are detected, providing stronger guarantees than trace equivalence.
  • Compositionality of Secrecy: The authors conjecture that their secrecy properties are compositional, meaning the secrecy of a system can be inferred from the secrecy of its components. This is crucial for building and analyzing complex systems.

Key Results

The paper presents a formal framework and a method for automatically checking secrecy degrees. While specific quantitative results are demonstrated through an example, the primary result is the development of the methodology itself. The example illustrates how the framework can identify when a credit card number is kept secret (vsd=2:2) but choices are not (vsd=1:3), and how modifications can improve secrecy.

Limitations and Future Work

  • Undecidability: While the framework is designed for automatic checking, the underlying model of timed automata can lead to undecidability in certain cases, as noted in related work.
  • Finite Domains: The current framework is primarily designed for finite domains of values. Extending it to infinite domains would be a significant challenge.
  • Compositionality Proof: The paper conjectures that secrecy degrees are compositional but leaves a formal proof as future work.
  • Approximate Bisimulation: The authors suggest exploring approximate bisimulation to handle margins of error or to match multiple transitions in one system with multiple transitions in another, particularly for time-based costs.
  • User Interface: They are developing an Eclipse-based graphical user interface to make building automata models easier and plan to integrate their µCRL scripts for wider accessibility.

Summary updated

BibTeX
@article{chothia2007keeping,
  author = {Tom Chothia and Jun Pang and Muhammad Torabi Dashti},
  title = {{Keeping Secrets in Resource Aware Components}},
  journal = {QAPL},
  year = {2007},
  doi = {10.1016/j.entcs.2007.07.006},
}
Figure