cloudgal42I recently read a very interesting paper on Leakage-Abuse Attacks against Order-Preserving Encryption (OPE) schemes and Order-Revealing Encryption (ORE) Schemes.
In this paper, the researchers show how the widely used encryption schemes are inadequate. Here are some snippets from the paper.
Order-preserving encryption (#OPE) - ensures that Ek(m1)<Ek(m2) for m1<m2 and Ek the encryption algorithm. Most widely used scheme is #BCLO.
Order-revealing encryption (#ORE) - reveals ordering relations by way of a public comparison function that operates on pairs of plaintexts. Most widely used scheme is #CLWW.
Popular belief is that OPE and ORE schemes remain secure in practice for plaintext data drawn from larger domains, and practitioners could simply avoid using OPE for small-domain data.
The researchers used a non-crossing attack (min-weight non-crossing #bipartite matching) which runs in only a few hours, even for the largest target dataset, against real-world datasets using the BCLO scheme to encrypt a set of first names.
Using this attack they were able to recover almost half the data set. The leakage was even worse for last names, with almost 97% of last names trivially recoverable.
#Composition of the two (BCLO & CLWW) schemes does #decrease attack accuracy but is still far from providing acceptable security.
Exploiting known plaintexts is even easier.
Attacking frequency-hiding schemes - #Kerschbaum recently introduced a scheme that hides frequency information. However, a “#binomial” attack performs reasonably well, recovering on average 30% of first names and 7% of last names. Notably, it recovers majority of high-frequency plaintexts (despite not having frequency information leaked), suggesting these plaintexts are particularly poorly protected by any order-revealing scheme.
In terms of countermeasures, an obvious suggestion is to move towards less leaky schemes, such as those that only reveal order, including Kerschbaum's scheme and the more recent #Boneh et al. scheme based on #multilinear maps. Unfortunately in most settings there exists inherent #challenges to deployment of these schemes. Kerschbaum's scheme is relatively efficient, but requires client-side state which impedes scaling. The Boneh et al. scheme has ciphertexts larger by 10 orders of magnitude than BCLO ciphertexts and requires tens of minutes to compute encryptions.