Practical Hardware Obfuscation Approaches and Key Contributions

HOP: Hardware makes Obfuscation Practical Kartik Kartik Nayak Nayak With Christopher W. Fletcher, Ling Ren, Nishanth Chandran, Satya Lokam, Elaine Shi and Vipul Goyal 1

Compression 1 KB 1 MB Used by everyone, perhaps license it - VBB Obfuscation No one should learn the algorithm Another scenario: Release patches without disclosing vulnerabilities 2

Known Results Known Results Heuristic approaches to obfuscation [KKNVT 15, SK 11, ZZP 04] - Efficient - No guarantees - Confuse the user Impossible to achieve program obfuscation in general [BGIRSVY 01] 3

Approaches Approaches Cryptography Cryptography Secure Processors Secure Processors 1. Indistinguishability Obfuscation [BGIRSVY 01, GGHRSW 13] - Not strong enough in practice - Non standard assumptions - Inefficient[AHKM 14] 1. Intel SGX, AEGIS, XOM [SCGDD 03, LTMLBMH 00] - Reveal access patterns - Obfuscation against s/w only adversaries 2. Using Trusted Hardware Tokens [GISVW 10, DMMN 11, CKZ 13] - Boolean circuits - Inefficient (FHE, NIZKs) 2. Ascend, GhostRider[FDD 12, LHMHTS 15] - Assume public programs 4

Key Contributions Key Contributions FHE, NIZKs Boolean circuits Efficient obfuscation of RAM programs using stateless trusted hardware token 1 Design and implement hardware system called HOP using stateful tokens 2 5x-238x better than a baseline scheme 3 Scheme Optimizations 8x-76x slower than an insecure system 5

Using Trusted Hardware Token Using Trusted Hardware Token Sender Receiver (malicious) (honest) Store Key Obfuscate Input Input2 Input3 Output Output2 Output3 Execute 6

Stateful Stateful Token Token Maintain state between invocations load a5, 0(s0) add a5, a4, a5 add a5, a5, a5 Oblivious RAM Authenticate memory Run for a fixed time T auth oramSt 7

A scheme with A scheme with stateless more challenging more challenging stateless tokens is tokens is Advantage: Advantage: Enables context switching Enables context switching Given a scheme with stateless tokens, Given a scheme with stateless tokens, using using stateful stateful tokens can be viewed as tokens can be viewed as an optimization an optimization 8

Stateless Token Stateless Token Does not maintain state between invocations load a5, 0(s0) add a5, a4, a5 add a5, a5, a5 Oblivious RAM Authenticated Encryption PID auth oramSt PID auth oramSt 9

Stateless Token Stateless Token - - Rewinding Rewinding load a5, 0(s0) add a5, a4, a5 add a5, a5, a5 Oblivious RAM Time 0: load a5, 0(s0) Time 1: add a5, a4 a5 PID auth oramSt Rewind! Time 0: load a5, 0(s0) Time 1: add a5, a4 a5 Oblivious RAMs are generally not secure against rewinding adversaries 10

0 1 2 3 4 5 6 7 A Rewinding Attack! A Rewinding Attack! Access Pattern: 3, 4 3, 4 Access Pattern: 3, 3 3, 3 4 2 4 7 4 T=0 T=1 T=0 T=1 1 4 3 3 Time 0: leaf 4 4, reassigned Time 1: leaf 1 1, reassigned Rewind! T = 0: leaf 4 4, reassigned 2 T = 1: leaf 2 2, reassigned Rewind! Time 0: leaf 4 4, reassigned Time 1: leaf 1 1, reassigned T = 0: leaf 4 4, reassigned 7 T = 1: leaf 7 7, reassigned 11

For rewinding attacks, ORAM uses For rewinding attacks, ORAM uses PRF PRFK K(program digest, input digest) (program digest, input digest) 12

Stateless Token Stateless Token Rewinding on inputs Rewinding on inputs Inp 1 = 20 Inp 2 = 10 Inp 3 = 40 Inp 1 = 20 Inp 2 = 10 Inp 3 = 30 Oblivious RAM PID auth oramSt 13

For rewinding on inputs, adversary For rewinding on inputs, adversary commits commits input digest input digest during initialization initialization during 14

Main Theorem: Informal Main Theorem: Informal Our scheme UC realizes the ideal functionality in the Ftoken-hybrid model assuming - ORAM satisfies obliviousness - sstore adopts a semantically secure encryption scheme and a collision resistant Merkle hash tree scheme and - Assuming the security of PRFs Proof in the paper. 15

Efficient obfuscation of RAM programs using stateless trusted hardware token Next: 1 1. Interleaving arithmetic and memory instructions Scheme Scheme Optimizations Optimizations 2 2. Using a scratchpad Design and implement hardware system called HOP 3 16

1. AN NM Scheduling M Scheduling Optimizations to the Scheme Optimizations to the Scheme 1. A Types of instructions Arithmetic and Memory Na ve schedule: A M A M A M A M A M A M 12000 extra cycles 1 cycle ~3000 cycles Memory accesses visible to the adversary M A A A A M 1170: load 1174: addi 1178: addi 117c: slli 1180: add 1184: load 1188: addi 118c: bne Histogram main loop a5,0(a0) a4,sp,64 a0,a0,4 a5,a5,0x2 a5,a4,a5 a4,-64(a5) a4,a4,1 a3,a0,1170 M M M A A M 17

1. AN NM Scheduling M Scheduling Optimizations to the Scheme Optimizations to the Scheme 1. A M A A A A MAA 1170: load 1174: addi 1178: addi 117c: slli 1180: add 1184: load 1188: addi 118c: bne a5,0(a0) a4,sp,64 a0,a0,4 a5,a5,0x2 a5,a4,a5 a4,-64(a5) a4,a4,1 a3,a0,1170 What if a memory access is performed after few arithmetic instructions? A A A4M schedule: 2 extra cycles 18

Optimizations to the Scheme Optimizations to the Scheme - - 1. 1. A AN NM Scheduling M Scheduling Ideally, N should be program independent ?????? ?????? ??????? ???? ????? ?????? ???????=3000 ? = 1 A A A A M A A M 6006 cycles of actual work A 2998 2996 A < 6000 cycles of dummy work 19

Amount of dummy work Amount of dummy work < 50% total work total work < 50% of the of the Our schedule incurs 2x Our schedule incurs 2x- - overhead relative to best schedule with no relative to best schedule with no dummy work dummy work overhead 20

Optimizations to the Scheme Optimizations to the Scheme 2. Using a Scratchpad 2. Using a Scratchpad Program Why does a scratchpad help? Memory accesses served by scratchpad void bwt-rle(char *a) { bwt(a, LEN); rle(a, LEN); } void main() { char *inp = readInput(); for (i=0; i < len(inp); i+=LEN) spld(inp + i, LEN, 0); len = bwt-rle(inp + i); } Why not use regular hardware caches? Cache hit/miss reveals information as they are program independent 21

HOP Architecture HOP Architecture 512 KB Variant of Path ORAM - Freecursive ORAM - PMMAC - 64 byte block, - 4 GB memory 1. single stage 32b integer base 2. spld 16 KB For efficiency, use stateful tokens 22

Slowdown Relative to Insecure Schemes Slowdown Relative to Insecure Schemes Slowdown to Insecure Slowdown to Insecure 8x 8x- -76x 76x 23

Conclusion Conclusion We are the first to design and prototype a secure processor with a matching cryptographically sound formal abstraction in the UC framework Thank You! kartik@cs.umd.edu 24