Combined Private Circuits - Combined Security Refurbished

Combined Private Circuits - Combined Security Refurbished Jakob Feldtkeller Ruhr University Bochum Horst Görtz Institute for IT Security Bochum, Germany [email protected] Tim Güneysu Ruhr University Bochum Horst Görtz Institute for IT Security Bochum, Germany [email protected] Thorben Moos Université catholique de Louvain Crypto Group, ICTEAM Institute Louvain-la-Neuve, Belgium thorben.mo[email protected] Jan Richter-Brockmann Ruhr University Bochum Horst Görtz Institute for IT Security Bochum, Germany [email protected] Sayandeep Saha Université catholique de Louvain Crypto Group, ICTEAM Institute Louvain-la-Neuve, Belgium [email protected] Pascal Sasdrich Ruhr University Bochum Horst Görtz Institute for IT Security Bochum, Germany [email protected] François-Xavier Standaert Université catholique de Louvain Crypto Group, ICTEAM Institute Louvain-la-Neuve, Belgium [email protected] ABSTRACT Physical attacks are well-known threats to cryptographic implementations. While countermeasures against passive Side-Channel Analysis (SCA) and active Fault Injection Analysis (FIA) exist individually, protecting against their combination remains a significant challenge. A recent attempt at achieving joint security has been published at CCS 2022 under the name CINI-MINIS. The authors introduce relevant security notions and aim to construct arbitraryorder gadgets that remain trivially composable in the presence of a combined adversary. Yet, we show that all CINI-MINIS gadgets at any order are susceptible to a devastating attack with only a single fault and probe due to a lack of error correction modules in the compression. We explain the details of the attack, pinpoint the underlying problem in the constructions, propose an additional design principle, and provide new (fixed) provably secure and composable gadgets for arbitrary order. Luckily, the changes in the compression stage help us to save correction modules and registers elsewhere, making the resulting Combined Private Circuits (CPC) more secure and more efficient than the original ones. We also explain why the discovered flaws have been missed by the associated formal verification tool VERICA (TCHES 2022) and propose fixes to remove its blind spot. Finally, we explore alternative avenues to repair the compression stage without additional corrections based on non-completeness, i.e., constructing a compression that never recombines any secret. Yet, while this approach could have merit for low-order gadgets, it is, for now, hard to generalize and scales poorly to higher orders. We conclude that our refurbished arbitrary order CINI gadgets provide a solid foundation for further research. CCS ’23, November 26–30, 2023, Copenhagen, Denmark ©2023 Copyright held by the owner/author(s). This is the author’s version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security (CCS ’23), November 26–30, 2023, Copenhagen, Denmark, https://doi.org/10.1145/3576915.3623129. CCS CONCEPTS •Security and privacy → Side-channel analysis and countermeasures. KEYWORDS Side-Channel Analysis; Fault-Injection Analysis; Combined Attacks; Gadgets; CINI MINIS 1 INTRODUCTION Standard black-box assumptions about cryptographic primitives often fail to hold in practice as an adversary can extract information about the internal computations of a cryptographic device by observing or manipulating its physical characteristics. On the one hand, a passive adversary exploits the fact that physical effects, such as timing [ 26 ], power consumption [ 27 ], or electromagnetic (EM) radiation [ 20 ] of a device are correlated with the data being processed. On the other hand, an active adversary deliberately perturbs the operating conditions (e.g., by clock/voltage glitches [ 4 , 42 ], or EM/laser pulses [ 31 , 41 ]) of the device to create computational faults and extracts information through faulty system behavior [8, 9]. Over the years, several countermeasures have been proposed to counter such passive Side-Channel Analysis ( SCA ) and active Fault Injection Analysis ( FIA ). For SCA masking [ 13 ] was introduced, which provides quantifiable security guarantees. The main idea behind masking is to split each variable into multiple independent random shares (cf. Section 3.1.4) so that the adversary is bound to perform a higher-order/multivariate statistical analysis with an exponential data complexity in the number of shares to recover the actual intermediate values (under some assumption of noise and independence [ 16 , 17 ]). A well-researched strategy to circumvent FIA is to incorporate computational redundancy in space, time, or information [ 24 ] to detect/correct occurring faults (cf. Section 3.2.4). In addition to attacks and countermeasures, the research community developed theoretical models to argue about security formally. The formal models for SCA consider access to internal values without 1 CCS ’23, November 26–30, 2023, Copenhagen, Denmark Feldtkeller et al. or with noise [ 16 , 23 , 32 ]. Likewise, FIA is modeled by allowing restricted capabilities of circuit manipulation [22, 35]. Countermeasures Against Combined Attacks. While both SCA and FIA are well-explored in isolation, both theoretically and practically, the security against an attacker able to mount both SCA and FIA¸ simultaneously is a new field of research. Indeed, only recently it has been shown that such Combined Analysis ( CA ) is feasible in practice, even with low-end injection and measurement setups [ 2 , 14 , 36 , 37 , 39 , 40 ]. In addition, the pure combination of countermeasures against SCA and FIA is not sufficient to protect against CA , neither in theoretic models [ 15 , 34 ] nor in practical implementations [ 36 , 37 , 40 ]. Therefore, there is a need for countermeasures in the context of CA with provable and formally verifiable security claims. Related Work: Only a few works have addressed the problem of constructing combined countermeasures. Initial efforts in this regard were based on the principles of Multi-Party Computation ( MPC ) [ 29 , 33 ]. However, proving security in such MPC -based schemes is highly complex. Recently the SCA research community has focused on designing small, secure gadgets, i.e., small subcircuits dedicated to some specific functionality, for which security can be proven even when combined to larger circuits (composition) [ 6 ]. In a nutshell, such composability notions restrict the propagation of leakage between different gadgets with isolation and re-randomization. The earliest notions in this regard are NonInterference ( NI ) [ 5 ] and Strong Non-Interference ( SNI ) [ 6 ]. Later, Probe-Isolating Non-Interference ( PINI ) [ 12 ] has been proposed as an elegant way to achieve composition by isolating so-called share-domains (cf. Section 3.1.5). Overall, gadget-based, composable constructions are a convenient way to build secure implementations against physical attacks. Similar to NI and SNI , composability notions have also been proposed for FIA and CA [ 15 , 19 , 34 ]. For CA , the notions for composition come in two flavors: (i) the SCA -based security order (i.e., the number of observations an adversary can make) is dependent on the number of injected faults, (ii) the security guarantees in SCA and FIA are independent of each other. The most recent work in this regard is Combined-Isolating Non-Interference ( CINI ) [ 19 ], where the concept of share-domain isolation in PINI was extended to the context of CA . More precisely, the concept of Shared Redundancy Domains ( SRD s), i.e., the intersection of shares and redundancies, is introduced. Then the leakage of probes is isolated within share domains, while the leakage from faults is isolated within SRD s (cf. Section 3.3.4). The authors also adapted a verification tool for CA , called VERICA [ 34 ], to support this composability notion for the automatic verification of small gadgets. Finally, the authors proposed several gadget constructions (CINI-MINIS), which, to the best of our knowledge, are the only existing gadgets based on Boolean masking and redundancy for hardware in the context of CA which until now have not been shown insecure. In this work, we demonstrate that these constructions need refinement, too, since they are missing a crucial design principle. Contributions: In this work, we first extend the well-established concepts of probe and fault propagation to a propagation framework in a combined setting (Section 3.3.3). Building on that, we show that the gadgets proposed by Feldtkeller et al. [ 19 ] are vulnerable to a simple yet effective combined attack when composed (Section 4). More precisely, an adversary can observe secret-dependent fault propagation, breaking the security with only a single probe and fault. Even worse, this attack was not detected by VERICA when verifying for CINI . This fact highlights the complexity of designing for CA . To tackle this complexity, design guidelines and principles are an essential building block. Given our attack, we pinpoint the exact vulnerability and extend the design principles for constructing CINI gadgets, eventually contributing to the general understanding of CA -secure constructions. The introduced principle guides the construction of two types of new provably secure CINI gadgets (called Combined Private Circuit ( CPC )) and a fix to VERICA (Section 5). The first gadget adds additional correction modules between the computation of partial products and the compression, however, it enables us to save some corrections and registers at other locations (Section 6). In total, this results in a net benefit in terms of area while fixing the security. In addition, we explore gadgets based on the non-completeness property from Threshold Implementations ( TI s) [ 30 ] (Section 7). While this approach could have merit for low-order gadgets, it is, for now, hard to generalize and scales poorly to higher orders. For all our gadgets, we evaluate the performance and provide a tool-based verification (Section 8). 2 BACKGROUND In this section, we provide important notations, describe our circuit model, and discuss proof techniques based on simulation. 2.1 Notation In general, we use upper-case calligraphic font for sets (e.g., S ) and sans serif font for functions (e.g., f). Further, we use superscript to denote the replication index and subscript for the share index of a value. Throughout the paper, the term faulty value is used as shorthand for a fault that was injected in the gate that produces the corresponding value. 2.2 Circuit Model Without loss of generality, we restrict the set of combinatorial gates to Gc={inv,and,xor} and the set of memory gates to clocked registers Gm={reg} . For randomized behavior, we use a randomnessgenerating gate Gr={rand} , that outputs an independent and uniformly chosen value from F2per clock cycle. Then, we model a digital-logic circuit Cas a directed acyclic graph D={V,E} , where vertices 𝑣∈ V represent logical gates 𝑔∈ Gc∪ Gm∪ Gr and edges 𝑒∈ E represent wires carrying an element of the finite field F2. 2.3 Security via Simulation Simulation is a technique often used for security proofs [ 10 , 28 ]. It defines two games, a real and an ideal game. The ideal game is trivially secure (under some adversary model), while the real game is secure iff there exists no adversary who can distinguish between the ideal and the real game with a probability higher than 1 / 2. The ideal game is constructed as a probabilistic polynomial-time simulator reproducing the view of the adversary without knowledge 2 Combined Private Circuits - Combined Security Refurbished CCS ’23, November 26–30, 2023, Copenhagen, Denmark (a) (b) (c) (d) (e) Figure 1. Rules for probe propagation. of any secret. This simulator treats each input-dependent value as deterministic. 3 PROBING & FAULTING 3.1 Side-Channel Analysis 3.1.1 Adversary Model. In the stateless 𝑑 -probing model [ 23 ], the adversary A𝑝 is given access to a circuit Cthat can be invoked multiple times. Before each invocation, A𝑝 can select up to 𝑑 wires of Cto be probed. Then, while executing, the circuit leaks the glitch-extended probes [ 18 ] to A𝑝 , i.e., all values stored in registers the probed values directly depend on 1 . In this work, we directly consider the glitch-extended instead of the standard probing model to focus on hardware implementations primarily. 3.1.2 Probing Security. In this context, a circuit Cis probing-secure iff the view of A𝑝 can be simulated without access to any secret [ 23 ]. 3.1.3 Probe Propagation. The information a probing adversary A𝑝 can learn from a set of probes is dependent on the structure of the circuit leading up to the probes. The leaked information captured by a set of probes can be determined via the concept of probe propagation [ 7 ]. Here, a probe propagates from wire 𝑤1 to wire 𝑤0 iff the value of wire 𝑤0 is required for the simulation of 𝑤1 . We provide the most important propagation rules in Figure 1, where probes always propagate from right to left. In particular, probes propagate backwards through the circuit (cf. Figure 1a and 1b) until they are stopped by the addition of unique randomness (cf. Figure 1c). Here, uniqueness means that the random value is not observed by any other propagating probe or at least only while masking the same intermediate value (cf. Figure 1d and 1e). We emphasize that a placed probe is first glitch-extended to the associated registers before a probe propagates backward through the circuit, starting from the respective registers. While probe propagation and glitch extension of a probe have some similarities, they still have fundamentally different properties. Probe propagation is stopped only by refreshing an intermediate value and is not stopped by registers. In contrast, glitch extension is stopped by registers but not by refreshing. 3.1.4 Masking. A well-understood countermeasure against SCA is Boolean masking [ 13 ]. Here, each value 𝑥∈F2 is replaced by a vector ⟨𝑥0, . . . 𝑥𝑠−1⟩ ∈ F𝑠 2 , where each 𝑥𝑖∈F2 is uniformly random, 𝑥=É𝑠−1 𝑖=0𝑥𝑖 , and each subset ˆ X={𝑥𝑖|𝑖∈ [𝑠− 1 ]} with |ˆ X| <𝑠 1 Glitches are short-term evaluation defects that occur due to timing differences in the propagation path of signals. Providing A𝑝 with all stable inputs is a worst-case assumption on the leakage via glitches [18]. is independent of 𝑥 . A component 𝑥𝑖 is called a share with share index 𝑖 . To securely process masked values, the computation circuit is transformed to a shared circuit, where each logical operation consists of a set of gates manipulating the shared values. In such a shared circuit, the initial sharing and final unsharing operation are not part of the shared circuit and cannot be probed by A𝑝[3, 23]. Definition 3.1 (Share Domain). The share domain 𝑖 of a shared circuit is defined by all wires with share index 𝑖. 3.1.5 Probe-Isolating Non-Interference. While being the fundamental goal, probing-secure circuits are not always composable, i.e., the combination of two probing-secure circuits is not necessarily probing secure again. To ease the construction of probing-secure circuits, different notions of composition were introduced, which define how to construct atomic building blocks, so-called gadgets, that can be securely composed into larger structures. PINI [ 12 ] requires the isolation of probe propagation within share domains (cf. Definition 3.1), i.e., a probe is only allowed to propagate within a single share domain. This ensures that the combination of multiple PINI gadgets is always PINI again. Definition 3.2 (Probe-Isolating Non-Interference [ 12 ]). A gadget Gis 𝑑 - PINI iff for any set of 𝑑1 internal probes and any set S2 of 𝑑2share domains, such that 𝑑1+𝑑2≤𝑑, there exists a set S1of at most 𝑑1 share domains such that the outputs of the share domains in S2 and the probes can be simulated with the inputs of the share domains in S1∪ S2. 3.2 Fault-Injection Analysis 3.2.1 Adversary Model. A faulting adversary A𝑓 is given access to a circuit Cthat can be invoked multiple times [ 22 , 34 ]. Before each invocation, A𝑓 can select up to 𝑘 gates of Cto be faulted and for each such gate a fault type from a set of allowed fault types T . Then, before invocation, the faulted gates are replaced by a different gate type specified by the fault type 𝑡∈ T [ 35 ]. Commonly used fault types are set,reset (replacing the targeted gate with a constant one or zero, respectively), or bit flips (inversion of the gate). After execution of the circuit, the correctness is leaked to A𝑓 , i.e., whether the output is equal to the output of the golden circuit, which is the fault-free version of C. Please note, we do not consider fault-detection mechanisms in this work, due to the difficulty to implement them in hardware [34]. 3.2.2 Fault Security. In this context, a circuit Cis fault-secure iff all faults can be corrected at the output [ 34 ]. That is, there exists a correction circuit G 𝐶 , such that the concatenation G 𝐶( C (·)) always yields an output equal to the golden circuit. 3.2.3 Fault Propagation. Similar to probe propagation, fault propagation is a well-known concept in the literature [ 1 , 38 ]. A fault propagates from wire 𝑤0 to 𝑤1 iff a faulty value at 𝑤0 causes a faulty value at 𝑤1 , i.e., if a difference between Cand the golden circuit in 𝑤0 causes a difference between Cand the golden circuit in 𝑤1 . As such, faults propagate always towards the outputs of a circuit. Again, we provide the most important rules in Figure 2, where faults always propagate from left to right. A fault occurs in an output wire 𝑤𝑔 of a gate 𝑔 if the fault injected in 𝑔 causes an effective fault at 𝑤𝑔 (cf. Figure 2a), i.e., the value carried by 𝑤𝑔 3 CCS ’23, November 26–30, 2023, Copenhagen, Denmark Feldtkeller et al. (a) (b) (c) (d) (e) (f) Figure 2. Rules for fault propagation. in the faulted circuit differs from the value in the golden circuit. Hence, observing this fault provides information about the correct value of 𝑤𝑔 . Similarly, a single fault propagates through a multiplication (we talk about addition and multiplication in F2 from here on) only if the other operand 𝑎 is equal to 1(cf. Figure 2c). Again, the observation of such a fault propagation leaks some information about 𝑎 . In contrast, a single fault always propagates through an addition (cf. Figure 2b). When both input operands are faulty then the fault propagates through a multiplication only if both operands are equal and does not propagate through an addition (cf. Figure 2d and 2e). A majority vote always stops the propagation of a certain maximum number of incoming faults (cf. Figure 2f). 3.2.4 Redundancy. Protecting against fault attacks always requires some form of redundancy, either in time, space, or information. The most basic form of redundancy is replication, where all data and computation are instantiated multiple times in parallel. Then, correction of corrupted data is possible with 2𝑘+1 replications via a majority vote maj . The initial replication and the final error correction are not part of the replicated circuit and cannot be faulted by A𝑓 [ 34 ]. For correctness, all replications must use the same random values whenever a randomness gate is used in C. Definition 3.3 (Redundancy Domain). The redundancy domain ℓ of a redundant circuit is defined by all gates and wires with replication index ℓ. 3.2.5 Fault-Isolating Non-Interference. The combination of two fault-secure circuits is in general not fault-secure. Hence, additional notions of composition were introduced for construction and analysis. Similar to PINI , Fault-Isolating Non-Interference ( FINI ) [ 19 ] requires the isolation of fault propagation within redundancy domains (cf. Definition 3.3). This is a natural expression of the security guarantees given by replication codes and ensures that any combination of FINI gadgets is FINI again. Definition 3.4 (Fault-Isolating Non-Interference [ 19 ]). A gadget G is 𝑘-FINI iff the following holds: (i) For any set F1 of 𝑘1 faulty redundancy domains and every set of 𝑘2 faults injected in gates of G, with 𝑘1+𝑘2≤𝑘 , there exists a set of at most 𝑘2 redundancy domains F2 , such that the gadget gives an output where all values, except those belonging to the redundancy domains F1∪ F2 , are equal to the values of the golden circuit. (ii) There exists a decoding gadget GD , such that given an input with at most 𝑘 faulty redundancy domains, GD outputs a correct result. (a) (b) (c) (d) (e) (f) Figure 3. Rules for combined propagation. 3.3 Combined Analysis 3.3.1 Adversary Model. An adversary A𝑐 with both faulting and probing capabilities is a trivial combination of A𝑝 and A𝑓 [ 15 , 34 ], i.e., A𝑐 features both capabilities (selecting 𝑑 wires for probing and selecting 𝑘 gates with fault types for faulting) and both leakages (glitch-extended probes and correctness of the output). However, for CA the definition of the golden circuit is slightly modified. In particular, all faults in randomness gates 𝑔𝑟∈ Gr are also injected into the golden circuit [ 34 ]. Please note, faults change the distribution of affected intermediate values and in turn affect the observation made by the placed probes (cf. Section 3.3.3). 3.3.2 Combined Security. In this context, a circuit Cis combinedsecure iff the view of A𝑐 can be simulated without access to any secret (privacy) and there exists a correction circuit G 𝐶 , such that the concatenation G 𝐶( C (·)) always yields an output equal to the golden circuit (correctness) [ 34 ]. Following probing and fault security, A𝑐 is not allowed to probe or fault the initial sharing and replication, nor the final unsharing and correction. 3.3.3 Combined Propagation. The concepts of probe and fault propagation can be combined to analyze the leakage of information in a combined attack setting. We provide the most important rules in Figure 3. In general, a fault can impact a set of probes in four different ways. Two are beneficial to A𝑐 , one is to the disadvantage of A𝑐, and one has no impact. Entropy Removal. Since probing security is primarily achieved through randomization the removal of entropy via faults can enhance the propagation of probes. For example, manipulating a random value with a biased fault gives A𝑐 the control over the used randomness and, hence, is equivalent to a known random value (cf. Figure 3a) [ 34 ]. However, this is only true for biased faults, while non-biased faults provide the adversary with no advantage at all (cf. Figure 3b) [34]. Conditioned Fault Propagation. Whenever a fault propagation is conditioned on some internal value 𝑎 and A𝑐 can distinguish 4 Combined Private Circuits - Combined Security Refurbished CCS ’23, November 26–30, 2023, Copenhagen, Denmark (a) (b) Figure 4. Combined propagation examples where 𝑎0=𝑎1 and 𝑏0=𝑏1 . between a faulty and a non-faulty wire (i.e., whether the fault propagates or does not propagate) the condition on 𝑎 is leaked to A𝑐 . This can happen due to a biased fault injected into a gate since the fault sets the output to a known value that is either correct or not (cf. Figure 3c). Or it happens when a non-reset fault propagates through a multiplication since the fault only propagates if the other input is set to one (cf. Figure 3d). While propagating through the circuit a fault can accumulate different propagation conditions and thereby indirectly recombine multiple shares of a secret. Intuitively, such a fault serves as an additional probe on the conditioned value. However, without probe propagation and, therefore, no protection via refreshing. It is important to note that such a fault alone is not sufficient for leakage. Instead, a probe is required that captures the existence of fault propagation, e.g., by observing a correct and faulty redundant value. Information Removal. A biased fault completely determines the output distribution of an affected gate. Hence, the output is determined only by the known fault and not by the input to the gate. This essentially disconnects the input and output of the faulted gate and thereby stops the propagation of an incoming probe (cf. Figure 3c). A similar effect is achieved when a reset fault propagates through a multiplication since again the output of the gate is fully determined by the faulty input and always set to zero (cf. Figure 3e). No Impact. A propagating fault has no impact on probe propagation for gates with deterministic inputs (cf. Figure 3f and 3d), as long as the fault does not remove information (see above). In such a case, the fault and probe propagation passes one another. The four types of fault impacts are by no means exclusive and a single fault can cause both effects at different locations of the circuit. As probes are passive, probe propagation has no impact on faults. Example. For clarification of the concept of combined propagation, let us consider the example in Figure 4a. From a pure probing security perspective, this circuit does not reveal any information about the inputs, since 𝑎0=𝑎1 and 𝑏0=𝑏1 which means 𝑟 is observed two times refreshing the same value (cf. Figure 1e). A bit-flip fault in 𝑏0 will cause an effective fault at the output of 𝑎0𝑏0+𝑟 iff 𝑎0= 1. Observing only this value also reveals no information about the inputs, as A𝑐 cannot distinguish between an effective and an ineffective fault. However, observing both outputs in Figure 4a allows A𝑐 to identify effective faults (if both values are different). Hence, the condition of the probe propagation, i.e., 𝑎0= 1, is leaked to the adversary, which means the input 𝑎0 is required for the simulation of the probes (if 𝑎0= 0both probes are random but equal; if 𝑎0= 1 both probes are random but different). When injecting a set fault in 𝑏0 instead, both 𝑎0 and 𝑏0 are required for simulation (cf. Figure 4b). The reason is that now the effectiveness of the fault in 𝑏0 is dependent on the value of 𝑏0 in the first place. The fault is only effective if 𝑏0= 0. Again, the fault propagates to the probe only if 𝑎0= 0and A𝑐 can observe the effectiveness of the fault by comparing both outputs. Definition 3.5 (Shared Redundancy Domain). The SRD (𝑖, ℓ) of replicated and shared circuits is defined by all gates and wires with share index 𝑖and replication index ℓ. 3.3.4 Combined-Isolating Non-Interference. Again, the combination of two combined-secure circuits is not always combined-secure and additional notions for composition were introduced. CINI [ 19 ] is a combination of PINI and FINI in that it isolates probe propagation and glitch extension within share domains and fault propagation within SRD s (cf. Definition 3.5). An SRD is the intersection of a share domain with a redundancy domain and it is required to restrict a fault to a single SRD to avoid the cross-share-domain leakage via faults [ 19 ]. In its simple form, CINI requires the order of probing security to be always at least the sum of the injected faults and probes, i.e., the number of injected faults reduces the number of remaining probes. The reason is the probe-like nature of faults when conditioned on internal values. We provide a formal definition of CINI in Definition 3.6. With Independent Combined-Isolating Non-Interference ( CINIind ) [ 19 ] there exists also a variant where the number of probes is always only restricted by the order of probing security and independent of the injected faults, which potentially allows more efficient implementations for a certain security order. Both variants are trivially composable, i.e., any combination of CINI ( CINIind ) gadgets is CINI ( CINIind ) again. In this work, we focus on CINI and discuss the relation to CINIind only briefly. Definition 3.6 (Combined-Isolating Non-Interference [ 19 ]). A gadget Gis (𝑑, 𝑘) - CINI iff for any set F1 of 𝑘1 faulty SRD s, every set of 𝑘2 faults injected in gates of G, any set of 𝑑1 probes placed on intermediate values, and any set S2 of 𝑑2 share domains, such that 𝑘1+𝑘2≤𝑘 and 𝑑1+𝑑2+𝑘1+𝑘2≤𝑑 , there exists a set F2 of at most 𝑘2SRD s and a set S1 of at most 𝑑1+𝑘2 share domains such that the following holds: Correctness: The gadget gives an output where all values, except those belonging to the SRD s F1∪F2 , are equal to the golden circuit, and there exists a decoding gadget GD , such that given an input with at most 𝑘 faulty SRDs, GDoutputs a correct result. Privacy: The outputs of the share domains in S2 , the outputs violating the independence property of Boolean sharing, and the probes can be simulated with the 5 CCS ’23, November 26–30, 2023, Copenhagen, Denmark Feldtkeller et al. Figure 5. Conditioned fault propagation exploited by our attack. inputs of the share domains in S1∪ S2 and knowledge of the faults both injected and on inputs in F1. 4 ATTACKING THE COMBINED GADGET In this section, we present a combined attack on the CINI and CINIind gadgets proposed by Feldtkeller et al. [ 19 ]. All three of those gadgets follow the same design principle: computing everything in multiple redundancy domains and performing error correction (using all redundancy domains), and mask refreshing whenever an intermediate value crosses SRD boundaries. This principle should ensure that probe propagation is isolated within share domains and fault propagation within SRDs. In the following, we describe a combined attack on those gadgets, based on the properties of combined propagation (cf. Section 3.3.3), without violating the basic security conditions described by [ 19 ]. The attack requires a single probe and a single fault in a simple composition of gadgets, exploiting a secret-dependent fault propagation observed by the probe. Attack Outline. The core principle of our attack is shown in Figure 5. The general structure of the presented gadgets follows the structure of the attacked gadgets, even if it only has two shares and two replications (the computation of 𝑐1 is omitted for brevity). The attack places a fault on 𝑎0 0 which, due to the structure of the gadget, propagates to the output 𝑐0 0 conditioned on 𝑣0 0 and 𝑣0 1 . In particular, the fault only propagates to the output if 𝑣0 0≠𝑣0 1 which is equivalent to 𝑏= 1. By observing both 𝑐0 0 and 𝑐1 0 the adversary can distinguish between effective and ineffective faults in 𝑐0 0 and hence, the secret 𝑏is leaked to A𝑐. In the following, we discuss the details when attacking realsized gadgets. For this, our explanation focuses on HPCC 1 . However, the attack is also applicable to the remaining gadgets. In particular, attacking HPCI 1 is possible without any changes while for the attack against HPCC 2the probe placement has to be adjusted. Algorithm 1: HPCC 1:CINI multiplication. 1function HPCC 1(𝑎0 0, . . . , 𝑎𝑛 𝑑,𝑏0 0, . . . , 𝑏𝑛 𝑑): Require: 𝑛=2𝑘+1 Require: 𝑎ℓ 𝑖=𝑎ℓ′ 𝑖and 𝑏ℓ 𝑖=𝑏ℓ′ 𝑖for 0≤ℓ, ℓ′≤𝑛, 0≤𝑖<𝑑 Require: Í𝑑 𝑗=0𝑎ℓ 𝑗=𝑎and Í𝑑 𝑗=0𝑏ℓ 𝑗=𝑏for 0≤ℓ<𝑛 // Initialize randomness 2for 𝑖=0to 𝑑do 3for 𝑗=𝑖+1to 𝑑do 4˜ 𝑟𝑖,𝑗 $ ←F2;˜ 𝑟𝑗,𝑖 ←˜ 𝑟𝑖,𝑗 5𝑟𝑖,𝑗 $ ←F2;𝑟𝑗,𝑖 ←𝑟𝑖,𝑗 // Refreshing 6for ℓ=0to 𝑛−1do 7for 𝑗=0to 𝑑do 8˜ 𝑣ℓ 𝑗←𝑏ℓ 𝑗+Í𝑑 𝑖=0,𝑖≠𝑗˜ 𝑟𝑖,𝑗 // Correction 9for ℓ=0to 𝑛−1do 10 for 𝑖=0to 𝑑do 11 for 𝑗=0to 𝑑do 12 𝑣ℓ 𝑖,𝑗 ←maj(˜ 𝑣0 𝑖. . . ˜ 𝑣𝑛−1 𝑖) // Multiplication 13 for ℓ=0to 𝑛−1do 14 for 𝑖=0to 𝑑do 15 𝑤ℓ 𝑖←𝑎ℓ 𝑖·reg[𝑣ℓ 𝑖,𝑖 ] 16 for 𝑗=0to 𝑑, 𝑗 ≠𝑖do 17 𝑧ℓ 𝑖,𝑗 ←𝑎ℓ 𝑖·reg[𝑣ℓ 𝑗,𝑖 ]+𝑟𝑖,𝑗 18 𝑐ℓ 𝑖←reg[𝑤ℓ 𝑖] + Í𝑑 𝑗=0;𝑗≠𝑖reg[𝑧ℓ 𝑖,𝑗 ] Ensures: 𝑐ℓ 𝑖=𝑐ℓ′ 𝑖for 0≤ℓ, ℓ′≤𝑛, 0≤𝑖≤𝑑 Ensures: Í𝑑 𝑖=0𝑐ℓ 𝑖=𝑎·𝑏for 0≤ℓ≤𝑛 19 return 𝑐0 0, . . . ,𝑐𝑛 𝑑 4.1 Attack on HPCC 1 Let us consider the HPCC 1 gadget described in Algorithm 1. The gadget is supposed to provide security against k-bit faults and d-probing adversary even under composition. For our attack, we inject a 1-bit fault at one of the input shares of 𝑎 . Assume that 𝑎ℓ 𝑖 has been corrupted which belongs to the SRD (𝑖, ℓ) . The fault propagates through the gadget and, following CINI, corrupts only the output belonging to SRD (𝑖, ℓ) . However, the propagation is conditioned on the secret 𝑏. The reason is that the fault-propagation path consists of addition ( xor ) and multiplication ( and ) gates and, hence, the fault propagation follows the principles illustrated in 2b and Figure 2c. Therefore, the fault propagation is unaffected by additions and conditioned when passing through a multiplication, leaking the propagation condition when A𝑐 can distinguish between an effective/ineffective fault. We have highlighted the fault-propagation path in Algorithm 1 (initial fault in red, conditioned variables in blue, and fault propagation in green). Due to the multiplication, the fault propagation to 𝑤ℓ 𝑖 , 𝑧ℓ 𝑖,𝑗 , and 𝑐ℓ 𝑖 is conditional on the corresponding 𝑣ℓ 𝑖,𝑗 . The algebraic expression at 6 Combined Private Circuits - Combined Security Refurbished CCS ’23, November 26–30, 2023, Copenhagen, Denmark the output with a fault in 𝑎ℓ 𝑖 (noted as ˆ 𝑎ℓ 𝑖 ) can be reduced as follows: 𝑐ℓ 𝑖←ˆ 𝑎ℓ 𝑖· (𝑏ℓ 𝑖+ 𝑑 ∑︁ ℎ=0,ℎ≠𝑖 ˜ 𝑟ℎ,𝑖) + 𝑑 ∑︁ 𝑗=0;𝑗≠𝑖 (ˆ 𝑎ℓ 𝑖· (𝑏ℓ 𝑗+ 𝑑 ∑︁ ℎ=0,ℎ≠𝑗 ˜ 𝑟ℎ,𝑗 ) + 𝑟𝑖,𝑗 ) ←ˆ 𝑎ℓ 𝑖· (𝑏ℓ 𝑖+ 𝑑 ∑︁ ℎ=0,ℎ≠𝑖 ˜ 𝑟ℎ,𝑖 + 𝑑 ∑︁ 𝑗=0;𝑗≠𝑖 (𝑏ℓ 𝑗+ 𝑑 ∑︁ ℎ=0,ℎ≠𝑗 ˜ 𝑟ℎ,𝑗 )) + 𝑑 ∑︁ 𝑗=0;𝑗≠𝑖 𝑟𝑖,𝑗 ←ˆ 𝑎ℓ 𝑖· (𝑏ℓ 𝑖+ 𝑑 ∑︁ 𝑗=0;𝑗≠𝑖 (𝑏ℓ 𝑗+˜ 𝑟𝑗,𝑖 + 𝑑 ∑︁ ℎ=0,ℎ≠𝑗 ˜ 𝑟ℎ,𝑗 )) + 𝑑 ∑︁ 𝑗=0;𝑗≠𝑖 𝑟𝑖,𝑗 ←ˆ 𝑎ℓ 𝑖·𝑏+ 𝑑 ∑︁ 𝑗=0;𝑗≠𝑖 𝑟𝑖,𝑗 (1) Note, that registers have no impact on fault propagation and are, therefore, omitted in the expression above. Due to the fact that all (refreshed) shares of 𝑏 are combined in a single 𝑐ℓ 𝑖 , the refreshing of 𝑏 is completely removed at this point. Under normal execution, this is not problematic, since the refreshing of the partial products remains untouched. However, the rearrangement of the terms shows that the fault propagation is conditioned on the secret 𝑏 . Still, observing 𝑐ℓ 𝑖 only does not directly leak the condition, since A𝑐 cannot distinguish between effective and ineffective faults, i.e., whether the fault indeed propagates to the output or not. To get the additional leakage, A𝑐 needs to observe the (potentially) faulty 𝑐ℓ 𝑖 and a (definitely) correct 𝑐ℓ′ 𝑖 from another replication domain. This can be achieved when gadgets are composed. Imagine a composition of two HPCC 1 gadgets, such that the output of the first gadget is the input 𝑏 of the second gadget (cf. Figure 7). Now, we place a probe at ˜ 𝑣ℓ 𝑖 of the second gadget, which, due to glitch extension, expands to all replication domains of the input. These are all the replication domains of the output share domain 𝑖 of the first gadget and 𝑐ℓ 𝑖 and 𝑐ℓ′ 𝑖 are in the extended probes. Hence, with this probe, A𝑐 can distinguish effective and ineffective faults in the above attack scenario. This leaks the secret 𝑏 to A𝑐 , violating the privacy of CINI . This attack always requires one probe and one fault regardless of the number of shares and duplications used in the gadget. Attack in the Standard Model. The above attack is also possible in the standard probing model, i.e., a probe leaks only the value carried by the probed wire. The reason is a dependency in the correction logic as depicted in Figure 6. We note that [ 37 ] also mentions a similar kind of leakage for DOM and TI gates, and DOM-based S-Boxes. In particular, without any input fault to the correction, the internal values of the correction are randomly distributed (since the inputs are randomly distributed). However, if there is a faulty input, some internal wires are always zero. Hence, again the secretdependent fault propagation is needed to simulate the respective probe. Impact of the Fault Model. The presented attack depends on the structural features of the circuit and works for all common fault models, i.e., set/reset and biased/unbiased bit-flips. Combined security is a notion of perfect security, in the sense that already a small bias towards the adversary is considered insecure. While the fault model impacts the condition of fault propagation (e.g., a set fault adds a condition dependent on the faulted value), it (a) (b) Figure 6. Illustration of leakage from single-bit error correction logic. If the codewords are correct, the outputs of the AND gates toggle with probability 0.5. If there is an error in the codeword, the probed wire gets stuck to zero. Figure 7. Composition of two HPCC 1 gadgets. The fault is injected at the input of the left gadget and the leakage is measured from the error correction logic of the right gadget. does not change the fact that the attack is possible for some value combinations. This already is a violation of combined security even if this may only marginally impact the success probability of a practical attack. Impact of the Attack. Multiple recent works have addressed faultpropagation based leakage [ 37 , 40 ]. While the fundamental cause of those attacks is the same as in the presented attack, none of them considers CA -secure gadgets, but target specific S-Box constructions. From that perspective, attacking gadgets is more generic, impacting all designs derived by compositions. Several techniques can be utilized to make the leakage exploitable. One option is to use a template attack as shown in [ 37 , 38 ]. In a recent work [ 40 ], it has been shown that such leakages can be exploited even in a non-profiled setting with multi-bit imprecise and random faults. The attacks in [ 40 ] exploit the bit-slice structure of GIMLI permutation to enable multi-bit fault attacks. Given that bit slicing is also very common in gadget-based constructions (for software) [ 21 ], it is expected that such attacks would also apply in such a context. 7 CCS ’23, November 26–30, 2023, Copenhagen, Denmark Feldtkeller et al. (a) (b) Figure 8. Probe propagation in the case of PINI and CINI. 5 DISCUSSION OF THE ATTACK In the following, we discuss the core flaw of the CINI proof provided by Feldtkeller et al. [ 19 ] and give a high-level intuition about the possible fixes. 5.1 The Concept of Probed Share Domains The concepts of PINI and CINI distinguish between probes placed internally to a gadget and probes placed outside of it. Specifically, probes within a gadget are considered as normal probes placed on individual wires. Those probes reveal the (glitch-extended) values of the probed wires to the adversary. In contrast, external probes are placed at share domains, leaking all values belonging to the probed share domain. This separation allows the trivial composition of PINI / CINI gadgets, as long as each gadget ensures the isolation of share domains to probe propagation. This is proven by the respective theorems for composition [ 12 , 19 ]. Hence, the underlying concept is free probe propagation within share domains, but a strict isolation between them. When combining individual gadgets, the separation of internal and external probes is essential to prove the isolation of share domains. In particular, a single external probe, probing an output share domain, can result in the requirement to simulate multiple output wires. Failing to do so, may lead to a gadget that is probing secure in itself, however, insecure under composition, i.e., the gadget is not PINI/CINI. For PINI , the scenario that more wires need to be simulated than there are placed probes only occurs for multiple-output gadgets (otherwise there is only one output wire per share domain). In Figure 8a we show an exemplary gadget composition, where a single probe propagates to multiple outputs of a multiple-output gadget. This clearly shows that to be first-order secure, the two outputs belonging to share domain 1need to be simulated at once. For CINI already a single-output gadget requires the simulation of more wires than placed probes since the replication of a wire explicitly belongs to the same share domain (cf. Definition 3.1). Intuitively this makes sense since a (non-faulted) replication of a wire contains the same information. Again, we give an exemplary gadget composition in Figure 8b. Indeed, a probe at the output of any (not otherwise protected) correction circuit contains all replications of the corrected value, by glitch extension and probe propagation. Our attack in Section 4 exploits exactly this. 5.2 Fixing VERICA With the introduction of the CINI notion [ 19 ], the authors also provided an extension to the formal verification framework VERICA [ 34 ] and analyzed several instantiations of corresponding multiplication gadgets. However, the above-introduced flaws have not been detected by VERICA since external probes have not been extended to all wires with the same share domain, i.e., to all replications. In the following, we briefly describe the structure of VERICA and present our fixes leading to correct verifications of the CINI and CINIind security notions. VERICA is partitioned into different passes starting with a parsing phase that is responsible to read the used cell library and the netlist under test implementing the target design. Afterwards, a preprocessing phase is executed preparing the circuit model for the verification process. This also includes a strategy that prepares the tool for SCA verifications determining among other things all valid probe positions and creating all valid probe combinations of up to 𝑑 probes. However, all probe positions are treated in the same fashion to compute the probe combinations and no particular rules for external probes are applied. Hence, if an external probe has been added to the set of a valid probe combination, all outputs with the same share domain have not been considered in this particular set. To this end, we extended the corresponding function in VERICA by checking if a probe combination contains an external probe and adding all outputs with the same share domain as virtual probes to this set (cf. Section 5.1). This distinction is necessary due to the underlying structure and functional principle of VERICA. In the verification process, the number of original probes is used to compute a threshold determining the maximum number of input shares that can be used for simulation. However, the original probes plus the virtual probes are considered to compute all possible combinations to check statistical independence to the corresponding input shares as introduced by Knichel et al. [ 25 ] together with the verification framework SILVER. With these changes VERICA can detect the flaw in the gadgets from Feldtkeller et al. [ 19 ] (cf. Table 2). We integrated our fix into VERICA2. 5.3 The Missing Design Principle The construction of the gadgets proposed by Feldtkeller et al. [ 19 ] are based on a simple design principle: Every intermediate value that crosses an SRD border needs to be refreshed (to stop probe propagation) and corrected (to stop fault propagation). While necessary, our attack shows that this design principle is not sufficient. In particular, the principle does not prevent the recombination of secrets due to conditional fault propagation (which is not stopped by refreshing). In HPCC 1 all shares of the secret 𝑏 are recombined (after refreshing and correction) within the SRD (𝑖, ℓ) , as shown by Equation 1. Then, a fault propagation within this share domain is conditioned on the recombined secret 𝑏 . Indeed, this is allowed under the correction property of CINI . However, the privacy property requires the simulation of all output wires belonging to the share domain 𝑖 (cf. Section 5.1), which will fail due to the fault propagation dependent on 𝑏. Hence, the design principle needs to be extended as follows: A fault shall never be conditioned on a recombined secret value (even 2https://github.com/Chair-for-Security-Engineering/VERICA 8 Combined Private Circuits - Combined Security Refurbished CCS ’23, November 26–30, 2023, Copenhagen, Denmark after refreshing). In non-linear operations, like multiplication, the fault propagation is always conditioned (cf. Figure 2c). Therefore, it is required that a fault propagating through a non-linear gate does not propagate to a point in the circuit, where a secret is recombined. This additional design principle was not discovered by Feldtkeller et al. [ 19 ] due to a mistake in the CINI proof of their gadgets. When looking closely at the proofs, it is apparent that an external probe does not capture all replications of the output. Instead, only a single wire is selected and simulated for this probe, leading always to the same amount of wires probed and simulated. As discussed above, this is not sufficient for CINI and the resulting gadgets are therefore insecure in composition, precisely because of the lack of considering the above design principle. 5.4 Fixing Gadgets In Section 3.3.3 we discuss how a fault can impact probing security. Intuitively, each type of impact requires a different handling to counteract them. The first type, i.e., the removal of randomness, can be handled via additional randomness, registers, or an increase in the number of shares. Handling the leakage via the observation of effective/ineffective faults is more difficult. In particular, fault propagation remains unaffected by registers and the addition of randomness. Indeed, the (conditioned) propagation only depends on the logical expression of the propagation path. The only effective way to stop fault propagation is via error correction. Therefore, we see two fundamental ways to adhere to the above design principle. (i) Inserting a correction module after each cross– domain partial-product computation ensures that the fault propagation is stopped before the recombination of the secret 𝑏 happens. We provide more details on this approach in Section 6. (ii) Via non-completeness in the compression of the gadget, we can ensure that the secret 𝑏 is never recombined within the gadget. Hence, fault propagation cannot be dependent on 𝑏 . More details follow in Section 7. 6 GADGETS BASED ON CORRECTION The core vulnerability exploited in Section 4 is the reduction in Equation 1, i.e., all shares of 𝑏 are implicitly recombined. Adding additional error-correction modules after the refreshing of the partial products belonging to cross-domains breaks this dependency in case of fault injection. In particular, a fault in 𝑎ℓ 𝑖 (noted as ˆ 𝑎ℓ 𝑖 ) does not propagate to the refreshed cross-domain 𝑎ℓ 𝑖𝑏ℓ 𝑗 but only to the product 𝑎ℓ 𝑖𝑏ℓ 𝑖 . Equation 2 shows that in this case, the different shares do not recombine to the secret 𝑏. 𝑐ℓ 𝑖←ˆ 𝑎ℓ 𝑖· (𝑏ℓ 𝑖+ 𝑑 ∑︁ ℎ=0,ℎ≠𝑖 ˜ 𝑟ℎ,𝑖) + 𝑑 ∑︁ 𝑗=0;𝑗≠𝑖 maj(ˆ 𝑎ℓ 𝑖· (𝑏ℓ 𝑗+ 𝑑 ∑︁ ℎ=0,ℎ≠𝑗 ˜ 𝑟ℎ,𝑗 ) + 𝑟𝑖,𝑗 ) ←ˆ 𝑎ℓ 𝑖· (𝑏ℓ 𝑖+ 𝑑 ∑︁ ℎ=0,ℎ≠𝑖 ˜ 𝑟ℎ,𝑖) + 𝑑 ∑︁ 𝑗=0;𝑗≠𝑖 𝑎ℓ 𝑖· (𝑏ℓ 𝑗+ 𝑑 ∑︁ ℎ=0,ℎ≠𝑗 ˜ 𝑟ℎ,𝑗 ) + 𝑟𝑖,𝑗 ←ˆ 𝑎ℓ 𝑖· (𝑏ℓ 𝑖+ 𝑑 ∑︁ ℎ=0,ℎ≠𝑖 ˜ 𝑟ℎ,𝑖) + 𝑎ℓ 𝑖· 𝑑 ∑︁ 𝑗=0;𝑗≠𝑖 (𝑏ℓ 𝑗+ 𝑑 ∑︁ ℎ=0,ℎ≠𝑗 ˜ 𝑟ℎ,𝑗 ) + 𝑑 ∑︁ 𝑗=0;𝑗≠𝑖 𝑟𝑖,𝑗 (2) 6.1 Combined-Isolating Non-Interference Structure. We provide our CINI multiplication gadget for arbitrary order in Algorithm 2. The structure is similar to the vulnerable gadgets proposed by Feldtkeller et al. [ 19 ] but with additional error correction. First, there is a refresh and error correction for all shares belonging to input 𝑏 . Due to the non-linearity of the multiplication, this is necessary to isolate the propagation of probes and faults within share domains and SRD s, respectively. Afterward, all partial products are computed, where cross-domain partial products are refreshed and corrected again. Finally, the partial products are compressed to reduce the number of output shares to the required number. For the error correction, it is necessary to do this computation in a replicated manner. Interestingly, the additional correction modules after the partialproduct computation allow us to optimize the gadget for the number of registers. In particular, the previous gadget required that each output of the correction (after the refresh of 𝑏 , cf. Algorithm 1) is only used in one SRD , meaning that a correction and register was required for every partial product. However, in our construction, all cross-domain partial products are corrected again, meaning that a fault after the correction of 𝑏 can only propagate to a single SRD even when only computed once. Hence, while the number of corrections remains the same we reduce the number of registers per redundancy domain from 2 𝑑2+ 4 𝑑+ 2(in HPCC 1 ) to 𝑑2+ 3 𝑑+ 2(in CPCC 1 ). Due to the large area footprint of registers, this optimization leads to significant savings (cf. Section 8.1). Formal Arguments. We continue by providing a formal argument for the CINI property of Algorithm 2. The core idea for correctness is that each share of input 𝑎 only influences the same SRD of the output, while all shares of 𝑏 are corrected before reaching the output. For privacy the core idea is that probes only propagate until they reach the intermediate values 𝑧ℓ 𝑖,𝑗 or 𝑣ℓ 𝑗 . The reason is that the masking of those values is refreshed by 𝑟𝑖,𝑗 and ˜ 𝑟𝑖,𝑗 , respectively. Of course, the probe propagation stops only at those values if the used randomness is not observed anywhere else in the probes and is not faulted. However, if that is the case, there are enough probes and internal faults to allow the probe propagation to the associated input shares. In addition, any secret-dependent fault propagation is carefully controlled to be either corrected before observation or independent of secrets. Theorem 6.1. The gadget CPCC 1 as defined in Algorithm 2 with a register-free majority function is (𝑑, 𝑘) - CINI in the glitch-robust probing model. Proof Structure. For the proof, we first show the correctness and then the privacy of the gadget. For privacy, we construct a simulator in the following two steps: (i) We define for each probe/fault combination the input shares the simulator is allowed to access, i.e., the inputs the probes can propagate to. This is done via Algorithm 3 and needs to adhere to the restrictions given in Definition 3.6. (ii) We define how the simulator computes the required intermediate values. Finally, we show that the constructed simulator has the same output distribution as the probes in the original gadget, i.e., both are indistinguishable. 9