Fault injection attacks

# Fault injection attacks

ISSISP 2017

Gif-sur-Yvette, France

July 21st, 2017

### .underline[**Ronan Lashermes**], Sébanjila Kevin Bukasa, Hélène Le Bouder and Jean-Louis Lanet
.pull-right[from the LHS lab/TAMIS @ INRIA-RBA]

---
class: inria, middle

# Practical
Design a simple algorithm to authenticate a user to a microcontroller (ARMv7-M) with a Personal Identification Number (PIN).

A stub is provided on the [git](https://gitlab.com/Artefaritaj/ISSISP2017).

You can do it with pencil and paper if prefered.

```shell
cd Documents/
git clone https://gitlab.com/Artefaritaj/ISSISP2017.git
```

---
class: inria, middle

```C
int array_compare(unsigned char* a, unsigned char* b, size_t size) {
  int i;
  for(i=0; i < size; i++) {
    if(a[i] != b[i]) {
      return 0;
    }}
  return 1;
}

void verify_pin(char* candidate_pin) {
  if(try_counter > 0) {
    int comparison = array_compare(candidate_pin, true_pin, PIN_SIZE);
    if(comparison == 1) {
      try_counter = MAX_TRY;
      auth = 1;
    } else {
      try_counter--;
      auth = 0;
    }}
  else {
    auth = 0;
  }
  if(try_counter == 0) {
    kill();
  }
}
```

---
class: inria

.right-column[
Fault injection attacks are the exploitation of a provoked incorrect behaviour of the targeted device.
]

---
class: inria
count: false

.right-column[
.dim[Fault injection attacks are the exploitation of a provoked incorrect behaviour of the target.]

Any means necessary. Here we will focus on hardware fault injection.
]

---
class: inria
count: false

.right-column[
.dim[Fault injection attacks are the exploitation of a provoked incorrect behaviour of the target.]

World domination of course!

(we will start by recovering encryption key and create vulnerabilities in software)
]

---
class: inria
count: false

.right-column[
.dim[Fault injection attacks are the exploitation of a provoked incorrect behaviour of the target.]

(we will gently start by recovering encryption key and create vulnerabilities in software)]

To show mathematicians that physics always win. And to illustrate the risks of abstraction barriers wrt. information security.
]

---
class: inria, middle

# The attacker must have physical access to the system.

- Smartcard,
- IoT,
- Phones,
- Smart Keys (cars, hotels, ...),
- ...
---
class: center, middle, inria

# Content
<div class="wrapper">
<ul class="flex cards">
  <li><h2><img src="./img/history.png" height="64px"/></h2>
    <p>
    Where do fault attacks come from?
    </p></li>
  <li><h2><img src="./img/flash-black.png" height="64px"/></h2>
    <p>How to perform hardware fault injection?
    </p></li>
  <li><h2><img src="./img/encryption.png" height="64px"/></h2>
    <p>Fault injection against cryptography.
    </p></li>
  <li><h2><img src="./img/software.png" height="64px"/></h2>
    <p>Fault injection against software. Where we show that physical fault attacks can <i>create</i> vulnerabilities in a sound program.
    </p></li>
  <li><h2><img src="./img/secure-shield.png" height="64px"/></h2>
    <p>How can we protect ourselves? Defense strategies to protect (generic) code and cryptography.
    </p></li>
</ul>
</div>
---
class: center, middle, inria

&nbsp;

# A bit of history

---

Faults before information security was a thing

---

Faults before information security was a thing

---
class: inria

## Radiations

Radiations were a threat to electronic devices from the start, sparking research on hardening chips in the 60s and 70s.

---
class: inria
count: false

## Radiations

.dim[Radiations were a threat to electronic devices from the start, sparking research on hardening chips in the 60s and 70s.]

A convenient way was invented to safely test designs: simulate faults with .underline[**lasers**].red[* ].

.footnote[.red[* ] "The Use of Lasers to Simulate Radiation-Induced Transients in Semiconductor Devices and Circuits", D. H. Habing, 1965]

---
class: inria
count: false

## Radiations

