CryptoDB
Brett Hemenway Falk
Publications
Year
Venue
Title
2021
EUROCRYPT
Alibi: A Flaw in Cuckoo-Hashing based Hierarchical ORAM Schemes and a Solution
📺
Abstract
There once was a table of hashes
That held extra items in stashes
It all seemed like bliss
But things went amiss
When the stashes were stored in the caches
The first Oblivious RAM protocols introduced the ``hierarchical solution,''
(STOC '90) where the server stores a series of hash tables of geometrically increasing capacities.
Each ORAM query would read a small number of locations from each level of the hierarchy,
and each level of the hierarchy would be reshuffled and rebuilt at geometrically increasing intervals to ensure that
no single query was ever repeated twice at the same level. This yielded an ORAM protocol with polylogarithmic overhead.
Future works extended and improved the hierarchical solution, replacing traditional hashing with cuckoo
hashing (ICALP '11) and cuckoo hashing with a combined stash (Goodrich et al. SODA '12).
In this work, we identify a subtle flaw in the protocol of Goodrich et al. (SODA '12)
that uses cuckoo hashing with a stash in the hierarchical ORAM solution.
We give a concrete distinguishing attack against this type of hierarchical ORAM
that uses cuckoo hashing with a \emph{combined} stash.
This security flaw has propagated to at least 5 subsequent
hierarchical ORAM protocols,
including the recent optimal ORAM scheme, OptORAMa (Eurocrypt '20).
In addition to our attack, we identify a simple fix that
does not increase the asymptotic complexity.
We note, however, that our attack only affects more recent \emph{hierarchical ORAMs},
but does not affect the early protocols that predate the use of cuckoo hashing,
or other types of ORAM solutions (e.g. Path ORAM or Circuit ORAM).
Coauthors
- Daniel Noble (1)
- Rafail Ostrovsky (1)