F-BLEAU: Fast Black-box Leakage Estimation

Giovanni Cherubin, Konstantinos Chatzikokolakis, Catuscia Palamidessi

Abstract

We consider the problem of measuring how much a system reveals about its secret inputs under a black-box setting: we assume no prior knowledge of the system's internals, and we run the system for choices of secrets and measure its leakage from the respective outputs. Our goal is to estimate the Bayes risk, from which one can derive some of the most popular leakage measures (e.g., min-entropy, additive, and multiplicative leakage). The state-of-the-art method for estimating these leakage measures is the frequentist paradigm, which approximates the system's internals by looking at the frequencies of its inputs and outputs. Unfortunately, this does not scale for systems with large output spaces, where it would require too many input-output examples. In this paper, we exploit an analogy between Machine Learning (ML) and black-box leakage estimation to show that the Bayes risk of a system can be estimated by using a class of ML methods: the universally consistent learning rules. We focus on nearest neighbor rules; we show that they significantly reduce the number of black-box queries required for a precise estimation whenever nearby outputs tend to be produced by the same secret; furthermore, some of them can tackle systems with continuous outputs.

Introduction

In computer security, quantifying "information leakage" is essential for assessing how much a secret input (e.g., a cryptographic key or user location) can be inferred from a system's output (e.g., execution time or obfuscated coordinates). The gold standard for this measurement is the Bayes risk, representing the minimum error an ideal attacker would make. However, calculating this for "black-box" systems—where internal logic is unknown—is challenging. The traditional frequentist approach, which involves counting occurrences of specific input-output pairs, fails when the output space is large or continuous, as the required sample size becomes prohibitive.

Methodology: Machine Learning as an Estimator

The core innovation of F-BLEAU is the realization that any "universally consistent" learning rule is, by definition, an estimator of the Bayes risk. By shifting from pure statistics to Machine Learning (ML), specifically Nearest Neighbor (NN) and $k_n$-Nearest Neighbor ($k_n$-NN) rules, we can exploit the geometric structure of the output space.

Unlike frequentist methods that treat every output as a discrete category, NN rules utilize a distance metric. If two outputs are "close" in the metric space, they are likely produced by the same secret. This allows the estimator to generalize from seen to unseen outputs, drastically reducing the data required for a precise estimate. F-BLEAU evaluates multiple estimators and selects the one that converges fastest for a given system, acknowledging that no single algorithm is optimal for every possible dataset.

Convergence of error for different estimators in geometric systems with varying noise levels. The NN and $k_n$-NN methods converge to the Bayes risk significantly faster than the frequentist approach.

Experimental Results

F-BLEAU was evaluated against synthetic systems, location privacy datasets (Gowalla), and RFID side-channel data.

Synthetic Systems and Speedup

In systems with geometric noise, F-BLEAU demonstrated significant speedups. For a system with 10,000 possible outputs and a noise parameter $\nu=0.1$, the NN estimator converged with only 333 examples, whereas the frequentist approach required over 35,000. This highlights the efficiency gained by exploiting the metric structure of the output space.

Real-World Effectiveness

On the Gowalla location dataset, F-BLEAU successfully estimated leakage for the Planar Laplacian mechanism. This is a continuous domain where traditional frequentist tools are inapplicable. Furthermore, in timing side-channel analysis of e-Passport RFID chips, F-BLEAU detected significant leakage (~54% accuracy) with only 1,000 examples, a scenario where state-of-the-art tools like leakiEst reported "no evidence of leakage" due to sample size limitations.

Comparison of the number of observations required for convergence across various synthetic and real-world systems. Bold values indicate the most efficient estimator.

Conclusion

F-BLEAU provides a robust and efficient framework for black-box leakage estimation. By leveraging the generalization power of nearest neighbor rules, it overcomes the scalability limitations of frequentist methods, particularly in high-dimensional and continuous output spaces. While "spiky" distributions—where nearby outputs correspond to different secrets—remain a challenge, F-BLEAU's multi-estimator approach ensures that the most efficient tool is utilized for the specific security context.

Summary updated

Abstract

We consider the problem of measuring how much a system reveals about its secret inputs. We work under the black-box setting: we assume no prior knowledge of the system's internals, and we run the system for choices of secrets and measure its leakage from the respective outputs. Our goal is to estimate the Bayes risk, from which one can derive some of the most popular leakage measures (e.g., min-entropy, additive, and multiplicative leakage). The state-of-the-art method for estimating these leakage measures is the frequentist paradigm, which approximates the system's internals by looking at the frequencies of its inputs and outputs. Unfortunately, this does not scale for systems with large output spaces, where it would require too many input-output examples. Consequently, it also cannot be applied to systems with continuous outputs (e.g., time side channels, network traffic). In this paper, we exploit an analogy between Machine Learning (ML) and black-box leakage estimation to show that the Bayes risk of a system can be estimated by using a class of ML methods: the universally consistent learning rules; these rules can exploit patterns in the input-output examples to improve the estimates' convergence, while retaining formal optimality guarantees. We focus on a set of them, the nearest neighbor rules; we show that they significantly reduce the number of black-box queries required for a precise estimation whenever nearby outputs tend to be produced by the same secret; furthermore, some of them can tackle systems with continuous outputs. We illustrate the applicability of these techniques on both synthetic and real-world data, and we compare them with the state-of-the-art tool, leakiEst, which is based on the frequentist approach.
BibTeX
@inproceedings{cherubin2019f,
  author = {Giovanni Cherubin and Konstantinos Chatzikokolakis and Catuscia Palamidessi},
  title = {{F-BLEAU: Fast Black-box Leakage Estimation}},
  booktitle = {IEEE Symposium on Security and Privacy},
  year = {2019},
  doi = {10.1109/sp.2019.00073},
}

Loading related content...

Figure