Oblivious RAM (ORAM)

Motivation

In the modern digital world there is a substantial divide between local and remote resources: data which needs to be used at a certain location is often stored at rest at a different location, and only accessed when needed. This is done for reasons of cost, availability, and efficiency, both at a large scale (think of cloud storage) and at a small to very small scale (as in the case of a memory bus connecting the CPU to a memory bank). Nowadays, even certain operating systems are often little more than an interface with a remote cloud provider. If on one side this has plenty of practical advantages, on the other side it raises issues of security and privacy.

Consider the example of a user operating on sensitive data stored on a remote server. How trusted is this server to the user? In an ideal world, the server's role would only be that of serving the data to the user and recording the related modifications, but in practice many things can go wrong. The user can establish an encrypted connection to the server in order to secure the data from malicious third-parties sitting in between, but the server will eventually be the last bastion to the data keeping. The server’s own security might be lax, or the server itself could be malicious, intercepting or even modifying the user’s data.

One solution could be to enforce trust in the server itself, but this is not always possible or reasonable. Furthermore, in modern cloud infrastructures there is no single "remote server", it is often very hard even to trace the position of a certain data chunk. This means that an effective solution should be trustless, only relying on the action of the user to secure the data.

An idea in this direction would be the one of encrypting the data stored remotely with a symmetric key locally kept by the user's client application. Whenever the client needs to read data stored at a particular location, the client will request that particular encrypted data chunk to the server, the server will transmit it to the client, which will then decrypt it and read the decrypted data. If the operation involves writing data at a certain location, instead, the client will locally encrypt the data (with the same key), and will request to upload it to the server at the desired position.

However there are two problems with this approach:

1. The server will still be able to know which data location is being accessed

2. It is pretty obvious whether the client is performing a "read" or "write" operation

Both issues can be critical in practice. For example, a physician accessing a database of possible diagnostic test datasheets on behalf of a patient might expose the patient’s sensitive health conditions, financial information can be inferred by monitoring a stock exchange's encrypted ledger, and so on.

Consider another example: a (trusted) CPU which needs to access data stored on an (untrusted) memory bank. In hardware design it is not uncommon to find situations where the CPU can be reasonably secured against external manipulation (for example as in smart cards), but doing so with the memory itself would prove to be impractical or very expensive. This is the reason, for example, why smart cards have usually only a few KiB of protected memory. While this is enough to store, e.g., encryption keys used to protect the rest of the bulk, untrusted memory, an adversary intercepting the communication bus between CPU and memory can still extract useful information and compromise the security of the system.

The above examples boil down to a simple point: encrypting data is not enough when the storage is not trusted, even if the storage is not malicious in the sense of mounting an active attack against the user, because access patterns can leak information.

Informally speaking, an "access pattern" is the information that can be extracted by only looking at the communication channel and the state change of the storage before and after the operation. In practice, this is equivalent to considering the case of an adversarial storage system (server, memory bank, etc). More formally, the security model addressed by ORAMs is that of an "honest but curious" adversary: this adversary does not modify the flow of information (does not interfere with the protocol), but passively observes the access patterns of the user to extract secrets.

So, given that access patterns expose sensitive information, and that encryption alone is not enough to hide these access patterns, is there a working defense?

ORAM

Formally speaking, an Oblivious Random Access Machine (ORAM) is a compiler, that turns any program into another program that has the same functionality of the original one, but such that the access patterns of the transformed program are independent from those of the original program.

In order to achieve this, it is sufficient to replace read and write operations of the original program with oblivious read and oblivious write operations. An ORAM can hence be seen as a simulator that is seen as a memory interface by the CPU, and vice versa.

This definition is better understood in a client-server scenario (but the case of CPU-memory is analogous). Consider the following, trivial example: A client $C$ wants to perform read and write operations on a large database residing on a remote, untrusted server $S$. The database is encrypted with a symmetric key owned by $C$. Whenever $C$ wants to perform an operation on the database, it does the following:

1. $C$ sends a request to $S$ to download the whole database.

2. $C$ decrypts the whole database, performs the operation on the desired element, then re-encrypts the database (with the same key).

3. Finally, $C$ re-uploads the re-encrypted whole database to $S$.

Notice two problems here:

• If the operation is "write" (i.e. one or more elements of the database are modified) then $S$ might detect the modification at a given position, because the encryption key is the same and hence might leave the encryption of untouched elements unaltered. This is fixable: in order to avoid this, $C$ must use a randomized (i.e. semantically secure) symmetric-key encryption scheme, such as a block cipher with suitable mode of operation, variable $IV$, and a good source of randomness (so, no OTP or similar).

• This trivial scheme is clearly not efficient, because every time $C$ must download and process locally the whole database. In the model we are considering, $C$ might not even have enough storage to do this. So, another approach is necessary.

The idea of an ORAM is to achieve the same level of security of the above scheme in a more efficient way. Intuitively, it is necessary not only to re-encrypt part of the database with a randomized encryption scheme at every access, but also to shuffle the position of the re-encrypted elements. At a first glance, the workflow of an ORAM scheme is as follows:

1. Given an element location/index on the database and an operation to perform on it, decide a subset of the remote storage that certainly (or at least with high probability) contains the desired element.

2. Download from $S$ that subset. This is more than downloading a single element, but less than downloading the whole database.

3. Decrypt locally the subset downloaded.

4. Find the desired element and perform the desired operation on it.

5. Shuffle the position of some or all the database elements in the subset. $C$ keeps track of the positions using an internal state.

6. Re-encrypt the subset with a randomized scheme, using the same symmetric key stored by $C$.

7. Re-upload the freshly re-encrypted subset to $S$.

There is clearly a tradeoff between performance and security, depending on the size of the subset, but with clever engineering the results can be optimized. Let's see an example.

Path ORAM

A huge advancement toward the realization of efficient ORAMs was achieved in 2012 with the scheme Path ORAM, by Stefanov et al.

In Path ORAM, a large database is stored on the server $S$ arranged in a binary tree structure. Each node of the tree is a bucket that contains a fixed number (say, 3 in this example) of encrypted database blocks. Every block is encrypted through a semantically secure symmetric-key encryption scheme using a key that is stored on the client $C$:

Client-Server model

From $C$'s point of view, a data request is a tuple (op, id, data), where op can be "read" or "write", id is a database location identifier, and data is the new data to be written in the case of a write operation, or nothing in the case of a read operation. The client also stores locally a position map, which is a table mapping every database location id to a tree leaf identifier. As a first approximation, this locally stored table has so many entries as the number of elements in the database, so it might appear unclear what the performance gain is in respect to client storage. However notice that, in practice, a database block can be much larger than a single entry in the position map; moreover, we will discuss later how to further reduce the size of this table. Initially, during Path ORAM initialization, the position map is initialized with random values.

(op, id, data)

When a data request is executed, $C$ looks into the position map for the leaf identifier corresponding to the block identifier, and communicates this leaf identifier to $S$:

l_i

Reference

An Introduction to Oblivious RAM (ORAM)Kudelski Security Research

An Introductionto Oblivious RAM (ORAM)