Skip to main content
main-content

Über dieses Buch

This book presents a collection of automated methods that are useful for different aspects of fault analysis in cryptography. The first part focuses on automated analysis of symmetric cipher design specifications, software implementations, and hardware circuits. The second part provides automated deployment of countermeasures. The third part provides automated evaluation of countermeasures against fault attacks. Finally, the fourth part focuses on automating fault attack experiments. The presented methods enable software developers, circuit designers, and cryptographers to test and harden their products.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Introduction to Fault Analysis in Cryptography

Abstract
This chapter first provides a brief overview of cryptography, introducing the necessary concepts that are used later in this book. Then, it focuses on fault injection attacks, methods, and techniques—outlining the terminology and providing background to understand the content of the following chapters. Countermeasures against fault attacks are detailed at the end of the chapter.
Jakub Breier, Xiaolu Hou

Automated Fault Analysis of Symmetric Block Ciphers

Frontmatter

Chapter 2. ExpFault: An Automated Framework for Block Cipher Fault Analysis

Abstract
Intentional or unintentional faults in computation or control flow of modern computing systems can be catastrophic if they are exploited maliciously. One of the primary targets of malicious faults are the modern cryptographic primitives—especially the block ciphers. Designing precise countermeasures against such threats is desirable, but that requires comprehensive knowledge about the attack space of the cryptographic algorithm as well as the implementation. Although manual efforts for vulnerability analysis of fault attacks is quite widespread, it becomes infeasible with the fact that the number of existing ciphers is quite large today. Formidable size of fault spaces and their diversity further highlights the need for automation in this context. Since fault attacks for block ciphers are critically dependent on the mathematical properties of the cipher, a comprehensive understanding of the attack space thus should begin with automated algorithmic analysis. This chapter lays the foundations for automated fault analysis of ciphers and presents a framework called ExpFault for automated algorithm-level fault analysis.
Sayandeep Saha, Debdeep Mukhopadhyay, Pallab Dasgupta

Chapter 3. Exploitable Fault Space Characterization: A Complementary Approach

Abstract
Consider the problem of estimating the success rate of an attacker for a given fault location. Intuitively, the success rate indicates the likeliness of an attack for returning the key bits within a practical computational bound. It is a quantity worth estimating as it helps in choosing cipher constructs and sub-operations showing a certain amount of robustness against fault attacks. In this chapter, we present a framework, which can estimate quantities like success rate and can provide new insights into the cipher structures in the context of fault attacks. The main idea is to utilize the exact encoding of algebraic fault attacks (AFA) for exploring the fault space without getting affected by its prohibitive time complexity. We propose a machine learning (ML) based speedup strategy to make the AFA suitable for characterizing huge fault spaces statistically. This statistical approach is found to be extremely informative for cipher designers and evaluators.
Sayandeep Saha, Dirmanto Jap, Sikhar Patranabis, Debdeep Mukhopadhyay, Shivam Bhasin, Pallab Dasgupta

Chapter 4. Differential Fault Analysis Automation on Assembly Code

Abstract
Normally, fault attack models are determined by analyzing the cipher algorithm and finding exploitable spots in non-linear and permutation layers. However, due to optimizations and different ways of realizing algorithmic operations, cipher level analysis does not capture enough details to locate the vulnerable parts of software implementations. On the other hand, manually analyzing the assembly code requires non-negligible amount of time and expertise.
In this chapter, we propose an automated approach for analyzing cipher implementations in assembly. By representing the whole assembly program as a data flow graph, we can efficiently identify the vulnerable spots. Fault propagation is analyzed in a subgraph, constructed from each vulnerable spot, allowing equations for differential fault analysis (DFA) to be automatically generated.
We have created a tool that implements our approach: DATAC—DFA Automation Tool for Assembly Code. We have successfully used DATAC for attacking PRESENT-80, being able to find implementation-specific vulnerabilities that can be exploited in order to recover the last round key with 16 faults. Our results show that DATAC is useful in finding attack spots that are not visible from the cipher structure, but can be easily exploited when dealing with real-world implementations.
Jakub Breier, Xiaolu Hou, Yang Liu

Chapter 5. An Automated Framework for Analysis and Evaluation of Algebraic Fault Attacks on Lightweight Block Ciphers

