A C++ Library for Oblivious Data Structures

When considering how to define secure program execution, there are many facets to consider: compute, memory, network devices, etc. all have the ability to leak different, potentially sensitive information. Since it is difficult to consider all facets of secure execution at once, researchers segment security definitions to deal with the specific ways in which data could be leaked as individual security guarantees.

In order for the execution of a program to be \textit{memory-trace oblivious}, an adversary observing the memory accesses must not be able to discern any information about sensitive program inputs or outputs (which may or may not include the program). This is important, as through memory access patterns, an adversary may be able to use techniques such as frequency analysis, co-occurrence analysis, or read-write distinguishability to reveal information about program inputs based on dependent control flow.

ORAM is a system and/or compiler level technique to translate programs into a memory-trace oblivious form. Almost all ORAM designs share the same core ideas for hiding data. When blocks are accessed, they are shuffled an remapped, so repeated accesses to the same data point will appear to be targeting a sequence of different, random memory locations. Data is also "over-fetched", meaning not all retrieved blocks contain useful data. This prevents an adversary from identifying which of several blocks is of use to the client.

ORAM is an active field of research, with many variants published, each optimized for slightly different use cases and implemented in slightly different ways. Some popular variants include path ORAM, circuit ORAM, and ring ORAM.

Our project uses a non-recursive path ORAM\cite{stefanov2018path} as the basis of our implementation. Figure \ref{fig:path-oram} shows an example of a path ORAM data structure with 4 levels (\(L = 4\)). The structure has \(2^L\) unique "paths" from root to leaf, with each path being identifiable by the index of the leaf node at which it terminates. Blocks of memory are placed into buckets located at nodes along the path their address is currently mapped to, with mappings stored either in a single lookup table, or a smaller, recursive set of path ORAMs (the size of the mapping table can be significant as the number of blocks becomes large). Non-leaf nodes may contain blocks from any path which intersects them.

When a block is read or written, \textit{all} blocks on the associated path are read from the path ORAM tree into the stash (a client side cache for ORAM blocks). The block data is then unencrypted, and the stored address tag is compared with the target address. The found block is then read/written as normal, and the address is remapped to a new, random leaf node. Once the operation is completed, blocks from the stash are written back if there is available bucket space on the path, starting from the leaf node and ending with the root bucket. The specific mapping and ordering of blocks will occasionally result in the stash not being fully empty after this step, and any remaining blocks will persist until the next write-back able to clear them.

Despite being well studied, all existing ORAMs share a few key problems. The first is the large mapping store. One motivation for the use of ORAM is a large amount of data that cannot fit on a small, trusted client's storage, so if follows that we do not have a large amount of storage to waste on a mapping table. The current technique for resolving the client-side storage overhead is a recursive path ORAM, which stores a small mapping table on the client used to lookup increasingly more granular mapping tables from the ORAM server. This recursive process introduces extra overhead in terms of communication bandwidth and computation. Unfortunately, current research has been unable to alleviate this problem in the general case. However, most programs do not require massive amounts of random access memory. This is because large data is typically organized by data structures designed for efficient access. Prior works\cite{wang2014oblivious} have shown that in this special case, the mapping lookup overhead can be almost \textit{entirely} eliminated on the client side.

A small number of prior works specifically target oblivious data structures, which are data structures built on top of secure technologies such as MPC or ORAM. Our work is based on the pointer-based ORAM oblivious data structures described by \cite{wang2014oblivious} due to the simplicity and extensibility of its design. The core idea of the work is that data structures restrict what memory locations can be accessed at any point to a small number of addresses, and therefore only a small number of mappings must be known at any point. The author's suggest adding metadata to each oram block indicating the revealed accessible addresses and their leaf mappings. The ORAM client itself also stores a small number of pointers (i.e., for an oblivious stack, the top pointer and mapping). The paper also proposes a locality based strategy for implementing efficient oblivious graph algorithms, but we do not implement this in our project.

Our design is based on a client server ORAM model, where communication occurs using serialized command structures over a TCP stream. The client initiates path reads or path write-backs, and then sends or receives a fixed number of encrypted ORAM blocks based on the path ORAM parameters. For example, a tree with \(L = 4\) levels and \(Z = 8\) blocks per node bucket would read/write \(4 \cdot 8 = 32\) blocks. The buckets are initialized to contain encrypted "empty" blocks, which are replaced during execution with real blocks as the data structure is populated.

We introduce two optimizations during our implementation phase. The first is delayed writes. For stack/queue push operations, and AVL tree insertion, we know that the block at the address we'd like to write to does not yet exist on the server. Therefore, there is no need for us to communicate with the server. Instead, we create a new block locally and place it into the stash. It will then eventually be propagated to the server when an operation necessitating a write-back does occur. To ensure this technique does not result in an overfilled stash, we introduce a threshold value. Once there are \code{THRESHOLD} number of blocks in the stash, the client triggers a \code{GET\_BLOCKS/DUMP\_STASH} command pairing to a randomly chosen leaf index, effectively draining the stash to prevent overflow.

The second optimization is the introduction of an \code{in\_use} flag for blocks in the stash. When an ORAM block is retrieved for the first time from the server or accessed from the stash the flag is set to indicate that it should not be evicted from the stash during a write-back. The function using the block is then responsible for un-setting the flag once the block is no longer needed. The usage of this flag is entirely transparent to the user, and does not introduce any programming overhead.

Our implementation is based on prior works\cite{wang2014oblivious, stefanov2018path} which provide an in-depth security analysis of the pointer based method. We briefly discuss the security of our practical implementation decisions here.

Block data and metadata is encrypted using the AES symmetric cipher, which is considered to be secure. We include a nonce in the blocks that is incremented before encryption to prevent the server from knowing which blocks on a path were/were not read/written since their last tenancy on the server. We also initialize the \texttt{data} field empty blocks to random bytes to prevent them from being identifiable by the server when encrypted.

The server also has minimal knowledge about the usage of the data structure. To begin, we do not explicitly inform the server which of the implemented data structures our client is. Any access to the server is done through the base \texttt{ORAMClient} class and provides only an opcode, an encrypted block, and a leaf index. The server cannot tell if an access is a read or write since all blocks will appear changed when written back due to the nonce.

The delayed write mechanism in conjunction with random stash flushes helps hide operations that could potentially reveal the identity of the data structure or the usage (reads vs. writes). Consider the case in which a client continuously pushes to a stack, and then continuously pops from the stack. In this case, the leaf indices seen by the server would appear symmetric, allowing the server to guess the access pattern. By caching writes on the client and then randomly choosing a path to fill to, we make access patterns appear more random and prevent such information leakage.

There is some information leakage in terms of read/write timing and the overall number of accesses, but this has not been solved by previous ORAM works, and therefore we do not attempt to address it.