.dim[Radiations were a threat to electronic devices from the start, sparking research on hardening chips in the 60s and 70s.

A convenient way was invented to safely test designs: simulate faults with .underline[**lasers**].red[* ].]

## Cryptography

Then modern cryptography was invented: DES (1975) and RSA (1977).

.footnote[.dim[.red[* ] "The Use of Lasers to Simulate Radiation-Induced Transients in Semiconductor Devices and Circuits", D. H. Habing, 1965]]

---
class: inria
count: false

## Radiations

.dim[Radiations were a threat to electronic devices from the start, sparking research on hardening chips in the 60s and 70s.

A convenient way was invented to safely test designs: simulate faults with .underline[**lasers**].red[* ].]

## Cryptography

First (public) fault attacks against cryptography:
- the "Bellcore" attack against RSA .red[*2]
- Differential Fault Analysis .red[*3]

.footnote[.dim[.red[*] "The Use of Lasers to Simulate Radiation-Induced Transients in Semiconductor Devices and Circuits", Habing, 1965]

.red[*2] "On the importance of checking cryptographic protocols for faults", Boneh, DeMillo, Lipton, 1997

.red[*3] "Differential fault analysis of secret key cryptosystems", Biham, Shamir, 1997
  ]
---
class: center, middle, inria

&nbsp;

# Experimental side: how we .underline[**do**] a fault injection?

---
class: center, middle, inria

# 1 - First principles

---
class: center, middle, inria

# Meet a synchronous circuit

&nbsp;

---
class: center, middle, inria

# Register memorization

&nbsp;

---
class: center, middle, inria

# Clock glitch

&nbsp;

---
class: center, middle, inria

# Underpowering / Temperature increase

&nbsp;

---
class: middle, inria

# Setup time violation

The small duration (< 1ns) before the clock rising edge where the D
signal must be constant is called the setup time.

It can be a source of .underline[**non determinism**] during fault injection if this constraint is not met.

---
class: middle, inria

# 2 - Electromagnetic (EM) fault injection

---
class: middle, inria, center

Mondrian?

---
class: middle, inria, center

---
class: inria, middle

EM fault injection is similar to a localized glitch. Glitches can reach Ground, VCC, Clock, any bus...

Resolution depends on the EM probe used but its order of magnitude is .underline[**1mm**].

---
class: middle, inria

# 3 - Laser fault injection.red[* ]

&nbsp;

.center.inria-back[
<img src="./img/laser_mechanism.svg" height="50%" width="50%" />
]

&nbsp;

.footnote[.red[* ] Explanation from the PhD dissertation of C. Roscian (advised by J.M. Dutertre)]
---
class: middle, inria

# 4 - Our EM fault injection setup

---
class: inria, middle, center

---
class: inria, middle, center

.inria-back[
<img src="./img/faustine.jpg" height="95%" width="95%" />
]
---
class: center, middle, inria

&nbsp;

# Using faults against cryptography

---
class: inria, middle, center

# 1 - "Bellcore" attack against RSA-CRT

Chinese Remainder Theorem could more judiciously be called **Sunzi Remainder theorem**.
*Or speak about the American Modular Multiplication or the Greek guy division...*

---
class: inria
## RSA
Setup:
```C
n = pq
φ(n) = (p-1)(q-1)
e | gcd(e, φ(n)) = 1 and e < φ(n)
d = e^-1 mod φ(n)

(n, e) is public, d is private
```
Sign:
```C
S = M^d mod n
```

Verify signature:
```C
M = S^e mod n
```

---
class: inria

## RSA-CRT
Setup:
```C
n = pq
φ(n) = (p-1)(q-1)
e | gcd(e, φ(n)) = 1 and e < φ(n)
d = e^-1 mod φ(n)

(n, e) is public, d is private
```
Sign:
```C
dp = d mod (p-1)
dq = d mod (q-1)
qinv = q mod p
S1 = M^dp mod p
S2 = M^dq mod q
h = qinv(S1-S2) mod p

S = S2 + hq
```

---
class: inria

