Paper 2016/134

More Practical and Secure History-Independent Hash Tables

Michael T. Goodrich, Evgenios M. Kornaropoulos, Michael Mitzenmacher, and Roberto Tamassia

Abstract

Direct-recording electronic (DRE) voting systems have been used in several countries including United States, India, and the Netherlands to name a few. In the majority of those cases, researchers discovered several security flaws in the implementation and architecture of the voting system. A common property of the machines inspected was that the votes were stored sequentially according to the time they were cast, which allows an attacker to break the anonymity of the voters using some side-channel information. Subsequent research (Molnar et al. Oakland’06, Bethencourt et al. NDSS’07, Moran et al. ICALP’07) pointed out the connection between vote storage and history-independence, a privacy property that guarantees that the system does not reveal the sequence of operations that led to the current state. There are two flavors of history-independence. In a weakly history-independent data structure, every possible sequence of operations consistent with the current set of items is equally likely to have occurred. In a strongly history-independent data structure, items must be stored in a canonical way, i.e., for any set of items, there is only one possible memory representation. Strong history- independence implies weak history-independence but considerably constrains the design choices of the data structures. In this work, we present and analyze an efficient hash table data structure that simultaneously achieves the following properties: • It is based on the classic linear probing collision-handling scheme. • It is weakly history-independent. • It is secure against collision-timing attacks. That is, we consider adversaries that can measure the time for an update operation, but cannot observe data values, and we show that those adversaries cannot learn information about the items in the table. • All operations are significantly faster in practice (in particular, almost 2x faster for high load factors) than those of the commonly used strongly history-independent linear probing method proposed by Blelloch and Golovin (FOCS’07), which is not secure against collision-timing attacks. The first property is desirable for ease of implementation. The second property is desirable for the sake of maximizing privacy in scenarios where the memory of the hash table is exposed, such as post-election audit of DRE voting machines or direct memory access (DMA) attacks. The third property is desirable for maximizing privacy against adversaries who do not have access to memory but nevertheless are capable of accurately measuring the execution times of data structure operations. To our knowledge, our hash table construction is the first data structure that combines history-independence and protection against a form of timing attacks.