At FDTC 2016, Nahid Farhaday Ghalaty will explain a successful attack on several recently (2010) proposed software fault countermeasures [1]. She demonstrates that, when the assumptions on the fault model in a fault countermeasure are not correct, then the countermeasure can still be broken. In all of the demonstrated attacks, only a single well-placed fault injection is needed.
A traditional technique of software fault countermeasures is to use time redundancy: you execute a given software function multiple times, and then you verify if each redundant copy obtained the same result. If not, you throw the result. This technique fails when an adversary can inject multiple identical faults, one in each redundant copy. To solve this problem, recent fault countermeasures try to make the injection of multiple, identical faults harder. Several authors have proposed to apply instruction-level redundancy, such that the redundant copies of a program are two interleaved instruction streams [2].
Take the following example, which is a time-redundant memory access. A variable is accessed two times from memory, and its consistency is verified. A fault in either memory access will be caught. Furthermore, under the assumption that identical back-to-back fault injections are difficult, it’s not possible to obtain identical faults in both %g2 and %g3. And so this countermeasure appears effective.
LD [%fp-12 ] ,%g2 ; LD1
LD [%fp-12 ] ,%g3 ; LD2
CMP %g2, %g3 ; CMP
BNE .error ; BNE
An adversary would like to bypass this countermeasure by injecting a fault in either %g2 or %g3 without triggering the branch. When we think of an instruction as an atomic entity, this looks impossible. However, the reality of software execution is different. Instruction executions are not atomic, but take several phases (fetch, decode, execute, and so on). The execution of this snippet of code on a RISC processor looks as follows.
| Cycle | Fetch | Decode | Access | Execute | Memory | Exception | Writeback |
|---|---|---|---|---|---|---|---|
| 0 | LD1 | ||||||
| 1 | LD2 | LD1 | |||||
| 2 | CMP | LD2 | LD1 | ||||
| 3 | stall | stall | LD2 | LD1 | |||
| 4 | BNE | CMP | stall | LD2 | LD1 | ||
| 5 | stall | stall | CMP | stall | LD2 | LD1 | |
| 6 | stall | stall | stall | CMP | stall | LD2 | LD1 |
| 7 | NOP | BNE | stall | stall | CMP | stall | LD2 |
The processor pipeline is stalled twice. The first stall resolves the data dependency between LD2 and CMP. The second stall resolves the branch target.
The pipeline diagram also illustrates that at any given clock, more than one instruction is executing. This implies that a single fault injection can affect multiple instructions. We found several clock cycles where a single fault injection can effectively break the countermeasure. In cycle 2, a fault injection can change the target of LD1, while turning CMP into a NOP. In cycle 4, a fault injection can change the result of LD1, while turning the BNE into a NOP.
Our paper shows that this is not an isolated case. Using a careful analysis of pipeline behavior – which is not very difficult for an adversary – we could disable multiple countermeasures, including one with a formal proof of correctness [3].
The bottom line is that better fault models are needed, and a better understanding of fault behavior in a pipeline. Come listen to Nahid’s talk at FDTC 2016 to learn more.
[1] B. Yuce, N. Farhady Ghalaty, H. Santapuri, C. Deshpande, C. Patrick, P. Schaumont, “Software Fault Resistance is Futile: Effective Single-glitch Attacks,” Fault Diagnosis and Tolerance in Cryptography (FDTC 2016), Santa Barbara, CA, August 2016.
[2] Alessandro Barenghi, Luca Breveglieri, Israel Koren, Gerardo Pelosi, and Francesco Regazzoni, “Countermeasures Against Fault Attacks on Software Implemented AES: Effectiveness and Cost”, in Proceedings of the 5th Workshop on Embedded Systems Security, New York, NY, USA, 2010, WESS ’10, pp. 7:1–7:10, ACM.
[3] Nicolas Moro, Karine Heydemann, Emmanuelle Encrenaz, and Bruno Robisson, “Formal verification of a software countermeasure against instruction skip attacks”, Cryptology ePrint Archive, Report 2013/679, 2013.