Threshold implementations: as countermeasure against higher-order differential power analysis

Embedded devices are used pervasively in a wide range of applications some of which require cryptographic algorithms in order to provide security. Today’s standardized algorithms are secure in the black-box model where an adversary has access to several inputs and/or outputs of the algorithm. However, sensitive information, such as the secret key used in the algorithm, can be derived from the physical leakage of these devices in the so called gray-box model. In a passive, non-invasive attack scenario, this physical leakage can be execution time, power consumption or electromagnetic radiation. The most common attack based on these leakages is differential power analysis (DPA) since the equipment required for such an attack is relatively cheap and the success rate of the attack is high on unprotected implementations. DPA exploits the correlation between the instantaneous power consumption of a device and the intermediate results of a cryptographic algorithm. Different countermeasures applied on various levels of the circuit have been proposed to prevent DPA. Some of these countermeasures focus on limiting the amount of power traces gathered from the cryptographic algorithm under attack using the same key. Some others aim at decreasing the signal-to-noise ratio in order to make the aforementioned correlation invisible. The final countermeasure group, which we study, randomizes the leakage depending on the sensitive information by randomizing the intermediate values of an algorithm in order to break the correlation. This powerful approach, which is called masking, provides provable security under certain leakage assumptions even if infeasibly many number of traces are analyzed. In standard masking, the model requires that there is no occurrence of unintended switching at the input or output of logic gates, the so called glitch. However, glitches are unavoidable in circuits using standard cells based on, for example, the most common hardware technology CMOS. This glitchy behavior typically results in the leakage of unintended information. There exist only two masking schemes that are proven secure even in the presence of glitches so far, namely by Nikova et al. from ICICS’06 and by Prouff et al. from CHES’11. The former, named threshold implementation, requires significantly smaller area and uses much less randomness compared to the method by Prouff et al. Threshold implementation (TI) is based on secret sharing and multi-party computation in which sensitive variables and functions using these variables are divided into s > d shares, such that knowledge of d of these shares does not reveal the secret information. An analysis using a nonlinear combination of leakages derived from d of these shares or their calculation is called a dth- order DPA. TI relies on four properties, namely correctness, non-completeness, uniformity of the shared variables and uniformity of the shared functions. It provides provable security even in the presence of glitches given the assumption that the overall leakage of the device is a linear combination of leakages caused by different shares and their calculation. This is both a common and realistic assumption made by most of the masking schemes. Achieving all four properties of TI for linear functions is straight-forward. On the other hand, it can be a challenging task when nonlinear functions, such as the S-boxes of symmetric key algorithms, are considered. Satisfying all the properties can impose using extra randomness or increasing the number of shares. Both of these solutions imply an increase of resources required by TI. The contribution of this thesis is two-fold. In the first part of the thesis, we introduce the theory for generating dth-order TI which can counteract dth- order DPA. The early works of TI provide security against first-order DPA attacks. However, it has been shown that second-order attacks are also feasible even though the amount of traces required for a successful attack increases exponentially in the noise standard deviation. Therefore, increasing the security using higher-order TI is valuable. In addition, we confirm the claimed security by analyzing a second-order TI of the block cipher KATAN. The resource requirements form a limiting factor for countermeasures especially on lightweight devices. In the second part of the thesis, we examine area- randomness-security trade-offs during a TI. In order to do that, we first investigate all 3 × 3 and 4 × 4, and some cryptographically significant classes of 5 × 5 and 6 × 6 invertible S-boxes. We use the gathered knowledge to choose S-boxes during the designs of the authenticated encryption algorithms FIDES and PRIMATEs such that the area footprints of their TIs are small. Then, we extend our research to the TIs of standardized symmetric-key algorithms AES and SHA-3 with detailed investigation on the trade-offs.