8. Idempotent Instructions to Counter Fault Analysis Attacks

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.