Oblivious RAM and Software Protection: An Overview

Oblivious RAM (ORAM) and software protection against piracy involve securing hardware and encrypted programs to prevent unauthorized access. With a focus on achieving security through encryption and indistinguishability, concepts like access patterns and data request sequences play a crucial role. The use of Physically-shielded CPUs, IND-CPA schemes, and secure ORAM constructions are essential in safeguarding sensitive information from potential adversaries.

• RAM
• Software Protection
• Encryption
• Security
• ORAM

kars146 Follow

Uploaded on Sep 23, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Oblivious RAM Applied Cryptography ECE/CS 498AM University of Illinois

2. Software Protection Problem: Software piracy Oded Goldreich: Existing solutions are ad-hoc What is the minimal protected hardware required? Approach: Physically-shielded (i.e., tamper-proof) CPU Encrypted program CPU: fetch, decrypt, execute Remark: RAM not protected! 2

3. Software Protection: Security Encrypted program ? Specification oracle ?: Given input ? returns output ?(?) and running time |?(?)|. Desideratum (informal): Software protection is secure if whatever a PPT adversary can do with access to the encrypted program she can do with access to a specification oracle 3

4. Software Protection How to achieve security? Adversary has full control of main memory (RAM) Must hide: 1. Values stored in memory CPU encrypts values with an IND-CPA scheme 2. Sequence of memory accessed Called memory access pattern Access pattern should be independent of the program 4

5. Oblivious RAM (ORAM) Server Client RAM - word - cell - block CPU Encrypted Program Capacity: ? 5

6. Encryption and Oblivious RAM Indistinguishability under chosen-plaintext attack (IND-CPA) Enc?? is really Enc??,? for some ? ${0,1}? Suppose RAM is a large array T ReadBlock(?,?): Return Dec?(T[?]) WriteBlock(?,?,?): T[?] = Enc?(?) Why this is used for ORAM: Let ? = ReadBlock(?,?), and ? ? Then: WriteBlock(?,?,?) and WriteBlock(?,?,? ) are indistinguishable 6

7. Oblivious RAM Data request sequence: ? = op1,?1,?1, , op?,??,?? op read,write ?: (logical) address / identifier of data item ?: data or if op = read Access pattern: ?( ?): sequence of accesses to the RAM / remote storage / server to satisfy request sequence ?. Typically construction dependent, e.g.,: ? ? = op1,?1, , op?,?? op read,write ?: actual address / identifier of block or cell 7

8. Oblivious RAM Definition: Let ?( ?) denote the sequence of accesses to the server performed by the ORAM construction to satisfy the request sequence ?. The ORAM construction is secure if: a) Correctness: The construction is correct, i.e., it returns data consistent with the request sequence with probability at least 1 negl( ? ) b) Obliviousness: For any two request sequences ?, ? with ? = ? , we have: ?( ?) ??( ?) for anyone except the client 8

9. 9

10. Naive Solution Server ?: table of N blocks Gen(1?): ? $0,1? Access(op,?,?): 1. ret = 2. For ? = 0 up to ?: 3. ??= ReadBlock(?,?) 4. If ? == ?: 5. ret = ?? If op is write: 6. WriteBlock(?,?,??) 7. Return ret Works: - Correct - Oblivious Overhead: O(N) - Read the entire table for every access ??= ? 10

11. Oblivious RAM: Square Root Algorithm N blocks N block shelter N dummy blocks Permuted memory - Correct - Oblivious? For each of N requests: Look for block in the shelter If not found, get block from permuted memory, put it in shelter Otherwise access the next dummy block After N requests: Reshuffle permuted memory, obliviously update with values in shelter 1. Overhead: O(N ) 2. 11

