# Secure order preserving hash function

Is there a construction of an order preserving hash function that keeps the preimage property of a crypto hash function? By order preserving hash function (OPHF) i mean for $x<y$ then $OPHF(x) < OPHF(y)$

-
Your requirement trivially allows a binary search to recover the the message in a chosen plaintext scenario. It's also easy to prove that the only way to satisfy the condition is order preserving encryption. So I have no clue what you even mean by an oder preserving hash. –  CodesInChaos Apr 29 '13 at 11:48
Your requirements are simply a contradiction. Order preservation allows binary search which allows trivial and efficient inversion of any unkeyed function. –  CodesInChaos Apr 29 '13 at 12:52
$OPHF(x):x\mapsto x||\operatorname{SHA-256}(x)$ is order-preserving, and second-preimage resistant. It is not first-preimage resistant, though. –  fgrieu Apr 29 '13 at 13:09
@fgrieu: $\:$ SHA is completely irrelevant for your construction. $\;\;\;$ –  Ricky Demer Apr 29 '13 at 17:41
In Boldyreva et al.'s second paper on OPE they describe a scheme that uses as an order-preserving hash function something called a monotone minimal perfect hash. I don't know all the details, but look at the top of page 11 for the description. –  pg1989 Oct 18 '13 at 22:23

The problem with a hash function like you ask for is that, if you hash an $n$-bit string and give the hash to someone else, they can recover the string using $n$ hash calculations with a binary search.

For a simple example, let's say the $n=8$, your string is $01011001$ in binary, and its hash is $Y = H(01011001)$.

1. To recover the string from the hash, I start by calculating $X_1 = H(10000000)$ and comparing it with $Y$. Since $10000000 > 01011001$, and since $H$ is order-preserving, $X_1 > Y$ and I therefore now know that the first bit of your string is $0$.

2. Next, I'll calculate $X_2 = H(01000000)$ and again compare it with $Y$. Since $01000000 < 01011001$, this time $X_2 < Y$, and thus I now know that the first two bits of your string are $01$.

3. Using this knowledge, the next hash I'll calculate will be $X_3 = H(01100000)$. Since $01100000 > 01011001$, now $X_3 > Y$, and thus I know that the first three bits of your string are $010$.

4. The next hash I'll calculate will be $X_4 = H(01010000)$, which I'll compare with $Y$ to find the fourth bit of your string, and so on, until I've recovered every bit of your string.

This flaw is inherent in the idea of order-preserving hashing: if I can obtain the hash of any valid string, then I can always carry out such a search. In fact, even if I can't get the actual hashes, but can only ask you for the result of the comparison between $H(s)$ and $Y$ for some input string $s$, I can still recover your original string without even seeing its hash value!

Basically, if you ever played the "guess what number I'm thinking of?" game as a child, this is exactly the same situation. You have a secret string, and I get to guess a string and see if it's less than or greater than your secret. As in the game, with the right guessing strategy I won't need too many guesses to find the right answer.

-
what if the hash function is not publicly available and it's keyed –  curious Apr 29 '13 at 18:29
@curious: If I can choose a string and ask you for its hash, then the attacks still works. Even if I can only ask whether the hash of my string is less than the hash of your string, that's still enough information for this attack. –  Ilmari Karonen Apr 29 '13 at 18:34
"if the hash function is not publicly available and it's keyed" then you have order-preserving encryption. –  Ricky Demer Apr 29 '13 at 18:49
@curious: Yes. As the paper you linked to notes at the end of section 1, order-preserving encryption is useless if the attacker has access to an encryption oracle. –  Ilmari Karonen Apr 29 '13 at 18:55
I can't do it in a comment, it's 40 pages long - a particularly dense 40 pages at that. One of their main goals is to reduce the necessary leakage of OPE schemes so that OPE can be achieved in the model described by Boldyreva with fewer than 1/2 the bits leaked. They do accomplish this. Their final scheme can leak much fewer than 1/2 the bits of the plaintext. However, they also show the number of bits leaked can never be zero. They do this using min-entropy in an argument I don't fully understand yet. They also define a couple new OPE security notions that their scheme provably meets. –  pg1989 Oct 28 '13 at 19:12