data61
Timing side channel in OptimalORAM?
Hi Marcel,
Hope you're doing well. I was working with OptimalORAM and I noticed that the current implementation leaks information on whether the type of operation being performed is a read or a store of N elements, but I'm not sure what's causing this.
In particular, I benchmarked OptimalORAM with N ranging from 2^2 to 2^11, and protocol parameters -E ring -R 64 -Z 3 -l. I found that the average store/read ratio across all sizes is 140.60%, and it remains within the 120-145% range for most sizes. This means that store operations are consistently ~40.6% slower than read operations; only size 8 shows a balanced ratio of 100.20%.
I'm attaching the results and the.mpc benchmark file (as .txt for GitHub). I've executed this benchmark as ./Scripts/compile-run.py -E ring -R 64 -Z 3 -l benchmark_core_oram for a given number of repetitions, but the variance is low and executing it once might suffice to reproduce this.
I've taken a look at the code to understand the reason. I haven't seen anything obvious in oram.py. In fact, I noticed that both read and write of AbstractORAM use the access method, and that the Boolean parameter that indicates whether a value has been read or written is only used in the context of a secure if_else branch. However, I guess that the compiler may be optimizing something for read operations, since these are run in fewer rounds than write operations despite the MBs transferred being the same, and this translates in a timing difference. Do you have any insights on what's happening?
Thank you!
OptimalORAM uses LinearORAM for the given sizes, which does not need to change the array for reading as it uses a simple scan. This explains the disparity. You shouldn't observe a difference if you use the access method, which is the intended method for hiding the kind of access. The security proposition is based on all parties having access to the high-level code, so they inherently know the kind of access if the code explicitly calls reading or writing. You can use RecursiveORAM to test the more sophisticated structure where reading and writing should come at the same cost.
Thank you. I had experimented with RecursiveORAM and PathORAM using the getters and setters, and I noticed that the read and store times were the same. Since OptimalORAM uses LinearORAM or RecursiveORAM, somehow I had assumed it would show the same behavior as RecursiveORAM throughout. Thanks for the clarification!