Catching Fault Attacks with Intra-Instruction Redundancy

Patrick Schaumont bio photo By Patrick Schaumont

At SAC 2016, Conor Patrick will be presenting our proposal for a software-based fault-attack countermeasure [1]. A fault-attack countermeasure detects the injection of faults during the execution of a software program, such that the release of faulty outputs can be prevented. There’s a rich body of work in fault analysis that describes how one uses such faulty outputs, but that is another matter [2]. The point of our paper is to explain how we catch faults during the execution of cryptographic software.

A classic technique for fault detection stems from fault tolerant computing, and makes use of redundancy. In software, the standard technique of redundancy is to execute sections of code more than once, and compare the results. There are many variants possible, but the bottom line is that redundancy is temporal - that is, the sections of redundant code are executed one after the other; they run sequentially.

Imagine this situation from the viewpoint of the adversary. In non-redundant code, a single fault injection can lead to a successful fault analysis. In time-redundant code, a single fault injection is typically not successful, because the adversary will affect only one of the redundant copies, and hence the difference in execution can be detected.

But that doesn’t make time-redundant code safe; it merely shifts the problem. If an adversary is able to inject two identical faults, the fault detection can still be fooled. Time-redundancy is not a holy grail as a fault-attack countermeasure.

And that’s where our SAC 2016 paper comes in. We use a software representation that gives spatial, rather than temporal redundancy. The idea is to use bitslicing, and to treat different bitslices as redundant copies. Bitslicing is commonly used as a performance-enhancing technique. The idea is to operate an n-bit processor as n parallel 1-bit processors, and to write the desired software program as a sequence of Boolean (bitwise) operations.

The key point of the SAC 2016 paper is how it achieves redundancy using bitslicing. For every bit in the processor word, we add a redundant bit that computes the same function in complementary logic. This means that a successful fault injection should inject two bit-precise, complementary faults, something which is quite tricky even for today’s advanced fault injection techniques (glitching, lasers, etc).

But we make it even harder for the adversary. We introduce random shifts in the processor word after each encryption round. Hence, after every round, the bitslice of interest moves to a different physical position in the processor word. That makes it extremely hard for an adversary to control the fault injection; the fault injection target shifts randomly.

The term intra-instruction redundancy in the title of our paper stems from the observation that using our technique, even a single processor instruction computes on spatially redundant data. Hence, a single fault injection is no longer enough - the adversary needs a fault injection with very precise and dynamically controlled fault characteristics.

At SAC 2016 you’ll hear Conor talk about the details of this design. The prototype implementation of an AES protected using this technique is on github.

[1] C. Patrick, B. Yuce, N. Farhady Ghalaty, P. Schaumont, “Lightweight Fault Attack Resistance in Software Using Intra-Instruction Redundancy,” Selected Areas in Cryptography (SAC 2016), St. John’s, Canada, August 2016.

[2] Marc Joye and Michael Tunstall, Eds., “Fault Analysis in Cryptography,” Information Security and Cryptography, Springer, 2012.