Constructive Side-Channel Analysis and Secure Design

We will discuss the RowHammer problem in DRAM, which is a prime (and likely the first) example of how a circuit-level failure mechanism in Dynamic Random Access Memory (DRAM) can cause a practical and widespread system security vulnerability. RowHammer is the phenomenon that repeatedly accessing a row in a modern DRAM chip predictably causes errors in physically-adjacent rows. It is caused by a hardware failure mechanism called read disturb errors. Building on our initial fundamental work that appeared at ISCA 2014, Google Project Zero demonstrated that this hardware phenomenon can be exploited by user-level programs to gain kernel privileges. Many other recent works demonstrated other attacks exploiting RowHammer, including remote takeover of a server vulnerable to RowHammer. We will analyze the root causes of the problem and examine solution directions. We will also discuss what other problems may be lurking in DRAM and other types of memories, e.g., NAND flash and Phase Change Memory, which can potentially threaten the foundations of reliable and secure systems, as the memory technologies scale to higher densities.

With the publication of Spectre & Meltdown attacks, cache-timing exploitation techniques have received a wealth of attention recently. On the one hand, it is now well understood which patterns in the source code create observable unbalances in terms of timing. On the other hand, some practical attacks have also been reported. But the exact relation between vulnerabilities and exploitations is not enough studied as of today. In this article, we put forward a methodology to characterize the leakage induced by a “non-constant-time” construct in the source code. This methodology allows us to recover known attacks and to warn about possible new ones, possibly devastating.

Horizontal attacks are a suitable tool to evaluate the (nearly) worst-case side-channel security level of ECC implementations, due to the fact that they allow extracting a large amount of information from physical observations. Motivated by the difficulty of mounting such attacks and inspired by evaluation strategies for the security of symmetric cryptography implementations, we derive shortcut formulas to estimate the success rate of horizontal differential power analysis attacks against ECSM implementations, for efficient side-channel security evaluations. We then discuss the additional leakage assumptions that we exploit for this purpose, and provide experimental confirmation that the proposed tools lead to good predictions of the attacks’ success.

Physical Unclonable Functions (PUFs) have the potential to provide a higher level of security for key storage than traditional Non-Volatile Memory (NVM). However, the susceptibility of the PUF primitives to non-invasive Side-Channel Analysis (SCA) is largely unexplored. While resistance to SCA was indicated for the Transient Effect Ring Oscillator (TERO) PUF, it was not backed by an actual assessment. To investigate the physical security of the TERO PUF, we first discuss and study the conceptual behavior of the PUF primitive to identify possible weaknesses. We support our claims by conducting an EM-analysis of a TERO design on an FPGA. When measuring TERO cells with an oscilloscope in the time domain, a Short Time Fourier Transform (STFT) based approach allows to extract the relevant information in the frequency domain. By applying this method we significantly reduce the entropy of the PUF. Our analysis shows the vulnerability of not only the originally suggested TERO PUF implementation but also the impact on TERO designs in general. We discuss enhancements of the design that potentially prevent the TERO PUF from exposing the secret and point out that regarding security the TERO PUF is similar to the more area-efficient Ring Oscillator PUF.

We present a new statistical fault analysis technique called fault intensity map analysis (FIMA) that evaluates the responses of cryptographic implementations to biased-fault injections with varying intensities. FIMA exploits information from fault bias, as well as the correlation between fault distribution and intensity, to retrieve the secret key with fewer fault injections than existing techniques. FIMA generalizes several existing statistical fault analysis techniques, such as fault sensitivity analysis (FSA), differential fault intensity analysis (DFIA), ciphertext-only fault analysis (CFA), and statistical ineffective fault analysis (SIFA). FIMA has the flexibility of using different observables, e.g., faulty ciphertexts, correct ciphertexts under ineffective fault inductions, and data-dependent intensity profiles, and is successful against a wide range of countermeasures. In this paper, we use FIMA to retrieve the entire 128-bit secret key of the Ascon authenticated cipher, a CAESAR finalist for lightweight applications. On a software implementation of Ascon, simulations show that FIMA recovers the secret key with fewer than 50% of the fault injections required by previous techniques that rely on fault bias alone; furthermore, in the presence of error-detection and infective countermeasures, FIMA is \(6\times \) more efficient than previous bias-based techniques.