Abstract
Algebraic fault analysis (AFA), which combines algebraic cryptanalysis with fault attacks, has represented serious threats to the security of lightweight block ciphers. Inspired by an earlier framework for the analysis of side-channel attacks presented at EUROCRYPT 2009, a new generic framework is proposed to analyze and evaluate algebraic fault attacks on lightweight block ciphers. We interpret AFA at three levels: the target, the adversary, and the evaluator. We describe the capability of an adversary in four parts: the fault injector, the fault model describer, the cipher describer, and the machine solver. A formal fault model is provided to cover most of the current fault attacks. Different strategies of building optimal equation set are also provided to accelerate the solving process. At the evaluator level, we consider the approximate information metric and the actual security metric. These metrics can be used to guide adversaries, cipher designers, and industrial engineers. To verify the feasibility of the proposed framework, we make a comprehensive study of AFA on an ultra-lightweight block cipher called LBlock. Three scenarios are exploited which include injecting a fault to encryption, to key scheduling, or modifying the round number or counter. Our best results show that a single fault injection is enough to recover the master key of LBlock within the affordable complexity in each scenario.
Fan Zhang, Bolin Yang, Shize Guo, Xinjie Zhao, Tao Wang, Francois-Xavier Standaert, Dawu Gu

Chapter 6. Automatic Construction of Fault Attacks on Cryptographic Hardware Implementations

Abstract
Fault attacks are an essential threat to security of cryptographic functions. This chapter focuses on underlying concepts of fault attacks on cryptographic circuit implementations. Rather than targeting a specific cipher, the presented approach aims at an automatic construction of fault attacks from the circuit description. A Boolean formula that describes the circuit operation and the fault injection is generated and handed over to a SAT solver; an adversary can deduce protected information, e.g., the secret key, from the solution. The chapter also includes a comparison of the described methodology with other existing fault attack frameworks that are not specifically targeted towards circuit implementations.
Ilia Polian, Mael Gay, Tobias Paxian, Matthias Sauer, Bernd Becker

Automated Design and Deployment of Fault Countermeasures

Frontmatter

Chapter 7. Automated Deployment of Software Encoding Countermeasure

Abstract
In this chapter, we provide insights on automated generation of an encoding-based software countermeasure against both fault and side-channel attacks. First, we outline the fault resistance properties that are necessary to design an encoding scheme designed to protect cryptographic software implementations against faults. We define theoretical bounds that clearly show the possibilities and limitations of encoding-based countermeasures, together with trade-offs between side-channel and fault resistance. Later, we detail the algorithm that automatically constructs a code according to pre-defined user criteria w.r.t. fault resistance and takes the stochastic device leakage into account to minimize the leaked side-channel information. As a result, we are able to design a code by using automated methods that can provide the optimal trade-off between side-channel and fault resistance. We simulate several codes with respect to most popular fault models, using a general-purpose microcontroller assembly implementation.
Jakub Breier, Xiaolu Hou

Chapter 8. Idempotent Instructions to Counter Fault Analysis Attacks

Abstract
In this chapter, we present an exposition to countermeasures against fault analysis via instruction-level redundancy in software. The presence of redundant instructions protects a software implementation against what are called “instruction-skip” attacks, wherein an adversary targeting a software-based crypto-implementation (e.g., on platform such as micro-controllers) might skip one or more instructions to leak secret information. The idea is to convert an instruction sequence that performs a specific task into a functionally equivalent sequence that is tolerant to skipping of a certain (pre-determined) number of instructions. In this context, we introduce the reader to “idempotent” instructions, which are instructions that may be duplicated without affecting the eventual outcome of the overall program. However, not all instructions may be simply duplicated; we show some non-trivial conversions of simple non-idempotent instructions into sequences of idempotent instructions that can then be made redundant via duplication. Finally, we discuss how to automate the process of compiling any program into a fault-tolerant sequence of assembly instructions via a case study on a modified LLVM compiler.
Sikhar Patranabis, Debdeep Mukhopadhyay

Chapter 9. Differential Fault Attack Resistant Hardware Design Automation

Abstract
Since fault analysis had shown that nearly all cryptographic primitives to be vulnerable, countermeasures against such attacks are becoming a necessity. Available countermeasures are either added at the algorithmic level or at the implementation level and incur performance, area and power consumption overhead. Therefore, a trade-off analysis of security and performance needs to be done during the design phase. In this chapter, we discuss an implementation-level countermeasure that can be easily automated and integrated into the commercial circuit design flows, making the task of implementing these countermeasures easier for hardware designers.
Mustafa Khairallah, Jakub Breier, Shivam Bhasin, Anupam Chattopadhyay

