Testing Security Equivalence in the Random Probing Model

Abstract

The random probing model is a theoretical model that abstracts the physical leakage of an embedded device running a cryptographic scheme with more realistic assumptions compared to the threshold probing model. It assumes that the wires of the target device leak their assigned values with probability p, and the said values may reveal information about secret data, which could lead to a security violation. From that, we can compute the probability ϵ that a side-channel adversary may learn secret data from any random combination of wires as a function of the number of wire combinations that breaches security with rate p. This model is used to evaluate the security of masked cryptographic implementations, or simply named circuits; and the research community has been focusing so far on approximating or estimating the probability ϵ for one circuit. Yet, no proposition has been made to quickly compare the probability ϵ of different circuits, e.g., a circuit and its optimized version. In this context, we present two statistical tests to make decisions about the level of security in the random probing model: the equivalence test compares the security of two circuits in terms of ϵ’s and the superiority test decides whether the undetermined ϵ of one circuit falls below a security threshold ϵ0, both with quantified uncertainty about the computations of the probabilities ϵ’s. The validity of these tests is proven mathematically sound and verified via empirical studies on small masked S-boxes.