White-box cryptography was first introduced by Chow et al. in 2002 as a software technique for implementing cryptographic algorithms in a secure way that protects secret keys in a compromised environment. Ever since, Chow et al.’s design has been subject to mainly two categories of attacks published by the cryptographic community. The first category encompasses the so-called differential and algebraic cryptanalysis. Basically, these attacks counteract the obfuscation process by inverting the applied encoding functions after which the used secret key can easily be recovered. The second category comprises the software counterpart of the well-known physical attacks often applied to thwart hardware cryptographic implementations on embedded devices. In this paper, we turn a cryptanalysis technique, called statistical bucketing attack, into a computational analysis one allowing an efficient key recovery from software execution traces. Moreover, we extend this cryptanalysis technique, originally designed to break DES white-box implementations, to target AES white-box implementations. To illustrate the effectiveness of our proposal, we apply our attack on several publicly available white-box implementations with different level of protections. Based on the obtained results, we argue that our attack is not only an alternative but also a more efficient technique compared to the existing computational attacks, especially when some side-channel countermeasures are involved as a protection.

At CHES 2016, Bos et al. introduced differential computational analysis (DCA) as an attack on white-box software implementations of block ciphers. This attack builds on the same principles as DPA in the classical side-channel context, but uses computational traces consisting of plain values computed by the implementation during execution. It was shown to be able to recover the key of many existing AES white-box implementations.

The DCA adversary is passive, and so does not exploit the full power of the white-box setting, implying that many white-box schemes are insecure even in a weaker setting than the one they were designed for. It is therefore important to develop implementations which are resistant to this attack. We investigate the approach of applying standard side-channel countermeasures such as masking and shuffling. Under some necessary conditions on the underlying randomness generation, we show that these countermeasures provide resistance to standard (first-order) DCA. Furthermore, we introduce higher-order DCA, along with an enhanced multivariate version, and analyze the security of the countermeasures against these attacks. We derive analytic expressions for the complexity of the attacks – backed up through extensive attack experiments – enabling a designer to quantify the security level of a masked and shuffled implementation in the (higher-order) DCA setting.

In Side-Channel Analysis (SCA), several papers have shown that neural networks could be trained to efficiently extract sensitive information from implementations running on embedded devices. This paper introduces a new tool called Gradient Visualization that aims to proceed a post-mortem information leakage characterization after the successful training of a neural network. It relies on the computation of the gradient of the loss function used during the training. The gradient is no longer computed with respect to the model parameters, but with respect to the input trace components. Thus, it can accurately highlight temporal moments where sensitive information leaks. We theoretically show that this method, based on Sensitivity Analysis, may be used to efficiently localize points of interest in the SCA context. The efficiency of the proposed method does not depend on the particular countermeasures that may be applied to the measured traces as long as the profiled neural network can still learn in presence of such difficulties. In addition, the characterization can be made for each trace individually. We verified the soundness of our proposed method on simulated data and on experimental traces from a public side-channel database. Eventually we empirically show that the Sensitivity Analysis is at least as good as state-of-the-art characterization methods, in presence (or not) of countermeasures.

Rank estimation is an important tool for a side-channel evaluations laboratories. It allows estimating the remaining security after an attack has been performed, quantified as the time complexity and the memory consumption required to brute force the key given the leakages as probability distributions over d subkeys (usually key bytes). These estimations are particularly useful when the key is not reachable with exhaustive search. We propose a new framework for rank estimation that is conceptually simple, and more time and memory efficient than previous proposals. Our main idea is to bound each subkey distribution by an analytical function, and estimate the rank by a closed formula. To demonstrate the power of the framework, we instantiate it with Pareto-like functions to create the PRank algorithm. Pareto-like functions have long-tails that model empirical SCA distributions, and they are easily calculable. We evaluated the performance of PRank through extensive simulations based on two real SCA data corpora, and compared it to the currently-best histogram-based algorithm. We show that PRank gives a good rank estimation with much improved time and memory efficiency, especially for large ranks: For ranks between \(2^{80}-2^{100}\) PRank estimation is at most 10 bits above the histogram rank and for ranks beyond \(2^{100}\) the PRank estimation is only 4 bits above the histogram rank—yet it runs in milliseconds, and uses negligible memory. One could employ our framework with other classes of functions and possibly achieve even better results.

