# What's wrong with this “order-preserving MAC” function?

Please note: this is purely a thought experiment and not intended for any real-world usage!

I came up with a simple function $\mathrm{OPF}$ to map the integers $[0,C)$ (where $C$ is the "ChunkSize") to $512$-bit hashes such that for any $(a, b)$ $$a < b\iff \mathrm{OPF}(a) < \mathrm{OPF}(b)$$ I'm wondering why this is not as secure as existing schemes out there.

The idea is to choose a random point under a certain minimum 512-bit integer $m$ (the MinVal), and map the numbers $[0, C)$ into $[m,M]$, where $M=16^{128}-1$ (the MaxVal) is the largest integer that can fit in 512-bits. For performance reasons, I arbitrarily chose $m = 5 * 10^{150}$. With these values in hand, we calculate the StepSize $s = (M - m) / C$.

The method then relies on 3 procedures, shown below in pseudo-code:

keyGen procedure:
S = <input random secret>
while true
R = random_bytes
hmac = HMAC(S, R)
break if hmac < StartVal
return hmac

encodeNumber procedure:
K = <output from keyGen>
N = <number in 0..4095>
start = K + StepSize * N
while true
R = random_bytes
hmac = HMAC(K, R)
break if hmac > start and (hmac - start) < StepSize
return hmac


(Interestingly, this method can give false positive for equality, but only for adjacent integers and only with 0.5 probability.) This can easily be shown from the code below:

equalTo procedure:
a, b = <encoded numbers>
abs(a - b) / StepSize < 1


Obviously, this scheme is not very "elegant", as it relies on "brute-forcing" our way to the correct results. Nevertheless, it seems easy to understand compared to order-preserving encryption schemes out there (keeping in mind that in this scheme, it is not possible to recover the plaintext.) How does it compare in terms of security?

Intuitively, with a secure order preserving function, we should have that

1. No adversary can predict the image of a point with more than with a pre-determined accuracy
2. No adversary can guess the distance between the points (more than with a pre-determined accuracy).

Let's assume, in this case, that the adversary is only allowed to observe the output of the function. That is, the adversary cannot ask for the encryption of a chosen plaintext.

-
Additionally, assume that the input random secret to the keyGen procedure is kept secret (i.e. the adversary is only allowed to observe the output of the function). – user2398029 Apr 8 '14 at 15:49
@RickyDemer Yes - edited accordingly. To the downvoter, care to explain why this is not a good question? I'm asking specifically why this is NOT secure. – user2398029 Apr 8 '14 at 15:52
"the adversary is only allowed to observe the output of the function" Are you saying he can't make queries to it, just see the output of values you choose to 'encrypt'? Or is he allowed to run any of your 3 procedures? – figlesquidge Apr 8 '14 at 16:01
@figlesquidge Thanks! that makes it much clearer and look more professional. Yes, I am implying that the adversary cannot ask for the "encryption" of a chosen plaintext. – user2398029 Apr 8 '14 at 16:03
Now I see where this scheme fails. Any of you guys care to put up your comment as an answer? – user2398029 Apr 8 '14 at 16:29

From what I see from the pseudocode, it would appear that $OPF(n)/stepsize−n \in \{0,1\}$, that is, an attacker can compute $OPF(n)/stepsize$, and rederive $n$ with a maximum error of 1.