Bending microarchitectural �weird machines towards practicality

Ping-Lun Wang, Riccardo Paccagnella, Riad S. Wahby, and Fraser Brown

USENIX Security, 08/14/2024

A new μArch side-channel

2

▲ CPU

µArch

ISA

🤯 Prevents code analysis

😎 µArch states → invisible to Arch

😈 Defeats debuggers and emulators

μArch computer?

µWMs: difficult to analyze!

Credit: irasutoya.com

Existing µWMs need improvements…

3

Flexo: a new design for µWM

4

ISA

Credit: irasutoya.com

Arch vs. μArch “weird” computation

5

ISA instructions

“Weird” gates: memory operations during transient execution

Registers or memory

“Weird” registers: cache residency information

- In the cache: value 1

- Out of cache: value 0

The construction of a weird gate

6

if (condition())

    tmp += out[in1[in2[0]]];

Misprediction

Prior work’s AND gate

7

Time

in1

condition returns

in2

out = 1

out = 0

if (condition())

    tmp += out[in1[in2[0]]];

Misprediction

Flexo’s circuit construction: differential encoding

• Use two wires for one binary value
• 1 → (+, -) = (1, 0)
• 0 → (+, -) = (0, 1)
• Invalid states: (1, 1) or (0, 0)
• Provides a lot of benefits!

8

Flexo

AND

+-

+-

+-

New encoding → much more scalable gates!

9

if (condition()) {   

tmp += out_p[in1_p[0] + in2_m[0]];

    tmp += out_p[in1_m[0] + in2_p[0]];

    tmp += out_m[in1_p[0] + in2_p[0]];

    tmp += out_m[in1_m[0] + in2_m[0]];

}

Any gate with ≤ 4 inputs works!!

E.g., 4-bit XOR or 2-bit adder

Error correction with dynamic voting

10

Prior work (GoT) ^[1]: 3-out-of-5 voting

[1] The Gates of Time: Improving Cache Attacks with Transient Execution, Katzman et al., USENIX Sec ‘23

Flexo’s compiler: the first compiler for μWMs

11

void __weird__sha1_round(

    unsigned* input,

    unsigned* output, unsigned* error_output

) {

    unsigned a = input[0];

    unsigned b = input[1];

    unsigned c = input[2];

    unsigned d = input[3];

    unsigned e = input[4];

    unsigned w = input[5];

    unsigned k = 0x5A827999;

�    unsigned f = (b & c) | ((~b) & d);

    unsigned temp = ROL(a, 5) + f + e + w + k;

�    output[0] = temp;

    output[1] = a;

    output[2] = ROL(b, 30);

    output[3] = c;

    output[4] = d;

}

_32BitValueToCacheState(C_arch, C1, NULL);

_32BitValueToCacheState(D_arch, D1, NULL);

_32BitValueToCacheState(E_arch, E, NULL);

_32BitValueToCacheState(K[0], K0, NULL);

_32BitValueToCacheState(W_arch, W, NULL);

LeftShift(A1, A1, 27);

mfence();

lfence();

trash = _32BitAnd(B1, C1, B_AND_C, trash);

mfence();

lfence();

trash = _32BitNot(B2, NOT_B, trash);

mfence();

lfence();

trash = _32BitAnd(NOT_B, D1, NOT_B_AND_D, trash);

mfence();

lfence();

trash = _32BitOr(B_AND_C, NOT_B_AND_D, B_AND_C_OR_NOT_B_AND_D, trash);

mfence();

lfence();

trash = _32BitAdder_impl(A1, B_AND_C_OR_NOT_B_AND_D, SUM_1, WORDSIZE, trash);

mfence();

lfence();

…�

(128 lines in total)

(21 lines in total)

😇 No low-level details

✨ Optimizations!

Evaluation: experimental setup

• 8 shared AWS EC2 instances
• All Flexo µWMs are generated by our compiler
• Compare with prior work (GoT) ^[1] on the Skylake machine

​

12

[1] The Gates of Time: Improving Cache Attacks with Transient Execution, Katzman et al., USENIX Sec ‘23

GoT vs. Flexo: 4-bit ALU and SHA-1 (1 round)

13

Flexo’s performance on crypto applications

14

(%)

20× faster

First AES μWM!

UPX + Flexo: the first μWM binary packer

15

Roughly 1 minute to unpack 132 KB using Simon

(5 minutes using AES)

Takeaways

✨ Flexo makes μWMs much faster and more accurate

• Bending microarchitectural weird machines towards practicality
• GitHub: https://github.com/joeywang4/Flexo
• Contact: Ping-Lun Wang, pinglunw@andrew.cmu.edu

✨ Flexo’s compiler makes it easy to develop new µWMs

✨ μWMs are practical for program obfuscation or other attacks

Future work

• Optimize circuits for µWMs
• Expand attack surfaces (e.g., bypass sandbox)
• Detect and defend µWMs

17

Arch vs. μArch

18

Arch

μArch

State-of-the-art μWMs

19

📜 Computing with time (EBEESG’21, ASPLOS, best paper)

• SHA-1: 26.5 minutes
• Obfuscate XOR operations in malware

