Paper 2016/895

Leakage-Abuse Attacks against Order-Revealing Encryption

Paul Grubbs, Kevin Sekniqi, Vincent Bindschaedler, 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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Minor revision. IEEE 2017 Symposium on Security and Privacy
Contact author(s)
pag225 @ cornell edu
History
2017-05-24: revised
2016-09-14: received
See all versions
Short URL
https://ia.cr/2016/895
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/895,
      author = {Paul Grubbs and Kevin Sekniqi and Vincent Bindschaedler and Muhammad Naveed and Thomas Ristenpart},
      title = {Leakage-Abuse Attacks against Order-Revealing Encryption},
      howpublished = {Cryptology {ePrint} Archive, Paper 2016/895},
      year = {2016},
      url = {https://eprint.iacr.org/2016/895}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.