12. Oblivious Shuffling Permuted memory Use a sorting network: Source: wikipedia Oblivious shuffling: sort based on a PRF ??( ) Enc?((?,??(?)) Sorted based on: ??? < ??(?) Enc?((?,??(?)) Cost: ?(?log?) 12

13. Lower Bound: Balls and Bins Claim (informally): No ORAM construction with capacity ? can satisfy all request sequences of length ?, unless it performs (?log?) accesses. Balls and Bins game model: Setup: ? balls in ? non-transparent cells; initially ball ? in cell ? Player (CPU): at most ? balls (registers) at each time, may be probabilistic Request sequence: ?1, ,?? such that each ?? {1, ,?} denotes a request for a specific ball Observer (adversary) Game (player) actions: 1. Put ball in cell 2. Get ball from cell 3. Touch a cell, but do nothing 13

14. Lower Bound: Balls and Bins Player produces action sequence: Sequence of ? actions: ?1, 1, , ??, ? ?1, ,??: visible access pattern 1, , ?: hidden actions Valid action sequence must satisfy: a) Correctness: The action sequence must satisfy the request sequence ?1, ,?? There is a sequence of indices 1 ?1 ?2 ??= ? such that for every 1 ? ?, after action ???, ?? ball ??is in the player s hand b) Obliviousness: Any request sequence ?1, ,?? must be satisfiable by: ?1, ,?? So: it must be possible to satisfy all?? possible request sequences 14

15. Lower Bound: Balls and Bins Proof: At each step the player holds at most ? balls A fixed sequence of actions can satisfy at most ?? request sequences Number of possible hidden action sequences: ? + 2? Possible hidden actions: 1. get ball from cell (b registers) 2. put ball in cell 3. do nothing By obliviousness, it must be possible to satisfy all ??with the same action sequence. So: ? ? + 2 ? ?log?(?+2)? ? ?? 15

16. 16

17. Path ORAM Bucket (capacity ? blocks) Server Height: ? ? = 2? leaves Position map Client block leaf x 3 y 1 Stash z 4 Stefanov, Emil, et al. "Path ORAM: An Extremely Simple Oblivious RAM Protocol." ACM CCS 2013. 17

18. Path ORAM Invariant: Each block is mapped to a uniformly random leaf Server A block is either in the stash or somewhere down the path to its leaf Position map Client block leaf x 3 y 1 Stash z 4 Stefanov, Emil, et al. "Path ORAM: An Extremely Simple Oblivious RAM Protocol." ACM CCS 2013. 18

19. Path ORAM: Example Invariant: Each block is mapped to a uniformly random leaf Server A block is either in the stash or somewhere down the path to its leaf ? ? ? 1 2 3 4 Position map Request: (writ?,?,?) block leaf Client x 3 ? y 1 z 4 Stash w 3 19

20. Path ORAM: Example Invariant: Each block is mapped to a uniformly random leaf Server A block is either in the stash or somewhere down the path to its leaf ? ? 1 2 3 4 Position map Request: (writ?,?,?) block leaf Client x 3 4 ? ? y 1 z 4 Stash w 3 20

21. Path ORAM: Pseudocode N: # of blocks; L: height of tree; Z: size of buckets; P(x,l) bucket at level l along path to leaf x from root; S: stash; position: position map Position map block leaf Stash 21

22. Path ORAM Bandwidth overhead: Per request: ? log? blocks read + ? log? blocks written Storage Server: O(? ?) blocks Client: position map + stash What if the stash overflows? Probability is negligible in ? if stash is of size ? log? ?(1) Position map size: ? log2? bits Solution: use recursion: If blocks are large (e.g., ( log?2) bits) => same bandwidth overhead Otherwise: additional log? factor for bandwidth overhead 22

23. Path ORAM Obliviousness: Server sees ?( ?) which is a sequence ? = pos1[?1], ,pos?[??] pos?[??] is the position of address ?? based on the position map, together with a sequence of encrypted paths ?(pos???) Proof: For ? < ?: pos??? is statistically independent of pos??? Observe that: If ??= ??: Once pos??? is revealed, it is remapped to a new random label If ?? ??: positions of different addresses are independent Therefore: ? Pr{pos???} = 2 ? q Pr ? = ?=1 23

24. 24

25. Oblivious RAM Today Three main applications: 1. Cloud Storage 2. Secure Processors 3. Secure Multi-party Computation (SMC) Current best: ?(log?) overhead, i.e., 20-40 X in practice Server can perform computations: ?(1) overhead Homomorphic encryption; still slower in many cases 25

26. References [G87] Oded Goldreich. "Towards a theory of software protection and simulation by oblivious RAMs." ACM STOC 1987. [GO96] Goldreich, and Ostrovsky. "Software protection and simulation on oblivious RAMs." Journal of the ACM (JACM) 1996. [SVSFRYD13] Emil Stefanov, Marten Van Dijk, Elaine Shi, Christopher Fletcher, Ling Ren, Xiangyao Yu, and Srinivas Devadas. "Path ORAM: an extremely simple oblivious RAM protocol." ACM CCS 2013. 26