Suppressing the Oblivious RAM Timing Channel While Making Information Leakage and Program Efficiency Trade-offs

Oblivious RAM (ORAM) is an established cryptographic technique to hide a program’s address pattern to an un-trusted storage system. More recently, ORAM schemes have been proposed to replace conventional memory controllers in secure processor settings to protect against information leakage in external memory and the processor I/O bus. A serious problem in current secure processor ORAM proposals is that they don’t obfuscate when ORAM accesses are made, or do so in a very conservative manner. Since secure processors make ORAM accesses on last-level cache misses, ORAM access timing strongly correlates to program access pattern (e.g., locality). This brings ORAM’s purpose in secure processors into question. This paper makes two contributions. First, we show how a secure processor can bound ORAM timing channel leak-age to a user-controllable leakage limit. The secure proces-sor is allowed to dynamically optimize ORAM access rate for power/performance, subject to the constraint that the leakage limit is not violated. Second, we show how chang-ing the leakage limit impacts program efficiency. We present a dynamic scheme that leaks at most 32 bits through the ORAM timing channel and introduces only 20% performance overhead and 12 % power overhead relative to a baseline ORAM that has no timing channel protection. By reducing leakage to 16 bits, our scheme degrades in per-formance by 5 % but gains in power efficiency by 3%. We show that a static (zero leakage) scheme imposes a 34% power overhead for equivalent performance (or a 30 % per-formance overhead for equivalent power) relative to our dy-namic scheme.