📜 The ghost is the machine (WBW’23, WOOT, best paper)

• First NOT gate construction in the literature
• Work on Intel, AMD, and ARM processors

• SHA-1: <1 second with 95.1% accuracy (prefetchers disabled)

📜 The Gates of Time (KKCRY’23, USENIX Sec)

OR gate: works in parallel

20

if (truish()) {

    out[in1[0]]++;

    out[in2[0]]++;

}

Time

in = 0

truish returns

out = 1

out = 0

NOT gate: variable transient window size

21

if (in[0])

    out[delay()]++;

Time

Transient execution ends

Problems with existing μWMs…

22

💥 Slow and inaccurate ^[1]

💥 Difficult to program ^[1]

• SHA-1 takes ~1 second
• Need to disable prefetchers

• SHA-1: ~2K LoC
• Only work on specific CPUs

💥 Limited for program obfuscation ^[2]

• Obfuscate trivial computations

[1] The Gates of Time: Improving Cache Attacks with Transient Execution, Katzman et al., USENIX Sec ‘23

[2] Computing with time: microarchitectural weird machines, Evtyushkin et al., ASPLOS ‘21

Existing μWMs vs. our work: Flexo

23

✨ New circuit construction

• SHA-1 is ~20× faster
• ≥ 97.8% accuracy with prefetchers enabled

✨ First compiler for μWMs

• SHA-1: 274 LoC
• Tested on 8 μArchs from AMD and Intel

• Obfuscate UPX with AES and Simon encryption

✨ First μWM binary packer

💥 Slow and inaccurate ^[1]

• SHA-1 takes ~1 second
• Need to disable prefetchers

• SHA-1: ~2K LoC
• Only work on specific CPUs

• Obfuscate trivial computations

[1] The Gates of Time: Improving Cache Attacks with Transient Execution, Katzman et al., USENIX Sec ‘23

[2] Computing with time: microarchitectural weird machines, Evtyushkin et al., ASPLOS ‘21

💥 Difficult to program ^[1]

💥 Limited for program obfuscation ^[2]

NO! Existing μWMs are slow and unstable!

• SHA-1 takes ~1 second
• Can only obfuscate XOR
• Accuracy drops quickly
• AES is ~5× larger than SHA-1

24

Problems with existing gates…

• Some gates are too complex to build
• XOR: (in1[0] ∨ in2[0]) ∧ ￢ (in1[0] ∧ in2[0])
• Existing work: at least 5 weird gates for XOR

​

25

→ We need a more efficient way to build gates!!

The construction of a weird gate

• Weird registers: store 1-bit values
• In cache/cache hit: value 1
• Out of cache/cache miss: value 0
• truish(): mis-trains the branch predictor to trigger transient execution

26

if (truish())

    out[in2[in1[0]]]++;

Weird gate

(code gadgets for computations)

Weird registers

(inputs/outputs)

Misprediction

Prior work’s AND and OR gates

27

if (truish())

    out[in2[in1[0]]]++;

// out = in1 & in2

Time

in1

truish returns

in2

out = 1

out = 0

if (truish()) {

    out[in1[0]]++;

    out[in2[0]]++;

} // out = in1 | in2

Time

in = 0

truish returns

out = 1

out = 0

Toy example: assignments to weird registers

• truish(): mis-trains the branch predictor to trigger transient execution
• Weird registers: store 1-bit values
• In cache/cache hit: value 1
• Out of cache/cache miss: value 0

28

if (truish()) {

// assign 1 to WeirdRegister1

    WeirdRegister1[0]++;

​

// assign 0 to WeirdRegister2

    clflush(WeirdRegister2);

}

New encoding → much more powerful gates

29

💥Prior work: 5+ gates for XOR

in1

in2

out

in1+

out+

out-

in2+

in1-

in2-

✨Flexo: XOR in 1 gate!

Constructing Flexo gates: from truth tables

30

Truth table of XOR

Constructing Flexo gates: XOR!

31

if (truish()) {

    out_m[in1_p[in2_p[0]]]++;

    out_p[in1_p[in2_m[0]]]++;

    out_p[in1_m[in2_p[0]]]++;

    out_m[in1_m[in2_m[0]]]++;

}

Truth table of XOR

OR the rows together

Any n-input gate in 1 transient execution!

• n = 4 in our experiments
• Reduce the circuit size by 75~87%

32

