Cryptology ePrint Archive: Report 2016/895
Leakage-Abuse Attacks against Order-Revealing Encryption
Paul Grubbs and Kevin Sekniqi and Vincent Bindschaedler and Muhammad Naveed and Thomas Ristenpart
Abstract: Order-preserving encryption and its generalization
order-revealing encryption (OPE/ORE) are used in a variety
of settings in practice in order to allow sorting, performing
range queries, and filtering data — all while only having access
to ciphertexts. But OPE and ORE ciphertexts necessarily leak
information about plaintexts, and what level of security they
provide has been unclear.
In this work, we introduce new leakage-abuse attacks that show
how to recover plaintexts from OPE/ORE-encrypted databases.
Underlying our new attacks against practically-used schemes is a
framework in which we cast the adversary’s challenge as a non-
crossing bipartite matching problem. This allows easy tailoring
of attacks to a specific scheme’s leakage profile. In a case study
of customer records, we show attacks that recover 99% of first
names, 97% of last names, and 90% of birthdates held in a
database, despite all values being encrypted with the OPE scheme
most widely used in practice.
We also show the first attack against the recent frequency-
hiding Kerschbaum scheme, to which no prior attacks have
been demonstrated. Our attack recovers frequently occurring
plaintexts most of the time.
Category / Keywords: secret-key cryptography /
Date: received 9 Sep 2016
Contact author: pag225 at cornell edu
Available format(s): PDF | BibTeX Citation
Version: 20160914:043030 (All versions of this report)
Short URL: ia.cr/2016/895
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]