Automated Analysis of Fault Countermeasures

Frontmatter

Chapter 10. Automated Evaluation of Software Encoding Schemes

Abstract
In this chapter we detail an architecture of automated framework for evaluating protected software implementations. To provide insights on the usefulness of such methodology, three different software encoding schemes were analyzed as a case study, with respect to fault injection attacks. After obtaining the simulated results, a real attack scenario with the usage of laser fault injection was conducted. Both results were then compared to validate the simulation methodology.
Jakub Breier, Dirmanto Jap, Shivam Bhasin

Chapter 11. Automated Evaluation of Concurrent Error Detection Code Protected Hardware Implementations

Abstract
Parity-based concurrent error detection (CED) techniques are often deployed as a countermeasure to fault injection attacks, owing to their low-overhead in hardware. Advanced linear and non-linear randomized encoding can be employed for constructing varying CED schemes. In this chapter, we provide an automated evaluation method to estimate the detection capability of both linear and non-linear parity-protected ciphers in the presence of fault attacks. The method takes the device characteristics into account to provide accurate results on fault coverage. Case study on PRESENT-80 CED-protected implementation is provided to show the usage and practicality of such method.
Dirmanto Jap, Jakub Breier, Shivam Bhasin, Anupam Chattopadhyay

Chapter 12. Fault Analysis Assisted by Simulation

Abstract
Side-channel and fault injection attacks are renown techniques to extract keys from cryptographic devices. Fortunately, leakage reduction and fault detection countermeasures exist and can be implemented right in the source-code. However, source-code level countermeasures might be altered during the compilation process. Design simulation is an effective means to detect such harmful simplifications. This is a well-known methodology to analyze regressions in terms of side-channel leakage.
In this chapter, we explain that protections against fault injection attacks are no exception. First of all, we show that vulnerabilities to those attacks can be easily detected by simulation methods. Second, we highlight that simulation techniques are also highly efficient in detecting logic simplifications which destroy (fully or partly) the countermeasures. Thus, the simulation-based methodology we present in this chapter shows that it is possible to decide quickly which compilation options are safe and which ones are detrimental to the security.
Kais Chibani, Adrien Facon, Sylvain Guilley, Damien Marion, Yves Mathieu, Laurent Sauvage, Youssef Souissi, Sofiane Takarabt

Automated Fault Attack Experiments

Frontmatter

Chapter 13. Optimizing Electromagnetic Fault Injection with Genetic Algorithms

Abstract
Fault injection is a serious threat for implementations of cryptography, especially on small embedded devices. In particular, electromagnetic fault injection (EMFI) is a powerful active attack, requiring minimal modifications on the device under attack while having excellent penetration capabilities. The challenge is in finding the right combination of the attack parameters and their values. Namely, the number of possible combinations (for all the values of relevant parameters) is typically huge and rendering exhaustive search impossible.
In this chapter, we introduce this problem and we survey some previous attempts for solving it. We also present a novel evolutionary algorithm for optimizing the parameters search for EM fault injection that outperforms all known search methods for EMFI. The results are widely applicable as the cryptographic device under attack is considered a black box, with only a few very general assumptions on its inner workings.
We test our novel evolutionary algorithm by attacking the SHA-3 algorithm. Our results leverage 40 times more faulty measurements and 20 times more distinct fault measurements than one could obtain with a random search. When this methodology is coupled with the algebraic fault attack, we get 25% more exploitable faults per individual measurement.
Antun Maldini, Niels Samwel, Stjepan Picek, Lejla Batina

Chapter 14. Automated Profiling Method for Laser Fault Injection in FPGAs

Abstract
Obtaining a knowledge of internal structure of a Field Programmable Gate Array (FPGA), together with the vulnerable spots that can be targeted by a laser fault injection, can be a time-consuming task when done manually. In this chapter, we present an automated method to identify regions of interest in an FPGA, such as logic arrays and cells. Such method identifies circuits that are implemented in FPGA and helps the attacker to determine which fault models are achievable with a given laser fault injection equipment. The chapter follows a step-by-step methodology of evaluation, starting with the chip decapsulation and preparation, followed by the characterization of the laser pulse interaction with the silicon. Later it focuses on the automated profiling itself, with a case study on Virtex-5 FPGA.
Jakub Breier, Wei He, Shivam Bhasin, Dirmanto Jap, Samuel Chef, Hock Guan Ong, Chee Lip Gan

Backmatter

Weitere Informationen