if (truish()) {

    c1_p[b1_p[a1_m[0]]] = 0;             // -0 + -1 = -1

    c1_p[b1_m[a1_p[0]]] = 0;             // -1 + -0 = -1

    c1_m[b1_m[a1_m[0]]] = 0;             // -0 + -0 = -0

    c1_m[b1_p[a1_p[0]]] = 0;             // -1 + -1 = -0

    c2_p[b2_m[a2_m[b1_p[a1_p[0]]]]] = 0; // 01 + 01 = 1-

    c2_p[b2_p[a2_m[b1_m[0]]]] = 0;       // 0- + 10 = 1-

    c2_p[b2_p[a2_m[a1_m[0]]]] = 0;       // 00 + 1- = 1-

    c2_p[b2_m[a2_p[b1_m[0]]]] = 0;       // 1- + 00 = 1-

    c2_p[b2_m[a2_p[a1_m[0]]]] = 0;       // 10 + 0- = 1-

    c2_p[b2_p[a2_p[b1_p[a1_p[0]]]]] = 0; // 11 + 11 = 1-

    c2_m[b2_m[b1_m[a2_m[0]]]] = 0;       // 0- + 00 = 0-

    c2_m[b2_m[a2_m[a1_m[0]]]] = 0;       // 00 + 0- = 0-

    c2_m[b2_p[b1_p[a2_m[a1_p[0]]]]] = 0; // 01 + 11 = 0-

    c2_m[b2_m[b1_p[a2_p[a1_p[0]]]]] = 0; // 11 + 01 = 0-

    c2_m[b2_p[b1_m[a2_p[0]]]] = 0;       // 1- + 10 = 0-

    c2_m[b2_p[a2_p[a1_m[0]]]] = 0;       // 10 + 1- = 0-

} // c2c1 = a2a1 + b2b1

Constructing Flexo gates: AND

33

AND

+-

+-

+-

out

in1

in2

1. Negate the minus wire

out+ = in1∙in2

out- = ￢(in1∙in2)

2. Expand to sum-of-product

out+ = in1∙in2

out- = ￢in1 + ￢in2

3. Replace inputs with +/- wires

out+ = in1+∙in2+

out- = in1- + in2-

Constructing Flexo gates: AND

34

AND

+-

+-

+-

out

in1

in2

out+ = in1+∙in2+

out- = in1- + in2-

if (truish()) {

    out_p[in2_p[in1_p[0]]] = 0;

    out_m[in1_m[0]] = 0;

    out_m[in2_m[0]] = 0;

}

🤔 Extra OR for an AND…

What are μWMs?

• Compute in transient execution
• Store values in cache residency
• Invisible architecturally
• Great for obfuscation!

35

if (truish())

    out[in2[in1[0]]] = 0;

▲ AND gate

Misprediction

Existing μWMs are perfect, right?

36

AND + NOT = any circuit! 🎉

Can we compute anything, like AES? 🤔

Flexo’s dynamic error correction

• Prior work: 3-out-of-5 majority voting
• Fixed 5× overhead for circuits with high accuracy
• Not enough votes for circuits with low accuracy
• Flexo: error detection + majority voting
• Rerun circuits until one of the following is true
• No error detected
• Have enough votes

37

Flexo: the first practical μWM

• New circuit construction
• Much more powerful gates
• SHA-1 is 24.7× faster
• AES with ≥ 99.7% accuracy
• Flexo compiler
• Build and optimize μWM easily
• Obfuscate real-world programs
• UPX with μWMs for decryption

38

Flexo

Error detection: invalid output states

• Suppose an AND gate should output 1

39

Flexo’s error correction: fast and accurate

40

Flexo

Prior work (GoT)

1. Circuit with high accuracy

2. Circuit with low accuracy

3. Circuit with extremely low accuracy

Applications of μWMs

1. Program obfuscation

41

if (truish()) {

    malicious_gates();

}

2. Amplify side-channel signals

if (truish()) {

out1[in[0]] = 0;

out2[in[0]] = 0;

out3[in[0]] = 0;

    …

}

One cache hit/miss

↓

Many cache hits/misses

⇒ coarse timers

• Not visible in architectural states
• Cannot debug (no single-stepping)
• Computations → memory accesses

Flexo’s compiler: the first compiler for μWMs

42

1. Input C/C++ program

2. Verilog circuit

3. Truth tables for Flexo gates

4. Output LLVM IR (with Flexo)

From C/C++ to Verilog

• Some limitations
• No branches or function calls
• No memory operations (except for input/output wires)

​

43

From Verilog to truth tables

• EDA tool (Yosys) synthesizes the circuit into truth tables (LUTs)
• Circuit optimizations
• Future work: circuit optimization for Flexo
• Schedule the gates
• Synthesize gates with multiple outputs

​

44

From truth tables to Flexo

• Generate Flexo gates, allocate wires, and perform optimizations
• Example: optimizing the memory layout
• Prefetchers may track memory access patterns
• Solution: randomize wires to memory mapping

​

45

Evaluation: experimental setup

• 8 shared AWS EC2 instances
• All Flexo circuits are generated by our compiler

46

GoT vs. Flexo: 4-bit ALU and SHA-1 (1 round)

47

Flexo’s accuracy on large circuits

48

AES (one round): 2524 gates

Simon: 4322 gates

Flexo’s runtime on large circuits

49

AES (one round): 2524 gates

Simon: 4322 gates

Unpacking speed of Flexo + UPX

50

(Seconds)

Compare with GoT: 4-bit ALU and SHA-1

51

4~38.8%

higher accuracy!

5.3~48.7× speedup!

Flexo’s performance on large circuits

52

2524 gates

4322 gates

Flexo’s performance on crypto applications

53

(TODO)

Unpacking speed of Flexo + UPX

54

(TODO)

UPX: an open-source binary packer

55