Multivariate cryptography is one of the main candidates for creating post-quantum public key cryptosystems. Especially in the area of digital signatures, there exist many practical and secure multivariate schemes. The signature schemes UOV and Rainbow are two of the most promising and best studied multivariate schemes which have proven secure for more than a decade. However, so far the security of multivariate signature schemes towards physical attacks has not been appropriately assessed. Towards a better understanding of the physical security of multivariate signature schemes, this paper presents fault attacks against SingleField schemes, especially UOV and Rainbow. Our analysis shows that although promising attack vectors exist, multivariate signature schemes inherently offer a good protection against fault attacks.

We present an optimized, constant-time software library for commutative supersingular isogeny Diffie-Hellman key exchange (CSIDH) proposed by Castryck et al. which targets 64-bit ARM processors. The proposed library is implemented based on highly-optimized field arithmetic operations and computes the entire key exchange in constant-time. The proposed implementation is resistant to timing attacks. We adopt optimization techniques to evaluate the highest performance CSIDH on ARM-powered embedded devices such as cellphones, analyzing the possibility of using such a scheme in the quantum era. To the best of our knowledge, the proposed implementation is the first constant-time implementation of CSIDH and the first evaluation of this scheme on embedded devices. The benchmark result on a Google Pixel 2 smartphone equipped with 64-bit high-performance ARM Cortex-A72 core shows that it takes almost 12 s for each party to compute a commutative action operation in constant-time over the 511-bit finite field proposed by Castryck et al. However, using uniform but variable-time Montgomery ladder with security considerations improves these results significantly.

To protect against the future threat of large scale quantum computing, cryptographic schemes that are considered appropriately secure against known quantum algorithms have gained in popularity and are currently in the process of standardization by NIST. One of the more promising so-called post-quantum schemes is NTRUEncrypt, which withstood scrutiny from the scientific community for over 20 years.

Similar to classical algorithms like AES, implementations of NTRUEncrypt must be protected against physical attacks. While different masking and hiding countermeasures have been proposed in the past, practical power analysis evaluations of masking for NTRUEncrypt are lacking. We therefore provide a practical evaluation of masking applied to index-based multiplication and a modern parameter set using trinary polynomials. With the use of SIMD instructions available in the Cortex-M4 microcontroller, we are able to implement additive masking without any significant performance overhead compared to an unmasked implementation. Our implementation showed no observable first-order leakage using a HW model and two million measurement traces. Successful second-order attacks are demonstrated for our implementation using SIMD instructions, which processes the mask and masked data simultaneously, as well as for a sequential implementation built for comparison. Finally, we show that applying both our low cost masking countermeasure together with a known and equally efficient shuffling scheme can provide a good trade-off achieving a high level of security without a large performance penalty.

When deployed in a potentially hostile environment, security-critical devices are susceptible to physical attacks. Consequently, cryptographic implementations need to be protected against side-channel analysis, fault attacks and attacks that combine both approaches. CAPA (CRYPTO 2018) is an algorithm-level combined countermeasure, based on MPC, with provable security in a strong attacker model. A key challenge for combined countermeasures, and CAPA in particular, is the implementation cost. In this work, we use CAPA to obtain the first hardware implementations of Keccak (SHA-3) with resistance against combined side-channel and fault attacks. We systematically explore the speed-area trade-off and show that CAPA, in spite of its algorithmic overhead, can be very fast or reasonably small. In fact, for the standardized Keccak-f[1600] instance, our low-latency version is nearly twice as fast as the previous implementations that only consider side-channel security, at the cost of area and randomness consumption. For all four presented designs, the protection level for side-channel and fault attacks can be scaled separately and to arbitrary order. To evaluate the physical security, we assess the side-channel leakage of a representative second-order secure implementation on FPGA. In addition, we experimentally validate the claimed fault detection probability.