Citation: Ling Ren, Xiangyao Yu, Christopher W. Fletcher, Marten van Dijk and Srinivas Devadas (2013/06) Design space exploration and optimization of path oblivious RAM in secure processors. International Symposium on Computer Architecture (RSS)
DOI (original publisher): 10.1145/2485922.2485971
Semantic Scholar (metadata): 10.1145/2485922.2485971
Sci-Hub (fulltext): 10.1145/2485922.2485971
Internet Archive Scholar (search for fulltext): Design space exploration and optimization of path oblivious RAM in secure processors
Download: https://dl.acm.org/doi/10.1145/2485922.2485971
Tagged: Computer Science (RSS) computer architecture (RSS), security (RSS)

Summary

Placeholder

Theoretical and Practical Relevance

Placeholder

How to outsource computation and retain privacy of data?
- Trust: processor, contents of RAM (encrypted)
  - We can trust the processor by checking a hardware certificate. Data is decrypted with the hardware key when it is loaded from RAM and encrypted when it is stored, so that is also secure.
- Don't trust: application, OS
- Assume can: know which addresses were accessed, run arbitrary applications on the private data

Oblivious RAM (ORAM): makes the sequence of accesses indistinguishable from random.
- Path ORAM: tree, stash, and position map manipulated by the access-algorithm.
  - Tree: each node is a bucket which contains multiple blocks of encrypted data.
  - Position map: maps each address to a leaf in a tree. The node/bucket containing the block containing the leaf containing data for that address is on the path from the root to that leaf.
  - Stash: basically a cache of data blocks unencrypted.
  - Access algorithm: Use the position map to turn the address into a leaf, read the path along the leaf into the stash. If access is a read, return the value; otherwise (access was write), map the block to a new leaf, and store all blocks on the path to the new leaf.
- Hierarchical Path ORAM: ORAM-1's position map is stored in ORAM-2, while ORAM-2's position map is stored in ORAM-3, ... Each subsequent ORAM has a smaller capacity, and the last one has to fit in silicon.
- Access overhead: Ratio of ORAM bytes accessed to actual plaintext bytes.
- Traditional Path ORAM is too expensive (up to 15x slower than native): high access overhead, stash overflow, high latency, low DRAM utilization.

The following optimizations reduce the over head to only 8x in the worst SPEC CPU benchmark.
Background eviction
- Even whether the stash filled up is sensitive information. Therefore, evictions should be indistinguishable from real accesses.
- In the background, ORAM controller can read/write (unmodified) a random block. This doesn't add to the stash, since read and write the same number of blocks. But some of the blocks which have been waiting in the stash might be able to be written along that path as well.
- Livelock can occur, but it is exceedingly rare.
- This background eviction does not compromise security.
Superblocks
- Put spatially-local blocks on the same path (not necessarily in the same bucket/node).
- This is not the same as just increasing the block size, because the superblock can have some blocks in processor's cache and some in ORAM stash and they don't necessarily live in the same bucket/node.
Pipelining Hierarchical Path ORAM accesses
- ORAM-n can start executing as soon as the read of ORAM-(n+1) is done; This can be parallel to the write-back of ORAM-(n+1), hiding its latency.
Design-space exploration on stash size, dummy-accesses-to-real-accesses ratio, bucket size.
Authors visualize time spent in each level of the hierarchical ORAM.
Easy to tack on integrity-verification
- Use a Merkle Tree

Intel TPM+TXT trusts RAM, but ORAM does not. Could use both.
Aegis and eXecute Only Memory encrypt the data, but leak information by what addresses are requested.
HIDE randomizes the access pattern, but only within blocks. It isn't efficient to use over the whole RAM.
Trusted Execution Module can only use small internal RAM; ORAM would let it securely use the larger, external DRAM.