## Fault on RSA-CRT
Setup:
```C
n = pq
φ(n) = (p-1)(q-1)
e | gcd(e, φ(n)) = 1 and e < φ(n)
d = e^-1 mod φ(n)

(n, e) is public, d is private
```
Sign:
```C
dp = d mod (p-1)
dq = d mod (q-1)
qinv = q mod p
S1' = ?????????
S2 = M^dq mod q
h' = qinv(S1'-S2) mod p

S' = S2+h'q
```

Exploit:
```C
gcd(S'-S,n) = gcd(h'q-hq, n) = gcd(q(h'-h), n) = q
```

---
class: inria, middle, center

# 2 - DFA on AES (Giraud's model)

---
class: inria, center

# AES

&nbsp;

---
class: inria, center

# Single-bit fault

&nbsp;

---
class: inria

# Exploitation

```C
C = K10 xor SB(M9)
C' = K10 xor SB(M9') with M9' = M9 xor e

C xor C' = SB(M9) xor SB(M9 xor e), such that e = 2^i
```

Solve previous equation, yielding *2-14* possibilities for M9.

```C
K10 = C xor SB(M9)
```
So we have *2-14* key possibilities for each (C, C') pair.

**Repeat the operation, with a new fault.**

At the end (*2.4* executions expected in average), only one K10 can explain our observations: the correct one.

---
class: inria, center, middle

# 3 - Fault models

---
class: inria, middle, center

### A fault is just too many electrons in the wrong place.

---
class: inria

How we interpret it is in the eye of the observer.

Effect:
- bit flip,
- stuck at 0,
- stuck at 1

Scope:
- single-bit,
- single-byte,
- single-word
- random*

Instructions:
- nop
- data tempering
- random jump
- random opcode

Program:
- dataflow tempering,
- controlflow modification

...

---
class: inria
# Real-life software fault model

The usual fault model used in theoretical works is the NOP fault model.
But it is not what is observed in practice.

From .red[* ]:
## During fetch

- The next opcode is corrupted, may be anything...
- If the new opcode has no side effects, virtual NOP
- If not you have side effects (random branch, ...), and often crashes.

## During decode for load from flash

The loaded value is corrupted.

.footnote[.red[* ] "Electromagnetic Fault Injection: Towards a Fault Model on a 32-bit Microcontroller", Moro et al., FDTC2013]
---
class: center, middle, inria

&nbsp;

# Using faults against any software
 where things start to get fun

---
class: inria, middle, center

# The attacker got the power

to nop any desired instruction

## What could go wrong?

---
class: inria, middle

# Implicit security model
### (application point of view)

- I am in control of **my** memory (with some exceptions for DMA).
- I trust the OS (the OS is all powerful wrt me).
- The CPU is faithful, my instructions will be executed as intended (static integrity == dynamic integrity).
- The compiler has correctly translated the programer's intention. (Well we are optimistic, arent we?)
- ...

---
class: inria, middle

# Implicit security model
### (application point of view)

- I am in control of **my** memory (with some exceptions for DMA).
- I trust the OS (the OS is all powerful wrt me).
- .underline[The CPU is faithful, my instructions will be executed as intended (static integrity == dynamic integrity).]

---
class: inria

# Buffer overflow, the beast comes back to life

```C
char text[128];
unsigned char key[16];
...
char big_buffer[256];

//consider strncpy OK for the sake of the demonstration
//buffer overflow mitigated with explicit destination size parameter
strncpy(text, big_buffer, 128);
```
=> (actual assembly in our test app)

``` ASM
mov	r2, r5
mov	r0, r6
ldr	r1, [pc, #24]	; (big_buffer address)
bl	8004770 <strncpy>
```

---
class: inria

# Buffer overflow, the beast comes back to life

```C
char text[128];
unsigned char key[16];
...
char big_buffer[256];

//consider strncpy OK for the sake of the demonstration
//buffer overflow mitigated with explicit destination size parameter
strncpy(text, big_buffer, 128);
```
=> (with a fault injection)

``` ASM
nop ; what is r2 value now? -> depends on previously executed instructions
mov	r0, r6
ldr	r1, [pc, #24]	; (big_buffer address)
bl	8004770 <strncpy>
```

---
class: inria, middle, center

# So we tried to do it experimentally

---
class: inria, middle, center

# So we tried to do it experimentally
and we did not achieve to nop the desired instruction (during first experimental campaign).

But we did better...

---
class: inria, middle, center

Buffer overflow is achieved by modification of the destination address!

(And we do not know how this worked...)

---
class: inria

# Buffer overflow, mitigation with a little bird

```C
char text[128];
char canary[8];
unsigned char key[16];
...
char big_buffer[256];

//consider strncpy OK for the sake of the demonstration
//buffer overflow mitigated with explicit destination size parameter
strncpy(text, big_buffer, 128);

if(canary != canary_correct) {//if canary not correct (pseudocode)
  kill();
}
```

Can we modify the key by targeting a piece of code not related to it, but handling data close in memory (and avoiding the canary)?

---
class: inria

# Buffer overflow, mitigation with a little bird

```C
char text[128];
char canary[8];
unsigned char key[16];
...
char big_buffer[256];

//consider strncpy OK for the sake of the demonstration
//buffer overflow mitigated with explicit destination size parameter
strncpy(text, big_buffer, 128);

if(canary != canary_correct) {//if canary not correct (pseudocode)
  kill();
}
```

Can we modify the key by targeting a piece of code not related to it, but handling data close in memory (and avoiding the canary)?

# YES!

But we hardly control the new key value.
We do not have a proper explanation for the detailed processus leading to this effect.

---
class: inria, middle

# Practical
Self-evaluate your previous design, is it secure?

How can you improve it?

---
class: inria, middle

```C
int array_compare(unsigned char* a, unsigned char* b, size_t size) {
  int i;
  for(i=0; i < size; i++) {
    if(a[i] != b[i]) {
      return 0;
    }}
  return 1;
}

---
class: inria, middle

# All your secrets belong to me...

... if you have not deleted my backdoor!

- Not properly hidden (maybe some of you spotted it),
- but invisible to static analysis, it is dead code.

---
class: inria

# How to activate the backdoor?

```C
void blink_wait()
{
  unsigned int wait_for = 3758874636;
  unsigned int counter;
  for(counter = 0; counter < wait_for; counter += 8000000);
}
```

```ASM
08000598 <blink_wait>:
push	{r7, lr}
sub	sp, #8
add	r7, sp, #0
ldr	r3, [pc, #44]	; (80005cc <blink_wait+0x34>)
...
adds	r7, #8
mov	sp, r7
pop	{r7, pc}
.word	0xe00be00c ; @80005cc, 0xe00be00c = 3758874636
```

---
class: inria

# How to activate the backdoor?

```C
void blink_wait()
{
  unsigned int wait_for = 3758874636;//go to backdoor
  unsigned int counter;
  for(counter = 0; counter < wait_for; counter += 8000000);
}
```

---
class: inria

# How to activate the backdoor?

```C
void blink_wait()
{
  unsigned int wait_for = 3758874636;//go to backdoor
  unsigned int counter;
  for(counter = 0; counter < wait_for; counter += 8000000);
}
```

```ASM
08000598 <blink_wait>:
push	{r7, lr}
sub	sp, #8
add	r7, sp, #0
ldr	r3, [pc, #44]	; (80005cc <blink_wait+0x34>)
...
adds	r7, #8
mov	sp, r7
nop ; pop	{r7, pc}
b other_verif ;.word	(0xe00b)e00c
b other_verif ;.word	0xe00b(e00c)
```

Gotcha!
---
class: center, middle, inria

&nbsp;

# How to protect ourselves

---
class: inria, middle, center

## 1 - Detect the "too many electrons in the wrong place"

---
class: inria, middle, center
count: false

## .dim[1 - Detect the "too many electrons in the wrong place"]
## 2 - Adapt the program to counter a fault model

---
class: inria, middle, center
count: false

## .dim[1 - Detect the "too many electrons in the wrong place"]
## .dim[2 - Adapt the program to counter a fault model]
## 3 - Enforce system and control flow integrity at all time

---
class: inria, middle, center

# 1 - Detecting and dealing with fault injection

---
class: inria, center

## Physically place sensors on the chip to detect abnormal behavior.

&nbsp;

&nbsp;

Guard signal must be 1 only when rising edge authorized.

---
class: inria, center, middle

Guard signal is often generated from the clock, by adding a delay.

Rising edge authorized only after critical path delay.
---
class: inria, center, middle
From the PhD of Loic Zussa

---
class: inria, center, middle

---
class: inria, center

## Add redundancy

&nbsp;

---
class: inria, center, middle

---
class: inria, center, middle

---
class: inria, center

## Shielding

&nbsp;

---
class: inria, center, middle

Better if data in transit in shield wires. Check data at the end to ensure shield integrity.

---
class: inria, middle

# 2 - Countering fault models

Assuming a **one** nop fault model.
You *just* have to ensure that no one nop can induce a vulnerability.

The first step is to **prove** (formal method) that your program is not vulnerable if it misses one instruction.
With this tool you can manually design a code that should be secure against the one-nop fault model.

But here the compiler is not your friend. Some of it can be automatized...

---
class: inria
From the PhD of Nicolas Moro:

## Idempotent instructions

Same system state if instruction is repeated:

```ASM
mov r1,r8
mov r1,r8
add r3,r1,r2
add r3,r1,r2
```
You can remove any instruction, the program still operates as expected.

## Separable instructions

There exists a mapping between an instruction and a **safer** sequence of instruction:
```ASM
add r1, r1, r3
```
becomes (rx is available register)
```ASM
mov rx, r1
mov rx, r1
add r1, rx, r3
add r1, rx, r3
```
---
class: inria
Stack operations:
```ASM
stmdb sp!, { r1, r2, r3, lr }
```
```ASM
stmdb sp, { r1, r2, r3, lr }
stmdb sp, { r1, r2, r3, lr }
sub rx, sp, #16
sub rx, sp, #16
mov sp, rx
mov sp, rx
```

Branch with return (routine must be idempotent):
```ASM
bl routine
```
```ASM
adr r12, return_label
adr r12, return_label
add lr, r12, #1 ; lr=r12+1 (thumb mode)
add lr, r12, #1 ;
b routine
b routine
return_label:
```

Some instructions cannot be replaced by a safer sequence.
The overhead is quite large!

---
class: inria

# The problem with countering fault models

What is the correct fault model?

It is computationally expensive to prove safety. So we focus on sensitive code only. But...

---
class: inria

# 3 - Control Flow Integrity.red[ *]

Hardware solution for an hardware problem.

Encrypt your instructions, with program state encoding:
```C
i' = Ek(PC_prev || PC) xor i
```

```ASM
1: i1'
2: i2'
3: i3'
4: i4'
```
To decrypt i4:
```C
i4 = Ek(3||4) xor i4'
```
Nice if all instructions have only 1 predecessor...
If not we have a special case to deal with.

.footnote[.red[ *]Solution from: "SOFIA: Software and control flow integrity architecture", de Clercq et al., 2016]
---
class: inria

# Conclusion

You cannot protect hardware with software only.

You should include protections at **all abstraction levels**.

You cannot write a *truly* secure Verify PIN on the proposed device.

## But

You can strenghten your system.
- minimizing attack surface <=> minimizing system interface **AND** complexity.
- harden software at **ALL** vulnerable points of the whole **system**.

Beware, the security of your system is only as good as the security of the weakest component.

---
class: inria, middle

# Conclusion continued

Fault attacks are back with a vengeance!

We need systematic tools and processes to evaluate and mitigate software vulnerability wrt faults. It cannot be the same tools as used for *safety* critical applications (not the same threat model).

We need hardened performance cores. Imagine a SoC with 3 "standard" cores and 1 "hardened" one. Any application could ask to be executed on this core for security related operations.

---
class: inria, middle, center
# The End

---
class:  inria

# Credit

## Images

- Icons from [flaticon](http://www.flaticon.com).
- NASA for the ISS
- Bugey nuclear reactors photo from [www.entrepriseetdecouverte.fr](https://www.entrepriseetdecouverte.fr)